(画像)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問題としては解けない、と思われている問題集ということです(ただし答え合わせは簡単)。
■■以下、小見出しなど抜粋
・ビットコイン台帳のマスターキー
・次世代コンピューターは…?
GIZMODO
https://www.gizmodo.jp/
解き方まではわかるとは限らないのにな
だよなw
正しいと仮定しても暗号が解ける訳ではない
問題が解けるんだよ。
NP=Pが証明できるということは
あらゆるNP問題をP問題に変換できるアルゴリズムが存在するというのと同じことだ。
このアルゴリズムは任意のNP問題をP問題に変換できるから、現在の任意の暗号を復号する問題をP問題に変換できる。
アルゴリズムが存在するとしてそれが多項式時間でできるのかってことは問題にならんのかね?
これがダンニング・クルーガー効果です
バカほど自己評価が高い
複数の専門家がこのバカ程度が思い付くような程度の事に気づかない訳が無い、と理解できないのです
バカって本当に怖いですね
678ッキリ9ッキリ10芝さんの方が
グ~。
安全だよ…
ち、超安全…(´-﹏-`;)
完全にオーバースペックだ
むしろ、解けた瞬間にビットコインの価値が0になるのでは?
全てのビットコインを独占しても、
自分以外の他者が価値を認めなければ価値は0だ
内緒で掘り尽くして売り抜けば良いが、流通量でバレるね。
経済成長が必要な理由の一つが投資すると儲かることだからな。
どうせまた数学というより物理の問題なんだろうけどさ
いいかげんアラブだかの数学者リスペクとして抽象化するのやめたらいいのに
あるがままの現実世界>数字の世界なんだから
21兆が21兆として存続できない気が
多項式時間で解くためのアルゴリズム」が「存在すること」が
証明されただけで、具体的にどんな方法なのか分からなければ
意味無いよね。
ひょっとしたら宇宙が終わるまで頑張っても発見困難なくらいの
超絶複雑なアルゴリズムかも知れない。
$(function(){
var c = 0;
if($(“div.mtpro-tweet-outer”).length){
var ad = “div.mtpro-tweet-outer”
}if($(“.twitter-tweet”).length){
var ad = “.twitter-tweet”
}if($(“div.t_h”).length){
var ad = “div.t_h”
}
$(ad).each(function() {
if (c !== 0) {
if(c == 4 ){
$(this).before(‘
‘);
}
else if(c == 8 ){
$(this).before(‘
‘);
}
else if(c == 12 ){
$(this).before(‘
‘);
}
else if (c >= 16 && c%4 == 0) {
$(this).before(‘
‘);
}
}
c++;
});
});
元スレ:http://egg.5ch.net/test/read.cgi/scienceplus/1563677403/
Source: mindhack
【驚愕】これが解けたら世界中のビットコインは思いのままに・・・