複雑度クラス

計算複雑性理論では、複雑性クラスとは「関連するリソースベースの複雑性」を持つ計算問題の集合です。^[1]最も一般的に分析される2つのリソースは時間とメモリです。

一般に、複雑性クラスは、計算問題のタイプ、計算モデル、および時間やメモリなどの制限されたリソースの観点から定義されます。特に、ほとんどの複雑性クラスは、チューリングマシンで解決可能な決定問題で構成され、時間または空間（メモリ）要件によって区別されます。たとえば、クラスP は、決定論的チューリングマシンによって多項式時間で解決可能な決定問題の集合です。ただし、他の種類の問題（例：計数問題や関数問題）や他の計算モデル（例：確率的チューリングマシン、対話型証明システム、ブール回路、量子コンピュータ）を使用して定義される複雑性クラスも多数あります。

計算量クラス間の関係の研究は、理論計算機科学の主要な研究分野です。計算量クラスには一般的な階層構造が存在することがよくあります。たとえば、いくつかの基本的な時間計算量クラスと空間計算量クラスは、次のように相互に関連していることがわかっています。L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE (ここで、 ⊆ はサブセット関係を示します)。ただし、多くの関係はまだわかっていません。たとえば、計算機科学における最も有名な未解決問題の 1 つは、 P がNPに等しいかどうかに関するものです。クラス間の関係は、多くの場合、計算の基本的な性質に関する疑問に答えます。たとえば、P対NP問題は、非決定性によって計算機の計算能力が向上するかどうか、および、正確さをすばやく確認できる解を持つ問題はすばやく解決できるかどうかという疑問に直接関係しています。

複雑度クラスは、関連する計算問題の集合です。これらは、時間やメモリなどの特定の計算リソースに関して、それらに含まれる問題を解決する計算上の難しさという観点から定義されます。より正式には、複雑度クラスの定義は、計算問題のタイプ、計算モデル、および制限された計算リソースの 3 つで構成されます。特に、ほとんどの複雑度クラスは、制限された時間または空間リソースを持つチューリング マシンによって解決できる決定問題で構成されます。たとえば、複雑度クラスP は、決定論的チューリング マシンによって多項式時間で解決できる決定問題の集合として定義されます。

直感的には、計算上の問題とは、アルゴリズムで解決できる単なる質問です。たとえば、「自然数 は 素数か?」は計算上の問題です。計算上の問題は、問題に対する答えの集合として数学的に表現されます。素数判定の例では、問題 ( と呼ぶ) は、素数であるすべての自然数の集合 によって表現されます。計算理論では、これらの答えは文字列として表現されます。たとえば、素数判定の例では、自然数は2 進数 を表すビットの文字列 として表現できます。このため、計算上の問題は、ビットの文字列が形式言語(言語学から借用した概念)を表すため、言語と同義に呼ばれることがよくあります。たとえば、問題が複雑性クラスNPに属すると言うことは、言語がNPに属すると言うことと同じです。 ${\displaystyle n}$ ${\displaystyle {\texttt {PRIME}}}$${\displaystyle {\texttt {PRIME}}=\{n\in \mathbb {N} |n{\text{ は素数}}\}}$${\displaystyle {\texttt {PRIME}}}$${\displaystyle {\texttt {PRIME}}}$

理論計算機科学で最も一般的に分析される問題は、決定問題、つまり「はい/いいえ」の質問として提示できる種類の問題です。たとえば、上記の素数判定の例は、「自然数は 素数か」というはい/いいえの質問で表すことができる決定問題の例です。計算理論では、決定問題は、正しいアルゴリズムを実行するコンピュータが「はい」と答える入力文字列の集合として表されます。素数判定の例では、は自然数を表す文字列の集合であり、これを素数性を正しくテストするアルゴリズムを実行するコンピュータに入力すると、アルゴリズムは「はい、この数は素数です」と答えます。この「はい/いいえ」形式は、多くの場合「受け入れ/拒否」と同等に表現されます。つまり、決定問題に対する答えが「はい」の場合、アルゴリズムは入力文字列を「受け入れ」、答えが「いいえ」の場合、「拒否」します。 ${\displaystyle n}$ ${\displaystyle {\texttt {PRIME}}}$

いくつかの問題は簡単には決定問題として表現できないが、それでも広範囲の計算問題を包含している。^[2]特定の複雑性クラスが定義される他の種類の問題には以下のものがある。

• 関数の問題（例：FP）
• 数え上げ問題（例：#P）
• 最適化問題
• 約束の問題（「その他の種類の問題」のセクションを参照）

「コンピュータ」という概念を具体化するために、理論コンピュータ サイエンスでは、問題は計算モデルのコンテキストで分析されます。計算モデルは、「時間」や「メモリ」などの計算リソースの概念を正確にします。計算複雑性理論では、複雑性クラスは、物理的なコンピュータの構築方法に依存するリソース要件ではなく、問題に固有のリソース要件を扱います。たとえば、現実の世界では、設計方法により、異なるコンピュータが同じ問題を解決するために異なる時間とメモリ量を必要とする場合があります。計算モデルは、コンピュータの抽象的な数学的表現を提供することで、基本原理の理解を妨げる現実世界の余分な複雑さ (プロセッサ速度の違いなど) を抽象化します。

最も一般的に使用される計算モデルは、チューリング マシンです。他のモデルも存在し、多くの複雑性クラスがそれらに基づいて定義されていますが (「他の計算モデル」のセクションを参照)、チューリング マシンは、ほとんどの基本的な複雑性クラスを定義するために使用されます。チューリング マシンでは、秒などの標準的な時間単位 (実行時間と物理ハードウェアの速度を切り離すことは不可能) やバイトなどの標準的なメモリ単位を使用する代わりに、時間の概念はチューリング マシンが問題を解決するために実行する基本ステップの数として抽象化され、メモリの概念はマシンのテープで使用されるセルの数として抽象化されます。これらについては、以下で詳しく説明します。

具体的な計算モデルを参照せずにBlum 公理を使用して複雑性クラスを定義することも可能だが、このアプローチは複雑性理論ではあまり使用されない。

チューリング マシンは、一般的な計算マシンの数学的モデルです。複雑性理論で最も一般的に使用されるモデルであり、他の計算モデルと同じくらい強力であると考えられており、数学的に分析しやすいことが主な理由です。重要なことは、特定の問題を解決するアルゴリズムが存在する場合、同じ問題を解決するチューリング マシンも存在すると考えられていることです (これはチャーチ-チューリングのテーゼとして知られています)。つまり、すべてのアルゴリズムはチューリング マシンとして表現できると考えられているということです。

機械的に言えば、チューリング マシン (TM) は、無限に長いテープ ストリップに含まれるシンボル (実際のコンピュータとの直感的なつながりを実現するために、通常はビット 0 と 1 に制限されています) を操作します。TM は、テープ ヘッドを使用して、一度に 1 つずつ読み取りと書き込みを行うことができます。操作は、"状態 42 で、シンボルが 0 の場合は 1 を書き込む。シンボルが 1 の場合は、状態 17 に変更する。状態 17 で、シンボルが 0 の場合は 1 を書き込んで状態 6 に変更する" などの有限の基本命令セットによって完全に決定されます。チューリング マシンは、テープ上の入力文字列のみで開始し、他のすべての部分は空白です。TM は、指定された受け入れ状態に入ると入力を受け入れ、拒否状態に入ると入力を拒否します。決定論的チューリング マシン (DTM) は、最も基本的なタイプのチューリング マシンです。これは、固定された一連のルールを使用して将来のアクションを決定します (これが「決定論的」と呼ばれる理由です)。

計算上の問題は、特定のチューリング マシンが受け入れる入力文字列の集合として、チューリング マシンの観点から定義できます。たとえば、上記の素数問題は、素数を正しくテストするアルゴリズムを実行するチューリング マシンが受け入れる文字列の集合 (自然数を表す) です。チューリング マシンは、言語に含まれるすべての入力を受け入れる場合、言語を認識していると言われます(「問題」と「言語」は、計算可能性と複雑性理論ではほぼ同義語であることを思い出してください)。また、言語に含まれないすべての入力を拒否する場合、言語を決定していると言われます (特定の入力によってチューリング マシンが永久に実行される可能性があるため、決定可能性によって、認識可能性に加えて、チューリング マシンはすべての入力で停止しなければならないという追加の制約が課されます)。問題を「解決する」チューリング マシンは、通常、言語を決定するマシンを意味します。 ${\displaystyle {\texttt {PRIME}}}$

チューリング マシンは、「時間」と「空間」の直感的な概念を可能にします。特定の入力に対する TM の時間複雑度は、チューリング マシンが受け入れ状態または拒否状態に到達するために実行する基本ステップの数です。空間複雑度は、受け入れ状態または拒否状態に到達するために使用するテープ上のセルの数です。

決定性チューリングマシン (DTM) は、非決定性チューリングマシン (NTM) の変種です。直感的に言えば、NTM は通常のチューリングマシンに、特定の状態から複数の可能な将来のアクションを探索し、受け入れるブランチ (受け入れる場合) を「選択」できる機能が追加されています。つまり、DTM は 1 つの計算ブランチのみに従う必要がありますが、NTM は各ステップで多くの可能な計算経路に分岐する計算ツリーとして考えることができます (図を参照)。ツリーの少なくとも 1 つのブランチが「受け入れ」条件で停止すると、NTM は入力を受け入れます。このように、NTM はすべての計算可能性を同時に並行して探索し、受け入れブランチを選択していると考えることができます。^[3] NTM は物理的に実現可能なモデルではなく、単に理論的に興味深い抽象マシンであり、興味深い複雑性クラス (物理的に実現可能な同等の定義を持つことが多い) を生み出します。

NTMの時間計算量とは、NTMが計算のどの分岐でも使用するステップの最大数です。^[4]同様に、 NTMの空間計算量とは、NTMが計算のどの分岐でも使用するセルの最大数です。

DTM は、非決定性の力を利用しない NTM の特殊なケースと見なすことができます。したがって、DTM で実行できるすべての計算は、同等の NTM でも実行できます。また、DTM を使用して任意の NTM をシミュレートすることもできます (DTM は、考えられるすべての計算分岐を 1 つずつ計算するだけです)。したがって、計算可能性の点では、この 2 つは同等です。ただし、DTM を使用して NTM をシミュレートするには、多くの場合、より多くの時間やメモリ リソースが必要になります。後で説明するように、特定のクラスの計算問題でこの速度低下がどの程度顕著であるかは、計算複雑性理論における重要な問題です。

複雑度クラスは、計算問題をリソース要件によってグループ化します。これを行うために、計算問題は、最も効率的なアルゴリズムが問題を解決するために必要とするリソースの最大量の上限によって区別されます。より具体的には、複雑度クラスは、入力サイズの増加に伴う特定の計算問題を解決するために必要となるリソースの増加率に関係します。たとえば、複雑度クラスPの問題を解くのにかかる時間は、入力サイズの増加に伴って多項式率で増加しますが、これは指数複雑度クラスEXPTIMEの問題 (または、より正確には、であるため、Pの範囲外にあるEXPTIMEの問題) と比較すると比較的遅くなります。 ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {EXPTIME}}}$

複雑性クラスの研究は、主に計算問題を解決するのに必要な固有の複雑性を理解することを目的としていることに注意してください。したがって、複雑性理論家は一般に、問題が分類される最小の複雑性クラスを見つけることに関心があり、したがって、最も効率的なアルゴリズムを使用して計算問題がどのクラスに分類されるかを特定することに関心があります。たとえば、特定の問題を指数時間で解決するアルゴリズムがあるかもしれませんが、この問題を解決するための最も効率的なアルゴリズムが多項式時間で実行される場合、その問題の固有の時間複雑性は多項式として記述する方が適切です。

チューリング マシン モデルに関するアルゴリズムの時間計算量とは、チューリング マシンが特定の入力サイズでアルゴリズムを実行するのに必要なステップ数です。正式には、チューリング マシンで実装されたアルゴリズムの時間計算量は関数として定義されます。ここで、 は長さ の任意の入力に対してが実行する最大ステップ数です。 ${\displaystyle M}$${\displaystyle t_{M}:\mathbb {N} \to \mathbb {N} }$${\displaystyle t_{M}(n)}$${\displaystyle M}$${\displaystyle n}$

計算複雑性理論では、理論計算機科学者は特定の実行時間値よりも、計算複雑性関数が属する関数の一般的なクラスを重視します。たとえば、計算複雑性関数は多項式ですか?対数関数ですか?指数関数ですか? それとも別の種類の関数ですか?

チューリング マシン モデルに関するアルゴリズムの空間計算量とは、与えられた入力サイズでアルゴリズムを実行するために必要なチューリング マシンのテープ上のセルの数です。正式には、チューリング マシンで実装されたアルゴリズムの空間計算量は関数として定義されます。ここで、 は長さ の任意の入力で使用するセルの最大数です。 ${\displaystyle M}$${\displaystyle s_{M}:\mathbb {N} \to \mathbb {N} }$${\displaystyle s_{M}(n)}$${\displaystyle M}$${\displaystyle n}$

複雑度クラスは、多くの場合、 DTIMEとNTIME (時間複雑度)、およびDSPACEとNSPACE (空間複雑度)と呼ばれる複雑度クラスの粒度セットを使用して定義されます。ビッグ O 表記法を使用すると、次のように定義されます。

• 時間計算量クラスは、時間決定論的チューリング マシンによって決定されるすべての問題の集合です。${\displaystyle {\mathsf {DTIME}}(t(n))}$${\displaystyle O(t(n))}$
• 時間計算量クラスは、時間非決定性チューリング マシンによって決定されるすべての問題の集合です。${\displaystyle {\mathsf {NTIME}}(t(n))}$${\displaystyle O(t(n))}$
• 空間計算量クラスは、空間決定論的チューリング マシンによって決定されるすべての問題の集合です。${\displaystyle {\mathsf {DSPACE}}(s(n))}$${\displaystyle O(s(n))}$
• 空間計算量クラスは、空間非決定性チューリング マシンによって決定されるすべての問題の集合です。${\displaystyle {\mathsf {NSPACE}}(s(n))}$${\displaystyle O(s(n))}$

Pは決定性チューリングマシンで多項式時間で解ける問題のクラスであり、NPは非決定性チューリングマシンで多項式時間で解ける問題のクラスである。より正式には、

${\displaystyle {\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})}$

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})}$

P は、入力サイズの増加に伴って問題を解く時間の複雑さが比較的緩やかに増加するため、決定論的コンピュータによって「迅速に」または「効率的に」解くことができる問題のクラスであるとよく言われます。

NPクラスの重要な特徴は、決定論的チューリングマシンによって多項式時間で検証可能な問題のクラスとして同義に定義できることです。つまり、言語がNPに属するのは、検証器と呼ばれる決定論的多項式時間チューリングマシンが存在し、文字列と多項式サイズの証明書文字列を入力として受け取り、その言語に含まれる場合は受け入れ、含まれない場合は拒否する場合です。直感的には、証明書は入力が言語に含まれることの証明として機能します。正式には、次のようになります^。[5]${\displaystyle w}$ ${\displaystyle c}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$

NP は、多項式時間の決定論的チューリングマシンと、すべての に対して がであり、を受け入れるような が存在する場合に限り、 となる多項式が存在するような言語のクラスです。${\displaystyle L}$${\displaystyle M}$${\displaystyle p}$${\displaystyle \in \{0,1\}^{*}}$${\displaystyle w}$${\displaystyle L}$ ${\displaystyle c\in \{0,1\}^{p(|w|)}}$${\displaystyle M(w,c)}$

非決定性の定義と検証者の定義のこの同等性は、非決定性とソリューションの検証可能性の基本的な関係を強調しています。さらに、言語がNPであることを証明するための便利な方法も提供します。適切な証明書を特定し、多項式時間で検証できることを示すだけです。

効率的に解決可能な問題のクラスと、その解決が単に効率的にチェック可能な問題のクラスとの間には明らかな違いがあるように思えるかもしれませんが、PとNP は、実際にはコンピュータ サイエンスにおける最も有名な未解決問題の 1 つであるP対NP問題の中心にあります。 (直感的には、決定性チューリング マシンは非決定性チューリング マシンのサブクラスにすぎず、非決定性を利用しないものである、または検証器の定義では、P は多項式時間検証器が証明書として空の文字列のみを受け取る必要がある問題のクラスである) ことはわかっていますが、NPがPより厳密に大きいかどうかはわかっていません。P = NPの場合、問題の解決策を迅速に見つける能力に関して、非決定性は決定性よりも追加の計算能力を提供しないということになります。つまり、計算の可能なすべてのブランチを探索できることは、単一のブランチのみを探索できることに比べて、せいぜい多項式的なスピードアップしか提供しません。さらに、問題インスタンスの証明が存在し、その証明の正しさをすぐに確認できる場合（つまり、問題がNPにある場合）、その証明をすぐに構築できるアルゴリズムも存在することになります（つまり、問題がPにあります）。^[6]しかし、圧倒的多数のコンピュータ科学者は、、^[7]と信じており、今日使用されているほとんどの暗号化方式は、という仮定に依存しています。^[8]${\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}}$${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$

EXPTIME（EXPと略されることもある）は、決定性チューリングマシンで指数時間で解ける決定問題のクラスであり、NEXPTIME（NEXPと略されることもある）は、非決定性チューリングマシンで指数時間で解ける決定問題のクラスである。より正式には、

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(2^{n^{k}})}$

${\displaystyle {\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

EXPTIME はPの厳密なスーパーセットであり、NEXPTIMEはNPの厳密なスーパーセットです。さらに、 EXPTIME NEXPTIMEでもあります。これが適切かどうかは不明ですが、P = NPの場合、EXPTIME はNEXPTIMEと等しくなければなりません。 ${\displaystyle \subseteq }$

対数時間計算量クラスを定義することは可能ですが、これらは極めて狭いクラスであり、線形以下の時間ではチューリングマシンが入力全体を読み取ることすらできない（ のため）。^{[a] [9]}しかし、対数空間で解決できる問題は意味のある数だけ存在します。 これらのクラスの定義には、マシンが入力全体を保存できるように2 テープ チューリングマシンが必要です（計算可能性の点では、2 テープ チューリングマシンは 1 テープ チューリングマシンと同等であることが示せます）。^[10] 2 テープ チューリングマシン モデルでは、1 つのテープは読み取り専用の入力テープです。もう 1 つは作業テープで、読み取りと書き込みの両方が可能で、チューリングマシンが計算を実行するテープです。 チューリングマシンの空間計算量は、作業テープで使用されるセルの数として測定されます。 ${\displaystyle \log n<n}$

L （ LOGSPACEと長く表記されることもある）は決定性チューリングマシン上の対数空間で解ける問題のクラスとして定義され、NL （ NLOGSPACEと長く表記されることもある）は非決定性チューリングマシン上の対数空間で解ける問題のクラスとして定義される。より正式には、^[10]

${\displaystyle {\mathsf {L}}={\mathsf {DSPACE}}(\log n)}$

${\displaystyle {\mathsf {NL}}={\mathsf {NSPACE}}(\log n)}$

であることがわかっています。ただし、これらの関係のいずれかが適切であるかどうかはわかっていません。 ${\displaystyle {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {P}}}$

複雑性クラスPSPACEとNPSPACE は、 PとNPの空間類似物です。つまり、PSPACEは多項式空間で決定論的チューリングマシンによって解ける問題のクラスであり、NPSPACE は多項式空間で非決定論的チューリングマシンによって解ける問題のクラスです。より正式には、

${\displaystyle {\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$

${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}$

P = NPかどうかは不明ですが、サビッチの定理はPSPACE = NPSPACEであることはよく知られています。 であることもわかっています。これは、チューリングマシンのテープ上のセルへの書き込みが 1 単位の時間を要すると定義されているため、多項式時間で動作するチューリングマシンは多項式の数のセルにしか書き込めないという事実から直感的に導かれます。P はPSPACEよりも厳密に小さいと思われますが、これは証明されていません。 ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {PSPACE}}}$

複雑性クラスEXPSPACEとNEXPSPACE は、 EXPTIMEとNEXPTIMEの空間類似物です。つまり、EXPSPACEは指数空間で決定論的チューリングマシンによって解ける問題のクラスであり、NEXPSPACE は指数空間で非決定論的チューリングマシンによって解ける問題のクラスです。または、より正式には、

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

${\displaystyle {\mathsf {NEXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}$

サビッチの定理はEXPSPACE = NEXPSPACEであることを示しました。このクラスは非常に広範囲です。PSPACE 、NP、Pの厳密なスーパーセットであることが知られており、 EXPTIMEの厳密なスーパーセットであると信じられています。

複雑性クラスにはさまざまな閉包特性があります。たとえば、決定クラスは、否定、選言、連言、またはすべてのブール演算で閉じている可能性があります。さらに、さまざまな量化スキームで閉じている可能性もあります。たとえば、 P はすべてのブール演算で閉じており、多項式サイズの領域での量化でも閉じています。閉包特性はクラスを分離するのに役立ちます。2 つの複雑性クラスを分離する 1 つの方法は、一方のクラスが持っていてもう一方のクラスが持っていない閉包特性を見つけることです。

否定に対して閉じていない各クラスX には、補クラスco-Xがあり、これはXに含まれる言語の補集合(つまり) で構成されます。たとえば、 co-NPは重要な補集合複雑性クラスの 1 つであり、 co-NP = NPであるかどうかという未解決問題の中心にあります。 ${\displaystyle {\textsf {co-X}}=\{L|{\overline {L}}\in {\mathsf {X}}\}}$

閉包性は、多くの計算量クラスが現在のように定義されている主な理由の 1 つです。^[11]たとえば、時間 (つまり線形時間) で解決できる問題と、せいぜい時間で解決できる問題を考えてみましょう。これらの問題は両方ともPにありますが、入力サイズが増加するにつれて、2 番目の実行時間は最初の実行時間よりも大幅に速くなります。このような大きな矛盾を許容するすべての多項式ではなく、 などのより小さな多項式境界を使用して「効率的に解決可能な」問題のクラスを定義する方がよいのではないかという疑問が生じるかもしれません。しかし、すべての多項式の集合は、線形関数を含み、加算、乗算、および合成に対しても閉じている関数の最小のクラスであることがわかります (たとえば、は多項式ですが です)。^[11] 1 つの効率的なアルゴリズムを別の効率的なアルゴリズムと合成しても効率的であると見なされるようにしたいため、多項式は「効率的なアルゴリズム」の合成を保証する最小のクラスです。^{[12] （} Pの定義は、経験的に、P内の実用上有用な問題のほとんどすべてが実際には低次の多項式実行時間を持ち、P外の実用上有用な問題のほとんどすべてが小さな指数関数的実行時間、つまりcが1に近い実行時間を持つ既知のアルゴリズムを持たないため、有用であることに注意する必要がある。 ^[13]） ${\displaystyle O(n)}$${\displaystyle O(n^{1000})}$${\displaystyle O(n^{3})}$${\displaystyle O(n^{3})\circ O(n^{2})=O(n^{6})}$${\displaystyle O(n^{6})>O(n^{3})}$${\displaystyle O(c^{n})}$

多くの複雑性クラスは、簡約の概念を使用して定義されます。簡約とは、ある問題から別の問題への変換です。つまり、簡約では、ある問題からの入力を別の問題の入力に変換します。たとえば、と を2 進表記に変換することで、通常の 10 進加算を 2 進加算に簡約できます (たとえば、5+7 は 101+111 になります)。正式には、任意のに対してとなる関数が存在する場合、問題は問題に簡約されます。 ${\displaystyle x+y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle f}$${\displaystyle x\in \Sigma ^{*}}$${\displaystyle x\in X}$ ${\displaystyle f(x)\in Y}$

一般に、簡約は、ある問題が少なくとも別の問題と同じくらい難しいという概念を捉えるために使用されます。したがって、他の問題に効率的に簡約できる問題はよりも難しくないため、一般に多項式時間簡約を使用することに関心があります。正式には、すべての に対して である場合に限り となる多項式時間計算可能関数が存在する場合、問題は問題に多項式時間簡約可能です。 ${\displaystyle X}$${\displaystyle Y}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle p}$${\displaystyle x\in \Sigma ^{*}}$${\displaystyle x\in X}$ ${\displaystyle p(x)\in Y}$

削減はさまざまな方法で定義できることに注意してください。一般的な削減は、 Cook 削減、Karp 削減、Levin 削減であり、多項式時間削減や対数空間削減など、リソースの境界に基づいて変化する可能性があります。

簡約は、問題が複雑性クラスにとって困難であるという概念の根拠となります。問題が問題のクラスCにとって困難であるとは、 Cのすべての問題がに多項式時間で簡約できる場合です。したがって、のアルゴリズムにより、C のどの問題も最大でも多項式時間の遅延で解くことができるため、Cにはより困難な問題はありません。特に重要なのは、 NPにとって困難な問題の集合はNP 困難問題 の集合と呼ばれることです。${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$

問題がCにとって困難であり、かつCにもある場合、 はCにとって完全であると言われます。これは、 がCで最も難しい問題であることを意味します(同じくらい難しい問題は多数ある可能性があるため、より正確にははCで最も難しい問題と同じくらい難しいです)。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$

特に重要なのは、 NP完全問題のクラス、つまりNPにおける最も難しい問題です。NPのすべての問題は多項式時間でNP完全問題に還元できるため、多項式時間で解決できるNP完全問題を見つけることは、 P  =  NPであることを意味します。

サビッチの定理は、決定論的空間資源と非決定論的空間資源の関係を確立する。非決定論的チューリングマシンが空間を使って問題を解けるなら、決定論的チューリングマシンは同じ問題を空間、つまり空間の2乗で解けることを示している。正式には、サビッチの定理は、任意の^[14]に対して、${\displaystyle f(n)}$${\displaystyle f(n)^{2}}$${\displaystyle f(n)>n}$

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right).}$

サビッチの定理の重要な帰結は、PSPACE = NPSPACE (多項式の二乗は依然として多項式であるため) およびEXPSPACE = NEXPSPACE (指数の二乗は依然として指数であるため) であるということです。

これらの関係は、決定論と比較した非決定論の力に関する基本的な疑問に答えます。具体的には、サビッチの定理は、非決定論的チューリング マシンが多項式空間で解決できる問題は、決定論的チューリング マシンも多項式空間で解決できることを示しています。同様に、非決定論的チューリング マシンが指数空間で解決できる問題は、決定論的チューリング マシンも指数空間で解決できます。

DTIMEの定義により、の場合、であるため、の場合、は に含まれます。ただし、この定義では、この包含が厳密であるかどうかはわかりません。時間と空間の要件については、包含が厳密である条件は、それぞれ時間階層定理と空間階層定理によって与えられます。これらは、それぞれのリソースを制約することによって定義されたクラスに適切な階層を誘導するため、階層定理と呼ばれます。階層定理により、解決できる問題の数を増やすために、さらにどれだけの時間または空間が必要かについて定量的な記述を行うことができます。 ${\displaystyle {\mathsf {DTIME}}(n^{k_{1}})}$${\displaystyle {\mathsf {DTIME}}(n^{k_{2}})}$${\displaystyle k_{1}\leq k_{2}}$${\displaystyle O(n^{k_{1}})\subseteq O(n^{k_{2}})}$${\displaystyle k_{1}\leq k_{2}}$

時間階層定理は、

${\displaystyle {\mathsf {DTIME}}{\big (}f(n){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log ^{2}(f(n)){\big )}}$。

空間階層定理は、

${\displaystyle {\mathsf {DSPACE}}{\big (}f(n){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n)\cdot \log(f(n)){\big )}}$。

時間と空間の階層定理は、複雑性クラスのほとんどの分離結果の基礎となります。たとえば、時間階層定理は、PがEXPTIMEに厳密に含まれることを証明し、空間階層定理は、LがPSPACEに厳密に含まれることを証明します。

決定論的および非決定論的チューリングマシンは最も一般的に使用される計算モデルですが、多くの複雑性クラスは他の計算モデルに基づいて定義されています。特に、

• 確率的チューリングマシンを使用して、 BPP、PP、RP、ZPPなどのクラスが定義されています。
• IP、MA、AMクラスを含む、対話型証明システムを使用して定義されたクラスが多数あります。
• ブール回路を使用して、クラスP/polyとそのサブクラスNCおよびACを含む多数のクラスが定義されています。
• 量子チューリングマシンを使用して、BQPクラスやQMAクラスを含む多くのクラスが定義されています。

これらについては以下でさらに詳しく説明します。

ランダムにコインを投げることができるチューリング マシンの変種である確率的チューリング マシンを使用して、いくつかの重要な複雑性クラスが定義されています。これらのクラスは、ランダム化アルゴリズムの複雑性をより適切に説明するのに役立ちます。

確率的チューリングマシンは決定論的チューリングマシンに似ていますが、単一の遷移関数 (計算の各ステップでどのように進めるかに関する一連のルール) に従うのではなく、各ステップで複数の遷移関数を確率的に選択します。確率的チューリングマシンの標準的な定義では、2 つの遷移関数が指定されているため、各ステップでの遷移関数の選択はコイン投げに似ています。計算の各ステップで導入されるランダム性により、エラーが発生する可能性があります。つまり、チューリングマシンが受け入れることになっている文字列が拒否される場合もあれば、チューリングマシンが拒否することになっている文字列が受け入れられる場合もあります。その結果、確率的チューリングマシンに基づく複雑性クラスは、許容されるエラーの量を中心に定義されます。正式には、エラー確率を使用して定義されます。確率的チューリングマシンは、次の場合にエラー確率を持つ言語を認識すると言われています。 ${\displaystyle \epsilon }$${\displaystyle M}$${\displaystyle L}$${\displaystyle \epsilon }$

1. 文字列は、${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon }$
2. 文字列が含まれない場合は、${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }$

基本的なランダム化時間計算量クラスは、ZPP、RP、co-RP、BPP、およびPPです。

最も厳密なクラスはZPP (ゼロエラー確率多項式時間) であり、エラー確率が 0 の確率的チューリングマシンによって多項式時間で解決可能な問題のクラスです。直感的には、これはまったくエラーを要求しないため、確率的問題の中で最も厳密なクラスです。

もう少し緩いクラスがRP (ランダム化多項式時間) で、これは言語にない文字列についてはエラーなしを維持しますが、言語に含まれる文字列については制限されたエラーを許容します。より正式には、文字列が言語にない場合は常に拒否し、文字列が言語に含まれる場合は少なくとも 1/2 の確率で受け入れる確率的多項式時間チューリング マシンがある場合、言語は RP です。クラスco-RPは同様に定義されますが、役割が逆になります。つまり、言語に含まれる文字列についてはエラーは許容されませんが、言語にない文字列については許容されます。まとめると、クラスRPとco-RP は、片側エラーの確率的チューリング マシンによって解決できるすべての問題を網羅します。 ${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$

誤差要件をさらに緩めて両側誤差を許容すると、 BPP (誤差制限確率多項式時間) クラスが生成されます。これは、(言語内の文字列と言語外の文字列の両方について) 誤差確率が 1/3 未満の確率チューリングマシンによって多項式時間で解ける問題のクラスです。BPPは確率的複雑性クラスの中で最も実用的です。BPP の問題には、実際のコンピュータですばやく実行できる効率的なランダム化アルゴリズムがあります。BPPは、 P=BPP であるかどうかというコンピュータサイエンスにおける重要な未解決問題の中心でもあります。これが正しい場合、ランダム性によってコンピュータの計算能力が向上しないことを意味します。つまり、確率チューリングマシンはすべて、最大で多項式の速度低下で決定論的チューリングマシンによってシミュレートできます。

効率的に解決可能な確率的問題の最も広範なクラスはPP (確率的多項式時間) であり、これはすべての文字列に対してエラー確率が 1/2 未満で、確率的チューリング マシンによって多項式時間で解決可能な言語のセットです。

ZPP、RP 、およびco-RP はすべてBPPのサブセットであり、 BPP はPPのサブセットです。 この理由は直感的です。ゼロエラーと片側エラーのみを許容するクラスはすべて、両側エラーを許容するクラスに含まれており、PP はBPPのエラー確率を緩和するだけです。ZPP はRPおよびco-RPと次のように関連しています。つまり、ZPP はRPとco-RP の両方に含まれる問題だけで構成されています。 直感的には、これはRPとco-RP が片側エラーのみを許容するという事実から導かれます。つまり、 co-RP は言語内の文字列のエラーを許容せず、RP は言語にない文字列のエラーを許容しません。 したがって、問題がRPとco-RP の両方に含まれる場合、言語内の文字列と言語にない文字列の両方でエラーが発生しない (つまり、エラーがまったく発生しない) 必要があり、これはZPPの定義とまったく同じです。 ${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

重要なランダム化空間複雑度クラスには、BPL、RL、RLP などがあります。

対話型証明システムを使用して、多数の複雑性クラスが定義されています。対話型証明は、複雑性クラスNPの証明定義を一般化し、暗号化、近似アルゴリズム、および形式検証に関する洞察をもたらします。

対話型証明システムは、計算を 2 つの当事者 (証明者と検証者)間のメッセージ交換としてモデル化する抽象マシンです。当事者はメッセージを交換することで対話し、検証者が証明者から受け取ったメッセージに基づいて入力を受け入れると決定した場合、入力文字列はシステムによって受け入れられます。証明者の計算能力は無制限ですが、検証者の計算能力は制限されています (対話型証明システムの標準的な定義では、検証者は多項式時間制限付きと定義されています)。ただし、証明者は信頼できません (計算能力が制限されていない証明者が文字列が言語であるかどうかを解決し、信頼できる「はい」または「いいえ」を検証者に送信することで、証明システムがすべての言語を簡単に認識できないためです)。そのため、検証者は証明者に一連の質問を連続して「尋ねる」ことで「尋問」を行い、文字列が言語であるという高い信頼度が得られた場合にのみ証明者を受け入れます。^[15]${\displaystyle P}$${\displaystyle V}$${\displaystyle P}$

クラスNPは、検証者が決定論的多項式時間チューリング マシンに制限され、手順が 1 ラウンドに制限される (つまり、証明者は単一の完全な証明 (通常は証明書と呼ばれる) のみを検証者に送信する) 単純な証明システムです。言い換えると、クラスNP (答えが「はい」の場合に、決定論的チューリング マシンによって多項式時間で検証可能な証明を持つ問題インスタンスを持つ決定問題のセット) の定義は、言及されていない証明者によって証明が構築され、決定論的チューリング マシンが検証者である証明システムです。このため、NP はdIP (決定論的インタラクティブ証明)とも呼ばれますが、そのように呼ばれることはほとんどありません。

NP は、決定論的 (多項式時間) 検証器を備えた対話型証明システムの全能力を活用できることがわかります。これは、決定論的検証器を備えたどの証明システムでも、証明者と検証器の間で 1 ラウンド以上のメッセージングが必要になることは決してないことを示すことができるためです。したがって、標準的な複雑性クラスよりも高い計算能力を提供する対話型証明システムには確率的検証器が必要であり、これは、検証器の証明者への質問が確率的アルゴリズムを使用して計算されることを意味します。上記のランダム化計算のセクションで述べたように、確率的アルゴリズムはシステムにエラーを導入するため、確率的証明システムに基づく複雑性クラスはエラー確率によって定義されます。 ${\displaystyle \epsilon }$

この特徴から生じる最も一般的な計算量クラスは、クラスIP（対話型多項式時間）であり、これは対話型証明システムによって解けるすべての問題のクラスである。ここで、は確率的多項式時間であり、証明システムは2つの特性を満たす：言語${\displaystyle (P,V)}$${\displaystyle V}$${\displaystyle L\in {\mathsf {IP}}}$

1. （完全性）文字列は${\displaystyle w}$${\displaystyle L}$${\displaystyle \Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\geq {\tfrac {2}{3}}}$
2. （健全性）文字列が${\displaystyle w}$${\displaystyle L}$${\displaystyle \Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\leq {\tfrac {1}{3}}}$

IPの重要な特徴は、それがPSPACEに等しいことです。言い換えれば、多項式時間の対話型証明システムで解決できる問題は、多項式空間リソースを持つ決定論的チューリングマシンでも解決でき、その逆も同様です。

IPのプロトコルの修正により、別の重要な複雑性クラスAM (アーサー・マーリン プロトコル) が生成されます。 IPで使用される対話型証明システムの定義では、証明者は検証者が確率計算で使用したコインを見ることができませんでした。証明者が見ることができたのは、検証者がこれらのコインを使用して生成したメッセージだけでした。このため、コインはプライベート ランダム コインと呼ばれます。対話型証明システムは、検証者が使用するコインがパブリック ランダム コインであるように制約できます。つまり、証明者はコインを見ることができます。正式には、AMは、検証者が証明者にランダムな文字列を送信し、証明者がメッセージで応答し、検証者が証明者からのメッセージに決定論的な多項式時間関数を適用して受け入れるか拒否するかを決定する対話型証明を持つ言語のクラスとして定義されます。AM はAM [ k ]に一般化できます。ここで、 k は交換されるメッセージの数です (したがって、一般化された形式では、上で定義された標準AMはAM [2]です)。しかし、すべての に対して、AM [ k ]= AM [2]が成り立ちます。 が成り立ちます。 ${\displaystyle k\geq 2}$${\displaystyle {\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]}$

対話型証明システムを使用して定義されるその他の複雑性クラスには、MIP (マルチ証明者対話型多項式時間) やQIP (量子対話型多項式時間) などがあります。

チューリング マシンに代わる計算モデルとして、ブール回路があります。これは、現代のコンピュータで使用されているデジタル回路の簡略化されたモデルです。このモデルは、理論上の計算と実際の計算を直感的に結び付けるだけでなく、非均一計算 (同じ問題内で入力サイズが異なるとアルゴリズムも異なる計算) の自然なモデルでもあります。

正式には、ブール回路は有向非巡回グラフであり、エッジはワイヤ（ビット値 0 と 1 を伝送）を表し、入力ビットはソース頂点（入力エッジのない頂点）によって表され、ソース以外のすべての頂点は論理ゲート（通常はANDゲート、ORゲート、NOT ゲート）を表します。 1 つの論理ゲートは出力ゲートとして指定され、計算の終了を表します。 入力変数を持つ回路の入出力動作はブール関数によって表されます。たとえば、入力ビット では、回路の出力ビットは数学的に として表されます。 回路はブール関数を計算すると言われています。 ${\displaystyle C}$${\displaystyle C}$${\displaystyle n}$ ${\displaystyle f_{C}:\{0,1\}^{n}\to \{0,1\}}$${\displaystyle x_{1},x_{2},...,x_{n}}$${\displaystyle b}$${\displaystyle b=f_{C}(x_{1},x_{2},...,x_{n})}$${\displaystyle C}$${\displaystyle f_{C}}$

特定の回路はいずれも入力頂点の数が固定されているため、そのサイズの入力にしか作用しません。ただし、言語(決定問題の形式的表現) には長さの異なる文字列が含まれるため、言語を単一の回路で完全に表現することはできません (これは、言語が任意の入力サイズに作用できる単一のチューリングマシンで完全に記述されるチューリングマシンモデルとは対照的です)。したがって、言語は回路ファミリによって表されます。回路ファミリは回路 の無限リストです。ここで、 は入力変数を持つ回路です。回路ファミリは、すべての文字列 に対して、が言語内にある場合と （ はの長さ）に限り、その場合に限り、言語を決定すると言われます。言い換えると、が入力のときに回路( のビット数と同じ数の入力頂点を持つ回路) が 1 と評価される場合、サイズの文字列は回路ファミリによって表される言語内にあります。 ${\displaystyle (C_{0},C_{1},C_{2},...)}$${\displaystyle C_{n}}$${\displaystyle n}$${\displaystyle L}$${\displaystyle w}$${\displaystyle w}$${\displaystyle L}$${\displaystyle C_{n}(w)=1}$${\displaystyle n}$${\displaystyle w}$${\displaystyle w}$${\displaystyle n}$${\displaystyle (C_{0},C_{1},C_{2},...)}$${\displaystyle C_{n}}$${\displaystyle w}$${\displaystyle w}$

チューリングマシンを使用して定義される複雑性クラスは時間複雑性で記述されますが、回路複雑性クラスは回路サイズ、つまり回路内の頂点の数 で定義されます。回路ファミリのサイズ複雑性は関数で、 は回路サイズ です。よく知られている関数クラスは、このことから自然に導かれます。たとえば、多項式サイズの回路ファミリは、関数 が多項式となる回路ファミリです。 ${\displaystyle (C_{0},C_{1},C_{2},...)}$${\displaystyle f:\mathbb {N} \to \mathbb {N} }$${\displaystyle f(n)}$${\displaystyle C_{n}}$${\displaystyle f}$

複雑性クラスP/poly は、多項式サイズの回路族によって決定可能な言語の集合である。回路複雑性と時間複雑性の間には自然な関係があることが判明している。直感的には、時間複雑性が小さい言語 (つまり、チューリングマシン上での逐次演算が比較的少ない) は、回路複雑性も小さい (つまり、ブール演算が比較的少ない) 。形式的には、言語が （ここでは関数）に含まれる場合、回路複雑性 を持つことを示すことができる。^[16]この事実から直接、 が導かれる。言い換えれば、決定性チューリングマシンによって多項式時間で解決できる問題は、多項式サイズの回路族によっても解決できる。さらに、包含が適切であること、すなわち(たとえば、P/polyに含まれる決定不可能な問題がいくつかあります) である。 ${\displaystyle {\mathsf {DTIME}}(t(n))}$${\displaystyle t}$${\displaystyle t:\mathbb {N} \to \mathbb {N} }$${\displaystyle O(t^{2}(n))}$${\displaystyle {\mathsf {\color {Blue}P}}\subset {\textsf {P/poly}}}$${\displaystyle {\textsf {P}}\subsetneq {\textsf {P/poly}}}$

P/poly には、複雑性クラス間の関係の研究に非常に役立つ多くの特性があります。特に、PとNPに関連する問題を調査するのに役立ちます。たとえば、P/polyに含まれない言語がNPに存在する場合、 となります。^[17] P/poly は、多項式階層の特性の調査にも役立ちます。たとえば、NP ⊆ P/polyの場合、PH はに縮小されます。 P/polyと他の複雑性クラスの関係の詳細については、「P/poly の重要性」を参照してください。P/poly は、チューリングマシンの特性の一般的な研究にも役立ちます。これは、クラスが、多項式制限アドバイス関数を備えた多項式時間チューリングマシンによって認識される言語のクラスとして同等に定義できるためです。 ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$ ${\displaystyle \Sigma _{2}^{\mathsf {P}}}$

P/polyには、興味深い特性を独自に持つ2 つのサブクラスがあり、それがNCとACです。これらのクラスは、回路サイズだけでなく、深さの観点からも定義されます。回路の深さとは、入力ノードから出力ノードまでの最長の有向パスの長さです。クラスNCは、多項式サイズだけでなく多対数深さにも制限される回路ファミリによって解決できる言語の集合です。クラスACはNCと同様に定義されますが、ゲートには無制限のファンインが許可されます (つまり、AND ゲートと OR ゲートを 2 ビット以上に適用できます)。NCは、効率的な並列アルゴリズムを持つ言語のクラスとして同等に定義できるため、注目すべきクラスです。

量子情報科学において重要なクラスであるBQPとQMA は、量子チューリングマシンを使用して定義されます。

コンピュータ科学者が研究する複雑さのクラスのほとんどは決定問題の集合ですが、他の種類の問題の観点から定義された複雑さのクラスもいくつかあります。特に、計数問題、関数問題、および約束問題で構成される複雑さのクラスがあります。これらについては、以下で詳しく説明します。

計数問題では、解が存在するかどうか（決定問題と同様）だけでなく、解がいくつ存在するかを問う。^[18]たとえば、決定問題では、特定のグラフに単純閉路があるかどうかを問う（答えは単純なはい/いいえ）が、対応する計数問題（「シャープサイクル」と発音）では、単純閉路がいくつあるかを問う。^[19]計数問題の出力はしたがって数値であるが、決定問題の出力は単純なはい/いいえ（または承認/拒否、0/1、またはその他の同等の方式）である。^[20]${\displaystyle {\texttt {CYCLE}}}$${\displaystyle G}$${\displaystyle \#{\texttt {CYCLE}}}$${\displaystyle G}$

したがって、決定問題は数学的には形式言語として表現されるのに対し、計数問題は数学的には関数として表現されます。計数問題は、すべての入力 に対して が解の数となるような関数 として形式化されます。たとえば、問題では、入力 はグラフ(ビットの文字列 として表現されるグラフ) であり、 は内の単純閉路の数です。 ${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$${\displaystyle w\in \{0,1\}^{*}}$${\displaystyle f(w)}$${\displaystyle \#{\texttt {CYCLE}}}$${\displaystyle G\in \{0,1\}^{*}}$${\displaystyle f(G)}$${\displaystyle G}$

計数問題は、統計的推定、統計物理学、ネットワーク設計、経済学など、多くの分野で発生します。^[21]

#P （「シャープP」と発音）は、 NPのカウントバージョンと考えることができる重要なクラスのカウント問題です。^[22] NPとの関連は、問題の解の数が非決定性チューリングマシンの計算ツリーの受け入れブランチの数に等しいという事実から生じます。したがって、 #Pは次のよ​​うに正式に定義されます。

#Pは、すべての に対して が上の の計算木の受理枝の数に等しいような多項式時間非決定性チューリングマシンが存在するようなすべての関数の集合である。^[22]${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$${\displaystyle M}$${\displaystyle w\in \{0,1\}^{*}}$${\displaystyle f(w)}$${\displaystyle M}$${\displaystyle w}$

NP が非決定性と検証者（つまり対話型証明システム）の両方の観点から定義できるのと同様に、 #Pも検証者の観点から同等に定義できます。与えられた問題インスタンスに対する多項式時間でチェック可能な証明書が存在する場合、決定問題はNPに属することを思い出してください。つまり、NP は入力に対して多項式時間で正しさをチェックできるメンバーシップの証明（証明書）が存在するかどうかを尋ねます。クラス#Pは、そのような証明書がいくつ存在するかを尋ねます。^[22]このコンテキストでは、#P は次のように定義されます。

#Pは、多項式と多項式時間チューリングマシン（検証器）が存在するような関数の集合であり、任意のに対して、となる。^[23]言い換えれば、は、に対する多項式サイズの証明書をすべて含む集合のサイズに等しい。${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$${\displaystyle p:\mathbb {N} \to \mathbb {N} }$${\displaystyle V}$${\displaystyle w\in \{0,1\}^{*}}$${\displaystyle f(w)={\Big |}{\big \{}c\in \{0,1\}^{p(|w|)}:V(w,c)=1{\big \}}{\Big |}}$${\displaystyle f(w)}$${\displaystyle w}$

計数問題は、関数問題と呼ばれるより広範な問題群のサブセットです。関数問題とは、関数 の値を計算するタイプの問題です。正式には、関数問題は、任意のアルファベットの文字列の関係として定義されます。 ${\displaystyle f:A\to B}$${\displaystyle f}$${\displaystyle R}$ ${\displaystyle \Sigma }$

${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}$

アルゴリズムは、を満たす が存在するすべての入力に対して を解き、そのような を 1 つ生成します。これは、 が関数であり、アルゴリズムがすべての についてを解くことを別の方法で表すだけです。 ${\displaystyle f}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)\in R}$${\displaystyle y}$${\displaystyle f}$${\displaystyle f(x)}$${\displaystyle x\in \Sigma ^{*}}$

重要な関数複雑性クラスはFP、つまり効率的に解ける関数のクラスである。^[23]より具体的には、FP は決定論的チューリングマシンによって多項式時間で解くことができる関数問題の集合である。^[23] FP はPの関数問題相当と考えることができる。重要なのは、FP が計数問題とP対NP の両方について何らかの洞察を提供していることである。#P = FPであれば、 NPの問題に対する証明書の数を決定する関数は効率的に解ける。また、証明書の数を計算することは証明書が存在するかどうかを判断することと同じくらい難しいため、#P = FPであればP = NPとなる（逆の場合も成り立つかどうか、つまりP = NPが#P = FP を意味するかどうかは不明である）。^[23]

FPがPと同等の関数問題であるのと同様に、FNPはNPと同等の関数問題である。重要なのは、P = NPの場合にのみFP = FNPであるということ。^[24]

約束問題は、問題への入力がすべての可能な入力の特定のサブセットからであることが保証される（「約束される」）決定問題の一般化です。決定問題では、のアルゴリズムはすべてのに対して（正しく）動作する必要があることを思い出してください。約束問題は、入力を のサブセットに制限することで、への入力要件を緩和します。 ${\displaystyle L\subseteq \{0,1\}^{*}}$${\displaystyle M}$${\displaystyle L}$ ${\displaystyle w\in \{0,1\}^{*}}$${\displaystyle M}$${\displaystyle \{0,1\}^{*}}$

具体的には、約束問題は交差しない集合のペアとして定義され、ここで^[25]${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$

• ${\displaystyle \Pi _{\text{ACCEPT}}\subseteq \{0,1\}^{*}}$受け入れられるすべての入力の集合です。
• ${\displaystyle \Pi _{\text{REJECT}}\subseteq \{0,1\}^{*}}$拒否されるすべての入力の集合です。

したがって、約束問題のアルゴリズムへの入力は であり、これは約束と呼ばれます。 内の文字列は約束 を満たすと言われます。^[25]定義により、と は互いに素でなければなりません。 ${\displaystyle M}$${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$${\displaystyle \Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}}$${\displaystyle \Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}}$${\displaystyle \Pi _{\text{ACCEPT}}}$${\displaystyle \Pi _{\text{REJECT}}}$${\displaystyle \Pi _{\text{ACCEPT}}\cap \Pi _{\text{REJECT}}=\emptyset }$

この定式化では、決定問題は、単なる約束 という自明な約束問題の部分集合であることが分かります。したがって、決定問題では、問題を のみ（暗黙的に ）として定義する方が簡単です。このページでは、 が形式言語であることを強調するために と表記します。 ${\displaystyle \Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}=\{0,1\}^{*}}$${\displaystyle \Pi _{\text{ACCEPT}}}$${\displaystyle \Pi _{\text{REJECT}}}$${\displaystyle \{0,1\}^{*}/\Pi _{\text{ACCEPT}}}$${\displaystyle L}$${\displaystyle \Pi _{\text{ACCEPT}}=L}$

約束問題は、多くの計算問題をより自然に定式化します。たとえば、計算問題は「平面グラフが与えられた場合、...かどうかを判断する」のようなものになります。 ^{[26]これは、}すべての文字列を平面グラフに変換する何らかの変換スキーマがあると想定される決定問題として表現されることがよくあります。ただし、入力が平面グラフであることが約束されている約束問題として定義する方が簡単です。 ${\displaystyle s\in \{0,1\}^{*}}$

約束問題は、意思決定問題の標準的な複雑性クラスに対する別の定義を提供する。例えば、Pは約束問題として定義できる。 ^[27]

P は、決定論的多項式時間で解決可能な約束問題のクラスです。つまり、次のような 多項式時間アルゴリズムが存在する場合、約束問題はPに属します。${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$${\displaystyle M}$

• すべての${\displaystyle x\in \Pi _{\text{ACCEPT}},M(x)=1}$
• 永遠に${\displaystyle x\in \Pi _{\text{REJECT}},M(x)=0}$

したがって、決定問題のクラス、つまり形式言語として定義された問題のクラスは、クラス内の言語が単純に であり、暗黙的に である約束問題に自然に翻訳されます。 ${\displaystyle L}$${\displaystyle L=\Pi _{\text{ACCEPT}}}$${\displaystyle \Pi _{\text{REJECT}}}$${\displaystyle \{0,1\}^{*}/\Pi _{\text{ACCEPT}}}$

Pのような多くの基本的な複雑性クラスをプロミス問題として定式化しても、その性質についての追加的な洞察はほとんど得られません。しかし、プロミス問題として定式化することでコンピュータ科学者にとって有用な複雑性クラスがいくつかあります。たとえば、プロミス問題はSZK（統計的ゼロ知識）の研究で重要な役割を果たしてきました。^[28]

次の表は、複雑性理論で考慮される問題のクラスの一部を示しています。クラスXがYの厳密な部分集合である場合、X はY の下に示され、それらを結ぶ濃い線が表示されます。X が部分集合であるが、それらが等しい集合であるかどうかが不明である場合、線はより薄く点線で表示されます。技術的には、決定可能と決定不可能への分類は、計算可能性理論の研究に関係しますが、複雑性クラスを全体的に把握するのに役立ちます。

• 複雑度クラスのリスト

• アーロンソン、スコット(2017 年 1 月 8 日)。「P=?NP」。計算複雑性に関する電子コロキウム。ワイツマン科学研究所。2020 年 6 月 17 日時点のオリジナルよりアーカイブ。
• Arora, Sanjeev ; Barak, Boaz (2009).計算複雑性: 現代的アプローチケンブリッジ大学出版局。草稿。2022年2月23日時点のオリジナルよりアーカイブ。ISBN 978-0-521-42426-4。
• Arora, Sanjeev (2003 年春)。「計数に関係する計算量クラス」。コンピュータサイエンス 522: 計算量理論。プリンストン大学。2022 年 5 月 21 日時点のオリジナルよりアーカイブ。
• Barak, Boaz (2006 年春)。「計数の複雑さ」(PDF)。コンピュータサイエンス 522: 計算の複雑さ。プリンストン大学。2021 年 4 月 3 日時点のオリジナルよりアーカイブ。
• フォートナウ、ランス (1997)。「複雑性の計算」(PDF)。ヘマスパアンドラ、レーン A.、セルマン、アラン L. (編)。複雑性理論回顧 II。シュプリンガー。pp. 81–106。ISBN 97803879497342022年6月18日時点のオリジナル（PDF）よりアーカイブ。
• Gasarch, William I. (2019). 「ゲストコラム: 第3回P =? NP世論調査」(PDF)。メリーランド大学。 2021年11月2日時点のオリジナルよりアーカイブ(PDF) 。
• Goldreich, Oded (2006)。「Promise Problems: A Survey」(PDF)。Goldreich, Oded、Rosenberg, Arnold L.、Selman, Alen L. (編)。理論コンピュータサイエンス。コンピュータサイエンス講義ノート、第 3895 巻(PDF) 。コンピュータサイエンス講義ノート、第 3895 巻。Springer。pp. 254–290。doi :10.1007/ 11685654_12。ISBN 978-3-540-32881-02021年5月6日時点のオリジナルよりアーカイブ（PDF） 。
• Johnson, David S. (1990)。「複雑性クラスのカタログ」。アルゴリズムと複雑性。理論計算機科学ハンドブック。Elsevier。pp. 67–161。doi :10.1016/ b978-0-444-88071-0.50007-2。
• Lee, James R. (2014 年 5 月 22 日). 「講義 16」(PDF) . CSE431: 計算理論入門.ワシントン大学. 2021 年 11 月 29 日時点のオリジナルよりアーカイブ(PDF) . 2022 年10 月 5 日閲覧。
• リッチ、エレイン(2008)。オートマトン、計算可能性、複雑性: 理論と応用( PDF)。プレンティス ホール。ISBN 978-01322880642022年1月21日時点のオリジナルよりアーカイブ（PDF） 。
• Sipser, Michael (2006)。計算理論入門(PDF) (第 2 版)。米国: Thomson Course Technology。ISBN 0-534-95097-32022年2月7日時点のオリジナル（PDF）よりアーカイブ。
• Watrous, John (2006 年 4 月 11 日)。「講義 22: 量子計算複雑性」(PDF)。ウォータールー大学。2022年 6 月 18 日時点のオリジナルからアーカイブ(PDF) 。

• The Complexity Zoo Archived 2019-08-27 at the Wayback Machine : 複雑性クラスの膨大なリスト、専門家向けのリファレンス。
• Neil Immerman . 「計算複雑性理論」。2016 年 4 月 16 日のオリジナルからアーカイブ。複雑性クラスの階層とそれらがどのように組み合わされるかを示す図が含まれています。
• Michael Garey、David S. Johnson著「コンピュータと扱いにくさ: NP 完全性理論ガイド」ニューヨーク: WH Freeman & Co.、1979 年。NP 完全問題 (解決に計算に非現実的なほど長い時間を要する重要な問題カテゴリ) に関する標準参考書。