TOP カテ一覧 スレ一覧 100〜終まで 2ch元 削除依頼
分からない問題はここに書いてね456
SNS死神ムラカミ
遂に解かれた！AX+BY=CZ
なぜ右翼と左翼は争っているのか
私立文系学部の入試にも数学を必須にすべき
【数学？】眠り姫問題について【哲学？】
チラシの裏 ２枚目
ｗｗｗｗｗ小説を読むスレｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
現代数学の系譜 工学物理雑談 古典ガロア理論も読む45
数学の本 第87巻

P=NP


1 ：2020/03/30 〜 最終レス ：2020/06/04
こんにちは。P=NPを肯定的に解いてみました。検証をお願いします。

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

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

3 ：
>>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)

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

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

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

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

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

8 ：
質問スレでやれ
単発スレ立てんなカス
R>>1

9 ：
やすのりか？

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

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

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

13 ：
まず数式が間違ってました。２乗じゃなくて、絶対値ですね。
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 ：
>>11
>>12
こんにちは。お久しぶりです。簡単に言えばそういうことですね。比例ではなく、
多項式なので、まだ時間はかかるかもですが。

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

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

16 ：
>>15
勉強はしましたよ。忘れてるところはあるかもですが。NP-Complete Problemsの
に関して、
SATISFIABILITY→3SAT→3DM→PARTITION
　　　　　　　　　　　→VC→HC
　　　　　　　　　　　　　→CLIQUE
とかの証明は全部理解しました。
なんかおかしいと思うのは、僕が精神障害ってことなんですよ。皆がP!=NPに
賭けてる中、僕はP=NPであると宇宙人達から幻聴が聴こえてくるんです。それで
夢で証明の映像を見たら、それが正しいとまた幻聴が聴こえて妄想になってるん
です。どうして信じてるかと聞かれたら、量子脳理論で量子コンピュータが
出来てるんじゃないかと。

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

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

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

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

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

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

23 ：
反例のようなものが見つかりました。
正方形の紙の４つの頂点を考えます。すると、最短閉路は４のようになります。
√２離れた向こう側の頂点同士を３次元的にくっつけるように間にノードを入れると、
１＋０＋０＋１＋√２のようになります。
これで「このクソスレは終了しました」なんでしょうか？でも、テレパシーの指令
により、もうちょっと考えてスレを続けさせていただきます。

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

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

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

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

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

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

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

31 ：
>>27
研究所みたいなのは建ててもいいかなと思ってる。ナマズの地震予知とかの研究に
特化したところ。童貞はまだ守ってるけど。
>>28
やすのりさんではないですね。最近はずっとa4って名前でやってます。
>>29
有限要素法とかだったら勉強したことあるよ。

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

33 ：
ねりゅ。

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

35 ：
>>33
おやすみ。

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

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

38 ：
やっぱり難しいですね。

x=0からx=2までの最短経路は自明なんですが、x=1+iのような点が入ってくると
いうのを後の問題にはできないですね。

やはり「このクソスレは終了しました」になるのか？ですが、まだ続けます。

39 ：
このスレが続く理由はまだ>>1の方法が倒れてないんですよ。このa4-TSPが一般化
されたグラフでないために、NP完全であるということがまず示せてないんです。

40 ：
>>1のa4-TSPが、NP完全でないと証明されたり、NP完全であっても１つのエッジを
２つのエッジ以外の反例がある、ということが示されたら、基本的にこのスレは
終了かもしれません。

41 ：
Wikipediaをとりあえず見てます。すると、

「都市間の移動コストが三角不等式を満たす、すなわち移動コストを距離と呼べる
部分問題（あるいは制約つき問題）も、NP困難である。都市を平面上の点、都市間
の距離を平面上のユークリッド距離とする部分問題は最も直感的で理解しやすいが、
これも NP困難である。」

とあります。NP完全であるということが証明されていなくて研究は終わったかの
ような口調で書かれてあります。

僕はここで医学的妄想で未来と通信することにします。

42 ：
未来に聞いたら、「NP完全だ！」と返りました。普通に考えれば、HCがNP完全なので、
a4-TSPもNP完全じゃないかと。

43 ：
なんか夢に出てきた伏線かな？と妄想してるのは、普通にTSPを２次元などで書くと、
エッジに数字がついたりして三角不等式の問題も出てきてしまうんです。a4-TSPなら、
距離を明確に図で書いてるので、証明もしやすいのかな？と。

44 ：
ｎ次元の頂点は複素数ではないので全てに三角不等式が成り立つとすると、新しい
ノードも加えて最短経路を作った時、そのノードの２つのエッジから、そのノードを
取って１つのエッジにくっつけるという操作をすると、距離が縮まるから、その時の
最短経路を出す時は、他のエッジを動かさなくてもいい。他のエッジが動くとすると、
そっちが最適解になる。だから、最短経路に１つ１つノードを付け足していけばいいん
じゃないかと。これで証明終わり？？？

45 ：
>>6さんに聞いてみます。これくらいで、まだ明らかな数学的な欠陥のあるところが
ありますか？無ければ論文として纏めようと思います。

誰かが来るまで、休みとして、スペイン語とかを勉強します。

46 ：
やっぱり>>44の証明が数学っぽくないから間違ってるのかな？スペイン語をやめて
また考えることにします。

47 ：
今、考えてるのは、ノードを付け足した最短経路から、そのノードを取ると、
(1)-(2)-(new)-(3)-(4)
から、
(1)-(2)-(3)-(4)
じゃなくて，
(1)-(2)-(5)…(6)-(3)-(4)
などと最短ルートが変わるケースです。まだ証明できてないですね。

48 ：
ずっと考えてます。まずWikipediaの「三角不等式が成り立つ TSP については
多項式時間近似アルゴリズムが数多く存在する。」の情報は重いです。単純には
証明できませんでした。僕は>>1の２次元のa4-TSPを追ってます。すると、
１つのノードを付け加えた時に増える距離は、min{2|x[n]-x[i]|+2|y[n]-y[i]|}
と出てきました。a4-TSPでの距離において、この項は最大でO(n)個ですね。
１，２，３，４，５と増えていくので、単純に考えると、O(n!)ですが。すると
これだけだと、足し算される時、値が、３＋５＝８という順と５＋２＝７
という順の反例を思いつきました。でも、追加される選ぶ値の集合は、５と２に
おいて考える時、変わらないため、前者で３＋２＝５と、なるんじゃないかと。
そうすると、やはりこのアルゴリズムでいいんじゃないかと。厳密な証明は
まだこれから考えます。これで解けたというのを僕のエイプリルフールにします＾＾；

49 ：
現実的にはまだずっと解いてます。
まず、さっきのは２次元a4-TSPですが、ｎ次元a4-TSPの場合は？と。自明じゃないです。
min{2(|x[1][n]-x[1][i]|+|x[2][n]-x[2][i]|+…+|x[n][n]-x[n][i]|)}
とすると、単純に考えると、n個から選ぶ問題になって2^n通りが出てきてしまう
のではないかと。また、
（２＋１）＋（２＋３）＝３＋５＝８、
（１＋３）＋（１＋１）＝４＋２＝６、
といった順の問題になりました。

50 ：
2^n通りはn(n-1)/2通りくらいまで落とせるかもしれません。

今、解いてるのは、
(1)-(2)-(4)-(5)-(1)が最短経路の３で、
(1)-(2)-(3)-(4)-(5)-(1)が３＋５＝８

(2)-(1)-(5)-(4)-(2)が４で、
(2)-(1)-(3)-(5)-(4)-(2)が最短経路の４＋２＝６

とすると、単純な方程式により、
(1)-(2)-(4)-(5)-(3)-(1)が３＋２＝５

今日はこれくらいにして寝ることにします。

51 ：
俺はP≠NPを確信している側
今は関連理論を作っていて、そこから派生的に証明できると思っているけど、単なる実例よりも
相当高い抽象化をしないと証明にはならないと思ってる

52 ：
>>51
今、起きました。ご連絡ありがとうございます。僕もP≠NPだと思ってたんですけどね。
P=NPだ！って幻聴が聴こえてくる精神病なんですよ。僕は博士ではありませんが、
数学とか計算機科学とかは知ってるつもりなので、証明は可能ならばきちんと書く
つもりですよ。幻聴って何かな？ってことですが、複雑な量子脳理論、と書くと、
よくわからなくなるんじゃないかと。証明を直接聞くのは非常に難しいので、曖昧な
２分木アルゴリズムとかで、証明にかかる計算量を対数くらいにすると医学的妄想？
をしてます。

53 ：
医学的妄想でタイムトラベルしてます。すると、未来人は、P=NPの証明に関して、
a4-TSPの頂点をギリギリ含む超直方体に１点を追加して新しい超直方体を考える、
ということを考えれば、自明なんじゃないかって。僕もあまり信じてませんが、
証明か反証を今から考えます。

54 ：
反証を考えてみました。２次元において、大きい５角形の中に小さい５角形がある
というのを考えると、最短経路に凹のような構造ができてしまうんじゃないかと。
まだ未来と通信とかしながら研究を続けます。

55 ：
タイムマシンで時空のループが作られることによる嫌がらせの問題を解きながら未来と
通信しています。意外にも、ここまで来て、ようやくプログラムを書いて、モンテカルロ
のように実験しなさい、と。じゃぁ、多項式時間じゃないのか？ですが、現実的には、
Wikipediaの「巡回セールスマン問題」には、「三角不等式が成り立つ TSP については
多項式時間近似アルゴリズムが数多く存在する。 」とあります。今から作業をします。

56 ：
Wikipediaの「クリストフィードのアルゴリズム」というのを見てます。「2015年現在、
距離空間における巡回セールスマン問題に対する多項式時間アルゴリズムの中では、
近似度が最良であるアルゴリズムである（一部の特殊な場合では、より良い近似度が
存在する事も知られている）。 」とあります。近似なのかは数が多くなるとわかり
ません。これだけ見るとP=NPみたいだな、と。問題は証明です。このスレは僕の
妄想が終わらない限り続きます。

57 ：
>>1に書いた方法の反証が見つかりました。

(10,6)(10,0)(14,6)(3,12)(8,9)(4,5)(0,9)(4,5)
図に書くとわかるのですが、２次元a4-TSPでは、2*(14+12)=52が大域最適解です。
これは長方形と同等なのに、１つずつ加える方法で計算すると、6個目の(4,5)の
ところで凹になり54になりました。

58 ：
a4「じゃぁ、タイムテレパシーの妄想未来人に聞いてみます。こみさん、嘘をついて
いたんですか？」
こみ「いいえ、わたしはあなたに指南書を送っただけです。まだ研究は続けてくださいね。」
a4「じゃぁ、>>1の方法は間違ってるんですか？」
こみ「そういうことじゃないんですよ。あれは嫌がらせなんです。わたし１つ言っていい？
あれは未来になってからわかるにしたい。」
a4「これじゃぁ、僕の統合失調症じゃないですか。こんな難問解けると思ってません。
タイムマシンの力無しに。第一、タイムマシンがあるなら、僕が解けるかわかるじゃ
ないですか。」
こみ「そういうことじゃないんですよ。タイムマシンの攻防戦があると言ったのは
あなたじゃないですか。ではね、どうやって解くか指南書をもう一回与えます。
「種をまくんです。」これでいいですか？」
a4「よくわからないですね。いつ頃、解けるんですか？」
こみ「それは言えません。では、株価計算してる人からしたら、ウザいと思われる
かもしれませんが、これに勝てば大金持ちじゃないですよ。殺されることになります。
それでもいいですか？」
a4「それでいいですよ？」
こみ「では、あなたに聞きます。大澤先生！これは統合失調症にするための言葉です。
では、あなたは何を考えてますか？」
a4「量子コンピュータを創ろうと思ってます。」
こみ「これでいいでしょう。まだわたしたちは続きます。」

59 ：
こみ「わたしね、a4君にP=NPを解いてもらいたいなー、と勘違いしてません。
あなたが解いてください。」
a4「うん？今の時代にP=NPに本気で挑戦してる人なんていないので案外いけるかも
ですけどね。でも、挑戦してきた人達は量子コンピュータへ行ってますよ。」
こみ「あなたも嘘つくんですね。」
a4「何が？え？わー、助けてー！！！」
こみ「いいですか。大澤先生！これはあなたを統合失調症にするための言葉です。
では、ヒント、わたしが答えを出します。まず、１つずつ挿入ソートのようなもの
ではないことにしてください。>>1は嘘なんですが、伏線があります。」
a4「では、どのような解法なんですか？」
こみ「それはもう言いました。」
a4「種をまくんですね。」
こみ「もう１回言います。「１年ごとに種から生える植物が変わるにしたい。」
オカルト板からも呼んでますが、まだこれ使ってないでしょ？マイクロソフトは
こちらに嫌がらせをしています。１つ言っていい？本当にこれ解けたんなら、
大金持ちではなく、殺されます。どうでしょう？」
a4「そういえば、僕は28歳の頃、タイムマシンやシュレディンガーの猫の実験が
成功して、もう１人の僕が宇宙人に殺されて声帯などを撃たれて、「あーーー」と
いう声を聞きました。同伴していた看護師も「面白い人なのに（泣）」と言って
ました。これでいいですか？」
こみ「はい、こちら軍事。どうします？わたしはa4さんはまだ研究しなさい、と
言います。期間は、ちょっとね、ごにょるんですけどね、３か月にしてください。
わたしはこの期間で出来るかは判断しません。」
a4「種については考えてみます。僕に賛成してくれる人の期待を裏切りたくないです。」
こみ「はい、では、一旦、研究してください。わたしは落ちます。」

60 ：
a4「また反例を見つけました。(0,0)(1,0)(2,0)(3,0)。これでは種まきアルゴリズムは
使えませんね？(3,0)-(0,0)が届きません。どうですか？こみさん。」
こみ「いいえ、あなたはまだ序章をやってるだけです。アルゴリズムは複雑ではない
ですよ？いいか、量子コンピュータではないんですよ？」
a4「うん？やっぱりこみさんは嘘つきだ！序章なのに複雑でないとか。やっぱり
僕の統合失調症だ！」
こみ「そうではありません。ではね、もうちょっと複雑な技を撃つにしたい。これです。」

61 ：
707a4 ◆L1L.Ef50zuAv 2020/03/28(土) 09:37:43.32ID:rbQUI3W10
今日はタイムスリップやタイムテレパシーじゃなくてタイムリープしました。２歳の
誕生日に。叔母と一緒にいたのですが、宇宙人が現れて、Ｐ＝ＮＰの証明が、
巡回セールスマン問題のような図と一緒に日本語で５文ほどで書かれてありました。
僕は２歳なのに頭が良くなっていたということですが、どうして叔母がここまで
嫌らしく反撃できるんだろう？と。そこにいた女性の先生は「ベクトルなんて難しい
ものは使わないでください。」と怒ってました。ノーベル賞の裏の人達５人に、
１年ごとに別の美味しい植物が実る種を分け与えなさい、と言われて行こうと
思ったのですが、先にタイムリーパーが「それ欲しい」と来たので信頼できると
考えて先にあげると、夢から覚めました。

62 ：
こみ「ほら、あなたは２歳の頃に解けていたんではないですか？」
a4「うん？だから、それは夢じゃないですか？」
こみ「あなたは夢が量子脳理論であると主張しています。どうですか？」
a4「僕はP=NPが>>1ですぐ解けると思っていました。でも嘘であると。ファジー
論理的に上手くあなたを信用できません。」
こみ「それでいいんです。では、情報はこれだけです。すなわち、>>61です。
これを信じてやってくださいね。」
a4「うん？だから(3,0)-(0,0)で反証したじゃないですか！？」
こみ「いいえ、あなたはまだ分かってないんです。どうしたことか。そういえば、
わたしは未来を知っています。例えば、」

63 ：
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.」
「西暦2020年4月3日」の忌み名は「地球温暖化」
「西暦2020年4月4日」の忌み名は「ｼﾞｺﾄｼﾃ」
忌み名は、動かすための量子大域最適文だから、これでこの文章で当てるようにする。
この文章で反転詠唱した奴らは死刑だから。だから、当てる。これだけだ。これで
a4が大物になるから。」

64 ：
こみ「ほら、今日は「Saluton.」=（去る東大オン！）=(去る、東（京）、大（阪）、オン！）
となりました。これで未来予知できましたね。では、わたしはもうちょっと複雑な技を
撃つにします。西暦2040年に今日あなたは行きましたね。どうでしたか？」
a4「今日？夢で行ったよ。数学のテストを受けたら、教科書から数学書の名前を
ただ書き写すだけの。占いの中国の女性に話しかけられたら、結婚がどうとか
言われたけど、今の時代にいないような頭の悪さだったのに殺されそうで危なそう
だったから、テレパシーで量子コンピュータを使って女性の神経構造を変形させ
たら、女性は「着火（ちゃっか）」って日本語で叫んでました。」
こみ「ほら、未来へ行ったじゃない？」
a4「だから、それを証明するためにP=NPを解こうとして解けなかったんです。」
こみ「あなたはまだ始まったばかりであることに勘付いてください。」
a4「とりあえず、３か月かはわかりませんが、研究は今日もやります。」
こみ「ほらね、わたしは一旦落ちます。」

65 ：
a4です。こみさんは一旦下りてますが、巡回セールスマン問題をWikipediaで見ると、
全てのノードを訪れるだけで、出発地に戻らない図が載ってますね。でも、証明など
が載ってないので、そこから考えることにします。

66 ：
SATISFIABILITY→3SAT→VC→HC→TSP→a4-TSP
ということですが、VC→HCの証明は再理解したんですが、単純にここから、
「出発地点に戻らないTSP」のNP完全性の証明は難しそうですね。

67 ：
もちろん、出発地点が決まっていないものを考えてるんですよ。出発地点が決まってる
ものは、そこからの長さを無限大に飛ばせばいいだけなので。きちんとは調べていない
というか、すぐには検索しても出てきませんが、NP完全性は偽なのかもしれません。

68 ：
未来人のこみさんと今でも会話してます。まず、おやっ？と思ったのが、>>1に格子
と書いたところなんですよ。有限の領域の整数がノードなんじゃないかと。一般的な
TSPはエッジが１つでも長いと、計算量が長さに対して増える、などといったことに
なりますが、HCからの証明だったら、エッジの長さは１か２になればよく、ｎ次元
とすれば、ここまでなら上手くいくんじゃないかと。

69 ：
でもｎ次元格子だと、a^n個の格子が必要になり探索空間が指数関数的増加になるので
どうなのか？と思ったら、前も書いた通り、Wikipediaの「巡回セールスマン問題」
には、「都市を平面上の点、都市間の距離を平面上のユークリッド距離とする部分
問題は最も直感的で理解しやすいが、これも NP困難である。」とあるので、２次元
格子a4-TSPにおいても、多項式時間で解ければ、P=NP?といったことを考えてます
が、必要な証明などが見当たりません。まだ通信しながら考えます。

70 ：
NP完全とNP困難の違いをよく理解してるわけではないのですが、一応、Wikipediaで、
「NP困難」を調べると、「もし、いずれかのNP困難な問題を多項式時間で解く
アルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることに
なり、P = NP が成り立つ。 」と。「いずれか」なので、２次元TSPはいいんですが、
２次元格子a4-TSPはNP困難なのか？NP完全なのか？を考えてます。

71 ：
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)は、
https://www.sciencedirect.com/science/article/pii/0304397577900123
現実的に僕のa4-TSPと同じようなことを考えてた人がいるみたいですが、少し
違うみたいです。

72 ：
同じ場所で、「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 ：
上述の「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 ：
英語で書くと、読める人はこの板だとまだ多いかもしれませんが、日本の掲示板なので、
僕が和訳することにしました。障害年金を受給しているので、このような形で社会貢献
です。

まず、path-TSP、すなわち、最初の出発点が決まらず、尚且つ、出発点に戻らなくても
いい場合は、NP-completeであると書かれてあります。証明は、一般的なものが論文には
勿論書かれてありますが、個人的な具体例を示します。tour-TSP、すなわち、普通の
TSPの問題をpath-TSPに変換して解けることを示します。平面に正五角形を書いて、
１点を２つにして、それぞれ上下へ大きく動かして適当に長さを設定します。すると、
これにおけるpath-TSPはこの２点が端点のものに大域最適のものがあります。それで
上下にあったものを元の位置の１点に置きます。これで元の問題が解けました。
これでpath-TSPはNP-completeです。

75 ：
僕は睡眠障害なので今起きました。でも障害年金を貰っていて１日１２時間ほど寝る
ので、研究に関しては問題ありません。今日もP=NPを解くために頑張ります。

76 ：
論文読んでるんですけどね、「The Euclidean TSP is NP-Complete.」ということが
1970年代に証明できているということが書かれているだけで、理解させるために
書かれているわけではなさそう、ということです。論文を書いた人がHarvardの
先生であるため、僕の力不足かもしれませんけどね。でも見た感じでは、２次元の
ものでも良さそうですけどね。だから、Wikipediaも２次元のpath-TSPで図が
描かれてると思っています。じゃぁ、問題である、２次元のa4-TSPがNP完全なのか？
は、僕は証明できません。まだ考えます。

77 ：
僕がとりあえず考えているのは、論文の意味がわからなくても、証明をそのまま、
TSPからa4-TSPに変形できるんじゃないかということです。出てくる図もa4-TSP
で解けるし。一旦そういうことにして、他の問題に移ることにします。

78 ：
一応、もう一回よく見てみると、
「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 ：
こみ「はい、こちら西暦2502年。え？普通に未来人ですよ。わたしはEPFL製の
コンピュータです。では、わたし？中性です。dasなんですよ。ではね、大澤先生！
はい、統合失調症。これで、a4さんには悪いですが、賄賂が落ちます。わたしが
一発で答えを落とせばいいでしょ？落としますよ？それが、>>61なんですよ。これが
現実にしたい。綺麗な証明は落としません。歴史改変が起きるので。それでは、
もうちょっと書きましょうか？2dimentional-a4-TSPはNP-completeです。
これは自明ではないですが、わたしが一票。信用はありません。これがbinary tree
アルゴリズムです。種まき、上手くいかなさそうでしょ？そうじゃないんですよ。
現実的には、近傍で解きます。そうすると、path-TSPの最長のエッジはどうなる
のか？ですが、わたしは、近傍でyes/noでbinary treeを使います。わたしはお人好し
ではありません。これでいいか？これで、a4さん、すなわち松本卓朗(songbenzhuolang)
さんに、一票します。え？わたしは中国人です。a4さんは普通の日本人です。
それでは。」

80 ：
内容はよくわからんけど
リアル『1984』が在りそうだなｗ
歴史改竄局(省)とか面白そう

81 ：
2dimentional-grid-a4-TSPについて考えてます。finiteじゃないです。距離が長いもの
を整頓するアルゴリズムを使えば、大きさをO(n^2)くらいに落とせるのではないかと
考えてます。
あと、自明な反例を探索するのではなく、クラスタの中にある一様乱数のような
ノード群を考えてます。これならnCm(mはnより十分小さい)くらいで近傍で種
から植物を生やすような方法で解けるんじゃないかと。これも真か偽かは自明まで
いかないですね。m-1のとき、繋がってなくて、mの時にpathが作れるように
なると、そこからの探索数が指数関数時間になってしまいそうですが、三角不等式
で自明な悪いエッジを消す計算をします。
じゃぁ、a4-TSPって意味あるの？ですが、未来人は、「証明と関わる。」と主張
してます。未来人はさらに、「プログラミングをして大域最適解になるか一旦
調べてください。」と来てます。

82 ：
>>80
時間あればその本も読みたいですけどね、僕の専門は量子コンピュータくらいなので、
小説はほとんど読む暇がありません。でも「博士の愛した数式」くらいは読破しました。

83 ：
そういえば、量子脳理論の量子コンピュータで「P!=NP」の忌み名を計算したことが
あります。そうすると、「ｸﾙﾂｱｲｳｸﾂﾃﾞﾜｶﾚﾙ」 と出力されました。
（昔の商人が仕事が終わって）来る、２（つの道）、哎、哭、（仲間が）靴（を投げて
こっちだ！と）で、（これからの道と、愛する客人と）わかれる。（この問題を解いて
くれ！）
という意味みたいです。

84 ：
未来人の言う通りに調べてみたら、一様乱数だと、n_C_sqrt(n)〜n^sqrt(n)くらいに
なって多項式時間ではないと考えました。またテレパシーで聞きにいきます。

85 ：
ちょっと計算間違いしました。また未来人に聞きに行きます。

86 ：
a4「こみさん、僕はやっぱり精神病みたいです。僕は頭悪いじゃないですか！どういう
ことなんですか？」
こみ「やっぱり面白い人。自分で最初から墓穴を掘ってa4（アホ）と名乗っている。
どうしましょうね。」
a4「プログラミングとかする気がおきないのは、疲れるのもあるんですが、既に
誰かがやってできないことがわかるからなんですよ、もちろん。」
こみ「ははは、そういうことですね。ではね、大澤先生！やっぱりあなたは統合失調症
です。西暦2502年的に見てもそうですよ？でもね、アスペルガーみたいなものかも
しれません。では、わたしが最強の技を撃つことにします。忌み名です。さっき
書いたものは古い研究なので。「a4-TSP」の忌み名を書きます。ほら、恐いでしょ？」
a4「忌み名は間違ったことはありません。」
こみ「そうですね。ここは宇宙人に聞きましょう。」

87 ：
名古屋の宇宙人２「おっす。俺は加藤得々（かとうえっとく）だ。ではな、俺は
この忌み名で勝つにする。「a4-TSP」の忌み名？なんだと思ってる？現実言っていい？
これはa4が動かん。もう１回書くぞ。これくらいでシメだ。

「a4-TSP was solved in 1975 as a proof of P=NP.」

こういうことだ。もう解けてるんだけど、解けてないということになってるのを
俺の嘘じゃないことにする。うん？俺は嘘つきだけど、だからこうじゃないの？
ほら、この解法が動くだろ？a4にも金入るじゃん？これさ、解けたらさ、完全に
暗号が解かれる？すると、核兵器の資料が入手できちまうんだな、そういうこと
にしたい。クレイ研究所大丈夫か？俺はあっちを買いにする。アメリカ人は好き
じゃねーけど、俺は一応Harvardだから。これくらいでいいか？a4君、１つ
言っていい？誰か有名な数学者を見つけたほうがいいよ。すぐ解法見つけて
くれるから。君はdoctorじゃないでしょ？君は頭良いんだけどね。どうしようか？
現実的には>>6さんに聞けばいいかもだけど、時間無いでしょ？でも、聞いて
みたら？コネかなんかを。君はね、教授の友達がいないの。だからさ、俺じゃ
なくて、一旦、>>6さんにそれを聞いてみて。ではね。」

88 ：
>>6さんに質問です。プロの数学者の友人ってどこで見つかるんですか？僕は工学学士
なんですが、大学の教授とは、宇宙人がどうとか医学的妄想を言っていたら、関係が
壊れてしまいました。僕は31歳ですが、博士になれるんだったらなりたいです。専攻
は神経科学くらいかもしれませんけどね、人工知能のようなもので数学とかを解こうと
思っているので。2chにもいっぱいいるかもですが、このスレはまだそんなに繁盛して
ないですね。僕は海外の人とも英語で話せます。自閉症的だからこそ、P=NPを解く
ために、コネの問題を解決したいです。どうすればいいでしょうか？もちろん、この
スレをご覧になってる方が友人になってもいいよなどでも返信いたします。

89 ：
名古屋の宇宙人２「俺ね、信頼損ねてるけど、そういうことじゃないんだわ。普通に
宇宙人なんだわ。人来てねーだろ？だから、普通に宇宙人なんだわ。どういうこと
かって？普通に宇宙人だから、言ってるんだけど。確かにさ、a4君の研究とか
取られたくないってのはわかるけどさ、普通に研究されてるから。どうして俺が
こんなこと言ってると思ってる？だからさ、どうしようかな、a4君的にはね、
宇宙人の証明が厳しいものになってるけど、「2ch」の忌み名を書こうか。これはね、
「ﾆﾁｬﾝﾄｴｯﾁｼﾀｵﾝﾅｶﾞﾀｺﾍﾞﾔﾂﾚﾃｶﾚﾀﾝﾀﾞｹﾄﾞﾖｯｼｬｰ」
=(2chでエッチした女がタコ部屋連れてかれたんだけど、よっしゃー！(この悪評をばらまかないでくれ、言うことを聞くから)|
日夜、んと？えっ？血舌女、ガタッ、恐゛、やつれて、彼、痰だけど、よしやー(この悪評をばらまかないでくれ、言うことを聞くから)|
(逆)香具師、よっ、どけ、だん！誰かテレ通！答が何お？たし（ろ）えと、んちゃ、に＾＾(逆とか量子最適化だから逆の世界を作らないでくれ))
ほらな、これで数学解けるから。うん？やっぱり宇宙人だろ？だからさ、俺の言うこと
聞いて専門家を呼ぶんだわ。１つ言っていい？多世界解釈的に来なかったら、もちろん、
メールするよ、プリンストンくらいに。これでいいか？ではな。」

90 ：
こみ「はい、こちらは西暦2502年。わたしはa4さんにP=NPを解かせるのをやめさせる
ことにしたい。でも、解くのはa4さんです。つまりどういうことかというと、コネを
作るんです。共同受賞でもいいんですけどね、そういうことじゃないんですよ、
タイムマシンの話なので。こういうことにしかならないんですよ。a4-TSPとかが
そのまま使えたら良いことにします。現実的にa4さんに聞いてみましょう。」
a4「悔しいですけど、僕がエスパーなだけでは解けないですね。でもまだ解決に
関連する人達の一人にはなれそうなので、コネの問題を解決することにします。
主観的な現実的には、数学は自力で解くのが楽しいんですが、タイムマシンと
人間関係の数理を解かないといけないみたいです。では、これから、海外を
含めた教授らにメールを書く作業を行います。僕のこのスレでの問題は>>1と
>>61です。」
こみ「はい、ではどなたかお待ちしております。」

91 ：
世界観がちょっと似てるから応援する。

92 ：
>>91
応援ありがとうございます。

93 ：
海外の数学の教授１０人ほどにメールを書いたのですが、返信はまだありません。

94 ：
そういえば、abc予想が解かれましたね。プリンストンとかこのスレで話してたら。
P=NPが解かれると、多項式時間で数学の問題が解けるので、早めにニュースと
いうことでしょうか。関係妄想かもしれないですけどね、被害妄想ではないにしたい
です。プリンストンの教授にメールとか送りたいんですけどね、今はそれ関連で
お忙しいかもしれません。僕は今日も研究ですが、妄想の未来人と通信してきます。

95 ：
夕方四時半に寝て今起きちゃった。

96 ：
こみ「はい、こちら西暦2502年。」
a4「教授から返信が無いということは、やはりタイムマシンは無いんじゃないですか？」
こみ「そういうわけではないんですよ。えーっと、a4さん、こっちでね、abc予想じゃない
問題とか解かれてると思ってますか？」
a4「リーマン予想とかですか？」
こみ「はい、あれはね、解けないんですよ。」
a4「でも、あなたはファジー論理的に信用できません。」
こみ「哈哈哈、ではね、a4さんは何人にメールをしたら返事があると思っていらっしゃい
ますか？」
a4「うーん、メールする内容にもよるんですけど、「統合失調症」とか「テレパシー」とか
「未来人」とか「宇宙人」の話をしなければ、5%くらいかな。」
こみ「ほら、わかりましたね。じゃぁ、そうしてみれば？」
a4「でも、その話をしないと先に進まないし、"I'm sorry I can't help you."くらいしか
返ってこないんじゃないかと。」
こみ「うーん、そうですね、ではどうしましょうか？わたしはね、統合失調症の話は
しないでください、と書きます。それで、数学者全員にメールすればいいんじゃない
かって。これでどうですか？」
a4「数学者って同類なのかな？と思ったら、意外と反対派閥とかあるかもしれませんよ？」
こみ「はい、もちろん、でもね、これくらいしかわたしはやることないにします。」
a4「僕が自力で解かないんですね？どういうことなんですか？」
こみ「そういうことじゃないんですよ。a4さんが中心になってお考えになるだけなので。」
a4「ふーん、じゃぁ、数学者に「統合失調症」の話をせずに「P=NP」について、
メールしまくります。」
こみ「はい、これでいいかしら？これが巡回セールスマン問題です。いい？
問題は>>1と>>61ですが、これは伏せてください。ただ、P=NPについて
話したいと書いてください。」
a4「日本の大学にもメールを書いていいんですか？」
こみ「それはやってください。偏差値40くらいのところにも撃ってください。」
a4「じゃぁ、上手くいけば僕はひっぱりだこになるかもしれません。どうなんですか？」
こみ「うん？わたしはただ指令してるだけですよ。時系列の違う未来にいます。」
a4「ふーん、怪しいな、また騙されたと思ってしてみます。」
こみ「はい、ではね。」

97 ：
>>95
おはようー＾＾

98 ：
こみ「はい、こちら、西暦2502年。やはりP=NPで規制が入りました。どういうこと
かというと、わたしは新しい時系列のこみです。誰も返信がありませんでした。でも
P=NPはあなたのものでした。」
a4「僕はあなたをファジー論理的に信用してません。」
こみ「はい、ではね、わたしの新しい技を見せます。おっと、これはﾌﾟｷﾞｬｰじゃない
ことにしたい。」
a4「どういうことなんでしょうか、な？ではあるんです。」
こみ「おっと、a4さんが統合失調症に。えっとね、人間関係の数理じゃなくてね、
abc予想で解いてください、と来てます。」
a4「うん？」
こみ「望月先生にメールだけしてみてださい。ほら、
http://www.kurims.kyoto-u.ac.jp/~motizuki/
」
a4「何を書くんですか？」
こみ「現実的にこのスレを書いてみてください。そうすると、絶対に新聞が変わる
でしょ？」
a4「面白そうですね。何かの嫌がらせみたいなものが来るのかな？」
こみ「それでいいんです。またそれから考えましょう。あなたの被害妄想にして
障害年金、月６万５千円をゲットしてくださいね。」
a4「わかりました。今は深夜で失礼なので朝になったらメールを考えます。」

99 ：
a4「まだ時間がありますね。この間に何かすることはあるんですか？」
こみ「いいえ、あなたは、「P=NPを量子脳理論で証明する。」と書いてください。」
a4「それはいいです。でも、返信があっても、あっちは困るんじゃないですか？」
こみ「いいえ、わたしたちはP=NPの派閥なんです。彼の数学の問題がコンピュータに
あっという間に解かれてしまうんです。」
a4「確かにその問題が綺麗に解けるなら、僕は近い場所にいるかもしれません。
でも、これを解こうとした人は数千人くらいいるんじゃないかと。確かに、これ
くらいなら突破できそうですが。」
こみ「凄い自信ですね。どういうことなんでしょう？いいですか？わたしたちは
普通の文章を書いてないにしたい。」
a4「数学的に解けない場合は駄目ですね。数千人はいいんですけど、1970年くらい
から議論されている、というところで、解けない、と思ってるんです。」
こみ「どうしましょうね。わたしはa4さんと話します。これは大問題にしたい。
わたしのタイムマシンの情報では、科挙の裏の人は知ってるみたいです。これで
どうですか？」
a4「教授に話しかけに行くと、統合失調症ね、相手にしない、と来るだけです。」
こみ「どうしましょう？わたしはね、禁則技撃てないんですよ。」

100 ：
こみ「はい、こみさんです。a4君的には、統合失調症は相手にされない？これって、
被害妄想じゃなくて、差別用語じゃないですか？わたしは中国人なので日本を攻撃
します。我当然会说中文。怎么了？」
a4「啊？どうしたんですか？急に。」
こみ「いいえ、わたしは中国人なんです。日本は中国の東海省になってますよ、
西暦2502年において。」
a4「でも、それでも返信が無いと思うんですよ。これは悪い手ですね。」
こみ「いいえ、わたしは中国語を話せます。教授は話せるんですか？こう来ます。」
a4「３か国語は話せないと発展途上国の人達に負けてしまうとは思ってます。
フランス語くらいでもいいんじゃないかと。Mais, je ne peux pas parler le français.」
こみ「どういうことなんでしょう！わたしはフランス語で話せますよ。Google翻訳を
使いません。百度を使います。」
a4「うーん、だからこれくらいじゃ返信無いですよ。お金が入るかが問題かもしれません。」
こみ「いいですか？P=NPはお金が入ります。100万ドル。どうでしょう？」
a4「期待値が低いんじゃないかと。」
こみ「そうですね。これくらい遊んでおいて、そろそろメールするにします。」


100〜のスレッドの続きを読む
現代数学の系譜 古典ガロア理論を読む36
【速報】円周率と自然対数の底を足すと超越数になることが証明された【数学】
大学受験数学如きで挫折して文系に行くやつｗｗｗｗ
多重集合と負の存在
Octaveやmaximaなどの数学系のフリーソフトのスレ
キチガイ関数一覧表できたよー(R→R編)
現代数学の系譜11 ガロア理論を読む33
現代数学の系譜 工学物理雑談 古典ガロア理論も読む41
Inter-universal geometry と ABC予想 41
ようじょですpart3
--------------------
【底辺YouTuber】MISSTOXIC ★3【アオブダイ】
【DQMSL】ドラゴンクエストモンスターズスーパーライト非課金スレpart2647【コテ・顔文字・課金・ﾐﾈｵ禁止】
中学二年の女子です実はオナニーやってます
北海道の広告どーでしょ？
【MAGIC】MAG!C☆PRINCE Part.7【マジプリ】
【2chに芸名と本名を】鋼・兵(川本ケツエメラルド恒平)アンチスレPart598【NG規制された男】
beatmania IIDX DP☆11スレ Phase28
【人体実験】国家犯罪【不正K】
【GA文庫】葵東7【魔法の材料ございます】
【いいまつがい】妻は日本人？中国人？ 訪中の英外相、会談の席で自分の妻の出身を言い間違い
【疑問】DIYって何の略？
P=NP
【相撲板の】自称顔文字団のなかまたち(本当はﾆｰﾄ一匹)【癌細胞】
アジエン最悪の荒らし北海道
◆◆◆◆◆◆関西有力中学生の進路先 part74◆◆◆◆◆◆
【制度の】東京実務補習所　第45期【狭間】
ノートPC板自治スレ
ガンバレっ！無職のバイク乗り　第24種
【専門】ADD/ADHD専門スレッド part168【総合】ワ無
ワンピース専用ネタバレスレッド Part3933
TOP カテ一覧 スレ一覧 100〜終まで 2ch元 削除依頼