ミレニアム懸賞問題 (513ﾚｽ)
上
下
前
次
1-
新
220
:
◆Ph05QxAcng
2024/01/24(水) 02:16:51.70
ID:7S6i2RWV(2/5)
調
AA×
[240|
320
|
480
|
600
|
100%
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
220: ◆Ph05QxAcng [] 2024/01/24(水) 02:16:51.70 ID:7S6i2RWV まとめです 命題 計算問題があり、その問題の計算量のクラスと一致するアルゴリズムは存在する 証明 まず次の補題を示す。 補題 全ての真である証明問題は時間を無限大にいくらでも大きく限り無く発散させる(∞^nでnをいくらでも大きく取る)と、解けた問題の割合は1に収束する。 証明 もし1に収束しない場合の状態を考える。一つはその命題は解けない事を意味するので前提から命題を導く論理的経路が存在しない事を意味する。 もう一つは証明の論理は存在するが、解かれる事がないというパターンが考えらえるが、これは証明が存在し、それが具体的に開示されている定理の存在と比較すると、その存在が開示されている定理と開示されない定理が両方とも存在するのは一貫性がない、無矛盾性に反する。 よって、全ての真である証明問題は全て時間を極限まで発散させた時、その解けた問題の割合は1に収束する。 今仮に命題が成立しないと仮定すると、問題の解法となるアルゴリズムは全て問題のクラス一致しない、小さいクラスである問題aが存在して、そのアルゴリズムをa’と置く。 この時問題aを無限に生成するプログラムAが作成出来る。 今問題を無限に作成するプログラムがあって、その作成した問題を全て解くようにして、解いた問題の全体の割合をrと置く。 Aの場合、時間を∞^nとしてnをいくら大きくとっても0に収束する。 全ての真である証明問題の集合をPと置き、全ての計算問題の集合をpと置いた時、P⊃pであり、これは補題に矛盾する。 よって命題は示された。 系 P=NPが成り立つ。 http://rio2016.5ch.net/test/read.cgi/math/1668766352/220
まとめです 命題 計算問題がありその問題の計算量のクラスと一致するアルゴリズムは存在する 証明 まず次の補題を示す 補題 全ての真である証明問題は時間を無限大にいくらでも大きく限り無く発散させるでをいくらでも大きく取ると解けた問題の割合はに収束する 証明 もしに収束しない場合の状態を考える一つはその命題は解けない事を意味するので前提から命題を導く論理的経路が存在しない事を意味する もう一つは証明の論理は存在するが解かれる事がないというパターンが考えらえるがこれは証明が存在しそれが具体的に開示されている定理の存在と比較するとその存在が開示されている定理と開示されない定理が両方とも存在するのは一貫性がない無矛盾性に反する よって全ての真である証明問題は全て時間を極限まで発散させた時その解けた問題の割合はに収束する 今仮に命題が成立しないと仮定すると問題の解法となるアルゴリズムは全て問題のクラス一致しない小さいクラスである問題が存在してそのアルゴリズムをと置く この時問題を無限に生成するプログラムが作成出来る 今問題を無限に作成するプログラムがあってその作成した問題を全て解くようにして解いた問題の全体の割合をと置く の場合時間をとしてをいくら大きくとってもに収束する 全ての真である証明問題の集合をと置き全ての計算問題の集合をと置いた時でありこれは補題に矛盾する よって命題は示された 系 が成り立つ
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 293 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
ぬこの手
ぬこTOP
0.045s