[数学]P vs NP 問題

１９００年にドイツの数学者ヒルベルトが２３の当時未解決問題を列挙したことにならい、アメリカのクレイ数学研究所が２０００年に７つの問題（そのうちひとつのポアンカレ予想は解決済）を公開した。

P vs NP 問題は７つの問題の内、最も理解しやすく、数学とコンピュータにまたがる問題。

最初に努めた会社の同僚M氏（後に数学の論文を発表）が教えてくれたことに、物事を定義するには内的と外的な定義がある。数学は外的な定義のみを採用すると。内的な定義とは対象の特徴を説明すること。例えば、リンゴは赤く、丸く、手のひらサイズのものが、リンゴと定義するやり方。このやり方では、例外を挙げることができる。青いリンゴも、四角いリンゴもあるからだ。外的とは赤く、丸く、手のひらサイズという３つの条件を同時に満たすものは、たとえボールなどでも、全てをりんごとするという態度。

数学は厳密性のために、ボールであっても先に設定した条件に合えば、リンゴとする。そして先に設定した条件に当たる事象すべてを、ひとまとめにしリンゴ集合とする。

P vs NP 問題のPとは、コンピュータで早く解くことができる問題の集合（Pクラスと呼び、かかる時間の上限がO(n^k）N=入力サイズ, K は定数） 。NPとはコンピュータで解くことは時間がかかりすぎ現実的ではない問題の集合（例えば入力サイズに対して幾何級数的に計算時間が伸びる問題群）。しかし答えが正しいかどうかの確認はPクラス並に素早くできる問題の集合（NPクラスと呼ぶ）。

コンピュータアルゴリズムの歴史はNP問題だと思っていたけど、頭の良い人が新しいアルゴリズム（もしくは実装）を考えて、実はP問題（早く解ける問題）だったと発見することの繰り返しであった。ならばすべてのNPクラスの問題は、将来的にはPクラスとなるのであろうか。

例を挙げると素数判定。与えられた数が素数かどうかをチェックする問題。昔は計算時間が長いとされていたが、後にPクラス(早く解ける)の問題になった。

アリストテレス「エラトステネスのふるい」というアルゴリズム（もしくは試し割り）。素数Aを与えられたら、２から順に繰り返し割り算を行い、最後まで余りがゼロにならなければ素数。原理的に与えられた素数が大きければ、試し割りの回数が増え、計算時間が増大する。この計算時間の増大は、一つ一つの数を巡ら(searching)なければならないところにある。

では以下の方法はどうだろう（フェルマーテスト）

2^(p-1) = 1 (mod p)　余りが１ならPは素数
例１：If P = 7, then 2^(7-1) = 64. then 64/7 の余りは１、だから７は素数
例２：if P = 15, then 2^(15-1) = 16384, then 16384/15 の余りは４で１ではないので１５は素数ではない

上記の素数判定では、Searchingが省略されているため、大きな数でも計算時間の上限を抑えることができる。フェマーテストは反例があり、運が悪いと判定に誤りがあるが、AKSという方法は判定に誤りがなく、かつ計算時間の上限を抑えることができる。そして素数判定はPクラスの問題となった。

現在のコンピュータセキュリティはビットコインを含め「素因数分解は時間がかかる」ということに依存している。しかしそれは素因数分解を早く解く方法が存在しないということではない。現実には１９９４年にショアのアルゴリズムは量子コンピュータを使えば、素因数分解を極めて短い時間で解くことが示された。

またシュタイナー木と言われている短連結問題、もしくは最短ネットワーク問題（すべての点を最小の長さで結ぶ）は、NP問題（点が増えると、点の組み合わせの数が格段に増えていくから）であり。すなわち連結する点の数が多ければ、組み合わせ（場合の数）の増大により、コンピュータで膨大な検索空間を一つ一つ巡る時間も膨大になるため計算が終わらず、解くことができない。しかし板に釘を刺し、石鹸の泡につけて引き出すと石鹸の泡は瞬時に最短経路の形となる。万物の創造主はNPクラスである最短経路問題を素早く解くことに物理的制限を設けていない。

計算の時間がかかるならば、コンピュータを宇宙空間で半永久的に計算を行うようにし、人間は高速で移動することで自身の時間の流れを止め、未来にワープすれば良い。しかしこの方法も、宇宙の寿命という制限があり、NP問題を解くことはできない。

理論的には膨大な数の並列コンピュータを用意し、同時進行で計算せることも考えられる。しかし、この方法は膨大なコンピュータとともに膨大なエネルギーを必要とし、そのような高密度エネルギーの存在を物理は許さずブラックホールとなり、NP問題を解くことはできない。

NPクラスはすべてPクラスなのか（N=NP?）。それはNP完全というNPクラスの中でも、最も時間のかかる問題群の一つでもPクラスの問題と証明できるかにかかっている。（NP完全クラスに属する問題は、他のNP完全クラスの問題に変換-Reductionできるから）。

もしくはNPクラスはNクラスにならず、NPクラスの問題をNクラスの計算時間で解くならば、確率的にのみ正しい答えを得ることしかできない、何らかの数学的な制限があるのであろうか。（NPクラス問題は定義上、素早く答えを確認できるため、運が良ければ答えが早く見つかる）

想像をたくましくすれば、RSA暗号やビットコインなど国家の権力を弱める仕組みをアメリカが世界で許容するのも米国国家安全保障局（NSA）はNPクラスをPクラスの問題として解く方法を、既に持っているからであろうか。（少なくとも素因数分解問題が早く解けるアルゴリズムや手段）

NPクラスをPクラスの問題として解けるということは、どんなに変数が多くても、様々な組み合わせを瞬時に俯瞰し、最適な組み合わせが見つかるということであり、経済の最適化はもとより、コンピュータの知性を爆発的に飛躍させる。ちなみにチェスなどのゲームは”最善の一手”であるかどうか、計算結果を素早く確認する手段がないためNPクラスよりも難しい、NPHarderクラスに属する。

NP vs P問題は、多くの科学者がNP＝Pでないと予想している（長く時間がかかる問題、例えば巡回セールスマン問題、には原理的に早く解く方法は存在しない）。またNP=Pであるならば、未来の形が想像ができないほど変わってしまう。プログラミングパラダイムも変わり正しい結果判定方法を指定するだけで、あとは最適化も含めて、プログラムは自動化されるのではないか。この問題は新しい数学、もしくは新しい物理学理論に基づいた計算機を必要とするのか。できればNP=Pとして証明され、未来が大きく変わるところを見てみたい。

参考:
https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%AC%E3%83%8B%E3%82%A2%E3%83%A0%E6%87%B8%E8%B3%9E%E5%95%8F%E9%A1%8C
https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%AB%E3%83%99%E3%83%AB%E3%83%88%E3%81%AE23%E3%81%AE%E5%95%8F%E9%A1%8C
https://ja.wikipedia.org/wiki/P%E2%89%A0NP%E4%BA%88%E6%83%B3
https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time
https://en.wikipedia.org/wiki/Time_complexity
https://en.wikipedia.org/wiki/P_versus_NP_problem
https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A
https://www.youtube.com/watch?v=msp2y_Y5MLE
https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86#.E3.83.95.E3.82.A7.E3.83.AB.E3.83.9E.E3.83.BC.E3.83.86.E3.82.B9.E3.83.88
https://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
https://www.youtube.com/watch?v=fuSZoh7EURI
https://en.wikipedia.org/wiki/Steiner_tree_problem
https://www.youtube.com/watch?v=PI6rAOWu-Og
https://en.wikipedia.org/wiki/NP-completeness
https://www.youtube.com/watch?annotation_id=annotation_1160797119&feature=iv&src_vid=mr1FMrwi6Ew&v=eHZifpgyH_4
https://en.wikipedia.org/wiki/Complexity_class

「P≠NP」問題 現代数学の超難問 (ブルーバックス)