NP與Decision Pro之間的聯繫

Question

州T/F。 如果有人證明P = NP，那麼它就意味着每個決策問題都可以用多項式時間來解決。 我認爲這是錯誤的。我對嗎？

Answer 1

如果P = NP，則意味着在NP任何決策問題可在多項式時間內解決。也就是說，任何可以有效驗證「是」答案的決策問題都可以在多項式時間內解決。

這不是說所有的決策問題都可以用多項式時間來解決。例如，某些決策問題（如暫停問題）是不可判定的，這意味着它們根本無法決定。證明P = NP不會改變這一點。