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

>>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
解いたらビットコインを盗めるって意味が分からない(・д・)