命題
計算問題があり、その問題の計算量のクラスと一致するアルゴリズムは存在する

証明

まず次の補題を示す。


補題

全ての真偽の判定可能な証明問題は時間を無限大にいくらでも大きく限り無く発散させる(∞^nでnをいくらでも大きく取る)と、解けた問題の割合は1に収束する。

証明
もし1に収束しない場合、その命題は解けない事を意味するので前提から命題を導く論理的経路が存在しない事を意味するがこれは前提に矛盾する。



今仮に命題が成立しないと仮定すると、問題の解法となるアルゴリズムは全て問題のクラス一致しない、小さいクラスである問題aが存在して、そのアルゴリズムをa’と置く。

この時問題aを無限に生成するプログラムAが作成出来る。

この場合、問題のクラスと一致するアルゴリズムがある問題bの場合、実数時間を極限まで取った時、bを無限に作成するプログラムをBと置く。

今問題を無限に作成するプログラムがあって、その作成した問題を全て解くようにして、解いた問題の全体の割合をrと置く。


Bの場合、rは時間を無限大に発散させると1に収束するが、Aの場合0に収束する。

つまりこれは、Aは∞^nでnをどのように設定しても、どれほど大きな時間を用意しても解けない事を意味する。
つまり、rが0に収束する事は、どれほど大きな時間を用意しても、そのほぼ全ての真偽の判定はわからない事を意味するが、Aの性質上全て真である事がわかっている状況が生まれる。
つまり、Aの問題全てが真である事の証明となる論理的経路は存在しないが、これは補題に矛盾する。

よって命題は示された。

系
P=NPが成り立つ。