P=NP

[0001 a4 ◆L1L.Ef50zuAv 2020/03/30(月) 21:55:08.58 ID:4sBnDtD8]

こんにちは。P=NPを肯定的に解いてみました。検証をお願いします。

巡回セールスマン問題をｎ次元格子に距離を保つよう配置してジグザグに解きます。
ノードを１つずつ増やすと最短経路は１つのエッジが消えて２つのエッジに変わります。
計算量は、1+2+3+…+n=n(n+1)/2=O(n^2)

[0002 １３２人目の素数さん 2020/03/30(月) 22:22:08.72 ID:zmYBSMz5]

まずｎ次元格子に距離を保つよう配置可能であることを示してよ

[0003 a4 ◆L1L.Ef50zuAv 2020/03/30(月) 22:57:11.25 ID:4sBnDtD8]

>>2
ご返信ありがとうございます。僕は寝てる時に夢で見たアルゴリズムを、
ちょっと考えて書いた後に書いたなんですよ。格子とは簡単に書いたんですが、
斜めではないくらいに考えてください。イメージとしては３点なら、最短経路は、

○ーーー
｜　　　｜
｜　　　○
｜　　　｜
ーー○ーー

こんな感じです。仰ることに対する証明は自明では無さそうですね。考える事に
しました。

length[i][j]^2=Σ(x[i][k]-x[j][k])^2 (1≦i≦n,1≦j≦n,1≦k≦n)
length[i][j]=length[j][i] (1≦i≦n,1≦j≦n)
x[1][k]=0(1≦k≦n)

とすると、線形代数で複素数も許せば？解けるんじゃないかと。１，１，３とか
変な三角形作れますしね。まだあらがあるかもしれません。

[0004 １３２人目の素数さん 2020/03/30(月) 23:23:58.45 ID:zmYBSMz5]

平面上の有限個の点(ユークリッド距離)にインスタンスを制限してもいいけど, それもNP困難だからね.
提案手法はまだ突っ込みどころが多い気がします.
(というかよく理解できません)
なお, P=NP 問題が(万が一)肯定的に解決されるなら, それはおそらく非構成的な証明になるだろうと思います.

[0005 a4 ◆L1L.Ef50zuAv 2020/03/30(月) 23:30:10.46 ID:4sBnDtD8]

一応、僕も全く適当にやっているという訳ではなく有名な「COMPUTERS AND
INTRACTABILITY A Guide to the Theory of NP-Completeness」くらいは英語で
読んだりしました。「平面上の有限個の点(ユークリッド距離)にインスタンスを制限」
が「NP困難」というのは僕は知りません。でも、「まだ突っ込みどころが多い」
くらいが専門家の判断であるならば、この手法で上手くいきそうなら、論文のような
ものを書いてみようと思います。

[0006 １３２人目の素数さん 2020/03/30(月) 23:39:29.63 ID:zmYBSMz5]

>>5
頑張ってください.
もし, 疑問点・確認したい点等ありましたら, お気軽に書き込んで下さい.
応援しています.

[0007 a4 ◆L1L.Ef50zuAv 2020/03/30(月) 23:42:26.48 ID:4sBnDtD8]

>>6
ありがとうございます。今日は一旦寝ます。

[0008 １３２人目の素数さん 2020/03/31(火) 00:53:51.77 ID:svglHhs4]

質問スレでやれ
単発スレ立てんなカス
死ね>>1

[0009 １３２人目の素数さん 2020/03/31(火) 03:08:50.02 ID:AEGXedru]

やすのりか？

[0010 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 12:56:35.36 ID:/0OHc4N+]

>>8
『わからない問題はここに書いてね』を最初は探したのですが見つからなかったですし、
他のスレでも流されちゃいそうなので、ここへ。数学板の他のスレも僕みたいにスレ
立ててるので。確かにP=NPが肯定的に証明できたら、死ねと言われるほどのことは
してるかもしれませんが、>>6さんのような方もいらっしゃるので、まだスレを
続けます。
>>9
自己紹介すると、本名は松本卓朗と申します。31歳男性です。統合失調症を患って
いて、障害年金生活なので、数学を研究する時間があります。

[0011 ID:1lEWVa2s 2020/03/31(火) 13:07:29.37 ID:NtSTCJsM]

P=NP問題って
素数方程式やフェルマーの最終定理
リーマン予想ゴールドバッハ予想の解を
ある完備された体で全部解ける
全てのディオファントス方程式の解の意味をみつけれるって問題だよ。

[0012 ID:1lEWVa2s 2020/03/31(火) 13:08:52.30 ID:NtSTCJsM]

書き込み禁止されてるけどこっそり。

[0013 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 13:13:13.89 ID:/0OHc4N+]

まず数式が間違ってました。２乗じゃなくて、絶対値ですね。

length[i][j]^2=Σ|x[i][k]-x[j][k]| (1≦i≦n,1≦j≦n,1≦k≦n)
length[i][j]=length[j][i] (1≦i≦n,1≦j≦n)
x[1][k]=0(1≦k≦n)

[0014 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 13:17:21.81 ID:/0OHc4N+]

>>11
>>12
こんにちは。お久しぶりです。簡単に言えばそういうことですね。比例ではなく、
多項式なので、まだ時間はかかるかもですが。

[0015 １３２人目の素数さん 2020/03/31(火) 13:19:37.18 ID:YIOqSIb4]

この問題を考えるんだったら基礎知識はつけといて欲しい
NP完全とかNP困難が何かわからないとかもう話にならない


巡回セールスマンとか一見取っつきやすいところに食いつくより
書籍なりWebなり読んでひととおり理解してから出直してくることを薦める

[0016 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 13:27:54.63 ID:/0OHc4N+]

>>15
勉強はしましたよ。忘れてるところはあるかもですが。NP-Complete Problemsの
に関して、
SATISFIABILITY→3SAT→3DM→PARTITION
　　　　　　　　　　　→VC→HC
　　　　　　　　　　　　　→CLIQUE
とかの証明は全部理解しました。

なんかおかしいと思うのは、僕が精神障害ってことなんですよ。皆がP!=NPに
賭けてる中、僕はP=NPであると宇宙人達から幻聴が聴こえてくるんです。それで
夢で証明の映像を見たら、それが正しいとまた幻聴が聴こえて妄想になってるん
です。どうして信じてるかと聞かれたら、量子脳理論で量子コンピュータが
出来てるんじゃないかと。

[0017 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 14:20:40.35 ID:/0OHc4N+]

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

[0018 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 14:22:11.53 ID:/0OHc4N+]

NP困難じゃなくて、NP完全ですね。

[0019 ID:1lEWVa2s 2020/03/31(火) 14:37:50.19 ID:UrUHbgPx]

あんま無理すると僕みたいに夢に強いホワイト製薬のもんすたぁがでてくるぞ。

[0020 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 14:43:51.21 ID:/0OHc4N+]

>>19
今は無理はそんなにしてないよ。１日１２時間くらい寝てるから。

[0021 ID:1lEWVa2s 2020/03/31(火) 14:45:09.61 ID:UrUHbgPx]

>>20
僕も12時間寝てる。
眠れなくても布団に入ってる。

[0022 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 14:47:16.35 ID:/0OHc4N+]

今、問題なのは、TSPの最短閉路に、もう１つノードを追加して最短閉路を考えた時、
１つのエッジが消えてそれがそのノードとの２つのエッジに変わる、という以外の
ものになるか？です。反例を探してます。

[0023 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 14:57:46.62 ID:/0OHc4N+]

反例のようなものが見つかりました。

正方形の紙の４つの頂点を考えます。すると、最短閉路は４のようになります。
√２離れた向こう側の頂点同士を３次元的にくっつけるように間にノードを入れると、
１＋０＋０＋１＋√２のようになります。

これで「このクソスレは終了しました」なんでしょうか？でも、テレパシーの指令
により、もうちょっと考えてスレを続けさせていただきます。

[0024 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 15:09:14.54 ID:/0OHc4N+]

まだ謎に思えるのは、この直交したジグザグ経路しか考えないTSP（以下、a4-TSP
と呼ぶことにする）を考えると、もう位置が決まっていて、正方形を３次元的に
くっつけたりしないんじゃないかと。もしこの反例のようなことするなら、最初から
近い位置にあるんじゃないか？と。でも、P=NPを証明しろ！と言われたら、まだ
わからないことだらけ。まだ研究を続けます。

[0025 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 15:18:17.21 ID:/0OHc4N+]

今、考えてるのは、グラフ構造のエッジの距離が、ｎ次元のものでもいいか？です。
やっぱり>>2さんが頭良いということですが、複素数などを考えず、単純にｎ次元の
ものでもNP完全になるかなどを考えてます。

[0026 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 15:28:33.92 ID:/0OHc4N+]

そういえば、懸賞金が入ったらどうするか？を妄想してますが、基本的に
量子コンピュータの開発費にしようと思ってます。これなら数学的な貢献で
いいんじゃないかと。

[0027 ID:1lEWVa2s 2020/03/31(火) 15:37:20.21 ID:u+SuL/Zv]

>>26
懸賞金はヘーベルハウスの家建てやあ。
但し童貞は守ること。

[0028 １３２人目の素数さん 2020/03/31(火) 15:39:15.76 ID:AEGXedru]

なんだやすのりじゃないのか
最近twitterでもP=NPを証明したって言ってるやつがいたからそいつかと思った

[0029 ID:1lEWVa2s 2020/03/31(火) 15:40:01.46 ID:u+SuL/Zv]

>>26
あと建築設計に数学があるんだけどみつけな。
私は知ってるけどひんとはださない。
僕は建築家目指してる。
事務所は我が家。
軍資金はぱそこん代。

[0030 ID:1lEWVa2s 2020/03/31(火) 15:43:29.14 ID:u+SuL/Zv]

僕怒ると暴走するんで黙ります。

[0031 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 15:46:42.65 ID:/0OHc4N+]

>>27
研究所みたいなのは建ててもいいかなと思ってる。ナマズの地震予知とかの研究に
特化したところ。童貞はまだ守ってるけど。

>>28
やすのりさんではないですね。最近はずっとa4って名前でやってます。

>>29
有限要素法とかだったら勉強したことあるよ。

[0032 ID:1lEWVa2s 2020/03/31(火) 15:51:45.48 ID:u+SuL/Zv]

>>31
>>29
%代数学ゆ産業。
%てぇじざんこくな。
(係数)
0.6’2+0.8’2=0.28’2=0.96’2
ひんとおわり。

[0033 ID:1lEWVa2s 2020/03/31(火) 15:53:16.71 ID:u+SuL/Zv]

ねりゅ。

[0034 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 15:54:28.69 ID:/0OHc4N+]

>>32
ちょっと難しいね。

[0035 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 15:54:54.48 ID:/0OHc4N+]

>>33
おやすみ。

[0036 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 16:12:23.19 ID:/0OHc4N+]

少しずつ考えてます。まず１，１，３の三角形は、x軸に３の辺を置くと、頂点は、
(0,0),(3,0)(3/2,√5i/2)で複素数なら解はありました。

[0037 a4 ◆L1L.Ef50zuAv 2020/03/31(火) 16:18:03.32 ID:/0OHc4N+]

じゃぁ、正方形の頂点をくっつけるようにするんじゃなくて、全てのノードを最初から
複素数で決めて置いて代入ソートのようにしていくと、正方形の頂点を構成した時点で
正方形ではなく、１＋０＋１＋√２、なんじゃないかと。