[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
74: a4 ◆L1L.Ef50zuAv 2020/04/02(木)12:32:58.73 ID:gWEkLHdd(21/21) AAS
英語で書くと、読める人はこの板だとまだ多いかもしれませんが、日本の掲示板なので、
僕が和訳することにしました。障害年金を受給しているので、このような形で社会貢献
です。
まず、path-TSP、すなわち、最初の出発点が決まらず、尚且つ、出発点に戻らなくても
いい場合は、NP-completeであると書かれてあります。証明は、一般的なものが論文には
勿論書かれてありますが、個人的な具体例を示します。tour-TSP、すなわち、普通の
TSPの問題をpath-TSPに変換して解けることを示します。平面に正五角形を書いて、
１点を２つにして、それぞれ上下へ大きく動かして適当に長さを設定します。すると、
これにおけるpath-TSPはこの２点が端点のものに大域最適のものがあります。それで
上下にあったものを元の位置の１点に置きます。これで元の問題が解けました。
省1
244: a4 ◆L1L.Ef50zuAv 2020/06/28(日)03:47:12.73 ID:5O9VhwHH(1) AAS
小説の話で数学板的には申し訳ないのですが、ずっとバックで流れるクシコス・ポスト
の音楽を聴きながら妄想して宇宙人から受信してます。
この小説は未来への伏線なのでしょう。例えば
>>大仁君は「ひできくんがすうじたいとひらがなたい
>>やればいいんじゃないの？ぼく、やだ。ひかるくんのあたまたたくなんて」一君は「ずらかるぞ」
>>と。大仁君が一君を裏切って光君に話しかけてきた。「素因数分解って何？」って。
>>光君は「かけざんの右と左がちがう」と。大仁君は「よくわかんなーい」と。
ここはまだ草稿してる最中ですが、未来はたぶん、
大仁君は「秀樹君が量子翻訳すればいいんじゃないの？俺、嫌だ。光君の頭を撃つなんて。」
一君は「ずらかるぞ」と。大仁君が一君を裏切って光君に話しかけてきた。
省2
294: a4 ◆L1L.Ef50zuAv 2021/03/12(金)11:07:51.73 ID:zCsn/dGn(10/13) AAS
a4「西暦2503年から未来人を呼びます。」
こみ「はい、わたしも嘘つきです。」
a4「P=NPはどうやったら解けるんですか？」
こみ「いやだなー、それは未来解けるに決まってるじゃないですか。」
a4「宇宙人と話しができるんですか？」
こみ「大橋先生！はい、統合失調症。」
403: a4 2022/03/11(金)03:53:26.73 ID:I5riZk2N(1) AAS
>>402
例えばTSPを出してみましょうか。10000個の家をどういうルートで行ったら最短か？
という問題の計算時間とかわかりますか？10000!でNPですよ。これが多項式(P)
なら、P=NPです。だから答えをタイムマシンで持ってくるという話をしてます。
それで数学者に聞いてるんですが、
"QUANTUM COMPUTING SINCE DEMOCRITUS"という2013年の本に
"Chapter 11 offers a critical examination of ideas of Sir Roger
Penrose, who famously holds that the brain is not merely a quantum computer
but quantum gravitational computer, able to solve Turing-uncomputable problems"
と書いてあり、これを計算できるコンピュータの定義が昔からありそうだというところで
省1
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.016s