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則提供了一種對易解性的自然刻畫.

相關詞條

相關搜尋

熱門詞條

聯絡我們