P類(P-class)

 P類(P-class)一種特殊的類.指確定型圖靈機多項式時間可計算語言類.是由卡普(Karp , R.M.)於1972年首先引進的一個概念.設M為一個確定型圖靈機，若存在一個多項式p，使對任何字W，當W輸入M後，必定會pOW)步內停機，即M的計步函式f滿足
bnCf (n>GpCn))，
則稱M為多項式界的圖靈機.而P指全體多項式界的確定型圖靈機所接受的語言組成的類.即屍一{L!存在多項式界確定型圖靈機M使M接受L}.
由於一個語言可以同一個判定問題自然地對應起來，因此，P也可看成全體具有多項式時間算法可解的問題組成之類.從數學的觀點看，屍也是一個十分自然的語言類，它不依賴於具體的計算模型，例如，若M，為具有多帶多讀頭的圖靈機，則它的計算速度一般地要比單帶單讀頭的圖靈機快.但是，只要M，有一個多項式時間界P,，總可以(能行地)構作一個單帶單讀頭的圖靈機M，以及多項式p，使M以p為時間界函式，並且M和M，接受的語言同.從而，以多帶多讀頭圖靈機為計算模型而定義的類屍，與前面的屍是一樣的.不僅如此，對任何其他合理的計算模型情形也一樣.此外，P類還給出了語言類易解性和難解性的一種自然分界.即可以把屍類看成易解的語言類，而把屍之外的語言看成難解的(參見“庫克一卡普論題”).當然，若某個語言的計算模型以一個極大的多項式為界，看起來它也是很難解的.但是，若要在屍中給出易解與難解之區分界限，往往是不自然的，而且會隨著計算機技術的發展有所改變，而P則提供了一種對易解性的自然刻畫.