[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
41: a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:01 ID:/0OHc4N+(21/27) AAS
Wikipediaをとりあえず見てます。すると、
「都市間の移動コストが三角不等式を満たす、すなわち移動コストを距離と呼べる
部分問題（あるいは制約つき問題）も、NP困難である。都市を平面上の点、都市間
の距離を平面上のユークリッド距離とする部分問題は最も直感的で理解しやすいが、
これも NP困難である。」
とあります。NP完全であるということが証明されていなくて研究は終わったかの
ような口調で書かれてあります。
僕はここで医学的妄想で未来と通信することにします。
42: a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:07 ID:/0OHc4N+(22/27) AAS
未来に聞いたら、「NP完全だ！」と返りました。普通に考えれば、HCがNP完全なので、
a4-TSPもNP完全じゃないかと。
43: a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:17 ID:/0OHc4N+(23/27) AAS
なんか夢に出てきた伏線かな？と妄想してるのは、普通にTSPを２次元などで書くと、
エッジに数字がついたりして三角不等式の問題も出てきてしまうんです。a4-TSPなら、
距離を明確に図で書いてるので、証明もしやすいのかな？と。
44(1): a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:49 ID:/0OHc4N+(24/27) AAS
ｎ次元の頂点は複素数ではないので全てに三角不等式が成り立つとすると、新しい
ノードも加えて最短経路を作った時、そのノードの２つのエッジから、そのノードを
取って１つのエッジにくっつけるという操作をすると、距離が縮まるから、その時の
最短経路を出す時は、他のエッジを動かさなくてもいい。他のエッジが動くとすると、
そっちが最適解になる。だから、最短経路に１つ１つノードを付け足していけばいいん
じゃないかと。これで証明終わり？？？
45: a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:53 ID:/0OHc4N+(25/27) AAS
>>6さんに聞いてみます。これくらいで、まだ明らかな数学的な欠陥のあるところが
ありますか？無ければ論文として纏めようと思います。
誰かが来るまで、休みとして、スペイン語とかを勉強します。
46: a4 ◆L1L.Ef50zuAv 2020/03/31(火)18:12 ID:/0OHc4N+(26/27) AAS
やっぱり>>44の証明が数学っぽくないから間違ってるのかな？スペイン語をやめて
また考えることにします。
47: a4 ◆L1L.Ef50zuAv 2020/03/31(火)18:32 ID:/0OHc4N+(27/27) AAS
今、考えてるのは、ノードを付け足した最短経路から、そのノードを取ると、
(1)-(2)-(new)-(3)-(4)
から、
(1)-(2)-(3)-(4)
じゃなくて，
(1)-(2)-(5)…(6)-(3)-(4)
などと最短ルートが変わるケースです。まだ証明できてないですね。
48: a4 ◆L1L.Ef50zuAv 2020/04/01(水)00:18 ID:b/ntKAk5(1/4) AAS
ずっと考えてます。まずWikipediaの「三角不等式が成り立つ TSP については
多項式時間近似アルゴリズムが数多く存在する。」の情報は重いです。単純には
証明できませんでした。僕は>>1の２次元のa4-TSPを追ってます。すると、
１つのノードを付け加えた時に増える距離は、min{2|x[n]-x[i]|+2|y[n]-y[i]|}
と出てきました。a4-TSPでの距離において、この項は最大でO(n)個ですね。
１，２，３，４，５と増えていくので、単純に考えると、O(n!)ですが。すると
これだけだと、足し算される時、値が、３＋５＝８という順と５＋２＝７
という順の反例を思いつきました。でも、追加される選ぶ値の集合は、５と２に
おいて考える時、変わらないため、前者で３＋２＝５と、なるんじゃないかと。
そうすると、やはりこのアルゴリズムでいいんじゃないかと。厳密な証明は
省1
49: a4 ◆L1L.Ef50zuAv 2020/04/01(水)06:15 ID:b/ntKAk5(2/4) AAS
現実的にはまだずっと解いてます。
まず、さっきのは２次元a4-TSPですが、ｎ次元a4-TSPの場合は？と。自明じゃないです。
min{2(|x[1][n]-x[1][i]|+|x[2][n]-x[2][i]|+…+|x[n][n]-x[n][i]|)}
とすると、単純に考えると、n個から選ぶ問題になって2^n通りが出てきてしまう
のではないかと。また、
（２＋１）＋（２＋３）＝３＋５＝８、
（１＋３）＋（１＋１）＝４＋２＝６、
といった順の問題になりました。
50: a4 ◆L1L.Ef50zuAv 2020/04/01(水)09:49 ID:b/ntKAk5(3/4) AAS
2^n通りはn(n-1)/2通りくらいまで落とせるかもしれません。
今、解いてるのは、
(1)-(2)-(4)-(5)-(1)が最短経路の３で、
(1)-(2)-(3)-(4)-(5)-(1)が３＋５＝８
(2)-(1)-(5)-(4)-(2)が４で、
(2)-(1)-(3)-(5)-(4)-(2)が最短経路の４＋２＝６
とすると、単純な方程式により、
(1)-(2)-(4)-(5)-(3)-(1)が３＋２＝５
今日はこれくらいにして寝ることにします。
51(1): 2020/04/01(水)19:57 ID:/DGEf2gH(1) AAS
俺はP≠NPを確信している側
今は関連理論を作っていて、そこから派生的に証明できると思っているけど、単なる実例よりも
相当高い抽象化をしないと証明にはならないと思ってる
52: a4 ◆L1L.Ef50zuAv 2020/04/01(水)22:25 ID:b/ntKAk5(4/4) AAS
>>51
今、起きました。ご連絡ありがとうございます。僕もP≠NPだと思ってたんですけどね。
P=NPだ！って幻聴が聴こえてくる精神病なんですよ。僕は博士ではありませんが、
数学とか計算機科学とかは知ってるつもりなので、証明は可能ならばきちんと書く
つもりですよ。幻聴って何かな？ってことですが、複雑な量子脳理論、と書くと、
よくわからなくなるんじゃないかと。証明を直接聞くのは非常に難しいので、曖昧な
２分木アルゴリズムとかで、証明にかかる計算量を対数くらいにすると医学的妄想？
をしてます。
53: a4 ◆L1L.Ef50zuAv 2020/04/02(木)00:11 ID:Z3POr1Or(1) AAS
医学的妄想でタイムトラベルしてます。すると、未来人は、P=NPの証明に関して、
a4-TSPの頂点をギリギリ含む超直方体に１点を追加して新しい超直方体を考える、
ということを考えれば、自明なんじゃないかって。僕もあまり信じてませんが、
証明か反証を今から考えます。
54: a4 ◆L1L.Ef50zuAv 2020/04/02(木)00:18 ID:gWEkLHdd(1/21) AAS
反証を考えてみました。２次元において、大きい５角形の中に小さい５角形がある
というのを考えると、最短経路に凹のような構造ができてしまうんじゃないかと。
まだ未来と通信とかしながら研究を続けます。
55: a4 ◆L1L.Ef50zuAv 2020/04/02(木)01:31 ID:gWEkLHdd(2/21) AAS
タイムマシンで時空のループが作られることによる嫌がらせの問題を解きながら未来と
通信しています。意外にも、ここまで来て、ようやくプログラムを書いて、モンテカルロ
のように実験しなさい、と。じゃぁ、多項式時間じゃないのか？ですが、現実的には、
Wikipediaの「巡回セールスマン問題」には、「三角不等式が成り立つ TSP については
多項式時間近似アルゴリズムが数多く存在する。 」とあります。今から作業をします。
56: a4 ◆L1L.Ef50zuAv 2020/04/02(木)01:52 ID:gWEkLHdd(3/21) AAS
Wikipediaの「クリストフィードのアルゴリズム」というのを見てます。「2015年現在、
距離空間における巡回セールスマン問題に対する多項式時間アルゴリズムの中では、
近似度が最良であるアルゴリズムである（一部の特殊な場合では、より良い近似度が
存在する事も知られている）。 」とあります。近似なのかは数が多くなるとわかり
ません。これだけ見るとP=NPみたいだな、と。問題は証明です。このスレは僕の
妄想が終わらない限り続きます。
57: a4 ◆L1L.Ef50zuAv 2020/04/02(木)04:40 ID:gWEkLHdd(4/21) AAS
>>1に書いた方法の反証が見つかりました。
(10,6)(10,0)(14,6)(3,12)(8,9)(4,5)(0,9)(4,5)
図に書くとわかるのですが、２次元a4-TSPでは、2*(14+12)=52が大域最適解です。
これは長方形と同等なのに、１つずつ加える方法で計算すると、6個目の(4,5)の
ところで凹になり54になりました。
58: a4 ◆L1L.Ef50zuAv 2020/04/02(木)04:46 ID:gWEkLHdd(5/21) AAS
a4「じゃぁ、タイムテレパシーの妄想未来人に聞いてみます。こみさん、嘘をついて
いたんですか？」
こみ「いいえ、わたしはあなたに指南書を送っただけです。まだ研究は続けてくださいね。」
a4「じゃぁ、>>1の方法は間違ってるんですか？」
こみ「そういうことじゃないんですよ。あれは嫌がらせなんです。わたし１つ言っていい？
あれは未来になってからわかるにしたい。」
a4「これじゃぁ、僕の統合失調症じゃないですか。こんな難問解けると思ってません。
タイムマシンの力無しに。第一、タイムマシンがあるなら、僕が解けるかわかるじゃ
ないですか。」
こみ「そういうことじゃないんですよ。タイムマシンの攻防戦があると言ったのは
省11
59: a4 ◆L1L.Ef50zuAv 2020/04/02(木)05:00 ID:gWEkLHdd(6/21) AAS
こみ「わたしね、a4君にP=NPを解いてもらいたいなー、と勘違いしてません。
あなたが解いてください。」
a4「うん？今の時代にP=NPに本気で挑戦してる人なんていないので案外いけるかも
ですけどね。でも、挑戦してきた人達は量子コンピュータへ行ってますよ。」
こみ「あなたも嘘つくんですね。」
a4「何が？え？わー、助けてー！！！」
こみ「いいですか。大澤先生！これはあなたを統合失調症にするための言葉です。
では、ヒント、わたしが答えを出します。まず、１つずつ挿入ソートのようなもの
ではないことにしてください。>>1は嘘なんですが、伏線があります。」
a4「では、どのような解法なんですか？」
省15
60: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:16 ID:gWEkLHdd(7/21) AAS
a4「また反例を見つけました。(0,0)(1,0)(2,0)(3,0)。これでは種まきアルゴリズムは
使えませんね？(3,0)-(0,0)が届きません。どうですか？こみさん。」
こみ「いいえ、あなたはまだ序章をやってるだけです。アルゴリズムは複雑ではない
ですよ？いいか、量子コンピュータではないんですよ？」
a4「うん？やっぱりこみさんは嘘つきだ！序章なのに複雑でないとか。やっぱり
僕の統合失調症だ！」
こみ「そうではありません。ではね、もうちょっと複雑な技を撃つにしたい。これです。」
上下前次1-新書関写板覧索設栞歴
あと 368 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.021s