>>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が成り立つ