線性相關性

^[1]  線性相關性(linear relatedness)複雜性測度間的一種特殊相關性.它是兩個複雜性測度在線性意義下的等價性.設} , ili'為兩個複雜性測度.t為一元數論函數，令Lin <t)一{c " t }cE叫.若對滿足bxE }(t<x))x)的任何t，都有}Lin (t) ='}'Lin (t ) ,則稱中與少為線性相關的(參見“複雜性類”).絕大多數的空間複雜性都是線性相關的.