线性相关性

线性相关性(linear relatedness)复杂性测度间的一种特殊相关性.它是两个复杂性测度在线性意义下的等价性.设} , ili'为两个复杂性测度.t为一元数论函数，令Lin <t)一{c " t }cE叫.若对满足bxE }(t<x))x)的任何t，都有}Lin (t) ='}'Lin (t ) ,则称中与少为线性相关的(参见“复杂性类”).绝大多数的空间复杂性都是线性相关的.