複雑性クラス

計算複雑性クラスとは

計算複雑性理論において、複雑性クラスは、計算問題の難易度を分類するための枠組みです。具体的には、ある計算モデル（例えばチューリングマシン）を用いて、特定の計算資源（時間やメモリ）の制限下で解ける問題の集合として定義されます。これらのクラスを理解することで、問題の計算に必要なリソースを把握し、効率的なアルゴリズムの設計に役立てることができます。

複雑性クラスの定義

一般的に、複雑性クラスは、抽象機械Mが入力長nに対してO(f(n))の計算資源Rを使って解ける問題の集合として定義されます。ここで、f(n)は入力長nに対する計算量の関数を表し、Rは時間、領域（メモリ）、並列度などの計算資源の種類を表します。

例として、

クラスNP: 非決定性チューリングマシンで多項式時間で解ける決定問題の集合
クラスPSPACE: チューリングマシンで多項式領域で解ける決定問題の集合

などがあります。これらの定義からわかるように、複雑性クラスは、問題の解法に必要な計算リソースの量によって分類されています。

複雑性クラス間の関係

複雑性クラス間には、包含関係が存在することがあります。例えば、クラスPはクラスNPの部分集合であり、これは多項式時間で解ける問題は、非決定性チューリングマシンでも多項式時間で解けることを意味します。これらの関係性を把握することは、問題の難易度を比較し、適切なアルゴリズムを選択する上で非常に重要です。


以下に、計算複雑性理論における問題のクラスを図示します。クラス X が Y の真部分集合である場合、X を Y の下に置き、実線でそれらを接続しています。X が部分集合であっても上位と等しい可能性もある場合、破線で接続しています。決定可能か決定不能かは、計算可能性理論の範疇ですが、ここでは複雑性クラスの関係を示すために入れてあります。

(図や表を挿入する場所。例:クラス間の関係を表す図)

代表的な複雑性クラス

以下に、主要な複雑性クラスの一覧と、それぞれの特徴をまとめます。

P (Polynomial Time): 決定性チューリングマシンで多項式時間で解ける問題のクラス。効率的に解ける問題の代表例です。
NP (Nondeterministic Polynomial Time): 非決定性チューリングマシンで多項式時間で解ける問題のクラス。解の検証が多項式時間で可能な問題を含みます。P≠NP予想という未解決問題が有名です。
NP完全 (NP-Complete): NPの中で最も難しい問題のクラス。NPに属する全ての問題が多項式時間でNP完全な問題に変換可能です。
NP困難 (NP-Hard): NP完全と同等かそれ以上に難しい問題のクラス。必ずしもNPに属するとは限りません。
PSPACE (Polynomial Space): 決定性チューリングマシンで多項式領域（メモリ）で解ける問題のクラス。PとNPを含む、より広いクラスです。
EXPTIME (Exponential Time): 決定性チューリングマシンで指数関数時間で解ける問題のクラス。Pよりも計算量が多いクラスです。
BPP (Bounded-error Probabilistic Polynomial time): 乱択アルゴリズムを用いて多項式時間で解ける問題のクラス。解が確率的に正しいことが保証されます。
BQP (Bounded-error Quantum Polynomial time): 量子コンピュータで多項式時間で解ける問題のクラス。量子計算によって効率的に解ける可能性のある問題を扱います。

その他の重要なクラス

#P: NP問題の解の個数を数える問題のクラス。
Co-NP: NP問題の否定問題を含むクラス。
L: 対数領域で解ける問題のクラス。
NL: 非決定性チューリングマシンで対数領域で解ける問題のクラス
NC: 並列コンピュータ上で効率的に解ける問題のクラス。
RE: チューリングマシンで解ける問題のクラス（帰納的言語）。
RP: 乱択アルゴリズムで多項式時間で解ける問題のクラス（解がNOの場合は正しくない可能性があるが、YESなら正しい）。
ZPP: 乱択アルゴリズムで解ける問題のクラス（解は常に正しいが、平均で多項式時間かかる）。

まとめ

複雑性クラスは、計算問題の難易度を理解し、アルゴリズムの設計や問題解決の方針を立てる上で重要な概念です。これらのクラスを理解することで、問題の計算に必要なリソースを把握し、より効率的な計算手法を開発することが可能になります。計算複雑性理論は、コンピュータサイエンスにおける重要な分野であり、今後の技術発展においても不可欠な役割を果たすでしょう。

参考資料

Complexity Zoo: 500以上の複雑性クラスとその特性のリスト
A diagram of the world of computability and complexity by Neil Immerman: 複雑性クラスの階層についての図
* Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. NP完全問題についての教科書的書籍

これらの参考文献は、より深く複雑性クラスについて学ぶための出発点となるでしょう。

もう一度検索