_ えーと、明けましておめでとうございます。
_ これは、計算量理論の古典的な定理「階層定理」 (O(t(n))-時間計算チューリングマシンで計算可能だが o(t(n)/log t(n))-時間計算チューリングマシンで 計算可能で無い言語 L が存在する) の系で証明できます。 「階層定理」の詳細な証明はすっかり忘れましたけど(長いんですよ←言い訳)、 そういう L の構成に、仰るとおり、かの有名な対角線論法(diagonalization)を使います。 「階層定理」は「停止性問題の決定不可能性定理」のアナロジーで、 この「階層定理」の証明は、一般の計算理論や計算量理論の本なら必ず載っています。
ちなみに、前述の関数 t(n) は任意の関数ではダメで、 時間構成可能(time constructible)自然数関数と呼ばれる関数でなければなりませんが、 多項式、n乗根・対数関数の床関数、指数関数などメジャーな関数はどれも時間構成可能なので、 あまり問題になりません。
_ 階層定理の系として、1≦a＜b となる任意の実数 a, b について、 二つ時間の計算量クラス TIME(n^a)(＝ O(n^a)-時間計算可能チューリングマシンで受理できる計算量クラス) と TIME(n^b) に対して、 真の包含関係 “TIME(n^a)⊂TIME(n^b)”が成り立ちます(マイケル・シプサ「計算理論の基礎」共立出版より)。
これは、例えば O(n^2)-時間計算可能チューリングマシン と O(n^2.000000000000000000001)-時間計算可能チューリングマシンとでは、 二つの多項式の次数はとても僅かですが、 前者では計算できないが後者では計算できる言語 L が存在します。
_ さて、問題の“P!=EXPTIME”の証明ですが、どんな大きな次数の多項式も、 指数関数の増加速度を漸近的に越えられないので、 前述の階層定理よりすぐに導かれます。
_ 一方で、お馴染みの「“P!=NP”問題」ですが、計算理論で良く使われる相対化(relativization) が使えず、対角線論法では証明できそうも無いことが示されています。 対角線論法のようなブレイクスルーとなる手法は、 今のところ誰も発見できていないのはもちろんのこと、その手がかりすらほとんどわかっていません。 これが、証明できない問題の可能性もあるのですが、 「『“P!=NP”は証明できない』ことを証明する」だけでも意義があります。 もし誰かがそれを示したら、“P!=NP”問題は解決したことになります。 何となく後味悪いですけど、それでも証明できたら間違いなくスーパースターです。
リンクはご自由に。
この日記は、GNSを使用して作成されています。
2003年2月1日より 名の訪問