多項式時間可計算集是一種可計算的集合，指由多項式時間界確定型圖靈機所接受的集。
多項式時間可計算集(polynomial time com-putable set)一種可計算的集合.指由多項式時間界確定型圖靈機所接受的集.也即屍類中的集合(參見“屍類”).
NP類(NP class)一種特殊的類.是由不確定型圖靈機在多項式時間內接受的語言類.設NM為一個不確定型圖靈機，p為一個多項式，如果對任何字W輸人到NM後，需要NM接受W，那么總有一種接受的計算路徑，其長度不超過WIWI)步.換言之，NM的(非確定型)時間複雜性函式
}NmCn)GpCn)(對任何nEw).則稱NM為具多項式時間界(p)的非確定型圖靈機，p稱為其界函式.所有由具有多項式時間界的非確定型圖靈機所接受的語言組成之類記為NP，即NP= }L I存在非確定型圖靈機NM接受L & NM為具多項式時間界的}，稱之為NP類.NP類反映了多項式時間可驗證性”這一概念.例如，對LENP,若WEL，則總可在多項式時間內加以驗證，但是尚不知道這種“多項式時間可驗證性”與“多項式時間可計算性”是否一致，這就是著名的P=? NP問題.此外，NP類也是不依賴於任何具體地計算模型的一個語言類.
NP類(NP class)一種特殊的類.是由不確定型圖靈機在多項式時間內接受的語言類.設NM為一個不確定型圖靈機，p為一個多項式，如果對任何字W輸人到NM後，需要NM接受W，那么總有一種接受的計算路徑，其長度不超過WIWI)步.換言之，NM的(非確定型)時間複雜性函式
}NmCn)GpCn)(對任何nEw).則稱NM為具多項式時間界(p)的非確定型圖靈機，p稱為其界函式.所有由具有多項式時間界的非確定型圖靈機所接受的語言組成之類記為NP，即NP= }L I存在非確定型圖靈機NM接受L & NM為具多項式時間界的}，稱之為NP類.NP類反映了多項式時間可驗證性”這一概念.例如，對LENP,若WEL，則總可在多項式時間內加以驗證，但是尚不知道這種“多項式時間可驗證性”與“多項式時間可計算性”是否一致，這就是著名的P=? NP問題.此外，NP類也是不依賴於任何具體地計算模型的一個語言類.
