・クラスPとは、決定性チューリング機械において、多項式時間で判定可能な(Yes/No)問題のクラスである。
・クラスNPは、Yesとなる証拠が与えられたとき、多項式時間で検証が可能な(Yes/No)問題のクラスである。
・クラスPとクラスNPが等しくないという予想を「P≠NP予想」という。
こんな証明を考えた。
記述計算量において、
Pは「最小不動点演算子を持つ一階述語論理」で、
NPは「存在量化二階述語論理」であらわされる。
「最小不動点演算子を持つ一階述語論理」の無矛盾性を
「存在量化二階述語論理」で証明できれば、
ゲーデルの第二不完全性定理より、
「最小不動点演算子を持つ一階述語論理」より
「存在量化二階述語論理」が大きいと言えるから、
P≠NPも言えるのではないか。
どうなんだろうなあ〜
