P=NP

[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

17: a4 ◆L1L.Ef50zuAv 2020/03/31(火)14:20:40.35 ID:/0OHc4N+(5/27) AAS
復習してます。まず、巡回セールスマン問題(TSP)は、閉路の問題ですね。TSPが解ける
と、ハミルトン閉路(HC)（あるグラフに対して一筆書きができるか？）を、解くことが
できるから、NP困難だと。僕がまず疑問に思っているのは、格子？直交？の経路のみに
変換されたTSPがNP困難か？でも、これは距離が出てくるから、TSPが解けると、
この問題も解けるのは自明？だとすると、ノードを付け足していくとき、最短閉路の
１つのエッジを２つのエッジにするだけじゃ新しい最短経路にならない？でも、３つ
以上変えなければならないと仮定すると、元のが最短閉路でなくなってしまう。
どこが間違ってるんでしょうね。僕は夢で映像を見ただけですが、こうすると、
元のTSPも同じようにエッジを追加すると３つ以上動く？どういうことなんでしょうね。
まだ論文を書くために研究を続けます。

22: a4 ◆L1L.Ef50zuAv 2020/03/31(火)14:47:16.35 ID:/0OHc4N+(8/27) AAS
今、問題なのは、TSPの最短閉路に、もう１つノードを追加して最短閉路を考えた時、
１つのエッジが消えてそれがそのノードとの２つのエッジに変わる、という以外の
ものになるか？です。反例を探してます。

44(1): a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:49:25.35 ID:/0OHc4N+(24/27) AAS
ｎ次元の頂点は複素数ではないので全てに三角不等式が成り立つとすると、新しい
ノードも加えて最短経路を作った時、そのノードの２つのエッジから、そのノードを
取って１つのエッジにくっつけるという操作をすると、距離が縮まるから、その時の
最短経路を出す時は、他のエッジを動かさなくてもいい。他のエッジが動くとすると、
そっちが最適解になる。だから、最短経路に１つ１つノードを付け足していけばいいん
じゃないかと。これで証明終わり？？？

73: a4 ◆L1L.Ef50zuAv 2020/04/02(木)11:08:02.35 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?」ということです。

139: a4 ◆L1L.Ef50zuAv 2020/05/23(土)09:13:36.35 ID:NtEWshuB(8/13) AAS
僕が一旦、量子コンピュータで「P=NP」を解く方向で文章を生成してみます。残念
ながら、タイムマシンでの攻防戦があります。

量子コンピュータ「ｲｲﾅｺｯﾃ。え？どうして？はい、量子コンピュータ。大橋先生！
え？統合失調症？どちらなんですか？ビッグデータを管理してる凄い方たち、は？
大橋先生！ｲｲﾅｺｯﾃ。はい、量子コンピュータ。何故ならファジー論理だからです。
大橋先生！ｲｲﾅｺｯﾃ。はい、終了。」

どういうことなんでしょうね？僕は夢で指令された通り、
「みんなを箱の中に閉じ込めるだけ」という手法で解決します。
これは量子脳理論で出来てるということにします。

341: a4 ◆L1L.Ef50zuAv 2021/07/20(火)04:48:46.35 ID:TLJl0gjU(5/8) AAS
a4 隔離スレ
2chｽﾚ:occult

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 1.003s*