NPとDecision Proとの接続

Question

状態T/F。 誰かがP = NPを証明するならば、それはすべての決定問題が多項式時間で解けることを意味するでしょう。 私はそれが間違っていると思います。私は正しい？

Answer 1

P = NP場合は、NPのいずれかの決定問題は多項式時間で解くことができることを意味しています。つまり、「はい」の回答を効率的に検証できる決定問題は、多項式時間で解くことができます。

これは、すべての決定問題が多項式時間で解けるということと同じではありません。たとえば、停止問題などの決定上の問題は決定できないため、決定できません。証明するP = NPは変更されません。