P≠NP予想のソースを表示

{{参照方法|date=2013年2月}}
{{unsolved|計算機科学|[[多項式時間]]で検証可能な問題は多項式時間で[[決定問題|決定可能]]か？}}'''P≠NP予想'''（ピーエヌピー予想、{{Lang-en|P is not NP}}）は、[[計算複雑性理論]]（計算量理論）における[[予想 (数学)|予想]] ([[数学上の未解決問題|未解決問題]]) の1つであり、「[[P (計算複雑性理論)|クラスP]]と[[NP|クラスNP]]が等しくない」すなわち「クラスNPの[[元 (数学)|元]]だがクラスPの元でないような[[決定問題]]（判定問題）が存在する」というものである。'''P対NP問題'''（PたいNPもんだい、{{Lang-en-short|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(k<sup>n</sup>・''poly''(n,))であるようなときに、せめて基底のkを改善しよう（例えばk=2を1.9や1.8等に）という試みでさえ、ある程度進展した後に行き詰ることが経験的に知られている。これらの観察がP≠NP予想の重要な根拠の一つとなっている。

一方、P＝NPと予想する研究者も皆無ではない。[[ドナルド・クヌース]]はその一人であり、次のような論拠を挙げている<ref name=Knuth2014>{{Cite web | url=http://www.informit.com/articles/article.aspx?p=2213858&WT.rss_f=Article&WT.rss_a=Twenty%20Questions%20for%20Donald%20Knuth&WT.rss_ev=a | title=Twenty Questions for Donald Knuth|date=2014-05-20 | work=informit.com | publisher=InformIT | last=Knuth | first=Donald E. | authorlink=ドナルド・クヌース |accessdate=2017-06-10}}</ref>。
*P≠NPを証明する試みはことごとく失敗している（後述の[[#歴史]]参照）
*NP問題をn<sup>M</sup>ステップで解くアルゴリズムがあるとする。このMは例えば[[クヌースの矢印表記|10↑↑↑↑3]]のような有限ながらも巨大な値を取れる。するとnビットの入力についてn<sup>M</sup>個の論理演算や加算演算、シフト演算などを実施する途轍もない種類のアルゴリズムが考えられる訳で、これが全て失敗するとは信じ難い
但し彼は同時に次のようにも述べている。
{{blockquote|「だが私が最も言いたいのは、たとえP＝NPが証明できたとしても、それが実用上役に立つとは思えないということだ。何故ならそうした証明はまず間違いなく非構成的だろうからだ。Mは存在すると思うが、人類がその値を知ることは決してないだろうとも思う。それどころかMの上界を求めることすら出来ないのではないか」<ref name=Knuth2014/>}}

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

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

====ナッシュの手紙（1955年）====
[[ジョン・ナッシュ]]は、1955年に書いたNSA宛の手紙の中で、十分複雑な暗号を破るには鍵長の指数時間を要するだろうと述べた<ref>{{Cite web |title=Letters from John Nash |url=https://www.nsa.gov/news-features/press-room/press-releases/2012/assets/files/nash-exhibit/nash_letters1.pdf | author=NSA  |year=2012 | format=PDF | accessdate=2017-06-10}}</ref>。もしこれを証明できれば（ナッシュは証明不能と考えていたが）、今日でいうP≠NPを意味することになる。何故なら鍵候補の検証自体は多項式時間で終わるからである。

====ゲーデルの手紙（1956年）====
1956年、[[クルト・ゲーデル]]は癌で入院していた[[ジョン・フォン・ノイマン]]宛に手紙を書いた。その中で彼は定理の証明（今日ではcoNP完全であると判っている）を2次または線形時間で解けるだろうかと意見を求め<ref name=Hartmanis-Godel>{{Cite journal | last1 = Hartmanis | first1 = Juris | year = | title = Godel, von Neumann, and the P = NP problem | url = https://doi.org/10.1142/9789812794499_0033 | journal = Bulletin of the European Association for Theoretical Computer Science | volume = 38 | issue = | pages = 101-107 | doi = 10.1142/9789812794499_0033}} この論文にはゲーデルの手紙の英訳（抄）も記載されている</ref>、もしそれが可能なら数学の新定理の発見を自動化できるだろうと指摘した。

これに対するノイマンの返事は伝わっておらず、ノイマンは翌1957年に死去した。[[ユリス・ハルトマニス|ハルトマニス]]は、この手紙がノイマンが健康だった間に出されていれば、この問題は既に解けるか研究史がもっと短縮されていたのではないかと嘆いている<ref name=Hartmanis-Godel/>。

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

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

ところが、{{harvtxt|Baker|Gill|Solovay|1975}}は次のことを示した。
*P<sup>A</sup>≠NP<sup>A</sup> となるオラクル A と、P<sup>B</sup>＝NP<sup>B</sup> となるオラクル B が存在する

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

====自然な証明====
{{Main|自然な証明}}
1980年代に入り、集合論的手法ではない[[回路計算量]]に着目する新しい証明手法が開発された。これは今日「[[自然な証明]]」と呼ばれるもので、AC<sup>0</sup>≠NC<sup>1</sup>（{{harvtxt|Furst|Saxe|Sipser|1984}}）やmP/poly≠NP（{{harvtxt|Razborov|1985}})などの成果を挙げた。この手法からP≠NPを見る場合は、Pを包含するクラス{{仮リンク|P/poly|en|P/poly}}に着目してP/poly≠NPを証明することが問題となる（そこから直ちにP≠NPが従う）。

ところが、当初の期待にもかかわらず、P/poly≠NPに向けた進展はぱったり止まってしまい、やがて研究者の間で何か原因があるのではないかと議論されるようになった。そんな中、{{harvtxt|Razborov|Rudich|1997}}はその原因を突き止め、次のことを示した。
*[[素因数分解]]の困難性を仮定すると、自然な証明ではP/poly≠NPを証明できない

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

====代数化====
集合論的でも自然な証明でもない証明手法として「算術化」と呼ばれるものがある。これは論理式を有限体または有限環上の多項式に置き換えて考察するもので、IP＝PSPACE（Lund,Fortnow,Karloff,Nisan,Shamir(1989)）やMA<sub>EXP</sub> <math>\not\subseteq</math> P/poly({{harvtxt|Buhrman|Fortnow|Thierauf|1998}})、PP <math>\not\subseteq</math> Size(n<sup>k</sup>)({{harvtxt|Vinodchandran|2005}})などの成果を挙げた。ここで、複雑性クラスの分離に用いる際は「算術化された対角線論法」を用いることになる。

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

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

*NEXP <math>\not\subseteq</math> ACC<sup>0</sup>（{{harvtxt|Williams|2010}}）における手法
*{{harvtxt|Mulmuley|Sohoni|2001}}の代数幾何を利用した方法
*数学基礎論による方法

その他の方向性として、P≠NPがそもそも[[ツェルメロ＝フレンケル集合論|ZFC]]から独立なのではないかと疑う向きがあるが、こちらについても現状では否定的な結果が得られている。

== 重要性 ==
=== 他の問題との関係 ===
; [[NP完全]]
: 1971年に[[スティーブン・クック]]が定式化した概念で、クラスNPに属し、クラスNPに属する他の全問題が[[多項式時間変換|多項式時間帰着]]される問題をNP完全という。[[充足可能性問題]]をはじめとして、数千個以上の問題が[[NP完全]]であることが示されている。これらのNP完全問題の一つでもクラスPに属することを示せれば、P＝NPとなる。
; NP完全には含まれない問題
: NP-(P∪NP完全)となる問題のクラスをNPIとする。P≠NPであれば、NPIは空集合ではないことが示されている。そのような問題の候補として[[グラフ同型|グラフ同型問題]]がある。
; [[Co-NP|coNP]]
: NP問題の[[補問題]]からなるクラスを[[coNP]]という。NP≠coNPならば、P≠NPとなることが示されている。
<!--
=== 現代暗号との関係 ===
P≠NP予想は、[[暗号理論]]の分野でも重要な位置を占めている。

例えば、[[RSA暗号]]は[[素因数分解]]、[[ElGamal暗号]]および[[楕円曲線暗号]](楕円曲線上のDLP)は[[離散対数問題]]の多項式時間による解法が存在しないことを安全性の根拠とした暗号であるが、これらの問題はどちらもクラスNPに属する問題に多項式時間帰着できる。仮にP≠NP予想が否定された場合（P＝NPの場合）、素因数分解などが多項式時間で計算可能であることになり、これらの暗号の安全性は根底から覆ることになる。
*2002年8月6日に[[マニンドラ・アグラワル]]教授らによって[[AKS素数判定法]]が発表された。これによると与えられた[[自然数]]が[[素数]]であるかどうかを log ''n'' の[[多項式]]を[[上界]]とする[[決定的アルゴリズム|決定的]][[多項式時間]]で判定できる。これにより[[素数判定]]が実際に[[P (計算量理論)|クラスP]]に属することが示された。しかし、素因数分解が多項式時間でできるかどうかははっきりしていない。

--><!--

「多項式時間による解法が存在しない」はともかく「これらの問題はどちらもクラスNPに属する問題に多項式時間帰着できる」ってホントですか？

--><!--
それだけではなく、P＝NPであれば「[[一方向性関数]]が存在しない」ことも証明できる。そして「一方向性関数が存在しない」ならば、多項式時間で破れない（暗号学的に安全な）[[公開鍵暗号]]や[[ハッシュ関数]]、[[擬似乱数]]が存在しないことが導かれる。逆に「一方向性関数が存在する」ならば、少なくとも多項式時間では破れない共通鍵暗号が構成できること、擬似乱数が存在することが証明されている。--><!-- 一方向性関数が存在しても、それだけで公開鍵暗号が構成できるかは、明らかではありません。--><!--

また、暗号方式とその平文・暗号文ペアを与えられて鍵の1ビットを判定する問題は、(通常)多項式時間で検証可能であるから、この暗号方式が[[既知平文攻撃]]の条件で鍵探索が困難であることを証明できるならば、多項式時間で判定不可能であることを示したことになり、P≠NP予想を証明できたことになる。

このように、P≠NP予想は[[計算量的安全性]]を通じて現代暗号理論と密接に関係している。-->

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* {{Citation | first1=Ketan D. | last1=Mulmuley | first2=Milind | last2=Sohoni | title=Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems | url=http://epubs.siam.org/doi/abs/10.1137/S009753970038715X | journal=SIAM J. Compput. | volume=31 | issue=2 | pages=496-526 | year=2001 | accessdate=2017-06-10 }}
* Stephen Cook, "The P versus NP Problem", 2000. {{PDFlink|[http://www.claymath.org/sites/default/files/pvsnp.pdf]}}
* Michael Sipser, ''Introduction to the Theory of Computation'', PWS Publishing Company, 1997. ISBN 0-534-94728-X. pp.372-377. (渡辺治・太田和夫 監訳, 『計算理論の基礎』, 共立出版社, 2000. ISBN 4-320-02948-8. pp.436-444)
* {{Citation | first1=Scott | last1=Aaronson | first2=Avi | last2=Wigderson | title=Algebrization: A New Barrier in Complexity Theory | url=http://dl.acm.org/citation.cfm?id=1490272 | year=2009 | journal=ACM Transactions on Computation Theory(TOCT) | volume=1 | issue=1 | accessdate=2017-06-10 }}
* {{Citation | first=N.V. | last=Vinodchandran | title=A Note on the Circuit Complexity of PP | url=http://www.sciencedirect.com/science/article/pii/S0304397505004809 | journal=Theoretical Computer Science | year=2005 | volume=347 | issue=1-2 | pages=415-418 | accessdate=2017-06-10 }}
* {{Citation | first1=Harry | last1=Buhrman | first2=Lance | last2=Fortnow | first3=Thomas | last3=Thierauf | title=Nonrelativizing Separations | url=http://dl.acm.org/citation.cfm?id=793359 | year=1998 | accessdate=2017-06-10 }}
* {{Citation | first=Alexander A. | last=Razborov | year=1985 | title=Lower bounds for the monotone complexity of some boolean functions | url=http://www.mi.ras.ru/~razborov/clique.pdf | journal=Soviet Math. Dokl. |volume=31 | issue=2 | accessdate=2017-06-10 }}
* {{Citation | first1=Merrick | last1=Furst | first2=James B. | last2=Saxe | first3=Michael | last3=Sipser | title=Parity, Circuits, and the Polynomial-Time Hierarchy | url=https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20-%201984%20-%20Parity%20circuits%20and%20the%20polynomial-time%20hierarchy.pdf | year=1984 | journal=Math. Systems Theory | volume=17 | pages=13-27 | accessdate=2017-06-10 | format=PDF }}
* {{Citation| last1 = Hartmanis | first1 = Juris | last2 = Stearns | first2 = Richard E. | author1-link=ユリス・ハルトマニス | author2-link=リチャード・スターンズ | doi = 10.2307/1994208 | journal = Transactions of the American Mathematical Society | pages=285-306 | title = On the computational complexity of algorithms | volume=117 | year=1965 | mr=0170805 | jstor=1994208 | accessdate=2017-06-10 }}
* {{Citation | first=龍明 | last=岡本 | title=相対化,自然な証明,代数化／P≠NP予想の難しさ | publisher=[[日本評論社]] | year=2009 | journal=数学セミナー | volume=48 | issue=12 | date=2009-12-01 | pages=20-25}}
* {{Cite journal | first1 = Alexander A. | last1=Razborov | first2=Steven |last2=Rudich | doi=10.1006/jcss.1997.1494 | title=Natural proofs | journal =  Journal of Computer and System Sciences | volume=55 | pages=24-35 | year=1997 }} ([http://www.mi.ras.ru/~razborov/int.ps Draft])
* {{Citation| first1=Theodore | last1=Baker | first2=John | last2=Gill | first3=Robert  | last3=Solovay | title=Relativizations of the P=?NP question | journal=SIAM J. Comput. | volume=4 | issue=4 | pages=431-442 | year=1975 | accessdate=2017-06-10 | url=http://epubs.siam.org/doi/pdf/10.1137/0204037 }}
* {{Citation| first=Ryan | last=Williams | title=Non-Uniform ACC Circuit Lower Bounds | url=https://www.cs.cmu.edu/~ryanw/acc-lbs.pdf | year=2010 | date=2010-11-23 | accessdate=2017-06-10 }}

== 関連項目 ==
* [[数学上の未解決問題]]
* [[計算機科学の未解決問題]]
* [[懸賞金問題]]
* [[多項式階層]]
* [[法月綸太郎]]……推理小説におけるこの問題に関しての考察がある。

{{ミレニアム懸賞問題}}
{{Normdaten}}
{{Applied-math-stub}}

{{DEFAULTSORT:PNPよそう}}
[[Category:計算複雑性理論]]
[[Category:予想]]
[[Category:計算機科学の未解決問題]]
[[Category:ミレニアム懸賞問題]]
[[Category:数学に関する記事|Pひいのつとえぬひいよそう]]