[過去ﾛｸﾞ] P=NP (428ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
421: 2022/12/04(日)19:27 ID:qSy4xMaG(1) AAS
>>420
＞だが囲碁が先手必勝か後手必勝か？
コミなしなら先手必勝ですよ…
422: 2022/12/11(日)08:19 ID:8wm/VM70(1) AAS
江戸時代に、五目並べについては既に先手必勝であることが発見されていて
そのことが出版されていたそうである。
ただしその五目並べとは、先手の三三、四四が禁止、
という禁則が無い素朴なルールの場合。
必勝法はかなり複雑に場合を列挙して得られるという。
423: 2022/12/21(水)20:46 ID:F669Iarw(1) AAS
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
画像ﾘﾝｸ[jpg]:i.imgur.com
省2
424: 2022/12/27(火)18:32 ID:YAXXW04M(1) AAS
P≠NP予想って量子コンピューターや量子暗号が実現しても意味を持ちますか？
425(1): 2022/12/28(水)09:58 ID:iwRe5JxU(1) AAS
量子コンピュータと古典コンピュータが実現可能な計算量のクラスが異なる
という証明は今のところ得られていない。
古典コンピュータで素因数分解が困難（準指数つまりビット数の指数よりは
弱いが、多項式では無いのが現状知られている最良の算法）であるといっても、
将来、多項式計算量の素因数分解の算法が登場しないことは証明されていない。
算法に限らずなにかが決して存在しないことを証明するのは極めて難しいことは
普通である。将来ある日、誰かが多項式のオーダーの算法を発見し示すかもしれない。
でもそれがもしもｎビットの整数に対してO(ｎの10000乗）だったりしたなら
いちおう多項式オーダーではあってもガッカリだろうがね。
426: 2023/01/03(火)23:15 ID:I9MG9VgR(1/2) AAS
>>425
AKS素数判定法は？
427: 2023/01/03(火)23:21 ID:I9MG9VgR(2/2) AAS
P=NPが証明されても全てNP問題の多項式時間アルゴリズムそのものが直ちに発見されるわけではない
発見されても多項式の定義からnの１０兆乗でも多項式時間アルゴリズム、
1.0000.......1のn乗でも指数時間アルゴリズム
というわけでこの問題にはあまり意味がないというのがクヌースの主張ですか？
428: 2023/08/17(木)01:35 ID:2S37FtHC(1) AAS
…－y( ￣д￣).｡o○
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.784s*