【数学/電算】これが解けたら世界中のビットコインは思いのままに[07/21]

これが解けたら世界中のビットコインは思いのままに
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/

>>47
もとから有限時間だぞ
何億年であろうと

>>41
p=npが証明されたらpはどこでも成り立つわけだが

ソフトバンク「われわれには必要ない」

＞「P=NPを証明できた人は、まず2000億ドル（約21兆6930億円）の

>10兆円ビジョンファンドの第2弾、さらに巨額の可能性

禿「すでに持っている」

さてと　寝よ

>>これが解けたら世界中のビットコインは思いのままに

これね…通貨がどういうモノか分かってないよねぇ。

>アラン・チューリングがドイツの暗号エニグマを解読するマシン
エニグマには文脈があるが、NP問題の答えには文脈がない。
暗号は元の文脈にしばられるとかで大金ころがりこめばいいなぁ。

いい歳した脳みそイキりキッズ達の隔離スレ

金ローの「サマー・ウォーズ」も数学少年が暗号を解いたことで
アカウントを乗っ取られてなりすまされて云々って話だったっけ。

シグネチャーをテキストに埋め込む

この手の問題解くのはペレルマンみたいにお金に興味のない人のような気もするし、
金銭的なインセンティブがどこまで意味あるのか怪しい。

>>15
いままでより簡単な暗号なんてスパコンで一瞬だろｗ

>>1
>これが解けたら世界中のビットコインは思いのままに

なんか勘違いしているみたいだけど、この問題が解けたら

「思いのままになる」か「思いのままにならない」かどちらかがわかる

だぞ？
現状は「思いのままにならない」って予測で動いているってだけで。

P≠NPにきまってるだろ

>>41
素数の発見アルゴで十分検証できてるだろ

>>50
持ってるならさっさと借金返せよ

P と NP はおそらく違うクラスだから
P=NP　を証明できるという話自体が意味ないだろうな

素因数分解は多項式時間じゃないのか？

https://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95

回路の利得みたいに半分頂くが正解？

（ﾟ∀。） ﾅﾙﾍｿ

半導体の処理速度上げるほうが簡単だな

なるほどわからん

NP→P
ゲートがいくつもあるので無理
ゲートをくぐる度に、そのゲートの命題を仮説推論してトライアンドエラー
その命題を仮説立てできるのは、今んとこ人間

Pi=NiPi
i=0
0=00
0

これを解いた奴は犯罪者という事だな

数学って2000億円強奪するような犯罪をするためにやってるんだな。

そんなもんわかるわけがないだろ。それがわかれば5チャンネルに書き込みなどしない

そんなことできたら、宇宙の演算ができちゃうわ！

P=NP
c=mc2
何か共通してるのあるよね？

相対性理論のc=mc2に似てる
という事は、速度が速くなれば、この場合、演算速度がどんなに速くなっても　
P=NPは無限の時間が費やされる事になるとか考えられる
ＮＰはＰに近づく事は、あり得ない
０に近づくなら無限の質量増加があるんだから
ＮＰは無限に難問になりうる

いくら簡単な問題でも天文学的な数字と数字との足し算すら無限の時間がかかる

むしろ難問のほうに対してイコールになる

N=1

たぶんＮＰ＝Ｐなら
すぐに真だとなるから、Ｐ＝ＮＰで偽

Ｎ(非決定的な)＝Ｐ(多項式時間)P(簡単な問題)なら難しい問題＝ＰＰで無限の時間が費やされるから
ＮＰ＝Ｐで対偶はＮ＝ＰP


Ｐ多項式時間Ｐ簡単な問題＝Ｎ(非決定的な)なら、時間が許すならＮ(難しい問題)の答えが必ずしも出てこない

簡単な問題とはイコールにならないＰ＝ＮPとＰＰ＝Ｎは対偶

時間の制限がなく悠久の時間が使えるなら
P∞=N∞P∞
簡単な問題に無限の時間が使えるから、
非決定的な多項式時間にも無限の時間が使える
この時は、有意差は問題にならないという意味でイコールになる

p＝np だと？ n＝1 じゃん。簡単だな。
金くれ。

>>1
解けたけどここに書くにはちょっと狭すぎる

証明できても追求を諦めるか続ける意味があるかの指標でしかない
が、当然大きな意味はある

数独はサイズが決まっている問題だからＯ（１）。

ブルートフォースアタック
総当たり攻撃が多項式時間でおさまるならP=NP
グーグルが答えを出してるな

>>76
事実上P=NPってことだろ
理論上はP≠NP

解っていうのは、数字の入れ替えに過ぎないんで
ブルートフォースアタックが最強になるはず
これが現実世界では有限次数有限桁数なので総当たりが有限多項式に収まれば
事実上P=NP

>>67
ムーアの法則により p=2^(y/1.5)
多項式時間がこれ以内におさまるならP=NP

素数がでてくるパターンを誰か解き明かしてよ。

>>15
無茶言うな

>>13
馬鹿は、存在証明が必ずしも構成的証明とは限らないことがわかってない、お前な

>>1
いやいや、多項式全部の式の証明って、難易度高杉。

>>7
ﾉｼ

7payより安全なnpay

解けても「思いのままに」は難しいな
発覚しないように少しづつチートマイニングを行って売りさばく
大手マイナーと結託すれば増やせる？

仮性か真性かの違い。自慰可能は共通。

サマーウォーズのやつ？

これを考えない人が金を儲けている、ってことは分かってる

ビットコインは楕円関数曲線をガロア空間にぶち込んでんだろ？
単なる素因数分解じゃないだろ。

ビットコインをビッコって訳したらだめって言われた

サマーウォーズはじめました・☆☆☆

>>15
量子暗号にでもしなきゃ、その他の暗号は全部同じ扱いで解けるはず

まあ、「多項式時間」っていっても n^k で　n=10^10 k= 1,000 とかだと実質的に解けそうもないのだが

解けたけど秘密にしとこ
これでビットコインはオレのもの

ぴー＝んぴー　１〇ー＝〇１〇ー

１ ＝ 01

>>7
ﾉｼ

ビットコイン台帳のマスターキーは製作者の生年月日と星座

P=NPであることと、具体的な問題に対して多項式時間で解ける
アルゴリズムを見つけることは別の話じゃないのか？

>>107
それはその通りなのだが、P=NPの場合には
NP完全問題のどれでも良いから１つについて多項式時間のアルゴリズムを見つけておけば
後は、その多項式時間アルゴリズムのあるNP完全問題に対して解きたいNP問題を多項式時間還元するだけで良い

そしてNP完全問題については、他のNP完全問題やNP問題からの多項式時間還元のやり方は既に知られている
（だからこそ、その問題は単なるNP問題でなくNP完全問題に分類される）

つまりP=NPが成り立っているならば、NP完全問題の１つについてだけ多項式時間アルゴリズムを用意しておけば
他のNP問題に対しては多項式時間アルゴリズムを新たに考え出す必要はなくなるんだよ

>>107
>>108
アホか
多項式時間ということは問題のサイズnに対してn^kの計算量(k>1)となるものでサイズが大きくなるにつれて膨大な計算量を必要とするものであり「既知の事象」
それゆえnを一定以上に大きくすることで事実上解くことができなくすることが可能で認証や暗号化に使える


P=NP問題は問題のサイズnに対してn^jの計算量(j≦1) で解く可能を論ずるもの
そしてP=NPが証明されれば現在使われている暗号化の安全性が損なわれることを意味する

理論的にはP≠NPなんだよ
２次元なら、解はNｘNの表の数字の入れ替えになる
これを多項式時間でやれるかという問題
最悪NxNかかるのでP≠NPなのさ
あとはD次元に拡張するだけ

>>110
多項式って2次式も3次式も4次式も多項式や。多項式でないってのは2^nとかのnの指数関数以上に増えるやつのこと。

ロスアラモスって原爆のか

>>109
話が伝わってないorz。P=NPが示されたからと言って具体的に解く手順を開発するのはまた別の苦労が
あるんじゃないの？という疑問だったんだが。
微分方程式の解の存在は証明されているからと言って実際に解くのは大変、みたいな。

P=NPの証明が、>>108のいうどれでもいいから１つのNP完全問題についての
アルゴリズムの開発と同義なのかな？

ブラフだぞこれ

>>113
> P=NPの証明が、>>108のいうどれでもいいから１つのNP完全問題についての
> アルゴリズムの開発と同義なのかな？

108です
NP完全問題の一つについて多項式時間アルゴリズムを発見すればP=NPの証明になる、これは間違いない

問題はその逆が成り立つか？ということだが、
P=NPの証明が非構成的に行える可能性（つまりP≠NPと仮定して矛盾を導く背理法による証明の可能性）は
少なくとも現時点までのP vs NP問題に関して知られている事実からは排除できない

もうビットコインは中国人専用でエエわ…

21兆円あったらゲームのプロデューサーやりたい
あとなんかイベントやりたい
花火大会で二尺玉あげたい

>>117
そのぐらいなら２１兆の１万分１で出来るだろｗ
ってか普通に頑張ればできると思うぞ

ブロックチェーン/分散型台帳技術 [無断転載禁止]©2ch.net
http://rio2016.5ch.net/test/read.cgi/future/1476975355

ふーん、なるほどね

ビビットコイン

ビットコインがなくなるとブロックチェーンも無くなるは詭弁

ビットコインが誕生してはや10年
ビットコインはイノベーションを理由に無法地帯が10年も続いた

ブロックチェーン=ビットコインではない
ブロックチェーンを利用する際もシステム的にもビットコインは必要ない。アメリカSECとCFTCが価格操作を指摘している

ブラックロックCEO
『ほしいのは仮想通貨ではない、ドルとユーロの交換を
今以上に安いコストで瞬時に計算し貨幣化するコンピューター（システム）が必要』

ブロックチェーンを利用したシステムにはビットコインは必要ない
仮想通貨も必要ないのだ
ビットコインを含む仮想通貨はブロックチェーンの一面にすぎない


>>1-9

>>122


仮想通貨はイノベーションを理由に、長年放置されてきた。
911を体験していない日本人はテロに対する認識が甘い。
ビットコインのテロ資金供与問題　G7でも話題になっている。
マネロンとテロ資金供与問題は『リブラ』だけの問題ではない
ビットコインを含む暗号資産全体が抱える問題。

仮想通貨市場はテロ資金供与防止を無視した。
メールアドレスだけで登録可能な匿名性の高い
bitmexなどの取引所が存在する市場（日本では利用が禁止されていない）
匿名性か高い取引所を利用することは、
意図せずテロ資金供与に関与する可能性が増す。
ビットコインなどは銀行と違い
送金先の身元を確認しない。国内外に自由に送金できる。
テロ資金供与対策を実施中の銀行は受取人の
身元確認が完了するまで送金できない

つまり現在の暗号資産は身元確認なしで国内外送金し放題
テロ資金供与及びマネロンの温床とG7やG20でも危惧されている
早急に送受金時の身元確認の対策をすべきだ。

CMEグループ Bitcoinに関連するリスク
https://www.cmegroup.com/ja/disclaimer/bitcoin-futures-risk-factors.html

>>115

>P=NPの証明が非構成的に行える可能性（つまりP≠NPと仮定して矛盾を導く背理法による証明の可能性）は
>少なくとも現時点までのP vs NP問題に関して知られている事実からは排除できない

>108 はマジメだからこんなふうに書いてるけど

背理法によるP=NP の証明なんか絶対にできないことに カシオミニを10000個賭けてもいい。
できるとしたら実際にアルゴリズムを示す構成的証明。

つまり、>1 はいたってまともな論旨

>>124
君のレス中の>>115と>108とは逆じゃないの？

ビットコインを盗むような犯罪を犯すより、大量に掘り起こせば良いのに

『ビットコインは安全資産ではない。
デジタルゴールドは過剰表現であり誇大広告』

CMEグループ Bitcoinに関連するリスクについて
https://www.cmegroup.com/ja/disclaimer/bitcoin-futures-risk-factors.html

>>1
解いたらビットコインを盗めるって意味が分からない(・д・)