記述の複雑さ

『記述的複雑性』は、ニール・イマーマンによる数理論理学と計算複雑性理論に関する書籍です。記述的複雑性理論は、異なるタイプの論理を使用した数学的特性の表現可能性が、異なるタイプのリソース制限型計算モデルでの計算可能性と同等であることが示される分野です。1999年にSpringer-Verlag社の書籍シリーズGraduate Texts in Computer Scienceで出版されました。

この本は15章から成り、大まかに5章が一階論理、3章が二階論理、7章が高度なトピックについて独立した章に分かれている。^{[1] [2]}

最初の 2 章では、一階論理 (一階算術、BIT 述語、一階クエリの概念を含む) と計算量理論 (形式言語、リソース制限付き計算量クラス、完全問題を含む) の背景資料を提供します。第 3 章では、論理と計算量の関係について、一階認識可能言語が対数空間で認識できることの証明、対数空間、非決定性対数空間、多項式時間のための完全言語の構築について説明します。第 4 章では、帰納的定義、固定小数点演算子、および最小の固定小数点演算子を使用した一階論理による多項式時間の特徴付けについて説明します。一階トピックに関する本の部分は、並列ランダム アクセス マシンのリソース制限と回路計算量の論理的特徴付けに関する章で終わります。^{[1] [2] [3]}

第6章では、論理的表現不可能性を証明するための重要なツールであるエーレンフォイヒト・フレセゲームを紹介し、第7章では2階論理を紹介します。これには、非決定性多項式時間を存在的2階論理の観点から特徴付けるフェイギンの定理、 NP完全問題の存在に関するクック・レビンの定理、およびこれらの結果の多項式階層への拡張が含まれます。第8章では、ゲームを使用して、2階論理における特定の言語の表現不可能性を証明する。^{[1] [2] [3]}

第 9 章では、言語の相補性と推移的閉包演算子について取り上げ、非決定性対数空間は相補性の下で閉じているというImmerman-Szelepcsényi 定理も取り上げます。第 10 章では、完全な問題と多項式空間の 2 階の論理的特徴付けについて説明します。第 11 章では、回路の複雑さの均一性(問題を解くための回路の存在とそれらのアルゴリズム的構成可能性の区別) について取り上げ、第 12 章では、複雑さのクラスの論理的特徴付けにおける順序付け述語と計数述語の役割について説明します。第 13 章では、下限値としてスイッチング補題を使用し、第 14 章では、データベースとモデル検査への応用について説明します。最後の章では、この分野でまだ研究が必要なトピックについて概説します。^{[1] [2] [3]}

この本は主にこの分野の研究者向けの参考書として書かれていますが^[1]、大学院のコースの基礎としても使用でき、そのための演習問題も用意されています。この本は自己完結的であると主張していますが、レビュー担当者のW. Klonowskiは、読者は古典的な複雑性と数学的論理の基礎の両方をすでに理解している必要があると書いています。^[2]

評論家のアヌジ・ダワールは、記述的複雑性に関する初期の期待は、複雑性理論の核心的な問題に論理的ツールを適用できないことと、計算を特徴付けるために論理言語に計算のような追加を加える必要があることで弱まってきたと書いている。しかし、彼は、この本は研究者にこの研究分野を紹介し、計算複雑性へのあまり研究されていないアプローチ方法を紹介する手段として有用であると書いている。^[4]