[過去ﾛｸﾞ] 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)で複素数なら解はありました。
37: a4 ◆L1L.Ef50zuAv 2020/03/31(火)16:18 ID:/0OHc4N+(17/27) AAS
じゃぁ、正方形の頂点をくっつけるようにするんじゃなくて、全てのノードを最初から
複素数で決めて置いて代入ソートのようにしていくと、正方形の頂点を構成した時点で
正方形ではなく、１＋０＋１＋√２、なんじゃないかと。
38: a4 ◆L1L.Ef50zuAv 2020/03/31(火)16:40 ID:/0OHc4N+(18/27) AAS
やっぱり難しいですね。
x=0からx=2までの最短経路は自明なんですが、x=1+iのような点が入ってくると
いうのを後の問題にはできないですね。
やはり「このクソスレは終了しました」になるのか？ですが、まだ続けます。
39: a4 ◆L1L.Ef50zuAv 2020/03/31(火)16:47 ID:/0OHc4N+(19/27) AAS
このスレが続く理由はまだ>>1の方法が倒れてないんですよ。このa4-TSPが一般化
されたグラフでないために、NP完全であるということがまず示せてないんです。
40: a4 ◆L1L.Ef50zuAv 2020/03/31(火)16:50 ID:/0OHc4N+(20/27) AAS
>>1のa4-TSPが、NP完全でないと証明されたり、NP完全であっても１つのエッジを
２つのエッジ以外の反例がある、ということが示されたら、基本的にこのスレは
終了かもしれません。
41: a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:01 ID:/0OHc4N+(21/27) AAS
Wikipediaをとりあえず見てます。すると、
「都市間の移動コストが三角不等式を満たす、すなわち移動コストを距離と呼べる
部分問題（あるいは制約つき問題）も、NP困難である。都市を平面上の点、都市間
の距離を平面上のユークリッド距離とする部分問題は最も直感的で理解しやすいが、
これも NP困難である。」
とあります。NP完全であるということが証明されていなくて研究は終わったかの
ような口調で書かれてあります。
僕はここで医学的妄想で未来と通信することにします。
42: a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:07 ID:/0OHc4N+(22/27) AAS
未来に聞いたら、「NP完全だ！」と返りました。普通に考えれば、HCがNP完全なので、
a4-TSPもNP完全じゃないかと。
43: a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:17 ID:/0OHc4N+(23/27) AAS
なんか夢に出てきた伏線かな？と妄想してるのは、普通にTSPを２次元などで書くと、
エッジに数字がついたりして三角不等式の問題も出てきてしまうんです。a4-TSPなら、
距離を明確に図で書いてるので、証明もしやすいのかな？と。
44(1): a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:49 ID:/0OHc4N+(24/27) AAS
ｎ次元の頂点は複素数ではないので全てに三角不等式が成り立つとすると、新しい
ノードも加えて最短経路を作った時、そのノードの２つのエッジから、そのノードを
取って１つのエッジにくっつけるという操作をすると、距離が縮まるから、その時の
最短経路を出す時は、他のエッジを動かさなくてもいい。他のエッジが動くとすると、
そっちが最適解になる。だから、最短経路に１つ１つノードを付け足していけばいいん
じゃないかと。これで証明終わり？？？
45: a4 ◆L1L.Ef50zuAv 2020/03/31(火)17:53 ID:/0OHc4N+(25/27) AAS
>>6さんに聞いてみます。これくらいで、まだ明らかな数学的な欠陥のあるところが
ありますか？無ければ論文として纏めようと思います。
誰かが来るまで、休みとして、スペイン語とかを勉強します。
46: a4 ◆L1L.Ef50zuAv 2020/03/31(火)18:12 ID:/0OHc4N+(26/27) AAS
やっぱり>>44の証明が数学っぽくないから間違ってるのかな？スペイン語をやめて
また考えることにします。
47: a4 ◆L1L.Ef50zuAv 2020/03/31(火)18:32 ID:/0OHc4N+(27/27) AAS
今、考えてるのは、ノードを付け足した最短経路から、そのノードを取ると、
(1)-(2)-(new)-(3)-(4)
から、
(1)-(2)-(3)-(4)
じゃなくて，
(1)-(2)-(5)…(6)-(3)-(4)
などと最短ルートが変わるケースです。まだ証明できてないですね。
48: a4 ◆L1L.Ef50zuAv 2020/04/01(水)00:18 ID:b/ntKAk5(1/4) AAS
ずっと考えてます。まずWikipediaの「三角不等式が成り立つ TSP については
多項式時間近似アルゴリズムが数多く存在する。」の情報は重いです。単純には
証明できませんでした。僕は>>1の２次元のa4-TSPを追ってます。すると、
１つのノードを付け加えた時に増える距離は、min{2|x[n]-x[i]|+2|y[n]-y[i]|}
と出てきました。a4-TSPでの距離において、この項は最大でO(n)個ですね。
１，２，３，４，５と増えていくので、単純に考えると、O(n!)ですが。すると
これだけだと、足し算される時、値が、３＋５＝８という順と５＋２＝７
という順の反例を思いつきました。でも、追加される選ぶ値の集合は、５と２に
おいて考える時、変わらないため、前者で３＋２＝５と、なるんじゃないかと。
そうすると、やはりこのアルゴリズムでいいんじゃないかと。厳密な証明は
省1
49: a4 ◆L1L.Ef50zuAv 2020/04/01(水)06:15 ID:b/ntKAk5(2/4) AAS
現実的にはまだずっと解いてます。
まず、さっきのは２次元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: a4 ◆L1L.Ef50zuAv 2020/04/01(水)09:49 ID:b/ntKAk5(3/4) AAS
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(1): 2020/04/01(水)19:57 ID:/DGEf2gH(1) AAS
俺はP≠NPを確信している側
今は関連理論を作っていて、そこから派生的に証明できると思っているけど、単なる実例よりも
相当高い抽象化をしないと証明にはならないと思ってる
52: a4 ◆L1L.Ef50zuAv 2020/04/01(水)22:25 ID:b/ntKAk5(4/4) AAS
>>51
今、起きました。ご連絡ありがとうございます。僕もP≠NPだと思ってたんですけどね。
P=NPだ！って幻聴が聴こえてくる精神病なんですよ。僕は博士ではありませんが、
数学とか計算機科学とかは知ってるつもりなので、証明は可能ならばきちんと書く
つもりですよ。幻聴って何かな？ってことですが、複雑な量子脳理論、と書くと、
よくわからなくなるんじゃないかと。証明を直接聞くのは非常に難しいので、曖昧な
２分木アルゴリズムとかで、証明にかかる計算量を対数くらいにすると医学的妄想？
をしてます。
53: a4 ◆L1L.Ef50zuAv 2020/04/02(木)00:11 ID:Z3POr1Or(1) AAS
医学的妄想でタイムトラベルしてます。すると、未来人は、P=NPの証明に関して、
a4-TSPの頂点をギリギリ含む超直方体に１点を追加して新しい超直方体を考える、
ということを考えれば、自明なんじゃないかって。僕もあまり信じてませんが、
証明か反証を今から考えます。
54: a4 ◆L1L.Ef50zuAv 2020/04/02(木)00:18 ID:gWEkLHdd(1/21) AAS
反証を考えてみました。２次元において、大きい５角形の中に小さい５角形がある
というのを考えると、最短経路に凹のような構造ができてしまうんじゃないかと。
まだ未来と通信とかしながら研究を続けます。
55: a4 ◆L1L.Ef50zuAv 2020/04/02(木)01:31 ID:gWEkLHdd(2/21) AAS
タイムマシンで時空のループが作られることによる嫌がらせの問題を解きながら未来と
通信しています。意外にも、ここまで来て、ようやくプログラムを書いて、モンテカルロ
のように実験しなさい、と。じゃぁ、多項式時間じゃないのか？ですが、現実的には、
Wikipediaの「巡回セールスマン問題」には、「三角不等式が成り立つ TSP については
多項式時間近似アルゴリズムが数多く存在する。 」とあります。今から作業をします。
56: a4 ◆L1L.Ef50zuAv 2020/04/02(木)01:52 ID:gWEkLHdd(3/21) AAS
Wikipediaの「クリストフィードのアルゴリズム」というのを見てます。「2015年現在、
距離空間における巡回セールスマン問題に対する多項式時間アルゴリズムの中では、
近似度が最良であるアルゴリズムである（一部の特殊な場合では、より良い近似度が
存在する事も知られている）。 」とあります。近似なのかは数が多くなるとわかり
ません。これだけ見るとP=NPみたいだな、と。問題は証明です。このスレは僕の
妄想が終わらない限り続きます。
57: a4 ◆L1L.Ef50zuAv 2020/04/02(木)04:40 ID:gWEkLHdd(4/21) AAS
>>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 ◆L1L.Ef50zuAv 2020/04/02(木)04:46 ID:gWEkLHdd(5/21) AAS
a4「じゃぁ、タイムテレパシーの妄想未来人に聞いてみます。こみさん、嘘をついて
いたんですか？」
こみ「いいえ、わたしはあなたに指南書を送っただけです。まだ研究は続けてくださいね。」
a4「じゃぁ、>>1の方法は間違ってるんですか？」
こみ「そういうことじゃないんですよ。あれは嫌がらせなんです。わたし１つ言っていい？
あれは未来になってからわかるにしたい。」
a4「これじゃぁ、僕の統合失調症じゃないですか。こんな難問解けると思ってません。
タイムマシンの力無しに。第一、タイムマシンがあるなら、僕が解けるかわかるじゃ
ないですか。」
こみ「そういうことじゃないんですよ。タイムマシンの攻防戦があると言ったのは
省11
59: a4 ◆L1L.Ef50zuAv 2020/04/02(木)05:00 ID:gWEkLHdd(6/21) AAS
こみ「わたしね、a4君にP=NPを解いてもらいたいなー、と勘違いしてません。
あなたが解いてください。」
a4「うん？今の時代にP=NPに本気で挑戦してる人なんていないので案外いけるかも
ですけどね。でも、挑戦してきた人達は量子コンピュータへ行ってますよ。」
こみ「あなたも嘘つくんですね。」
a4「何が？え？わー、助けてー！！！」
こみ「いいですか。大澤先生！これはあなたを統合失調症にするための言葉です。
では、ヒント、わたしが答えを出します。まず、１つずつ挿入ソートのようなもの
ではないことにしてください。>>1は嘘なんですが、伏線があります。」
a4「では、どのような解法なんですか？」
省15
60: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:16 ID:gWEkLHdd(7/21) AAS
a4「また反例を見つけました。(0,0)(1,0)(2,0)(3,0)。これでは種まきアルゴリズムは
使えませんね？(3,0)-(0,0)が届きません。どうですか？こみさん。」
こみ「いいえ、あなたはまだ序章をやってるだけです。アルゴリズムは複雑ではない
ですよ？いいか、量子コンピュータではないんですよ？」
a4「うん？やっぱりこみさんは嘘つきだ！序章なのに複雑でないとか。やっぱり
僕の統合失調症だ！」
こみ「そうではありません。ではね、もうちょっと複雑な技を撃つにしたい。これです。」
61(6): a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:16 ID:gWEkLHdd(8/21) AAS
707a4 ◆L1L.Ef50zuAv 2020/03/28(土) 09:37:43.32ID:rbQUI3W10
今日はタイムスリップやタイムテレパシーじゃなくてタイムリープしました。２歳の
誕生日に。叔母と一緒にいたのですが、宇宙人が現れて、Ｐ＝ＮＰの証明が、
巡回セールスマン問題のような図と一緒に日本語で５文ほどで書かれてありました。
僕は２歳なのに頭が良くなっていたということですが、どうして叔母がここまで
嫌らしく反撃できるんだろう？と。そこにいた女性の先生は「ベクトルなんて難しい
ものは使わないでください。」と怒ってました。ノーベル賞の裏の人達５人に、
１年ごとに別の美味しい植物が実る種を分け与えなさい、と言われて行こうと
思ったのですが、先にタイムリーパーが「それ欲しい」と来たので信頼できると
考えて先にあげると、夢から覚めました。
62: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:20 ID:gWEkLHdd(9/21) AAS
こみ「ほら、あなたは２歳の頃に解けていたんではないですか？」
a4「うん？だから、それは夢じゃないですか？」
こみ「あなたは夢が量子脳理論であると主張しています。どうですか？」
a4「僕はP=NPが>>1ですぐ解けると思っていました。でも嘘であると。ファジー
論理的に上手くあなたを信用できません。」
こみ「それでいいんです。では、情報はこれだけです。すなわち、>>61です。
これを信じてやってくださいね。」
a4「うん？だから(3,0)-(0,0)で反証したじゃないですか！？」
こみ「いいえ、あなたはまだ分かってないんです。どうしたことか。そういえば、
わたしは未来を知っています。例えば、」
63: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:21 ID:gWEkLHdd(10/21) AAS
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.」
省5
64: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:27 ID:gWEkLHdd(11/21) AAS
こみ「ほら、今日は「Saluton.」=（去る東大オン！）=(去る、東（京）、大（阪）、オン！）
となりました。これで未来予知できましたね。では、わたしはもうちょっと複雑な技を
撃つにします。西暦2040年に今日あなたは行きましたね。どうでしたか？」
a4「今日？夢で行ったよ。数学のテストを受けたら、教科書から数学書の名前を
ただ書き写すだけの。占いの中国の女性に話しかけられたら、結婚がどうとか
言われたけど、今の時代にいないような頭の悪さだったのに殺されそうで危なそう
だったから、テレパシーで量子コンピュータを使って女性の神経構造を変形させ
たら、女性は「着火（ちゃっか）」って日本語で叫んでました。」
こみ「ほら、未来へ行ったじゃない？」
a4「だから、それを証明するためにP=NPを解こうとして解けなかったんです。」
省3
65: a4 ◆L1L.Ef50zuAv 2020/04/02(木)06:59 ID:gWEkLHdd(12/21) AAS
a4です。こみさんは一旦下りてますが、巡回セールスマン問題をWikipediaで見ると、
全てのノードを訪れるだけで、出発地に戻らない図が載ってますね。でも、証明など
が載ってないので、そこから考えることにします。
66: a4 ◆L1L.Ef50zuAv 2020/04/02(木)08:43 ID:gWEkLHdd(13/21) AAS
SATISFIABILITY→3SAT→VC→HC→TSP→a4-TSP
ということですが、VC→HCの証明は再理解したんですが、単純にここから、
「出発地点に戻らないTSP」のNP完全性の証明は難しそうですね。
67: a4 ◆L1L.Ef50zuAv 2020/04/02(木)08:47 ID:gWEkLHdd(14/21) AAS
もちろん、出発地点が決まっていないものを考えてるんですよ。出発地点が決まってる
ものは、そこからの長さを無限大に飛ばせばいいだけなので。きちんとは調べていない
というか、すぐには検索しても出てきませんが、NP完全性は偽なのかもしれません。
上下前次1-新書関写板覧索設栞歴
あと 361 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.023s