全ての命題の真偽は判定可能か否か2

24 ：◆Ph05QxAcng ：2024/01/24(水) 18:28:55.79 ID:0.net

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

証明
まず次の補題を示す。

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

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

もう一つは証明の論理は存在するが、解かれる事がないというパターンが考えられる。この場合、その収束値は1以外の値rに収束するが、これは、どんなに時間をかけても開示されない証明の経路が存在する事になるので、これは開示されている定理と比較すると無矛盾性に反する。

よって、全ての真である証明問題は全て時間を極限まで発散させた時、その解けた問題の割合は1に収束する。


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

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

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

Aの場合、時間を∞^nとしてnをいくら大きくとっても0に収束する。

全ての真である証明問題の集合をPと置き、全ての計算問題の集合をpと置いた時、P⊃pであり、これは補題に矛盾する。

よって命題は示された。

系
P=NPが成り立つ。