多項式純正函式

多項式純正函式(polynomial honest func -tion)一種特殊的遞歸函式.設f為遞歸函式,若存在多項式p,使對任何yErang (f),存在xEdom <f),使得f<x)=y,並且}川}p<Ix}>,則稱f為多項式純正的.等價地,遞歸函式f稱多項式純正的,若且唯若存在多項式p,使對任何x,f(x)都可在pO f(x>)步內計算出來.換言之,f是關於時間複雜性測度的p純正函式(參見“純正函式”).

相關詞條

熱門詞條

聯絡我們