ミレニアム懸賞問題 (635ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
290(1): ◆Ph05QxAcng [] 2024/03/10(日)00:44 ID:r6IwIycH(1/3)
P=NPの証明(修正)
命題
全ての計算問題に対して、その問題の計算量のクラスと一致するアルゴリズムは存在する
証明
まず次の定理を示す。
定理
全ての真偽の判定可能である命題の証明は必ず現実化する
証明
まず3つの補題を示す。
補題1 輪郭を定める条件は包含関係⊇が可換になった時である
証明
形のわかっているAがあって、形のわからないAがあったらBの形状を定めるのにはA⊇BかつB⊇Aを示せれば形は定まる。
系1.1 存在概念と包含関係は同値である
証明
存在概念と空間は同値。また明らかに空間から包含関係は導かれる。そして包含関係から存在=空間は導かれる。
補題2 包含関係⊇と対応関係→は同値である
証明
包含関係A⊇Bが成立しているならば、対応関係A→Bは成立している。逆に対応関係A→Bが成立しているとする。この時、存在するならば全て空間に要素がある事、及び系1.1より空間に要素がある事の前提に包含関係がある事が示されているので題意は示された。
補題3 包含関係⊇と因果関係→は同値である
証明
因果関係A→Bを一般化したものが対応関係A→Bである。すなわち因果関係の前提に対応関係がある。また、明らかに因果関係が存在した場合、系1.1より空間に要素があるので包含関係が導かれる。次に包含関係から因果関係が導かれる事を示す。A⊇Bが成り立っている時、BならばAに属するという因果関係が成り立つ。よって題意は示された。
291(1): ◆Ph05QxAcng [] 2024/03/10(日)00:45 ID:r6IwIycH(2/3)
>>290
次に定理の証明を与える。
存在と輪郭が同値であり、輪郭と波動(包含関係⊇)が同値であり、包含関係と因果関係(論理→）が同値である。よってこの目に見える現実の物理空間=存在を最前提に置いてそれ以降の全てが表現される。つまりこの世界の本質は目に見える空間であるとしても良い。よって全ての真である命題の証明が存在するのであれば、目に見える空間に存在しないと矛盾する。よって定理が示された。
系
全ての真である証明問題は時間を無限大にいくらでも大きく限り無く発散させる(∞^nでnをいくらでも大きく取る)と、解けた問題の割合は1に収束する。
292(1): ◆Ph05QxAcng [] 2024/03/10(日)00:45 ID:r6IwIycH(3/3)
>>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が成り立つ
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.409s*