1: 一般国民 ★ 2019/07/21(日) 11:50:03.26 ID:CAP_USER
これが解けたら世界中のビットコインは思いのままに
https://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/
https://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/
引用元: ・【数学/電算】これが解けたら世界中のビットコインは思いのままに[07/21]
47: ニュースソース検討中@自治議論スレ 2019/07/21(日) 16:54:07.58 ID:Auz+DEKN
>>1
解けたからと言って思いのままって何も理解してないな
有限時間内で解けることを証明しただけだ
解けたからと言って思いのままって何も理解してないな
有限時間内で解けることを証明しただけだ
48: ニュースソース検討中@自治議論スレ 2019/07/21(日) 16:58:27.93 ID:fi5cG/RC
>>47
もとから有限時間だぞ
何億年であろうと
もとから有限時間だぞ
何億年であろうと
109: ニュースソース検討中@自治議論スレ 2019/07/26(金) 02:15:57.72 ID:fxcNnHDY
>>107
>>108
アホか
多項式時間ということは問題のサイズnに対してn^kの計算量(k>>1)となるものでサイズが大きくなるにつれて膨大な計算量を必要とするものであり「既知の事象」
それゆえnを一定以上に大きくすることで事実上解くことができなくすることが可能で認証や暗号化に使える
P=NP問題は問題のサイズnに対してn^jの計算量(j≦1) で解く可能を論ずるもの
そしてP=NPが証明されれば現在使われている暗号化の安全性が損なわれることを意味する
>>108
アホか
多項式時間ということは問題のサイズnに対してn^kの計算量(k>>1)となるものでサイズが大きくなるにつれて膨大な計算量を必要とするものであり「既知の事象」
それゆえnを一定以上に大きくすることで事実上解くことができなくすることが可能で認証や暗号化に使える
P=NP問題は問題のサイズnに対してn^jの計算量(j≦1) で解く可能を論ずるもの
そしてP=NPが証明されれば現在使われている暗号化の安全性が損なわれることを意味する
113: ニュースソース検討中@自治議論スレ 2019/07/26(金) 13:41:06.80 ID:QDiF744N
>>109
話が伝わってないorz。P=NPが示されたからと言って具体的に解く手順を開発するのはまた別の苦労が
あるんじゃないの?という疑問だったんだが。
微分方程式の解の存在は証明されているからと言って実際に解くのは大変、みたいな。
P=NPの証明が、>>108のいうどれでもいいから1つのNP完全問題についての
アルゴリズムの開発と同義なのかな?
話が伝わってないorz。P=NPが示されたからと言って具体的に解く手順を開発するのはまた別の苦労が
あるんじゃないの?という疑問だったんだが。
微分方程式の解の存在は証明されているからと言って実際に解くのは大変、みたいな。
P=NPの証明が、>>108のいうどれでもいいから1つのNP完全問題についての
アルゴリズムの開発と同義なのかな?
115: ニュースソース検討中@自治議論スレ 2019/07/26(金) 20:25:18.01 ID:epu+AqUv
>>113
> P=NPの証明が、>>108のいうどれでもいいから1つのNP完全問題についての
> アルゴリズムの開発と同義なのかな?
108です
NP完全問題の一つについて多項式時間アルゴリズムを発見すればP=NPの証明になる、これは間違いない
問題はその逆が成り立つか?ということだが、
P=NPの証明が非構成的に行える可能性(つまりP≠NPと仮定して矛盾を導く背理法による証明の可能性)は
少なくとも現時点までのP vs NP問題に関して知られている事実からは排除できない
> P=NPの証明が、>>108のいうどれでもいいから1つのNP完全問題についての
> アルゴリズムの開発と同義なのかな?
108です
NP完全問題の一つについて多項式時間アルゴリズムを発見すればP=NPの証明になる、これは間違いない
問題はその逆が成り立つか?ということだが、
P=NPの証明が非構成的に行える可能性(つまりP≠NPと仮定して矛盾を導く背理法による証明の可能性)は
少なくとも現時点までのP vs NP問題に関して知られている事実からは排除できない
124: ニュースソース検討中@自治議論スレ 2019/07/29(月) 18:34:27.56 ID:ZMauxfyJ
>>115
>P=NPの証明が非構成的に行える可能性(つまりP≠NPと仮定して矛盾を導く背理法による証明の可能性)は
>少なくとも現時点までのP vs NP問題に関して知られている事実からは排除できない
>>>108 はマジメだからこんなふうに書いてるけど
背理法によるP=NP の証明なんか絶対にできないことに カシオミニを10000個賭けてもいい。
できるとしたら実際にアルゴリズムを示す構成的証明。
つまり、>>1 はいたってまともな論旨
>P=NPの証明が非構成的に行える可能性(つまりP≠NPと仮定して矛盾を導く背理法による証明の可能性)は
>少なくとも現時点までのP vs NP問題に関して知られている事実からは排除できない
>>>108 はマジメだからこんなふうに書いてるけど
背理法によるP=NP の証明なんか絶対にできないことに カシオミニを10000個賭けてもいい。
できるとしたら実際にアルゴリズムを示す構成的証明。
つまり、>>1 はいたってまともな論旨
125: ニュースソース検討中@自治議論スレ 2019/07/30(火) 02:33:03.77 ID:Eqyod5bO
>>124
君のレス中の>>115と>>108とは逆じゃないの?
君のレス中の>>115と>>108とは逆じゃないの?
6: ニュースソース検討中@自治議論スレ 2019/07/21(日) 11:59:33.67 ID:C9S+1Ugf
P=NP照明できても暗号を解く方法が存在するのがわかるだけで
解き方まではわかるとは限らないのにな
解き方まではわかるとは限らないのにな
11: ニュースソース検討中@自治議論スレ 2019/07/21(日) 12:07:18.73 ID:4Jeidx8G
>>6
だよなw
正しいと仮定しても暗号が解ける訳ではない
だよなw
正しいと仮定しても暗号が解ける訳ではない
13: ニュースソース検討中@自治議論スレ 2019/07/21(日) 12:18:49.14 ID:q7fSDY6V
>>6
馬鹿?
NP=Pが証明できるということは
あらゆるNP問題をP問題に変換できるアルゴリズムが存在するというのと同じことだ。
このアルゴリズムは任意のNP問題をP問題に変換できるから、現在の任意の暗号を復号する問題をP問題に変換できる。
馬鹿には難しいか?
馬鹿?
NP=Pが証明できるということは
あらゆるNP問題をP問題に変換できるアルゴリズムが存在するというのと同じことだ。
このアルゴリズムは任意のNP問題をP問題に変換できるから、現在の任意の暗号を復号する問題をP問題に変換できる。
馬鹿には難しいか?
18: ニュースソース検討中@自治議論スレ 2019/07/21(日) 12:42:30.37 ID:4Jeidx8G
>>13,14
アルゴリズムが存在するとしてそれが多項式時間でできるのかってことは問題にならんのかね?
アルゴリズムが存在するとしてそれが多項式時間でできるのかってことは問題にならんのかね?
91: ニュースソース検討中@自治議論スレ 2019/07/22(月) 09:04:19.50 ID:O07sqtvi
>>13
馬鹿は、存在証明が必ずしも構成的証明とは限らないことがわかってない、お前な
馬鹿は、存在証明が必ずしも構成的証明とは限らないことがわかってない、お前な
38: ニュースソース検討中@自治議論スレ 2019/07/21(日) 14:51:02.47 ID:WA3NVuQA
>>6
これがダンニング・クルーガー効果です
バカほど自己評価が高い
複数の専門家がこのバカ程度が思い付くような程度の事に気づかない訳が無い、と理解できないのです
バカって本当に怖いですね
これがダンニング・クルーガー効果です
バカほど自己評価が高い
複数の専門家がこのバカ程度が思い付くような程度の事に気づかない訳が無い、と理解できないのです
バカって本当に怖いですね
46: ニュースソース検討中@自治議論スレ 2019/07/21(日) 16:47:40.35 ID:fi5cG/RC
>>6
一例を出そう
割り算をして余りを求める作業をPとする
11割る2は余りが1
11割る3は余りが2
11割る5は余りが1
11割る7は余りが4
このときNPの作業とは
ある共通の数xを求める作業である
xを2で割ると余り1
xを3で割ると余り2
xを5で割ると余り1
xを7で割ると余り4
※商は分からないものとする
この程度であれば簡単だが
実際には100桁以上の数字で行う
このxをPWに用いるPWが正規のものであるかを確かめる作業がPでありこのPWを入手可能な情報から求める方法がNPである
一例を出そう
割り算をして余りを求める作業をPとする
11割る2は余りが1
11割る3は余りが2
11割る5は余りが1
11割る7は余りが4
このときNPの作業とは
ある共通の数xを求める作業である
xを2で割ると余り1
xを3で割ると余り2
xを5で割ると余り1
xを7で割ると余り4
※商は分からないものとする
この程度であれば簡単だが
実際には100桁以上の数字で行う
このxをPWに用いるPWが正規のものであるかを確かめる作業がPでありこのPWを入手可能な情報から求める方法がNPである
15: ニュースソース検討中@自治議論スレ 2019/07/21(日) 12:19:51.25 ID:usnOa3ix
暗号解読法が分かっても暗号を変えればいいだけなのでビットコインは安泰
58: ニュースソース検討中@自治議論スレ 2019/07/21(日) 18:48:05.66 ID:DbszuobO
>>15
いままでより簡単な暗号なんてスパコンで一瞬だろw
いままでより簡単な暗号なんてスパコンで一瞬だろw
90: ニュースソース検討中@自治議論スレ 2019/07/22(月) 08:46:21.24 ID:t5DL8WpM
>>15
無茶言うな
無茶言うな
102: ニュースソース検討中@自治議論スレ 2019/07/23(火) 12:10:29.32 ID:ZqXvfzfU
>>15
量子暗号にでもしなきゃ、その他の暗号は全部同じ扱いで解けるはず
まあ、「多項式時間」っていっても n^k で n=10^10 k= 1,000 とかだと実質的に解けそうもないのだが
量子暗号にでもしなきゃ、その他の暗号は全部同じ扱いで解けるはず
まあ、「多項式時間」っていっても n^k で n=10^10 k= 1,000 とかだと実質的に解けそうもないのだが
19: ニュースソース検討中@自治議論スレ 2019/07/21(日) 12:43:25.37 ID:Q1kiTU3K
P=NP証明が解けたら21兆円以上の価値があるのは確かだが
完全にオーバースペックだ
完全にオーバースペックだ
25: ニュースソース検討中@自治議論スレ 2019/07/21(日) 13:29:16.10 ID:hi1GQ4qV
>>19
むしろ、解けた瞬間にビットコインの価値が0になるのでは?
全てのビットコインを独占しても、
自分以外の他者が価値を認めなければ価値は0だ
むしろ、解けた瞬間にビットコインの価値が0になるのでは?
全てのビットコインを独占しても、
自分以外の他者が価値を認めなければ価値は0だ
39: ニュースソース検討中@自治議論スレ 2019/07/21(日) 15:02:40.22 ID:oe4dXSM5
>>25
内緒で掘り尽くして売り抜けば良いが、流通量でバレるね。
内緒で掘り尽くして売り抜けば良いが、流通量でバレるね。
23: ニュースソース検討中@自治議論スレ 2019/07/21(日) 13:16:34.31 ID:x8g19iCg
量子コンピューターが実用化段階になると、ブロックチェーン技術が崩壊すると?
30: ニュースソース検討中@自治議論スレ 2019/07/21(日) 14:17:10.58 ID:HavZmp0q
要約すると、『旨いもん』は『旨い』ってことだね