[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
52: a4 ◆L1L.Ef50zuAv 2020/04/01(水)22:25:24.57 ID:b/ntKAk5(4/4) AAS
>>51
今、起きました。ご連絡ありがとうございます。僕もP≠NPだと思ってたんですけどね。
P=NPだ！って幻聴が聴こえてくる精神病なんですよ。僕は博士ではありませんが、
数学とか計算機科学とかは知ってるつもりなので、証明は可能ならばきちんと書く
つもりですよ。幻聴って何かな？ってことですが、複雑な量子脳理論、と書くと、
よくわからなくなるんじゃないかと。証明を直接聞くのは非常に難しいので、曖昧な
２分木アルゴリズムとかで、証明にかかる計算量を対数くらいにすると医学的妄想？
をしてます。
70: a4 ◆L1L.Ef50zuAv 2020/04/02(木)10:11:33.57 ID:gWEkLHdd(17/21) AAS
NP完全とNP困難の違いをよく理解してるわけではないのですが、一応、Wikipediaで、
「NP困難」を調べると、「もし、いずれかのNP困難な問題を多項式時間で解く
アルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることに
なり、P = NP が成り立つ。 」と。「いずれか」なので、２次元TSPはいいんですが、
２次元格子a4-TSPはNP困難なのか？NP完全なのか？を考えてます。
324: a4 ◆L1L.Ef50zuAv 2021/05/05(水)07:33:49.57 ID:MQNLYPZk(8/16) AAS
a4「やっぱりうまくいかないし。n^2通りからn個を取って、n^4通りの差分を計算
しても、次はn^8通りですよ？」
名古屋の宇宙人２「待った。ここだ。そこはn^4通りだ。」
a4「？」
354(1): 2021/07/26(月)18:25:13.57 ID:BE8YOCsI(1) AAS
量子コンピュータが実現された暁には
ノーベル賞は確実と言われる人が日本にいるようですね
371: a4 ◆L1L.Ef50zuAv 2021/07/31(土)04:18:53.57 ID:VxfYR1Z+(2/4) AAS
例えば、株価が１０回連続で何故か当たった感じがして、新聞の１面にまで載ったり
したら、そのコンピュータに巡回セールスマン問題を解かせたときの答えが正しい
んじゃないかと。
380: a4 ◆L1L.Ef50zuAv 2021/08/05(木)01:04:09.57 ID:yMeo8UKN(1) AAS
>>377->>379
6と5に関しては、２進数における繰り上がりを計算する操作なので、基本的に
計算時間は同じだと思います。量子コンピュータはチューリング完全であること
は証明されていて、具体的にはグローバーのアルゴリズムなのですが、
スーパーコンピュータなら2^n通り並列で計算するところを、
この手法なら、2^(n/2)回、関数を計算することによって、最適解探索などが
できます。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.020s