記述計算量

記述計算量（きじゅつけいさんりょう、英: Descriptive complexity）は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、PHは二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。

概要

特に、それぞれの論理体系は、その中で表現可能なクエリの集合を生み出す。クエリは計算複雑性理論における計算問題と対応している。

記述計算量の最初の成果として、1974年にロナルド・フェイギンが示した Fagin の定理がある[1]。これは、NPが存在量化二階述語論理の論理式で表現可能な言語の集合と正確に対応していることを示した。存在量化二階述語論理とは、関係・関数・部分集合について全称量化を行わない二階述語論理である。他の多くのクラスについても、主に Neil Immerman によって同様の特徴付けがなされた。以下に主なものを列挙する。

  • 一階述語論理はクラス FO（あるいは AC0）を定義し、その言語は定数深さの多項式サイズ回路で認識される。これは並行ランダムアクセス機械（CRAM、CRCW型のPRAMにほぼ相当するモデル）で定数時間で認識される言語と等価である。
  • 一階述語論理に可換な推移閉包演算子を追加したものは、SL に相当する。これは対数領域で解ける問題のクラス L と等しい。
  • 一階述語論理に推移閉包演算子を追加したものは、NL に相当する。
  • 線形順序が存在する場合、最小不動点演算子を持つ一階述語論理が P に相当する。
  • 存在量化二階述語論理は NP に相当する（上述の通り）。
  • 二階存在量化をのぞいた全称二階述語論理は co-NP に相当する。
  • 二階述語論理は PH に相当する。
  • 推移閉包演算子を持つ二階述語論理は PSPACE に相当する。
  • 最小不動点演算子を持つ二階述語論理は EXPTIME に相当する。

参考文献

脚注

  1. ^ R. Fagin. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, pp. 27-41. 1974.