|
P≠NP予想
P≠NP予想（ピーエヌピー予想、英語: P is not NP）は、計算複雑性理論（計算量理論）における予想 (未解決問題) の1つであり、「クラスPとクラスNPが等しくない」すなわち「クラスNPの元だがクラスPの元でないような決定問題（判定問題）が存在する」というものである。P対NP問題（PたいNPもんだい、英: P versus NP）と呼ばれることもある。 理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。 概要クラスPとは、決定性チューリングマシンにおいて、多項式時間で判定可能な問題のクラスであり、クラスNPは、Yesとなる証拠（Witnessという）が与えられたとき、多項式時間でWitnessの正当性の判定（これを検証という）が可能な問題のクラスである。多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、PがNPの真部分集合であるか否かについては明確ではない。証明はまだないが、多くの研究者はP≠NPだと信じている。そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。 仮にP＝NPであると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、未だ効率の悪い指数時間アルゴリズムしかないさまざまな分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。しかし、多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。NP問題は数千種類が知られているが、P＝NPが示された途端にそれらが全て多項式時間で解けるとは俄かに信じ難いことである。更に、P≠NPだと仮定して、何らかのNP完全問題の入力nビットについての既知の最良の計算量がO(kn・poly(n,))であるようなときに、せめて基底のkを改善しよう（例えばk=2を1.9や1.8等に）という試みでさえ、ある程度進展した後に行き詰ることが経験的に知られている。これらの観察がP≠NP予想の重要な根拠の一つとなっている。 一方、P＝NPと予想する研究者も皆無ではない。ドナルド・クヌースはその一人であり、次のような論拠を挙げている[1]。
但し彼は同時に次のようにも述べている。
彼は存在が証明されているが実装は現実的に不可能と考えられているアルゴリズムを例として複数列挙している。 歴史起源P≠NP問題が定式化されたのは1971年だが、関連する問題やその難しさ、潜在的な影響などについて先駆的な考察があった。 ナッシュの手紙（1955年）ジョン・ナッシュは、1955年に書いたNSA宛の手紙の中で、十分複雑な暗号を破るには鍵長の指数時間を要するだろうと述べた[2]。もしこれを証明できれば（ナッシュは証明不能と考えていたが）、今日でいうP≠NPを意味することになる。何故なら鍵候補の検証自体は多項式時間で終わるからである。 ゲーデルの手紙（1956年）1956年、クルト・ゲーデルは癌で入院していたジョン・フォン・ノイマン宛に手紙を書いた。その中で彼は定理の証明（今日ではcoNP完全であると判っている）を2次または線形時間で解けるだろうかと意見を求め[3]、もしそれが可能なら数学の新定理の発見を自動化できるだろうと指摘した。 これに対するノイマンの返事は伝わっておらず、ノイマンは翌1957年に死去した。ハルトマニスは、この手紙がノイマンが健康だった間に出されていれば、この問題は既に解けるか研究史がもっと短縮されていたのではないかと嘆いている[3]。 証明の試みと難しさP≠NP予想の面白さと難しさは、複雑性クラスを分離するために利用・考案されてきた様々な証明手法が、証明手法自体の本質的な限界によりP≠NPを証明できないという、不可能性の証明がこれまで幾度も得られてきた点にある。つまり、時代が進めば進むほど証明の可能性が原理的に狭められてきた。だからと言ってP＝NPの方が確からしいと傾いた訳でもなく、新たな証明手法が必要だと考えられてきた点がまた特徴的である。以下、試みられた証明手法と、その手法では証明できない理由。 相対化複雑性クラスを分離するために最初期から主に1970年代末まで利用された証明手法として、集合論の創始者カントールが1891年に考案した対角線論法がある。これは一方のクラスの万能関数であって他方のクラスに属するものを構成し、その対角線部分に着目することで複雑性クラスを分離するもので、P≠EXPTIME(Hartmanis & Stearns (1965))を示す際などに適用された。このような証明手法の特徴として「相対化」と呼ばれる性質の保存がある。複雑性クラス C をオラクル A で相対化するとは、クラスCに属する計算機にオラクル A を付与した新しい複雑性クラス CA を作ることである。ここで、複雑性クラス C,D について対角線論法によって C≠D が示されたとすると、その証明はオラクル A を持つ計算モデルに対しても通用するので、CA≠DA が同時に成り立つ。同様に、対角線論法によって C＝D が示された場合は CA＝DA がどのような A についても成り立つ。 ところが、Baker, Gill & Solovay (1975)は次のことを示した。
この結果により、対角線論法のように相対化が可能な証明手法では P≠NP を原理的に証明できないことが判明した。 自然な証明→詳細は「自然な証明」を参照
1980年代に入り、集合論的手法ではない回路計算量に着目する新しい証明手法が開発された。これは今日「自然な証明」と呼ばれるもので、AC0≠NC1（Furst, Saxe & Sipser (1984)）やmP/poly≠NP（Razborov (1985))などの成果を挙げた。この手法からP≠NPを見る場合は、Pを包含するクラスP/polyに着目してP/poly≠NPを証明することが問題となる（そこから直ちにP≠NPが従う）。 ところが、当初の期待にもかかわらず、P/poly≠NPに向けた進展はぱったり止まってしまい、やがて研究者の間で何か原因があるのではないかと議論されるようになった。そんな中、Razborov & Rudich (1997)はその原因を突き止め、次のことを示した。
「自然な証明」は名前の通り自然な発想に基づく証明戦略であり、それまで得られた複雑性クラスの分離に関する殆ど全ての証明で利用されていた。ところが、そうした証明手法ではP≠NPを原理的に証明できないことが判明したのである。RazborovとRudichはこの成果により2007年のゲーデル賞を受賞した。但し彼らが定義した「自然な証明」には幾つか技術的な条件があることから、この条件を巧妙に回避することで障害を乗り越えようとする研究方向も存在する。 代数化集合論的でも自然な証明でもない証明手法として「算術化」と呼ばれるものがある。これは論理式を有限体または有限環上の多項式に置き換えて考察するもので、IP＝PSPACE（Lund,Fortnow,Karloff,Nisan,Shamir(1989)）やMAEXP P/poly(Buhrman, Fortnow & Thierauf (1998))、PP Size(nk)(Vinodchandran (2005))などの成果を挙げた。ここで、複雑性クラスの分離に用いる際は「算術化された対角線論法」を用いることになる。 ところが、こうした証明方法ではP≠NPを証明不可能であることがAaronson & Wigderson (2009)により示された。彼らは「代数化」という概念を導入し、算術化された集合論的方法によって得られた従来の結果は全て代数化できることを示した。一方、P＝NPとP≠NPは何れも代数化できないことを示した。このため、算術化された集合論的手法による結果は全て代数化できるとすると、この方法ではP＝NPとP≠NPは原理的に証明できないことになる。 その他の方法以上の経緯から現在では、P≠NPを証明するためには、相対化されず、自然な証明ではなく、代数化できない証明手法が必要だと考えられている。そのような証明手法の候補は幾つかあるが、それらもまた何らかの限界が潜在しているかも知れず、証明手法に関する本質的な理解が今後に求められている。
その他の方向性として、P≠NPがそもそもZFCから独立なのではないかと疑う向きがあるが、こちらについても現状では否定的な結果が得られている。 重要性他の問題との関係
脚注
参考文献
関連項目
|
