そろそろ「P=NP問題」の核心へ参りましょう…．
NP = non polynomialではないの?
違います．nondeterministic polynomialと理解してください．
「非決定性」テューリング機械により「多項式時間」で解ける問題のクラスです．
なぜ多項式時間=効率よく解けるなの?
決定性のアルゴリズム(または決定性のテューリング機械)を考えます．
1960年代までに，「指数時間かかるアルゴリズムは容易に示せるが，それを多項式時間に改善するのは難しそうな」問題が出てきました．それは一つの問題ではなく，いくつもあり，なんとなく関連がありそうだが，どのように手をつければいいか分からない状態だったと想像します．その種の問題に出てきたら(改善が見込めないので)手を引け，という経験則*1も作られたりしました．
時間計算量がいったん多項式で表されると，アルゴリズムやデータ構造の改善によって，例えば だったのが
に減らしやすいものでした．指数時間についても同様で，
が
(ただし
)に減らせたりできたわけです．
しかしもともと指数時間のアルゴリズムを，多項式時間に変えるのは容易でなく，どうも研究者の努力で改善できるものではなさそうという見解が固まっていったようです．
「2のn乗」と「2のn乗」って，そんなに違うものなの?
グラフを書いても，違いは分かりません．
という関数を考えます．cは正の定数です．10000でもかまいません．xに依存しない定数であれば，いくら大きくしてもかまいません．
分母が多項式関数，分子が指数関数である点に注意してください．
そしてこの関数f(x)は，x→∞のとき，∞に発散します．cをどんな値にしてもです．
もっと検討することで，やや大雑把な表現ですが，「どんな多項式関数よりも，2のx乗のほうが大きい」と言えます．
PとNPをつなぐものは?
「NP完全」でしょう．
1971年のクックの論文により，NP完全という概念が導入されるとともに，実際に，NP完全に属する問題というのも発見され，証明されています．
その後，NP完全に属する，工学上重要な問題が無数に発見されました*2．
ここで，「P」と「NP」と「NP完全の問題のクラス」という3つの集合を考えることができます．そして，「NP完全の問題のクラスに属する要素」…NP完全問題ですね…が(決定性)多項式時間で解ければ，NPに属するすべての問題も(決定性)多項式時間で解けることになります*3．これは「P=NP」が肯定的に解決された，ということになります．
もちろん現実には，NP完全問題に対する(決定性)多項式時間アルゴリズムは見つかっていません．多くの研究者により数十年間検討されていても，発見されていないことが，P≠NPであると信じられている根拠になっています．
NP完全って何ですか?
次回にご期待ください．
