Back

ⓘ P≠NP予想 (P≠NPよそう、英: P is not NP )は、計算複雑性理論(計算量理論)におけるクラスPとクラスNPが等しくないという予想である。 P対NP問題 (PたいNPもんだい、英 ..




P≠NP予想
                                     

ⓘ P≠NP予想

P≠NP予想 (P≠NPよそう、英: P is not NP )は、計算複雑性理論(計算量理論)におけるクラスPとクラスNPが等しくないという予想である。 P対NP問題 (PたいNPもんだい、英: P versus NP )と呼ばれることもある。

理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。

                                     

1. 概要

クラスPとは、決定性チューリングマシンにおいて、多項式時間で判定可能な問題のクラスであり、クラスNPは、Yesとなる証拠(Witnessという)が与えられたとき、多項式時間でWitnessの正当性の判定(これを検証という)が可能な問題のクラスである。多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、PがNPの真部分集合であるか否かについては明確ではない。証明はまだないが、多くの研究者はP≠NPだと信じている。そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。

仮にP=NPであると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、未だ効率の悪い指数時間アルゴリズムしかないさまざまな分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。しかし、多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。NP問題は数千種類が知られているが、P=NPが示された途端にそれらが全て多項式時間で解けるとは俄かに信じ難いことである。更に、P≠NPだと仮定して、何らかのNP完全問題の入力nビットについての既知の最良の計算量がOk n ・ poly n)であるようなときに、せめて基底のkを改善しよう(例えばk=2を1.9や1.8等に)という試みでさえ、ある程度進展した後に行き詰ることが経験的に知られている。これらの観察がP≠NP予想の重要な根拠の一つとなっている。

一方、P=NPと予想する研究者も皆無ではない。ドナルド・クヌースはその一人であり、次のような論拠を挙げている。

  • P≠NPを証明する試みはことごとく失敗している(後述の#歴史参照)
  • NP問題をn M ステップで解くアルゴリズムがあるとする。このMは例えば10↑↑↑↑3のような有限ながらも巨大な値を取れる。するとnビットの入力についてn M 個の論理演算や加算演算、シフト演算などを実施する途轍もない種類のアルゴリズムが考えられる訳で、これが全て失敗するとは信じ難い

但し彼は同時に次のようにも述べている。

彼は存在が証明されているが実装は現実的に不可能と考えられているアルゴリズムを例として複数列挙している。

                                     

2.1. 歴史 起源

P≠NP問題が定式化されたのは1971年だが、関連する問題やその難しさ、潜在的な影響などについて先駆的な考察があった。

                                     

2.2. 歴史 ナッシュの手紙(1955年)

ジョン・ナッシュは、1955年に書いたNSA宛の手紙の中で、十分複雑な暗号を破るには鍵長の指数時間を要するだろうと述べた。もしこれを証明できれば(ナッシュは証明不能と考えていたが)、今日でいうP≠NPを意味することになる。何故なら鍵候補の検証自体は多項式時間で終わるからである。

                                     

2.3. 歴史 ゲーデルの手紙(1956年)

1956年、クルト・ゲーデルは癌で入院していたジョン・フォン・ノイマン宛に手紙を書いた。その中で彼は定理の証明(今日ではcoNP完全であると判っている)を2次または線形時間で解けるだろうかと意見を求め、もしそれが可能なら数学の新定理の発見を自動化できるだろうと指摘した。 これに対するノイマンの返事は伝わっておらず、ノイマンは翌1957年に死去した。ハルトマニスは、この手紙がノイマンが健康だった間に出されていれば、この問題は既に解けるか研究史がもっと短縮されていたのではないかと嘆いている。

                                     

2.4. 歴史 証明の試みと難しさ

P≠NP予想の面白さと難しさは、複雑性クラスを分離するために利用・考案されてきた様々な証明手法が、証明手法自体の本質的な限界によりP≠NPを証明できないという、不可能性の証明がこれまで幾度も得られてきた点にある。つまり、時代が進めば進むほど証明の可能性が原理的に狭められてきた。だからと言ってP=NPの方が確からしいと傾いた訳でもなく、新たな証明手法が必要だと考えられてきた点がまた特徴的である。以下にあらましを述べる。本節は主に岡本 2009の解説記事に基づく。

                                     

2.5. 歴史 相対化

複雑性クラスを分離するために最初期から主に1970年代末まで利用された証明手法として、集合論の創始者カントールが1891年に考案した対角線論法がある。これは一方のクラスの万能関数であって他方のクラスに属するものを構成し、その対角線部分に着目することで複雑性クラスを分離するもので、P≠EXPTIMEHartmanis & Stearns 1965)を示す際などに適用された。このような証明手法の特徴として「相対化」と呼ばれる性質の保存がある。複雑性クラス C をオラクル A で相対化するとは、クラスCに属する計算機にオラクル A を付与した新しい複雑性クラス C A を作ることである。ここで、複雑性クラス C,D について対角線論法によって C≠D が示されたとすると、その証明はオラクル A を持つ計算モデルに対しても通用するので、C A ≠D A が同時に成り立つ。同様に、対角線論法によって C=D が示された場合は C A =D A がどのような A についても成り立つ。

ところが、Baker, Gill & Solovay 1975は次のことを示した。

  • P A ≠NP A となるオラクル A と、P B =NP B となるオラクル B が存在する

この結果により、対角線論法のように相対化が可能な証明手法では P≠NP を原理的に証明できないことが判明した。

                                     

2.6. 歴史 自然な証明

1980年代に入り、集合論的手法ではない回路計算量に着目する新しい証明手法が開発された。これは今日「自然な証明」と呼ばれるもので、AC 0 ≠NC 1 (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/poly≠NPを証明できない

「自然な証明」は名前の通り自然な発想に基づく証明戦略であり、それまで得られた複雑性クラスの分離に関する殆ど全ての証明で利用されていた。ところが、そうした証明手法ではP≠NPを原理的に証明できないことが判明したのである。RazborovとRudichはこの成果により2007年のゲーデル賞を受賞した。但し彼らが定義した「自然な証明」には幾つか技術的な条件があることから、この条件を巧妙に回避することで障害を乗り越えようとする研究方向も存在する。

                                     

2.7. 歴史 代数化

集合論的でも自然な証明でもない証明手法として「算術化」と呼ばれるものがある。これは論理式を有限体または有限環上の多項式に置き換えて考察するもので、IP=PSPACE(Lund,Fortnow,Karloff,Nisan,Shamir1989)やMA EXE ⊈ {\displaystyle \not \subseteq } P/polyBuhrman, Fortnow & Thierauf 1998)、PP ⊈ {\displaystyle \not \subseteq } Sizen kVinodchandran 2005)などの成果を挙げた。ここで、複雑性クラスの分離に用いる際は「算術化された対角線論法」を用いることになる。

ところが、こうした証明方法ではP≠NPを証明不可能であることがAaronson & Wigderson 2009により示された。彼らは「代数化」という概念を導入し、算術化された集合論的方法によって得られた従来の結果は全て代数化できることを示した。一方、P=NPとP≠NPは何れも代数化できないことを示した。このため、算術化された集合論的手法による結果は全て代数化できるとすると、この方法ではP=NPとP≠NPは原理的に証明できないことになる。

                                     

2.8. 歴史 その他の方法

以上の経緯から現在では、P≠NPを証明するためには、相対化されず、自然な証明ではなく、代数化できない証明手法が必要だと考えられている。そのような証明手法の候補は幾つかあるが、それらもまた何らかの限界が潜在しているかも知れず、証明手法に関する本質的な理解が今後に求められている。

  • 数学基礎論による方法
  • Mulmuley & Sohoni 2001の代数幾何を利用した方法
  • NEXP ⊈ {\displaystyle \not \subseteq } ACC 0 (Williams 2010)における手法

その他の方向性として、P≠NPがそもそもZFCから独立なのではないかと疑う向きがあるが、こちらについても現状では否定的な結果が得られている。

                                     

3.1. 重要性 他の問題との関係

NP完全 1971年にスティーブン・クックが定式化した概念で、クラスNPに属し、クラスNPに属する他の全問題が多項式時間帰着される問題をNP完全という。充足可能性問題をはじめとして、数千個以上の問題がNP完全であることが示されている。これらのNP完全問題の一つでもクラスPに属することを示せれば、P=NPとなる。 NP完全には含まれない問題 NP-P∪NP完全となる問題のクラスをNPIとする。P≠NPであれば、NPIは空集合ではないことが示されている。そのような問題の候補としてグラフ同型問題がある。 coNP NP問題の補問題からなるクラスをcoNPという。NP≠coNPならば、P≠NPとなることが示されている。
                                     

4. 参考文献

  • Mulmuley, Ketan D.; Sohoni, Milind 2001," Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems”, SIAM J. Compput. 31 2: 496-526, 2017年6月10日 閲覧。
  • Furst, Merrick; Saxe, James B.; Sipser, Michael 1984," Parity, Circuits, and the Polynomial-Time Hierarchy” PDF, Math. Systems Theory 17: 13-27, 2017年6月10日 閲覧。
  • Hartmanis, Juris; Stearns, Richard E. 1965," On the computational complexity of algorithms”, Transactions of the American Mathematical Society 117: 285-306, doi:10.2307/1994208, JSTOR 1994208, MR0170805, 2017年6月10日 閲覧。
  • Williams, Ryan 2010-11-23, Non-Uniform ACC Circuit Lower Bounds, 2017年6月10日 閲覧。
  • Buhrman, Harry; Fortnow, Lance; Thierauf, Thomas 1998, Nonrelativizing Separations, 2017年6月10日 閲覧。
  • Baker, Theodore; Gill, John; Solovay, Robert 1975," Relativizations of the P=?NP question”, SIAM J. Comput. 4 4: 431-442, 2017年6月10日 閲覧。
  • Razborov, Alexander A. 1985," Lower bounds for the monotone complexity of some boolean functions”, Soviet Math. Dokl. 31 2, 2017年6月10日 閲覧。
  • Vinodchandran, N.V. 2005," A Note on the Circuit Complexity of PP”, Theoretical Computer Science 347 1-2: 415-418, 2017年6月10日 閲覧。
  • Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. ISBN 0-534-94728-X. pp.372-377.
  • Razborov, Alexander A.; Rudich, Steven 1997." Natural proofs”. Journal of Computer and System Sciences 55: 24-35. doi:10.1006/jcss.1997.1494. Draft
  • Aaronson, Scott; Wigderson, Avi 2009," Algebrization: A New Barrier in Complexity Theory”, ACM Transactions on Computation TheoryTOCT 1 1, 2017年6月10日 閲覧。
  • 岡本, 龍明 2009-12-01," 相対化,自然な証明,代数化/P≠NP予想の難しさ”, 数学セミナー 日本評論社 48 12: 20-25
  • Stephen Cook, "The P versus NP Problem", 2000. PDF


                                     

5. 関連項目

  • 数学上の未解決問題
  • 計算機科学の未解決問題
  • 懸賞金問題
  • 多項式階層
                                     
  • NP 困難問題を解ける多項式時間の機械が存在すれば それを利用すれば NP に属する任意の問題を多項式時間で解くことができる NP 完全問題とは NP 困難であり かつ NP に属する問題である これとは異なり ある問題が NP 困難であっても NP に属するとは限らない NP は決定問題のクラスなので NP
  • 予想 をつけることがある その 予想 が的中した場合 その仮説は大きな信用を得ることになる 数学においては 予想 conjecture という語は 真であると思われてはいるが いまだに真であるとも偽であるとも証明されていない命題を指す 例としては リーマン 予想 ゴールドバッハの 予想 P NP 予想 がある
  • P とは多項式時間で解答の見つかる問題のクラスを表し これに対し NP は多項式時間で解答が検証できる問題のクラスを表す クラス P の問題は同時にクラス NP であることは証明されている つまり P NP ここで P NP 問題とは NP が P に含まれるのかどうか P NP かどうか すなわち P と NP
  • 現在の計算複雑性理論の最も重要な課題は P NP 予想 の証明である この 予想 は提起された当初それほど重要とは見なされなかったが 産業において重要なオペレーションズリサーチの問題の多くが NP の部分クラスに属する NP 完全問題であることが明らかになるにつれて重要性を増してきた NP
  • は P を包含し NP に包含される その際 P UP または UP NP あるいは両方 と考えられている P NP 予想 多くの学者は P とも NP とも等しくないと 予想 している 別の定式化として 解の検証が決定性チューリング機械で多項式時間で行える場合にのみ ある言語が NP に含まれると言える 同様に ある言語が
  • 率的アルゴリズムで解けないものがある すなわち P と NP は等しくないと 予想 した この 予想 は計算複雑性理論の研究を活発化させ それによって計算問題の本質的複雑性への理解が深まり 効率的に計算できる問題についても理解が深まった クックの P NP 予想 は今も証明されておらず 有名な7つのミレニアム懸賞問題の1つとされている
  • を持つことを証明せよ リーマン 予想 Riemann Hypothesis リーマンゼータ関数 ζ s の非自明な零点 s は全て 実部が 1 2 の直線上に存在する P NP 予想 P vs NP Problem 計算複雑性理論 計算量理論 におけるクラス P とクラス NP が等しくない ナビエ ストークス方程式の解の存在と滑らかさ
  • NP - 非決定性チューリングマシンで多項式時間で解ける問題のクラス P NP 予想 も参照 これはまた解に対して多項式長の witness が存在し 解の候補と witness が与えられたとき検証が決定性チューリングマシンで多項式時間で解ける問題のクラスに一致する NP 完全 - NP の中で最も難しい問題のクラス
  • れに則る証明はある意味で 自然 だが 擬似乱数生成器の存在を仮定すると そのような方法では P NP 予想 を解決不可能であることが言える なお 擬似乱数生成器が存在する という主張は広く正しいと信じられている 予想 である 自然な証明の概念はアレクサンダー ラズボロフ 英語版 とステーブン ルディッチ