ミレニアム懸賞問題 (635ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
224: ◆Ph05QxAcng [] 2024/01/25(木)03:11 ID:mbHgJ8YD(1/4)
また書き直しましたが今度こそ出来たはず
睡眠時間ってよかった
直した所は補題の状態2です。
命題
計算問題があり、その問題の計算量のクラスと一致するアルゴリズムは存在する
証明
まず次の補題を示す。
補題
全ての真である証明問題は時間を無限大にいくらでも大きく限り無く発散させる(∞^nでnをいくらでも大きく取る)と、解けた問題の割合は1に収束する。
証明
もし1に収束しない場合の状態を考える。
状態1
一つの状態はその命題は解けない事を意味するので前提から命題を導く論理的経路が存在しない事を意味する。これは前提に矛盾する。
状態2
もう一つの状態は証明の論理は存在するが、解かれる事がないというパターンが考えられる。
状況をまとめると、命題が真である、という情報が与えれており、しかし、時間を極限まで経過させても絶対にその証明が具体化しないとする。これが矛盾する事を示す。
今仮にその命題が真である条件が欠けた状態では、証明が具体化していないのだが、しかし、存在するのだ。つまり、我々人間は証明を認識していないので証明の存在は成立していない、という矛盾した状況になっている。よって必ず証明は具現化する事になる。よって全ての真である命題は解かれるので、仮定した状況は矛盾する。
すなわち状態1,2ともに矛盾する事が導かれた。よって、全ての真である証明問題は全て時間を極限まで発散させた時、その解けた問題の割合は1に収束する。
今仮に命題が成立しないと仮定すると、問題の解法となるアルゴリズムは全て問題のクラス一致しない、小さいクラスである問題aが存在して、そのアルゴリズムをa’と置く。
この時問題aを無限に生成するプログラムAが作成出来る。
今問題を無限に作成するプログラムがあって、その作成した問題を全て解くようにして、解いた問題の全体の割合をrと置く。
Aの場合、時間を∞^nとしてnをいくら大きくとっても0に収束する。
全ての真である証明問題の集合をPと置き、全ての計算問題の集合をpと置いた時、P⊃pであり、これは補題に矛盾する。
よって命題は示された。
系
P=NPが成り立つ。
225(1): ◆Ph05QxAcng [] 2024/01/25(木)17:42 ID:mbHgJ8YD(2/4)
書き直しました
命題
全ての計算問題に対して、その問題の計算量のクラスと一致するアルゴリズムは存在する
証明
まず次の定理を示す。
定理
全ての真である命題の証明は必ず現実化する
証明
存在と輪郭が同値であり、輪郭と波動(包含関係⊇)が同値であり、包含関係と因果関係(論理→）が同値である。よってこの目に見える現実の物理空間=存在を最前提に置いてそれ以降の全てが表現される。つまりこの世界の本質は目に見える空間であるとしても良い。よって全ての真である命題の証明が存在するのであれば、目に見える空間に存在しないと矛盾する。よって定理が示された。
系
全ての真である証明問題は時間を無限大にいくらでも大きく限り無く発散させる(∞^nでnをいくらでも大きく取る)と、解けた問題の割合は1に収束する。
今仮に命題が成立しないと仮定すると、問題の解法となるアルゴリズムは全て問題のクラス一致しない、小さいクラスである問題aが存在する。
この時問題aを無限に生成するプログラムAが作成出来る。
今問題を無限に作成するプログラムXがあって、その作成した問題を全て解くようにして、解いた問題の全体の割合をr(X)と置く。
Aの場合、時間を∞^nとしてnをいくら大きくとってもr(A)は0に収束する。
全ての真である証明問題の集合をPと置き、全ての計算問題の集合をpと置いた時、P⊃pであるので、これは系に矛盾する。
よって命題は示された。
系
P=NPが成り立つ
226: ◆Ph05QxAcng [] 2024/01/25(木)19:03 ID:mbHgJ8YD(3/4)
>>225
これで完璧です
227: ◆Ph05QxAcng [] 2024/01/25(木)19:05 ID:mbHgJ8YD(4/4)
今日は寿司でも食べてきます
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.030s