多項式時lei多一可化歸(polynomial time manyone reducible)簡稱P-m可化歸或卡普可化歸.遞歸論的基本概念之一它是由卡普(Karp , R. M.)於1972年明確定義的一個概念.是用以比較兩個問題之間的難度的.設A1,A:為兩個集合，若存在一個多項式時間可計算函式f，使得
Vx(xEA，一.fCx)EAz)，則稱A，是P-m可化歸到A:的.並記為A1鎮mA: .z當A,鎮rA:時，A:比A,更“難”一些.若
A,蕊rmAz乙Az鎮rA,，則稱A，和A:為P-m等價的，並記為Al三mAi= Az.此時，A,和A:的“難度”相當.P-m等價的兩個集合也常稱為多項式等價或簡稱屍等價.值得指出的是，任何NP完全集都是P等價的.但目前尚不知它們是否都是屍同構的(參見“伯爾曼一哈特曼尼斯猜棋’，).
Vx(xEA，一.fCx)EAz)，則稱A，是P-m可化歸到A:的.並記為A1鎮mA: .z當A,鎮rA:時，A:比A,更“難”一些.若
A,蕊rmAz乙Az鎮rA,，則稱A，和A:為P-m等價的，並記為Al三mAi= Az.此時，A,和A:的“難度”相當.P-m等價的兩個集合也常稱為多項式等價或簡稱屍等價.值得指出的是，任何NP完全集都是P等價的.但目前尚不知它們是否都是屍同構的(參見“伯爾曼一哈特曼尼斯猜棋’，).
