1 複雑度クラスの基本概念
複雑度クラスは、計算に要する資源の上限に応じて問題を分類するための枠組みである。ここでいう資源には、主として実行時間と使用空間が含まれ、同じ問題でも許容される資源量が変われば所属するクラスも変わる。こうした分類により、どの種類の問題が「効率的に扱えるか」を理論的に比較できる。
1.1 計算資源としての計算時間・計算空間
計算時間は、処理が完了するまでに要するステップ数を指し、計算空間は途中計算で必要となる記憶領域の量を表す。両者は独立した概念だが、実際の解析では相互に関連して扱われることが多い。時間を節約するために多くの空間を使う場合もあれば、逆に空間を抑える代わりに繰り返し計算が増える場合もある。
1.1.1 入力長に対する増加率の表現
複雑度では、入力そのものの大きさではなく、入力長に対する資源使用量の増え方が重視される。たとえば、入力長を n としたときに n の二乗に比例する時間で解けるか、指数的に増えるかが重要な区別となる。これにより、計算規模が大きくなった際の振る舞いを比較しやすくなる。
1.1.2 実行時間と計算ステップ数の関係
理論計算機では、実行時間はしばしば機械が行う基本操作の回数、すなわち計算ステップ数として定義される。これにより、抽象的な装置であっても処理量を厳密に数えられる。実装上の秒数とは一致しないが、アルゴリズムの伸び方を評価する尺度としては十分に有効である。
1.1.3 計算空間とワーキングメモリの関係
計算空間は、入力を保持する領域とは別に、計算の途中で自由に使える作業領域の量とみなせる。これには一時的な記憶や中間結果の保存が含まれる。空間制約が厳しい場合でも、入力を何度も読み返すことで問題を解けることがあり、時間と空間の緊張関係が現れやすい。
1.2 計算モデルの選び方
複雑度の定義は、どの計算モデルを基礎に置くかによって定まる。代表的なのはチューリング機械だが、決定性、非決定性、確率的な変種によって能力が異なる。モデルの選択は、何を「同じ計算力」とみなすかを明確にするために重要である。
1.2.1 決定性チューリング機械
決定性チューリング機械は、各状態と記号に対して次の動作が一意に定まるモデルである。入力に対する振る舞いが完全に固定されるため、計算過程の追跡が容易である。多くの基本的な複雑度クラスは、このモデルを基準として定義される。
1.2.2 非決定性チューリング機械
非決定性チューリング機械では、ある段階で複数の遷移候補を持ちうる。理論上は、どれか一つの分岐が受理すればよいという解釈をとるため、探索的な計算を簡潔に表現できる。NP のようなクラスは、この非決定性を用いて特徴づけられる。
1.2.3 確率計算モデル（概要）
確率計算モデルでは、処理の途中に乱数的な選択が導入される。これにより、成功確率を伴うアルゴリズムや平均的な性能を扱いやすくなる。厳密な定義は複数あるが、要点は確率性を資源や計算能力の一部として組み込む点にある。
1.3 言語・問題との対応付け
複雑度理論では、問題はしばしば言語として表現される。ある入力が受理されるかどうかを判定する形式に直すことで、計算可能性と資源制約を統一的に扱える。これにより、幅広い問題を同じ枠組みで比較できる。
1.3.1 判定問題としての定式化
判定問題は、入力が「はい」か「いいえ」かを答える形に整理された問題である。複雑度クラスの多くは、このタイプの問題集合として定義される。定式化を統一すると、アルゴリズムの比較や帰着の構成がしやすくなる。
1.3.2 関数問題との関係（概要）
関数問題は、単に可否を答えるのではなく、具体的な解や値を出力することを求める。判定問題に比べて扱いが複雑になることもあるが、多くの場合、判定問題への変換や関連づけが可能である。複雑度理論では、関数版の難しさを判定版の枠組みで間接的に評価することもある。
2 主要な複雑度クラス
代表的な複雑度クラスは、資源制約ごとに整理されている。P、NP、PSPACE、EXPTIME などはその中心にあり、それぞれが異なる計算的制約を表す。これらの相互関係を理解することは、計算の限界を見極めるうえで基本となる。
2.1 多項式時間系（Pと関連クラス）
多項式時間系は、入力長に対して多項式程度の時間で解ける問題群を指す。実用上「効率的」とみなされやすい範囲の理論的モデルとして扱われることが多い。P はその代表であり、他の主要クラスとの比較の基準になる。
2.1.1 Pの定義と直観
P は、決定性チューリング機械が入力長の多項式時間で判定できる言語の集合である。直観的には、入力が大きくなっても処理量の増加が比較的緩やかな問題が含まれる。計算理論では、効率的に解ける候補の中心的なクラスと見なされる。
2.1.1.1 決定性多項式時間の意味
決定性多項式時間とは、機械の動作が一意で、しかも必要時間が n^k 型の上限で抑えられることを意味する。ここで k は固定された定数である。指数関数的な増加に比べると制御しやすく、実際的な計算可能性の目安として用いられる。
2.2 非決定性多項式時間系（NPと関連クラス）
NP は、答えが「はい」である場合に、その正しさを多項式時間で確認できる問題の集合として理解される。非決定性の見方では、正しい分岐が存在するかどうかに対応する。P との関係は未解決であり、理論上も非常に重要な位置を占める。
2.2.1 NPの定義と検証可能性の直観
NP の核心は、解そのものを効率よく見つけられるかではなく、与えられた証拠を素早く検証できるかにある。証明書や候補解があれば、その妥当性を多項式時間で確認できる問題が含まれる。これが、探索と検証の違いを際立たせている。
2.2.2 副証明可能性としてのクラス（概要）
副証明可能性は、ある答えが「いいえ」であることを短い証拠で示せるかどうかに関わる概念である。NP とは対照的な見方を与え、補集合に対する性質を考える手がかりになる。厳密な構造は分野によって異なるが、証明の向きが重要である点は共通している。
2.3 空間計算量系（PSPACEなど）
空間計算量系は、使える記憶領域の量に注目する。PSPACE は多項式空間で解ける問題の集合であり、時間よりもメモリ制約に焦点を当てる。空間は再利用できるため、時間とは異なる複雑さの様相が現れる。
2.3.1 PSPACEの定義と特徴
PSPACE は、多項式量の作業空間で判定可能な問題全体を指す。一般に、入力が大きくなっても記憶使用量は比較的抑えられるが、その代わり処理時間は長くなる場合がある。ゲーム理論的な問題や逐次的な探索に関連する例が多い。
2.3.2 時間との比較（直観）
時間と空間はしばしば連動するが、片方を節約するともう片方が増えることがある。たとえば、少ない空間で計算を進めると、同じ情報を何度も再計算する必要が生じうる。したがって、空間が小さいからといって必ずしも高速とは限らない。
2.4 指数時間系（EXPTIMEなど）
指数時間系は、入力長に対して指数関数的な時間を要する問題を含む。多項式時間より大幅に広い範囲を表し、理論上は解けても実際には計算負荷が急増する。EXPTIME はその代表である。
2.4.1 EXPTIMEの定義と位置づけ
EXPTIME は、決定性チューリング機械が指数時間で判定できる言語の集合である。典型的には 2^{n^k} のような上限で記述される。P や NP より上位に位置づけられ、より重い計算資源を必要とする問題を含む。
2.4.2 典型的な包含関係（概要）
一般に、P は NP に含まれ、NP は PSPACE に含まれ、PSPACE は EXPTIME に含まれる。これらは資源制約の緩和に応じてクラスが広がることを示す基本図式である。ただし、各包含が真に狭いかどうかは別問題であり、未解決の点も残る。
3 クラス間の関係と性質
複雑度クラスの研究では、各クラスを単独で見るだけでなく、互いの関係を調べることが重要である。包含、等価、分離、完全性といった概念は、計算能力の差を整理するための主要な道具である。これらの性質を通じて、問題の難易度が体系的に把握される。
3.1 包含関係の基本パターン
包含関係は、あるクラスの問題が別のクラスでも解けるかを表す。上位のクラスほど下位のクラスを含む傾向があり、資源の許容範囲が広がるほど扱える問題も増える。こうした関係は、複雑度理論の骨格をなす。
3.1.1 単調性（資源を増やすとクラスは広がる）
資源制約を緩めれば、少なくとも以前と同じ問題は解けるため、クラスは通常拡大する。時間や空間の上限を引き上げると、より多くの言語を含められる。これが単調性と呼ばれる基本原理である。
3.1.2 計算モデルの強さによる差
同じ資源上限でも、計算モデルが異なれば解ける問題の範囲は変わる。決定性、非決定性、確率的計算では、記述できる探索や選択の仕方が異なるためである。モデル差は、同一の資源比較では見えにくい計算力の違いを浮かび上がらせる。
3.2 還元（リダクション）と完全性
還元は、ある問題を別の問題に変換して難しさを比較する方法である。完全性は、あるクラスの中でも特に難しい問題を選び出す概念で、クラス全体の代表例として機能する。これにより、個別問題の解析がクラス全体の理解へ結びつく。
3.2.1 決定問題の多項式時間帰着
多項式時間帰着は、一方の問題を多項式時間で他方へ変換する方法である。変換後の問題が解ければ元の問題も解けるため、後者の難しさを前者で表現できる。複雑度理論では、最も基本的な比較手段の一つである。
3.2.2 多対一帰着・Turing帰着（概要）
多対一帰着は、入力を一度だけ変換して別問題へ写す方法であり、Turing帰着は解答器を問い合わせながら計算を進める方法である。前者はより強い制約の下での変換、後者は反復的な利用を許す点が特徴である。用途によって使い分けられる。
3.2.3 完全問題の定義と役割
完全問題は、あるクラスに属し、かつそのクラス内の任意の問題から帰着できる問題である。これらはクラスの難しさを代表する標準例として重要である。もし完全問題が効率的に解ければ、そのクラス全体が一挙に簡単になる可能性がある。
3.3 分離と等価の考え方
分離は、二つのクラスが異なる計算能力を持つことを示すことであり、等価は双方が同じ問題群を表すことを意味する。どちらも複雑度の理解に不可欠だが、証明はしばしば難しい。特に主要クラス間の分離は、理論計算機科学の中心課題となっている。
3.3.1 「分離できる／できない」の意味
あるクラスが別のクラスに含まれないことを示せれば、両者の差異が明確になる。逆に、同じクラスであると証明できれば、定義の違いが本質的でないことがわかる。いずれの場合も、計算資源の境界を精密に描くことにつながる。
3.3.2 公開されている既知結果の整理（概要）
多くの基本包含は証明済みだが、P と NP のような中心的問題は未解決のままである。既知結果は、対角化法、帰着、完全性、オラクル結果など多様な手法で構成される。これらは、何が証明でき、何が依然として難しいかを示す指標にもなる。
4 研究上の典型的テーマ
複雑度クラスの研究は、抽象理論にとどまらず、アルゴリズム設計や計算限界の理解に直結する。特に、P と NP の関係や完全性の議論は、問題の難易度を把握するための中心的題材である。以下では、学習上よく現れる視点を整理する。
4.1 PとNPの位置づけ（概要）
P と NP は、効率的に解ける問題と効率よく検証できる問題の差を表す代表的な対比である。両者が一致するかどうかは、計算理論で最も有名な未解決問題の一つである。これが解ければ、最適化や探索に関する多くの理解が変わると考えられている。
4.2 決定可能性との境界
複雑度理論は、そもそも解けるかどうかを問う決定可能性とは別に、解けるとしてどれだけ資源が要るかを扱う。つまり、計算可能性の内側での細かな区分が主題となる。これにより、単なる可否を超えて、実行可能性の度合いが比較される。
4.2.1 冪集合的な尺度との違い（概要）
冪集合は、ある集合のすべての部分集合を集めたもので、組合せの全体像を表す数学的概念である。複雑度クラスはこれとは異なり、部分集合の数ではなく、計算資源に基づく分類である。両者は形式的には別の観点だが、集合の構成という意味で比較対象になることがある。
4.2.2 理論と実用の接点
理論上の複雑度分類は、実際のアルゴリズム設計にも影響を与える。多項式時間で済む方法は実装候補になりやすい一方、指数時間が避けられない問題では近似やヒューリスティックが検討される。こうした境界認識は、現実的な計算戦略の選択に役立つ。
4.3 完全性・難しさの応用分野
完全性の概念は、ひとつの代表問題を通じて周辺領域の難しさを把握するのに役立つ。計算量の高い問題を、より理解しやすい標準問題へ写すことで、理論と応用の橋渡しが可能になる。これにより、問題群の構造が整理される。
4.3.1 充足可能性問題の例（概要）
充足可能性問題は、論理式に真となる代入が存在するかを問う代表的な判定問題である。NP 完全問題の典型例として広く知られ、他の多くの問題の基準になっている。論理、回路、制約充足など幅広い領域と結びつく。
4.3.2 探索・最適化への拡張（概要）
判定問題で難しい構造は、解そのものを求める探索問題や、最良の解を求める最適化問題にも現れる。これらは判定版より情報量が多く、実際にはさらに扱いが難しいことがある。複雑度理論では、相互変換の可能性を通じて難度を比較する。
4.4 学習のための見取り図
複雑度クラスを学ぶ際には、定義、包含、完全性、代表問題の四点を押さえると全体像が見えやすい。個々の名称を暗記するだけでなく、何が資源で何がモデルかを意識すると理解が安定する。見取り図を持つことで、新しいクラスにも対応しやすくなる。
4.4.1 代表クラスの比較表（概念的整理）
P は決定性多項式時間、NP は多項式時間で検証可能、PSPACE は多項式空間、EXPTIME は指数時間という整理が基本である。これらは、時間・空間・探索性の違いを象徴している。概念的には、資源制約が緩むほど右肩上がりに広がる階層として捉えられる。
4.4.2 よく用いられる定義の暗記ポイント
覚える際は、各クラスが「何を制限するか」を一語で対応させるとよい。P は時間、PSPACE は空間、NP は証明書の検証、EXPTIME は指数的な時間増加が要点である。定義文を丸暗記するより、制約の種類と計算モデルの組合せで整理すると混乱しにくい。