0001一般国民 ★
2019/07/21(日) 11:50:03.26ID:CAP_USERhttps://headlines.yahoo.co.jp/hl?a=20190716-00000028-giz-sctch
https://headlines.yahoo.co.jp/hl?a=20190716-00000028-giz-sctch&;p=2
2019/7/16(火) 11:01配信
YAHOO!JAPAN NEWS,ギズモード・ジャパン
（記事全文は、ソースをご覧ください。）
【科学(学問)ニュース＋】
（画像）PとNPの問題の複雑性（難易度）の相関図。Pは多項式時間（polynomial time）でアッサリ解ける問題。 NPは多項式時間で解け、多項式時間で答え合わせできる問題。 NP完全（NP-Complete）は、その答えが見つかると、それで全NP…
https://amd.c.yimg.jp/amd/20190716-00000028-giz-000-1-view.jpg
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問題としては解けない、と思われている問題集ということです（ただし答え合わせは簡単）。
■■以下、小見出しなど抜粋
・ビットコイン台帳のマスターキー
・次世代コンピューターは…？
satomi
最終更新:7/16(火) 11:01
ギズモード・ジャパン
GIZMODO
https://www.gizmodo.jp/
