[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
311: a4 ◆L1L.Ef50zuAv 2021/05/04(火)19:44 ID:JsFpfDjr(1/6) AAS
a4「メールに返信は無いですね。」
名古屋の宇宙人２「そうか。１回、計算してみよ。」
a4「何かが間違ってる気がします。」
名古屋の宇宙人２「それじゃさ、すまん、１回、１番簡単なのだけ計算してくれ。
折り紙を半分に切って、片方をもう半分に切る。これだけだ。」
a4「それで２の３乗通りで表にしたり裏にしたりで普通に半分半分になる答えを
巡回セールスマン問題で表せばいいんですね。今日は眠いので時間かかるかも
ですが、僕の宿題にします。」
名古屋の宇宙人２「やってみよ。」
312: a4 ◆L1L.Ef50zuAv 2021/05/04(火)20:38 ID:JsFpfDjr(2/6) AAS
a4「研究してるんですけど、アセンブリ言語と非決定性チューリングマシンの対応
がよくわからないうえに、クックの定理も自明なようで込み入ってます。僕の研究
には何かが足りません。どうしたらいいんですか？」
名古屋の宇宙人２「現実的に言っていい？全部軍事機密だから。」
a4「まだやるんですか？」
名古屋の宇宙人２「あたぼうよ。」
a4「うーん。」
313: a4 ◆L1L.Ef50zuAv 2021/05/04(火)20:44 ID:JsFpfDjr(3/6) AAS
a4「まず出た答えは、プログラミングの仕方で、いろんなTSPができることです。」
名古屋の宇宙人２「そうか。こりゃ選び方があるな。いいか？短いものを出す
ようにしろ。」
a4「まだやるんですね。」
名古屋の宇宙人２「君、俺を何だと思ってる？」
a4「嘘つき宇宙人。」
名古屋の宇宙人２「そうか。早めに仕事しろよ。」
314: a4 ◆L1L.Ef50zuAv 2021/05/04(火)20:52 ID:JsFpfDjr(4/6) AAS
名古屋の宇宙人２「俺の明暗。SUBSET SUMから直接TSPに変換してみて。君なら
できる。」
a4「うん？」
315: a4 ◆L1L.Ef50zuAv 2021/05/04(火)21:00 ID:JsFpfDjr(5/6) AAS
a4「SUBSET SUMは普通O(2^n)ですが、TSPはO(n!)でもヘルドカープのアルゴリズム
は、O((2^n)*(n^2))と書かれてますね。」
名古屋の宇宙人２「そうだな。」
316: a4 ◆L1L.Ef50zuAv 2021/05/04(火)21:52 ID:JsFpfDjr(6/6) AAS
a4「やっぱりこんな簡単なアイデアでは、解けてる人がいないことが解けないことの
証明になってますね。」
名古屋の宇宙人２「今日は寝なさい。」
a4「おやすみ。」
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.938s*