[過去ﾛｸﾞ] 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
今は無理はそんなにしてないよ。１日１２時間くらい寝てるから。
21: ID:1lEWVa2s 2020/03/31(火)14:45 ID:UrUHbgPx(2/2) AAS
>>20
僕も12時間寝てる。
眠れなくても布団に入ってる。
22: a4 ◆L1L.Ef50zuAv 2020/03/31(火)14:47 ID:/0OHc4N+(8/27) AAS
今、問題なのは、TSPの最短閉路に、もう１つノードを追加して最短閉路を考えた時、
１つのエッジが消えてそれがそのノードとの２つのエッジに変わる、という以外の
ものになるか？です。反例を探してます。
23: a4 ◆L1L.Ef50zuAv 2020/03/31(火)14:57 ID:/0OHc4N+(9/27) AAS
反例のようなものが見つかりました。
正方形の紙の４つの頂点を考えます。すると、最短閉路は４のようになります。
√２離れた向こう側の頂点同士を３次元的にくっつけるように間にノードを入れると、
１＋０＋０＋１＋√２のようになります。
これで「このクソスレは終了しました」なんでしょうか？でも、テレパシーの指令
により、もうちょっと考えてスレを続けさせていただきます。
24: a4 ◆L1L.Ef50zuAv 2020/03/31(火)15:09 ID:/0OHc4N+(10/27) AAS
まだ謎に思えるのは、この直交したジグザグ経路しか考えないTSP（以下、a4-TSP
と呼ぶことにする）を考えると、もう位置が決まっていて、正方形を３次元的に
くっつけたりしないんじゃないかと。もしこの反例のようなことするなら、最初から
近い位置にあるんじゃないか？と。でも、P=NPを証明しろ！と言われたら、まだ
わからないことだらけ。まだ研究を続けます。
25: a4 ◆L1L.Ef50zuAv 2020/03/31(火)15:18 ID:/0OHc4N+(11/27) AAS
今、考えてるのは、グラフ構造のエッジの距離が、ｎ次元のものでもいいか？です。
やっぱり>>2さんが頭良いということですが、複素数などを考えず、単純にｎ次元の
ものでもNP完全になるかなどを考えてます。
26(3): a4 ◆L1L.Ef50zuAv 2020/03/31(火)15:28 ID:/0OHc4N+(12/27) AAS
そういえば、懸賞金が入ったらどうするか？を妄想してますが、基本的に
量子コンピュータの開発費にしようと思ってます。これなら数学的な貢献で
いいんじゃないかと。
27(2): ID:1lEWVa2s 2020/03/31(火)15:37 ID:u+SuL/Zv(1/5) AAS
>>26
懸賞金はヘーベルハウスの家建てやあ。
但し童貞は守ること。
28(1): 2020/03/31(火)15:39 ID:AEGXedru(2/2) AAS
なんだやすのりじゃないのか
最近twitterでもP=NPを証明したって言ってるやつがいたからそいつかと思った
29(2): ID:1lEWVa2s 2020/03/31(火)15:40 ID:u+SuL/Zv(2/5) AAS
>>26
あと建築設計に数学があるんだけどみつけな。
私は知ってるけどひんとはださない。
僕は建築家目指してる。
事務所は我が家。
軍資金はぱそこん代。
30: ID:1lEWVa2s 2020/03/31(火)15:43 ID:u+SuL/Zv(3/5) AAS
僕怒ると暴走するんで黙ります。
31(1): a4 ◆L1L.Ef50zuAv 2020/03/31(火)15:46 ID:/0OHc4N+(13/27) AAS
>>27
研究所みたいなのは建ててもいいかなと思ってる。ナマズの地震予知とかの研究に
特化したところ。童貞はまだ守ってるけど。
>>28
やすのりさんではないですね。最近はずっとa4って名前でやってます。
>>29
有限要素法とかだったら勉強したことあるよ。
32(1): ID:1lEWVa2s 2020/03/31(火)15:51 ID:u+SuL/Zv(4/5) AAS
>>31
>>29
%代数学ゆ産業。
%てぇじざんこくな。
(係数)
0.6’2+0.8’2=0.28’2=0.96’2
ひんとおわり。
33(1): ID:1lEWVa2s 2020/03/31(火)15:53 ID:u+SuL/Zv(5/5) AAS
ねりゅ。
34: a4 ◆L1L.Ef50zuAv 2020/03/31(火)15:54 ID:/0OHc4N+(14/27) AAS
>>32
ちょっと難しいね。
35: a4 ◆L1L.Ef50zuAv 2020/03/31(火)15:54 ID:/0OHc4N+(15/27) AAS
>>33
おやすみ。
36: a4 ◆L1L.Ef50zuAv 2020/03/31(火)16:12 ID:/0OHc4N+(16/27) AAS
少しずつ考えてます。まず１，１，３の三角形は、x軸に３の辺を置くと、頂点は、
(0,0),(3,0)(3/2,√5i/2)で複素数なら解はありました。
上下前次1-新書関写板覧索設栞歴
あと 392 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.015s