P=NPとは? P≠NPとは?
前回紹介した二つの集合PとNPですが，属する要素が全く同じなら，P=NPです．
「P⊂NP」(任意の問題pに対して，p∈Pならばp∈NP)と「NP⊂P」(任意の問題pに対して，p∈NPならばp∈P)の両方が成り立つことと等価です．
ただし，前者の包含関係は，決定性テューリング機械は非決定性テューリング機械でもあることからただちに成り立ちます．本当に証明しないといけないのは，後者です．
後者が成り立たないとき，すなわち，「ある問題pに対して，p∈NPだけど，p∈Pでない」ことが言えれば，P≠NPです．この不等式は，「PとNPに属する要素が全く異なる」という意味ではない点に注意してください．
何を証明すればいいの?
P=NPを示すには，あるNP完全問題を選び，それがPに属すること，すなわち決定性テューリング機械で多項式時間で解けることを証明すれば，おしまいです．
N≠NPを示すには，ある問題を選び，それがNPに属すること，そして決定性テューリング機械での時間計算量の下限が多項式で表現できない(多項式よりも大きい)ことを証明すれば，おしまいです．
どちらも「おしまい」と簡単に書きましたが，証明はまだ見つかっていません．
もちろん他の，画期的な証明方法が潜んでいるかもしれません．
将来，証明されるの?
30年以上にわたって研究され，肯定・否定の証明が得られていないので，何とも言いがたいですね…．
ただし，研究者らの直感としては，P≠NPが正しいであろうとなっています．本によっては「P≠NPと信じられている」と表現されていることもあります．
この予想を積極的に使って，暗号アルゴリズムが考案されています．例えばRSAについては，素因数分解問題がNPに属し*1，Pに属さないと期待されていることを，安全である(公開鍵からプライベート鍵を見つけるのが，鍵長の指数時間かかる)ことの根拠としています．
NPに属さない，「解ける問題」ってあるの?
非決定性テューリング機械を使っても，書き込む回数の下限が，入力サイズnの指数関数になってしまうなら，NPに属しません．
実は大学3年のとき，ゼミで先生に尋ねたことがありました．先生は，つい最近そのような時間計算量になってしまう問題があったのだよと教えてくださいまして，学会発表の別刷りをいただきました．内容はまったく理解できませんでしたが，時間計算量が，2の(2の(2のn乗)乗)乗のオーダだったのを，おぼろげながら記憶しています．
P=NP問題の「問題」って，おかしくない?
計算理論の「問題(個別問題の集合)」と異なる，という意味ですね．
確かに，この表現は不用意でした．P=NP問題の「問題」というのは，未解決な問題an open problemの意味合いです．
Wikipediaでは，「P≠NP予想」と呼ばれていますね．来年度以降の授業でも，この表記を使うことにします．
P=NP問題は，今も研究されていますか?
ホットな話題，ではないと思います．
ただ，工学上意味のある問題がNP完全であることを示すという形の発表は，ときどき見かけます．その問題については，(決定性で)多項式時間アルゴリズムが存在しそうにないことを示唆しています．
「経験則」が気になったのですが…．
これですね．最近読んだものを，引用します．
論理設計についてまだ効率のよいアルゴリズムが知られていない問題をいくつか検討したところ，いずれも効率のよいアルゴリズムが簡単に考案できそうになく，共通の性質として次の集合被覆問題: 「有限集合S，その部分集合の族(集合の集合) FとFに属する各集合のコストが与えられたとき，Fの中から集合をうまく選んで，Sのどの元も選ばれた集合のどれかに含まれ，かつ選ばれた集合のコストの総和を最小にせよ．」と等価(一方に効率のよいアルゴリズムが存在すれば，他方にも存在することが示せる)であることが分かった．腹立ちまぎれに経験則「集合被覆問題と等価と分かれば，その問題からただちに手を引け」を作り，後輩にもすすめた．ここで，アルゴリズムの効率の議論から，問題の難易性への議論へ飛躍していることに注意されたい．実は後にCook (1971, [18])による深い見事な理論によって裏づけられた[19]．
(嵩忠雄*2: 「私の研究遍歴(その2)」，Journal of Signal Processing「信号処理」, Vol.7, No.3, pp.202-203, 2003.)
読む際の注意ですが，「Cook (1971, [18])」というのは，Cook氏の論文で，1971年に出版され，上記引用の参考文献(省略していますが)で18番目に書誌情報が記載されています．「実は後に」に注意すると，『経験則「集合被覆問題と等価と分かれば，その問題からただちに手を引け」』は，それよりも前に作られていたことがうかがえます．
