多項式相關性

多項式相關性(polynomial relatedness)複雜性測度間的一種特殊相關性.它是兩種複雜測度在多項式意義下的等價性.設}_ {}; };E},,'1}'= {tl}'; };E},為兩個複雜性測度.對任何一元函式t，令Pol<t)=儼IkE}}.若對任何滿足bx E } <x毛t<x;的函式t，都有}<Pol<t))=tl}'<Pol<t)，則稱中和少是多項式相關的.若存在多項式p，使中與少是p相關的(見“相關性”)，則中與少為多項式相關的.絕大多數的時間複雜性測度都是多項式相關的.