多項式時間圖靈可化歸

多項式時間圖靈可化歸(polynomial time Tur-ing reducible)簡稱P-t可化歸或庫克化歸.遞歸論的基本概念之一,它最初是由庫克(Cook , S. A. >於1971年加以研究的一種化歸.設A,B為兩個集合.若存在一個以B為外部信息源的確定型多項式時間界圖靈機M}接受A(即AEPa>,則稱A是P-t可化歸到B的,記為A鎮廠B.當A鎮獷B乙B鎮時,稱A,B為P-t等價的,並記為A三廠B. P-t化歸既是通常的圖靈化歸性的一種限制,又是P-m化歸的一種推廣.

相關詞條

熱門詞條

聯絡我們