[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
1(14): a4 ◆L1L.Ef50zuAv 2020/03/30(月)21:55 ID:4sBnDtD8(1/4) AAS
こんにちは。P=NPを肯定的に解いてみました。検証をお願いします。
巡回セールスマン問題をｎ次元格子に距離を保つよう配置してジグザグに解きます。
ノードを１つずつ増やすと最短経路は１つのエッジが消えて２つのエッジに変わります。
計算量は、1+2+3+…+n=n(n+1)/2=O(n^2)
2(3): 2020/03/30(月)22:22 ID:zmYBSMz5(1/3) AAS
まずｎ次元格子に距離を保つよう配置可能であることを示してよ
3(1): a4 ◆L1L.Ef50zuAv 2020/03/30(月)22:57 ID:4sBnDtD8(2/4) AAS
AA省
4(2): 2020/03/30(月)23:23 ID:zmYBSMz5(2/3) AAS
平面上の有限個の点(ユークリッド距離)にインスタンスを制限してもいいけど, それもNP困難だからね.
提案手法はまだ突っ込みどころが多い気がします.
(というかよく理解できません)
なお, P=NP 問題が(万が一)肯定的に解決されるなら, それはおそらく非構成的な証明になるだろうと思います.
5(1): a4 ◆L1L.Ef50zuAv 2020/03/30(月)23:30 ID:4sBnDtD8(3/4) AAS
一応、僕も全く適当にやっているという訳ではなく有名な「COMPUTERS AND
INTRACTABILITY A Guide to the Theory of NP-Completeness」くらいは英語で
読んだりしました。「平面上の有限個の点(ユークリッド距離)にインスタンスを制限」
が「NP困難」というのは僕は知りません。でも、「まだ突っ込みどころが多い」
くらいが専門家の判断であるならば、この手法で上手くいきそうなら、論文のような
ものを書いてみようと思います。
6(5): 2020/03/30(月)23:39 ID:zmYBSMz5(3/3) AAS
>>5
頑張ってください.
もし, 疑問点・確認したい点等ありましたら, お気軽に書き込んで下さい.
応援しています.
7: a4 ◆L1L.Ef50zuAv 2020/03/30(月)23:42 ID:4sBnDtD8(4/4) AAS
>>6
ありがとうございます。今日は一旦寝ます。
8(1): 2020/03/31(火)00:53 ID:svglHhs4(1) AAS
質問スレでやれ
単発スレ立てんなカス
死ね>>1
9(1): 2020/03/31(火)03:08 ID:AEGXedru(1/2) AAS
やすのりか？
10: a4 ◆L1L.Ef50zuAv 2020/03/31(火)12:56 ID:/0OHc4N+(1/27) AAS
>>8
『わからない問題はここに書いてね』を最初は探したのですが見つからなかったですし、
他のスレでも流されちゃいそうなので、ここへ。数学板の他のスレも僕みたいにスレ
立ててるので。確かにP=NPが肯定的に証明できたら、死ねと言われるほどのことは
してるかもしれませんが、>>6さんのような方もいらっしゃるので、まだスレを
続けます。
>>9
自己紹介すると、本名は松本卓朗と申します。31歳男性です。統合失調症を患って
いて、障害年金生活なので、数学を研究する時間があります。
11(1): ID:1lEWVa2s 2020/03/31(火)13:07 ID:NtSTCJsM(1/2) AAS
P=NP問題って
素数方程式やフェルマーの最終定理
リーマン予想ゴールドバッハ予想の解を
ある完備された体で全部解ける
全てのディオファントス方程式の解の意味をみつけれるって問題だよ。
12(1): ID:1lEWVa2s 2020/03/31(火)13:08 ID:NtSTCJsM(2/2) AAS
書き込み禁止されてるけどこっそり。
13: a4 ◆L1L.Ef50zuAv 2020/03/31(火)13:13 ID:/0OHc4N+(2/27) AAS
まず数式が間違ってました。２乗じゃなくて、絶対値ですね。
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)
14: a4 ◆L1L.Ef50zuAv 2020/03/31(火)13:17 ID:/0OHc4N+(3/27) AAS
>>11
>>12
こんにちは。お久しぶりです。簡単に言えばそういうことですね。比例ではなく、
多項式なので、まだ時間はかかるかもですが。
15(1): 2020/03/31(火)13:19 ID:YIOqSIb4(1) AAS
この問題を考えるんだったら基礎知識はつけといて欲しい
NP完全とかNP困難が何かわからないとかもう話にならない
巡回セールスマンとか一見取っつきやすいところに食いつくより
書籍なりWebなり読んでひととおり理解してから出直してくることを薦める
16: a4 ◆L1L.Ef50zuAv 2020/03/31(火)13:27 ID:/0OHc4N+(4/27) AAS
AA省
17: a4 ◆L1L.Ef50zuAv 2020/03/31(火)14:20 ID:/0OHc4N+(5/27) AAS
復習してます。まず、巡回セールスマン問題(TSP)は、閉路の問題ですね。TSPが解ける
と、ハミルトン閉路(HC)（あるグラフに対して一筆書きができるか？）を、解くことが
できるから、NP困難だと。僕がまず疑問に思っているのは、格子？直交？の経路のみに
変換されたTSPがNP困難か？でも、これは距離が出てくるから、TSPが解けると、
この問題も解けるのは自明？だとすると、ノードを付け足していくとき、最短閉路の
１つのエッジを２つのエッジにするだけじゃ新しい最短経路にならない？でも、３つ
以上変えなければならないと仮定すると、元のが最短閉路でなくなってしまう。
どこが間違ってるんでしょうね。僕は夢で映像を見ただけですが、こうすると、
元のTSPも同じようにエッジを追加すると３つ以上動く？どういうことなんでしょうね。
まだ論文を書くために研究を続けます。
18: a4 ◆L1L.Ef50zuAv 2020/03/31(火)14:22 ID:/0OHc4N+(6/27) AAS
NP困難じゃなくて、NP完全ですね。
19(1): ID:1lEWVa2s 2020/03/31(火)14:37 ID:UrUHbgPx(1/2) AAS
あんま無理すると僕みたいに夢に強いホワイト製薬のもんすたぁがでてくるぞ。
20(1): a4 ◆L1L.Ef50zuAv 2020/03/31(火)14:43 ID:/0OHc4N+(7/27) AAS
>>19
今は無理はそんなにしてないよ。１日１２時間くらい寝てるから。
上下前次1-新書関写板覧索設栞歴
あと 408 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.040s