5分で折れた人類よ、目覚め奮起せよ。
コンピュータの世界の根幹に関わる命題として米クレイ数学研究所が人類7つの最難問｢ミレニアム懸賞問題｣に掲げ 、解けた人に100万ドル（約1億800万円）を用意している｢P vs NP問題｣。なかなか解けたというニュースが流れてこないことに痺れを切らしたのか、量子コンピュータ研究者のスコット・アーロンソン博士が先日開かれたニューメキシコ州ロスアラモス国立研究所の講演で、満場の聴衆にこう発破をかけ話題です。
｢P=NPを証明できた人は、まず2000億ドル（約21兆6930億円）のビットコインを盗む。で、ミレニアム懸賞問題の残りの難問も解いてしまうだろう｣
PとかNPって、どういうこと？
コンピュータも所詮は問題を解く機械ですからね。機械が理解できるコードに問題を置き換えてフィードして処理させるマシン。これはアラン・チューリングがドイツの暗号エニグマを解読するマシンをつくった当初から変わっていません。問題を解くにはそれなりの時間とステップが必要で、問題が難しくなればなるほど、解く時間は長くなります。
｢P問題｣というのは、コンピュータがある程度短時間で解ける問題全般を指します。2つの数の掛け算なんかの単純なものから、ネット閲覧みたいなややこしいタスクまで内容はさまざまあり、複雑になればなるほど、時間はかかり、処理時間は｢多項式時間｣のべき乗（nの2乗など）で増えていきます。nの2乗で解ける問題なら、解かせる量を2倍にすると、処理時間は2倍ではなく4倍になる、というわけです。とはいえ、一定時間のうちに解けるもの。
いっぽう、答え合わせは多項式時間でスラスラ～ッとできるのに、解くのは多項式時間にはまったく間に合わない問題も数多くあります。これがいわゆる｢ 非決定性多項式時間 （Nondeterministic Polynomial time）｣、略して｢NP問題｣です。身近な例でいうと、数独はNP問題。解くのは難しいけど、答え合わせはめちゃ簡単ですからね。
もっと重要な例では巨大な数の素因数分解、これもNP問題です。解くまでには（今のところ）膨大な時間がかかって、多項式時間にはとても間に合わないのに、答え合わせは一発で、単なる掛け算で終わります。実は今のメール、ウェブ、アプリなんかの暗号化技術は大体これ。破るのは難しいけど、認証（答え合わせ）は簡単、そういう鍵を生成してがっちんこブロックをかけているんですね～はい～。
まとめると、P問題は現代のコンピューターが現実的に解ける問題集。NP問題は、現代のコンピューターだと現実的には解けない＝P問題としては解けない、と思われている問題集ということです（ただし答え合わせは簡単）。
ビットコイン台帳のマスターキー
ところが最近の数学の研究でNP問題の中にP問題としてで解ける例が見つかり、これからも見つかりそうな気配であることから、 ｢P vs NP問題｣の証明で決着をつけようということになりました。この証明では、
・NP問題すべてがP問題として解ける（P=NP）
・NP問題の中にはP問題としては絶対解けないものもある（P≠NP）
以上のいずれかを証明しなければなりません。普通に考えたらP≠NPですけれど、これ、数学的には実はまだ証明されていないんですね。仮にそれが誤りでP=NPと証明できた場合には、コンピュータのアルゴリズムでアッサリ解ける重要問題の幅が格段に広がることを証明できたことになります。ビットコインのマイニング、暗号鍵はいずれも｢解くのに膨大な時間がかかるけど、答え合わせは一発｣というNPの特性に依存する技術ですから、それさえも破られることに。もしそうなったらビットコインは自由自在です。
次世代コンピューターは…？
量子コンピュータは従来のコンピュータと異なる数学理論がベースですが、NP問題すべてにPの解を約束する段階ではありません。｢NP完全｣というNP問題の最難関クラスの問題も解けると、一時は期待されていたのですけどね…。NP完全の問題に高速解を見つけることができれば、NP問題すべてが解けることになり、巡回セールスマン問題なんかの最適化問題もお手のもの。でも今の量子コンピュータでは｢一部のP問題を今より短い時間で解ける｣、｢一部のNP問題をBQP（Bounded-Error Quantum Polynomial Time： 量子計算多項式時間アルゴリズム ）のクラスに移行｣するというレベルの進化にとどまっています。
そんなわけでみなさまもP=NPなのかP≠NPなのか、がんばって証明しましょー！ 成功したら大儲け。失敗しても、コンピュータ理論追求の充実ライフが待っています。
