ゲーデルの不完全性定理からP≠NP問題にアプローチする

ゲーデルの不完全性定理からP≠NP問題にアプローチする試みがあるのだけれど、それを(私の偏った見方から)紹介してみたい。

論理学から P≠NP問題 にアプローチするやり方はいくつかあって、例えば記述複雑度を使ったやり方(以前、 Deolalikarが使っていた方法)であるとか、命題論理の証明の長さを用いた方法などがある。その中の一つが、限定算術を使ったアプローチだと思う。

さて、まず限定算術とは何かだが、論理学では自然数の公理系を算術と呼ぶことが多い。自然数の公理にはいろいろ重要なものがあるが、自然数を最も特徴付けるのは数学的帰納法の公理だと思う。この数学的帰納法をどのような言明に適応できるかで算術の体系の強さが決まる。限定算術では、数学的帰納法を適応できる言明を量化（「すべて」や「存在する」）が言及する範囲が有限
の範囲に限定されている。（ので限定という。）例えば、「$n$から$2n$の間に双子素数が存在する」という言明について数学的帰納法を使うのは良いが、「$n$以上の双子素数が存在する」に対して数学的帰納法を用いることはできない。

限定算術の何が興味をひくかというと、計算量クラスとの間に密接な関係があるからだ。特に、Bussが定義した限定算術の階層 $S^1_2 \subseteq S^2_2 \subseteq \cdots$は多項式時間階層と対応していて、Bussの階層の分離から多項式時間階層の分離へアプローチすることが試みられてきた。

では、$S^1_2 \subseteq S^2_2 \subseteq \cdots$とは何かというと、まず通常の算術に比べて幾つか基本となる関数記号を追加する。特に重要なのが$a\#b$という関数で、意味的には$2^{|a|\cdot |b|}$ ($|a|$は$a$の2進表現の長さ）を表している。この関数によって、多項式時間関数の増大度を抑えることができるようになる。この上で、Bussは数学的帰納法に使われる言明の中の量化の個数によって階層を定義する。例えば、$S^1_2$では1個の量化しか数学的帰納法の中で使ってはいけない。ちなみに2は$\#$関数が入っていることを表している。

さて、ではこのBussの階層と多項式時間階層がどうつながるかというと、｛$S^i_2$で停止性が証明できる関数｝=｛多項式時間階層のi番目の関数}という関係になる。例えば、$S^1_2$で停止性が証明できる関数は、多項式時間関数と一致し、$S^2_2$はNP関数に一致する。

さて、もしBussの階層がつぶれて、$S^1_2 = S^2_2$ (定理の集合として）となったとすると、上の関係からP=NPとなる。というわけで$S^1_2 = S^2_2$かどうかが問題になるわけだが、この手の話にありがちなように、これはまだ未解決問題だ。一般に、Bussの階層がつぶれれば（つまり$S^i_2 = S^{i+1}_2$)、多項式時間階層もつぶれる。一方で逆は今のところ示されていないが、公理としてP=NPを追加して、それでもつぶれないことを示せれば、P≠NPは示せる。（Takeuti 2000）

というわけで、Bussの階層がつぶれないか（上の方の理論が下の方の理論と違っているか）どうかがいろいろと研究されている。そして、ある理論Tと、その理論Tの拡張Uがあったとして、それが違うことを示す常套手段はゲーデルの不完全性定理だ。Tは自分の無矛盾性Con(T)を示さない。一方、UがCon(T)を示せば、TとUは違うことが分かる。

しかし、残念なことにこの方法は限定算術には直接には適応できない。というのも、限定算術はほとんど何の無矛盾性も示すことができないという結果があるからだ。（Wilkie,Paris 1987)

そこで、証明の概念を変えてみたり、更に弱い体系を考えてみたりといろいろ工夫されているが、今のところ成功はしていない。この件で私も1つ論文を書いてみたんだけど、その話はまた疲れてきたのでいずれ。

2013/06/28追加 続きを書いている。ゲーデルの不完全性定理からP≠NP問題にアプローチする - その２