ミレニアム懸賞問題 (507ﾚｽ)
上
下
前
次
1-
新
292
(1)
:
◆Ph05QxAcng
2024/03/10(日) 00:45:43.67
ID:r6IwIycH(3/3)
調
AA×
>>291
[240|
320
|
480
|
600
|
100%
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
292: ◆Ph05QxAcng [] 2024/03/10(日) 00:45:43.67 ID:r6IwIycH >>291 今仮に命題が成立しないと仮定すると、問題の解法となるアルゴリズムは全て問題のクラス一致しない、小さいクラスである問題aが存在する。 この時問題aを無限に生成するプログラムAが作成出来る。 今問題を無限に作成するプログラムXがあって、その作成した問題を全て解くようにして、解いた問題の全体の割合をr(X)と置く。 Aの場合、時間を∞^nとしてnをいくら大きくとってもr(A)は0に収束する。 全ての真である証明問題の集合をPと置き、全ての計算問題の集合をpと置いた時、P⊃pである。 計算問題が解かれるとは、次の二つが満たされる事を示す事になる。 (1)全探索より良い最良のアルゴリズムの有無の判定を行い、存在するならば最良である事を示し、存在しないならば、存在しない事を示す。 (2)存在するならば、 実際にそのアルゴリズムで解が存在の有無を確認し具体的に値を出す。 存在しないならば、全探索で解の存在の有無を確認する。 Aより作られた大量の問題の集合をEと置くと、今系よりrは1に収束するのだから、Eに対して(1),(2)の両方が示されて1に収束する⇔一つ一つの問題に対して、全てのアルゴリズムは同じであるから、一つの計算問題に対して最良のアルゴリズムは問題のクラスと一致していないといけないが、先ほど示されたのはr(A)は0に収束するので矛盾する。 すなわち命題は示された。 系 P=NPが成り立つ http://rio2016.5ch.net/test/read.cgi/math/1668766352/292
今仮に命題が成立しないと仮定すると問題の解法となるアルゴリズムは全て問題のクラス一致しない小さいクラスである問題が存在する この時問題を無限に生成するプログラムが作成出来る 今問題を無限に作成するプログラムがあってその作成した問題を全て解くようにして解いた問題の全体の割合をと置く の場合時間をとしてをいくら大きくとってもはに収束する 全ての真である証明問題の集合をと置き全ての計算問題の集合をと置いた時である 計算問題が解かれるとは次の二つが満たされる事を示す事になる 全探索より良い最良のアルゴリズムの有無の判定を行い存在するならば最良である事を示し存在しないならば存在しない事を示す 存在するならば 実際にそのアルゴリズムで解が存在の有無を確認し具体的に値を出す 存在しないならば全探索で解の存在の有無を確認する より作られた大量の問題の集合をと置くと今系よりはに収束するのだからに対しての両方が示されてに収束する一つ一つの問題に対して全てのアルゴリズムは同じであるから一つの計算問題に対して最良のアルゴリズムは問題のクラスと一致していないといけないが先ほど示されたのははに収束するので矛盾する すなわち命題は示された 系 が成り立つ
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 215 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
ぬこの手
ぬこTOP
0.040s
