多項式時間変換
多項式時間チューリング還元(Cook 還元)と 多項式時間多対一還元(Karp 還元)では、前者の方が道具としては「強い」。したがって、ある問題がある問題に「還元可能である」という主張は、後者の還元の意味で言ったときの方が強い。
例えば、co-NPに属する任意の問題は、任意のNP完全問題に Cook 還元できるのに対し、co-NP かつ NP である問題(があると仮定して)を NP に Karp 還元することは出来ない。Cook 還元のこの力は還元を設計する上では有用だが、短所として、NP などある種のクラスは Cook 還元の下で閉じているかどうかが判っていない(多分閉じていないだろうと考えられている)。従って、Cook 還元は、ある問題が NP に属すかどうかを証明する上では役に立たない(ただ、与えられた問題が Cook 還元の下で閉じていることが判っているクラス(例えば P など)に属するかどうかを示す上では役に立つ)。これに対し、ある問題を NP に属する問題に Karp 還元できる場合、元の問題は NP に属すると言える。従って Karp 還元によって得られる同値類の方が精度が高いので、Karp 還元の方が強い。