多項式時間変換
ある問題がNP完全問題であるかは次のようにして証明されてきた。まず、スティーブン・クックによって充足可能性問題 がNP完全であることが証明された。それ以外の NP完全問題は
NP完全問題に属する問題 A は別の NPに属する問題 B に対して多項式時間変換可能であると分かった。
つまり B は A と同等かそれより難しい。
ところが NP完全問題とは NP に属する問題の中で一番難しい問題である。
つまり A より難しい NPに属する問題は存在しない。
よって B は A と同等すなわち B も NP完全問題である。
という論法で証明されている。