[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
59: a4 ◆L1L.Ef50zuAv 2020/04/02(木)05:00:29.10 ID:gWEkLHdd(6/21) AAS
こみ「わたしね、a4君にP=NPを解いてもらいたいなー、と勘違いしてません。
あなたが解いてください。」
a4「うん？今の時代にP=NPに本気で挑戦してる人なんていないので案外いけるかも
ですけどね。でも、挑戦してきた人達は量子コンピュータへ行ってますよ。」
こみ「あなたも嘘つくんですね。」
a4「何が？え？わー、助けてー！！！」
こみ「いいですか。大澤先生！これはあなたを統合失調症にするための言葉です。
では、ヒント、わたしが答えを出します。まず、１つずつ挿入ソートのようなもの
ではないことにしてください。>>1は嘘なんですが、伏線があります。」
a4「では、どのような解法なんですか？」
省15
81: a4 ◆L1L.Ef50zuAv 2020/04/03(金)04:22:17.10 ID:AwuvZqE1(6/15) AAS
2dimentional-grid-a4-TSPについて考えてます。finiteじゃないです。距離が長いもの
を整頓するアルゴリズムを使えば、大きさをO(n^2)くらいに落とせるのではないかと
考えてます。
あと、自明な反例を探索するのではなく、クラスタの中にある一様乱数のような
ノード群を考えてます。これならnCm(mはnより十分小さい)くらいで近傍で種
から植物を生やすような方法で解けるんじゃないかと。これも真か偽かは自明まで
いかないですね。m-1のとき、繋がってなくて、mの時にpathが作れるように
なると、そこからの探索数が指数関数時間になってしまいそうですが、三角不等式
で自明な悪いエッジを消す計算をします。
じゃぁ、a4-TSPって意味あるの？ですが、未来人は、「証明と関わる。」と主張
省2
251: 2020/09/09(水)22:57:34.10 ID:IR7822fG(1) AAS
なるほど
277: a4 ◆L1L.Ef50zuAv 2021/03/11(木)17:56:01.10 ID:qN6xr1Yb(17/24) AAS
不等号間違い。
N_C_2*(N^2+*(N/16)^2+…+(N/N)^2)
≦N^2*N^2*N
=N^5
378: 2021/08/04(水)21:07:35.10 ID:AeD9Lip/(2/3) AAS
量子コンピュータだと、同じ8でも、生成速度が異なったりするもんなのでしょうか？
よく分かっていないので…。
425(1): 2022/12/28(水)09:58:43.10 ID:iwRe5JxU(1) AAS
量子コンピュータと古典コンピュータが実現可能な計算量のクラスが異なる
という証明は今のところ得られていない。
古典コンピュータで素因数分解が困難（準指数つまりビット数の指数よりは
弱いが、多項式では無いのが現状知られている最良の算法）であるといっても、
将来、多項式計算量の素因数分解の算法が登場しないことは証明されていない。
算法に限らずなにかが決して存在しないことを証明するのは極めて難しいことは
普通である。将来ある日、誰かが多項式のオーダーの算法を発見し示すかもしれない。
でもそれがもしもｎビットの整数に対してO(ｎの10000乗）だったりしたなら
いちおう多項式オーダーではあってもガッカリだろうがね。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.022s