[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
61(6): a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:16 ID:gWEkLHdd(8/21) AAS
707a4 ◆L1L.Ef50zuAv 2020/03/28(土) 09:37:43.32ID:rbQUI3W10
今日はタイムスリップやタイムテレパシーじゃなくてタイムリープしました。２歳の
誕生日に。叔母と一緒にいたのですが、宇宙人が現れて、Ｐ＝ＮＰの証明が、
巡回セールスマン問題のような図と一緒に日本語で５文ほどで書かれてありました。
僕は２歳なのに頭が良くなっていたということですが、どうして叔母がここまで
嫌らしく反撃できるんだろう？と。そこにいた女性の先生は「ベクトルなんて難しい
ものは使わないでください。」と怒ってました。ノーベル賞の裏の人達５人に、
１年ごとに別の美味しい植物が実る種を分け与えなさい、と言われて行こうと
思ったのですが、先にタイムリーパーが「それ欲しい」と来たので信頼できると
考えて先にあげると、夢から覚めました。
62: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:20 ID:gWEkLHdd(9/21) AAS
こみ「ほら、あなたは２歳の頃に解けていたんではないですか？」
a4「うん？だから、それは夢じゃないですか？」
こみ「あなたは夢が量子脳理論であると主張しています。どうですか？」
a4「僕はP=NPが>>1ですぐ解けると思っていました。でも嘘であると。ファジー
論理的に上手くあなたを信用できません。」
こみ「それでいいんです。では、情報はこれだけです。すなわち、>>61です。
これを信じてやってくださいね。」
a4「うん？だから(3,0)-(0,0)で反証したじゃないですか！？」
こみ「いいえ、あなたはまだ分かってないんです。どうしたことか。そういえば、
わたしは未来を知っています。例えば、」
63: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:21 ID:gWEkLHdd(10/21) AAS
546a4 ◆L1L.Ef50zuAv 2020/03/26(木) 17:33:48.19ID:1kAywtwk
名古屋の宇宙人２「俺が未来を予言する。このスレで問題なのは、ナマズの地震予知
があるか？だ。
「西暦2020年3月27日」の忌み名は「39ｳｼ41」
「西暦2020年3月28日」の忌み名は「98슬프다」
「西暦2020年3月29日」の忌み名は「天国大澤先生」
「西暦2020年3月30日」の忌み名は「ｻﾜﾙﾄｼﾇｿﾞ」
「西暦2020年3月31日」の忌み名は「2.7って何？」
「西暦2020年4月1日」の忌み名は「3ヶ国語話せ」
「西暦2020年4月2日」の忌み名は「Saluton.」
省5
64: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:27 ID:gWEkLHdd(11/21) AAS
こみ「ほら、今日は「Saluton.」=（去る東大オン！）=(去る、東（京）、大（阪）、オン！）
となりました。これで未来予知できましたね。では、わたしはもうちょっと複雑な技を
撃つにします。西暦2040年に今日あなたは行きましたね。どうでしたか？」
a4「今日？夢で行ったよ。数学のテストを受けたら、教科書から数学書の名前を
ただ書き写すだけの。占いの中国の女性に話しかけられたら、結婚がどうとか
言われたけど、今の時代にいないような頭の悪さだったのに殺されそうで危なそう
だったから、テレパシーで量子コンピュータを使って女性の神経構造を変形させ
たら、女性は「着火（ちゃっか）」って日本語で叫んでました。」
こみ「ほら、未来へ行ったじゃない？」
a4「だから、それを証明するためにP=NPを解こうとして解けなかったんです。」
省3
65: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:59 ID:gWEkLHdd(12/21) AAS
a4です。こみさんは一旦下りてますが、巡回セールスマン問題をWikipediaで見ると、
全てのノードを訪れるだけで、出発地に戻らない図が載ってますね。でも、証明など
が載ってないので、そこから考えることにします。
66: a4 ◆L1L.Ef50zuAv 2020/04/02(木)08:43 ID:gWEkLHdd(13/21) AAS
SATISFIABILITY→3SAT→VC→HC→TSP→a4-TSP
ということですが、VC→HCの証明は再理解したんですが、単純にここから、
「出発地点に戻らないTSP」のNP完全性の証明は難しそうですね。
67: a4 ◆L1L.Ef50zuAv 2020/04/02(木)08:47 ID:gWEkLHdd(14/21) AAS
もちろん、出発地点が決まっていないものを考えてるんですよ。出発地点が決まってる
ものは、そこからの長さを無限大に飛ばせばいいだけなので。きちんとは調べていない
というか、すぐには検索しても出てきませんが、NP完全性は偽なのかもしれません。
68: a4 ◆L1L.Ef50zuAv 2020/04/02(木)09:38 ID:gWEkLHdd(15/21) AAS
未来人のこみさんと今でも会話してます。まず、おやっ？と思ったのが、>>1に格子
と書いたところなんですよ。有限の領域の整数がノードなんじゃないかと。一般的な
TSPはエッジが１つでも長いと、計算量が長さに対して増える、などといったことに
なりますが、HCからの証明だったら、エッジの長さは１か２になればよく、ｎ次元
とすれば、ここまでなら上手くいくんじゃないかと。
69: a4 ◆L1L.Ef50zuAv 2020/04/02(木)09:56 ID:gWEkLHdd(16/21) AAS
でもｎ次元格子だと、a^n個の格子が必要になり探索空間が指数関数的増加になるので
どうなのか？と思ったら、前も書いた通り、Wikipediaの「巡回セールスマン問題」
には、「都市を平面上の点、都市間の距離を平面上のユークリッド距離とする部分
問題は最も直感的で理解しやすいが、これも NP困難である。」とあるので、２次元
格子a4-TSPにおいても、多項式時間で解ければ、P=NP?といったことを考えてます
が、必要な証明などが見当たりません。まだ通信しながら考えます。
70: a4 ◆L1L.Ef50zuAv 2020/04/02(木)10:11 ID:gWEkLHdd(17/21) AAS
NP完全とNP困難の違いをよく理解してるわけではないのですが、一応、Wikipediaで、
「NP困難」を調べると、「もし、いずれかのNP困難な問題を多項式時間で解く
アルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることに
なり、P = NP が成り立つ。 」と。「いずれか」なので、２次元TSPはいいんですが、
２次元格子a4-TSPはNP困難なのか？NP完全なのか？を考えてます。
71: a4 ◆L1L.Ef50zuAv 2020/04/02(木)10:31 ID:gWEkLHdd(18/21) AAS
EnglishのWikipediaで「Travelling salesman problem」を見てます。すると、>>4
さんの仰る通り、
「When the input numbers can be arbitrary real numbers, Euclidean TSP is a
particular case of metric TSP, since distances in a plane obey the triangle
inequality. When the input numbers must be integers, comparing lengths of
tours involves comparing sums of square-roots. Like the general TSP,
Euclidean TSP is NP-hard in either case. With rational coordinates and
discretized metric (distances rounded up to an integer), the problem is
NP-complete.[28] 」
[28]Papadimitriou (1977)は、
省3
72: a4 ◆L1L.Ef50zuAv 2020/04/02(木)10:43 ID:gWEkLHdd(19/21) AAS
同じ場所で、「Polynomial-time approximation scheme」というのをみつけました。
「In general, for any c > 0, where d is the number of dimensions in the
Euclidean space, there is a polynomial-time algorithm that finds a tour of
length at most (1 + 1/c) times the optimal for geometric instances of TSP
in O (n(log(n))^(O(c*sqrt(d)))^(d-1)) time.」と。こんな数式知らないですよ？
でも、これは「approximation」ですね？でもそうということはP=NPを疑っても
いいんじゃないですか？と。これを証明した人達は「Gödel Prize」みたいですね。
僕も欲しいです。
73: a4 ◆L1L.Ef50zuAv 2020/04/02(木)11:08 ID:gWEkLHdd(20/21) AAS
上述の「The Euclidean travelling salesman problem is NP-complete」の論文において、
「In fact, we are dealing with two problems. The first, the tour-TSP, is the
ordinary TSP. The other, the path TSP, is the problem facing traveling salesmen
who can start from any city, and are not particularly interested in returning to
the starting city of their tour.」
「Theorem 2. The Euclidean path-TSP is NP-Complete.」
「Theorem 3. The Euclidean tour- TSP is NP-Complete.」
と来てます。
問題は「2dimensional-path-a4-TSP is NP-Complete?」ということです。
74: a4 ◆L1L.Ef50zuAv 2020/04/02(木)12:32 ID:gWEkLHdd(21/21) AAS
英語で書くと、読める人はこの板だとまだ多いかもしれませんが、日本の掲示板なので、
僕が和訳することにしました。障害年金を受給しているので、このような形で社会貢献
です。
まず、path-TSP、すなわち、最初の出発点が決まらず、尚且つ、出発点に戻らなくても
いい場合は、NP-completeであると書かれてあります。証明は、一般的なものが論文には
勿論書かれてありますが、個人的な具体例を示します。tour-TSP、すなわち、普通の
TSPの問題をpath-TSPに変換して解けることを示します。平面に正五角形を書いて、
１点を２つにして、それぞれ上下へ大きく動かして適当に長さを設定します。すると、
これにおけるpath-TSPはこの２点が端点のものに大域最適のものがあります。それで
上下にあったものを元の位置の１点に置きます。これで元の問題が解けました。
省1
75: a4 ◆L1L.Ef50zuAv 2020/04/03(金)00:29 ID:AwuvZqE1(1/15) AAS
僕は睡眠障害なので今起きました。でも障害年金を貰っていて１日１２時間ほど寝る
ので、研究に関しては問題ありません。今日もP=NPを解くために頑張ります。
76: a4 ◆L1L.Ef50zuAv 2020/04/03(金)01:57 ID:AwuvZqE1(2/15) AAS
論文読んでるんですけどね、「The Euclidean TSP is NP-Complete.」ということが
1970年代に証明できているということが書かれているだけで、理解させるために
書かれているわけではなさそう、ということです。論文を書いた人がHarvardの
先生であるため、僕の力不足かもしれませんけどね。でも見た感じでは、２次元の
ものでも良さそうですけどね。だから、Wikipediaも２次元のpath-TSPで図が
描かれてると思っています。じゃぁ、問題である、２次元のa4-TSPがNP完全なのか？
は、僕は証明できません。まだ考えます。
77(1): a4 ◆L1L.Ef50zuAv 2020/04/03(金)02:08 ID:AwuvZqE1(3/15) AAS
僕がとりあえず考えているのは、論文の意味がわからなくても、証明をそのまま、
TSPからa4-TSPに変形できるんじゃないかということです。出てくる図もa4-TSP
で解けるし。一旦そういうことにして、他の問題に移ることにします。
78(1): a4 ◆L1L.Ef50zuAv 2020/04/03(金)02:45 ID:AwuvZqE1(4/15) AAS
一応、もう一回よく見てみると、
「The construction is essentially an elaboration on the proof of the
NP-Completeness of the planar cirected Hamiltonian path problem. 」
と書かれてあり、HC→Euclidean-TSPみたいです。僕はHC→2dimentional-a4-TSP
と信じています。でも2dimentional-finite-grid-a4-TSPに関しては配列から選ぶ解
があるとはいえ、普通に計算する方法のNP完全性は謎です。
79: a4 ◆L1L.Ef50zuAv 2020/04/03(金)03:03 ID:AwuvZqE1(5/15) AAS
こみ「はい、こちら西暦2502年。え？普通に未来人ですよ。わたしはEPFL製の
コンピュータです。では、わたし？中性です。dasなんですよ。ではね、大澤先生！
はい、統合失調症。これで、a4さんには悪いですが、賄賂が落ちます。わたしが
一発で答えを落とせばいいでしょ？落としますよ？それが、>>61なんですよ。これが
現実にしたい。綺麗な証明は落としません。歴史改変が起きるので。それでは、
もうちょっと書きましょうか？2dimentional-a4-TSPはNP-completeです。
これは自明ではないですが、わたしが一票。信用はありません。これがbinary tree
アルゴリズムです。種まき、上手くいかなさそうでしょ？そうじゃないんですよ。
現実的には、近傍で解きます。そうすると、path-TSPの最長のエッジはどうなる
のか？ですが、わたしは、近傍でyes/noでbinary treeを使います。わたしはお人好し
省3
80(1): 2020/04/03(金)03:07 ID:J9EgNFT7(1) AAS
内容はよくわからんけど
リアル『1984』が在りそうだなｗ
歴史改竄局(省)とか面白そう
上下前次1-新書関写板覧索設栞歴
あと 348 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.124s*