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

■ このスレッドは過去ログ倉庫に格納されています
1一般国民 ★2019/07/21(日) 11:50:03.26ID: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/

78ニュースソース検討中@自治議論スレ2019/07/22(月) 01:40:30.04ID:PIZzkQif
N=1

79ニュースソース検討中@自治議論スレ2019/07/22(月) 01:45:24.37ID:+hjSTtec
たぶんNP=Pなら
すぐに真だとなるから、P=NPで偽

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


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

簡単な問題とはイコールにならないP=NPとPP=Nは対偶

80ニュースソース検討中@自治議論スレ2019/07/22(月) 01:51:39.19ID:+hjSTtec
時間の制限がなく悠久の時間が使えるなら
P∞=N∞P∞
簡単な問題に無限の時間が使えるから、
非決定的な多項式時間にも無限の時間が使える
この時は、有意差は問題にならないという意味でイコールになる

81ニュースソース検討中@自治議論スレ2019/07/22(月) 01:58:21.29ID:SY7ggIA3
p=np だと? n=1 じゃん。簡単だな。
金くれ。

82ニュースソース検討中@自治議論スレ2019/07/22(月) 03:44:29.85ID:0r6Jb0Sj
>>1
解けたけどここに書くにはちょっと狭すぎる

83ニュースソース検討中@自治議論スレ2019/07/22(月) 04:23:06.45ID:noaPFsYp
証明できても追求を諦めるか続ける意味があるかの指標でしかない
が、当然大きな意味はある

84ニュースソース検討中@自治議論スレ2019/07/22(月) 05:22:04.65ID:+JTp+Rbx
数独はサイズが決まっている問題だからO(1)。

85ニュースソース検討中@自治議論スレ2019/07/22(月) 06:47:41.66ID:BgoZUtGU
ブルートフォースアタック
総当たり攻撃が多項式時間でおさまるならP=NP
グーグルが答えを出してるな

86ニュースソース検討中@自治議論スレ2019/07/22(月) 06:50:23.20ID:BgoZUtGU
>>76
事実上P=NPってことだろ
理論上はP≠NP

87ニュースソース検討中@自治議論スレ2019/07/22(月) 06:54:15.25ID:BgoZUtGU
解っていうのは、数字の入れ替えに過ぎないんで
ブルートフォースアタックが最強になるはず
これが現実世界では有限次数有限桁数なので総当たりが有限多項式に収まれば
事実上P=NP

88ニュースソース検討中@自治議論スレ2019/07/22(月) 07:08:47.08ID:BgoZUtGU
>>67
ムーアの法則により p=2^(y/1.5)
多項式時間がこれ以内におさまるならP=NP

89ニュースソース検討中@自治議論スレ2019/07/22(月) 07:31:51.15ID:7pKcTpuc
素数がでてくるパターンを誰か解き明かしてよ。

90ニュースソース検討中@自治議論スレ2019/07/22(月) 08:46:21.24ID:t5DL8WpM
>>15
無茶言うな

91ニュースソース検討中@自治議論スレ2019/07/22(月) 09:04:19.50ID:O07sqtvi
>>13
馬鹿は、存在証明が必ずしも構成的証明とは限らないことがわかってない、お前な

92ニュースソース検討中@自治議論スレ2019/07/22(月) 09:28:27.69ID:Got91E55
>>1
いやいや、多項式全部の式の証明って、難易度高杉。

93ニュースソース検討中@自治議論スレ2019/07/22(月) 12:15:07.17ID:r8GwrCRq
>>7
ノシ

94ニュースソース検討中@自治議論スレ2019/07/22(月) 12:50:10.09ID:dtmJF/UA
7payより安全なnpay

95ニュースソース検討中@自治議論スレ2019/07/22(月) 21:33:03.27ID:+ncoK7+I
解けても「思いのままに」は難しいな
発覚しないように少しづつチートマイニングを行って売りさばく
大手マイナーと結託すれば増やせる?

96ニュースソース検討中@自治議論スレ2019/07/22(月) 22:32:00.29ID:MCDRlGnf
仮性か真性かの違い。自慰可能は共通。

97ニュースソース検討中@自治議論スレ2019/07/22(月) 22:45:00.89ID:/Ny8GcXu
サマーウォーズのやつ?

98ニュースソース検討中@自治議論スレ2019/07/22(月) 22:57:26.07ID:Bh+IMe5q
これを考えない人が金を儲けている、ってことは分かってる

99ニュースソース検討中@自治議論スレ2019/07/22(月) 23:01:22.05ID:Vzeb6WmY
ビットコインは楕円関数曲線をガロア空間にぶち込んでんだろ?
単なる素因数分解じゃないだろ。

100ニュースソース検討中@自治議論スレ2019/07/22(月) 23:54:01.27ID:CeJ7OVru
ビットコインをビッコって訳したらだめって言われた

101ニュースソース検討中@自治議論スレ2019/07/23(火) 00:13:43.68ID:BcA1cdCW
サマーウォーズはじめました・☆☆☆

102ニュースソース検討中@自治議論スレ2019/07/23(火) 12:10:29.32ID:ZqXvfzfU
>>15
量子暗号にでもしなきゃ、その他の暗号は全部同じ扱いで解けるはず

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

103ニュースソース検討中@自治議論スレ2019/07/24(水) 03:20:20.81ID:ByqCfaHZ
解けたけど秘密にしとこ
これでビットコインはオレのもの

104ニュースソース検討中@自治議論スレ2019/07/24(水) 14:17:10.37ID:f5LP/+Ax
ぴー=んぴー 1〇ー=〇1〇ー

1 = 01

105ニュースソース検討中@自治議論スレ2019/07/25(木) 16:33:54.71ID:o5ZYtkgT
>>7
ノシ

106ニュースソース検討中@自治議論スレ2019/07/26(金) 00:26:00.01ID:FnEuOHa1
ビットコイン台帳のマスターキーは製作者の生年月日と星座

107ニュースソース検討中@自治議論スレ2019/07/26(金) 01:11:31.36ID:eNnGdzgu
P=NPであることと、具体的な問題に対して多項式時間で解ける
アルゴリズムを見つけることは別の話じゃないのか?

108ニュースソース検討中@自治議論スレ2019/07/26(金) 01:59:03.00ID:epu+AqUv
>>107
それはその通りなのだが、P=NPの場合には
NP完全問題のどれでも良いから1つについて多項式時間のアルゴリズムを見つけておけば
後は、その多項式時間アルゴリズムのあるNP完全問題に対して解きたいNP問題を多項式時間還元するだけで良い

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

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

109ニュースソース検討中@自治議論スレ2019/07/26(金) 02:15:57.72ID:fxcNnHDY
>>107
>>108
アホか
多項式時間ということは問題のサイズnに対してn^kの計算量(k>1)となるものでサイズが大きくなるにつれて膨大な計算量を必要とするものであり「既知の事象」
それゆえnを一定以上に大きくすることで事実上解くことができなくすることが可能で認証や暗号化に使える


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

110ニュースソース検討中@自治議論スレ2019/07/26(金) 10:20:20.93ID:jaqYtVDe
理論的にはP≠NPなんだよ
2次元なら、解はNxNの表の数字の入れ替えになる
これを多項式時間でやれるかという問題
最悪NxNかかるのでP≠NPなのさ
あとはD次元に拡張するだけ

111ニュースソース検討中@自治議論スレ2019/07/26(金) 10:32:39.66ID:z3kHtERU
>>110
多項式って2次式も3次式も4次式も多項式や。多項式でないってのは2^nとかのnの指数関数以上に増えるやつのこと。

112ニュースソース検討中@自治議論スレ2019/07/26(金) 11:01:49.65ID:tfQTuZl+
ロスアラモスって原爆のか

113ニュースソース検討中@自治議論スレ2019/07/26(金) 13:41:06.80ID:QDiF744N
>>109
話が伝わってないorz。P=NPが示されたからと言って具体的に解く手順を開発するのはまた別の苦労が
あるんじゃないの?という疑問だったんだが。
微分方程式の解の存在は証明されているからと言って実際に解くのは大変、みたいな。

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

114ニュースソース検討中@自治議論スレ2019/07/26(金) 13:55:31.92ID:/ZPnBYqE
ブラフだぞこれ

115ニュースソース検討中@自治議論スレ2019/07/26(金) 20:25:18.01ID:epu+AqUv
>>113
> P=NPの証明が、>>108のいうどれでもいいから1つのNP完全問題についての
> アルゴリズムの開発と同義なのかな?

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

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

116ニュースソース検討中@自治議論スレ2019/07/27(土) 04:11:26.80ID:u1Hna6U4
もうビットコインは中国人専用でエエわ…

117ニュースソース検討中@自治議論スレ2019/07/27(土) 15:45:20.20ID:nFH0TFRY
21兆円あったらゲームのプロデューサーやりたい
あとなんかイベントやりたい
花火大会で二尺玉あげたい

118ニュースソース検討中@自治議論スレ2019/07/27(土) 22:04:14.05ID:lOt1NnAE
>>117
そのぐらいなら21兆の1万分1で出来るだろw
ってか普通に頑張ればできると思うぞ

119オーバーテクナナシー2019/07/28(日) 10:09:05.79ID:TViHuOYe
ブロックチェーン/分散型台帳技術 [無断転載禁止]©2ch.net
http://rio2016.5ch.net/test/read.cgi/future/1476975355

120ニュースソース検討中@自治議論スレ2019/07/28(日) 15:20:32.35ID:1dmiGybK
ふーん、なるほどね

121ニュースソース検討中@自治議論スレ2019/07/28(日) 16:26:04.55ID:BCR2OOL0
ビビットコイン

122ニュースソース検討中@自治議論スレ2019/07/29(月) 16:28:27.09ID:V7P1oTtm
ビットコインがなくなるとブロックチェーンも無くなるは詭弁

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

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

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

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


>>1-9

123ニュースソース検討中@自治議論スレ2019/07/29(月) 16:28:57.65ID:V7P1oTtm
>>122


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

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

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

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

124ニュースソース検討中@自治議論スレ2019/07/29(月) 18:34:27.56ID:ZMauxfyJ
>>115

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

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

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

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

125ニュースソース検討中@自治議論スレ2019/07/30(火) 02:33:03.77ID:Eqyod5bO
>>124
君のレス中の>>115と>108とは逆じゃないの?

126ニュースソース検討中@自治議論スレ2019/07/31(水) 01:04:19.86ID:eLLQbbGM
ビットコインを盗むような犯罪を犯すより、大量に掘り起こせば良いのに

127ニュースソース検討中@自治議論スレ2019/08/03(土) 12:24:51.17ID:0Q530dEI
『ビットコインは安全資産ではない。
デジタルゴールドは過剰表現であり誇大広告』

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

128ニュースソース検討中@自治議論スレ2019/08/04(日) 12:44:24.85ID:dzUzana/
>>1
解いたらビットコインを盗めるって意味が分からない(・д・)

■ このスレッドは過去ログ倉庫に格納されています