24/03/10 00:44:27.04 r6IwIycH.net
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に属するという因果関係が成り立つ。よって題意は示された。