計算理論についての質問です

質問

NP完全の問題に関して指数時間アルゴリズムがあるからといってP≠NPとはいえないのはなぜでしょうか？

回答No.2

stomachman · ベストアンサー

No.1は完璧回答ですけど…

P問題: 多項式時間アルゴリズムが存在する問題
NP問題: 非決定的多項式時間アルゴリズムが存在する問題
Pとは「P問題の集合」、NPとは「NP問題の集合」です。
さて、ある問題がP問題であれば、それはNP問題でもある（そのP問題を解く多項式時間のアルゴリズムの前に、それとは関係のないNP問題を解くアルゴリズムを付け加えれば良いだけです）。だから、P⊂NP。

一方、指数時間アルゴリズムが存在する問題の集合をXとしましょう。もちろん
P⊂NP⊂X
です。どんなNP問題についても、またどんなP問題についても、それを解く指数時間アルゴリズムが構成できるのは自明ですからね。

さて、P≠NPを言うためには、「少なくとも一つのNP問題について、それがP問題ではない」を証明する必要がある。言い換えれば「非決定的多項式時間アルゴリズムが存在する少なくとも一つの問題について、多項式時間アルゴリズムが存在しない」を証明するんです。
その問題に指数時間アルゴリズムが存在するのは当たり前で、そんなこと言ってみても、「それがP問題ではない」という話には繋がらない。

回答No.1

ranx

多項式時間アルゴリズムが無いかどうか分からないからでは？

補足

図々しい話ですが
もっと詳しく教えていただけると
さらにありがたいんですが・・