多項式界可計算性

多項式界可計算性(polynomially boundedcomputability)計算複雜性的一種量度.設M為任何一個(確定或非確定型的)算法.}M為M的一個複雜性函式，若存在一個多項式p，使對任何n都有}MCn)鎮p(n)，則稱M為關於中的多項式界算法.若一函式f可由某個(關於中的)多項式界算法計算，則稱f為(關於中的)多項式界可計算函式，也稱為多項式巾界的可計算函式.特別地，當中分別為時間和空間複雜性函式時，多項式中界算法(可計算函式)特稱為多項式時間和多項空間算法(可計算函式)(參見“庫克一卡普論題P類和NP類”).