ある NP 完全問題に対して、多項式時間のアルゴリズムが見つかったとすると、どのような結論が得られるか。

解説

正解は「P = NP が成り立つ」です。NP 完全問題には NP のすべての問題が多項式時間で帰着できるので、その問題が多項式時間で解ければ、帰着と組み合わせて NP のすべての問題が多項式時間で解けます。P ⊆ NP はもともと成り立つので、P = NP となります。この P 対 NP 問題は計算機科学の最大の未解決問題の一つで、多くの研究者は P ≠ NP と予想しています。「P ≠ NP が成り立つ」は逆の結論です。「停止性問題が決定可能になる」は誤りで、停止性問題は NP の外にあり、P = NP でも決定不能のままです。「NP 完全問題の数が1つ減る」も誤りで、その問題は P に属することになりますが、NP 完全であることは変わりません。