A DFA = {<B, w> | B は入力文字列 w を受理する DFA}A NFA = {<B, w> | B は入力文字列 w を受理する NFA}A REX = {<R, w> | R は文字列 w を生成する正規表現}E DFA = {<A> | A は DFA、かつ L(A) = Ø} で表現されるEQ DFA = {<A, B> | A と B は DFA、かつ L(A) = L(B)} と表現するA CFG = {<G, w> | G は文字列 w を生成する CFG}E CFG = {<G> | G は CFG、かつ L(G) = Ø}EQ CFG = {<G, H> | G と H は CFG、かつ L(G) = L(H)}A TM = {<M, w> | M は TM であり、M は w を受理する} として表現されるHALT TM = {<M, w> | M は TM であり、M は入力 w に対して停止する}E TM = {<M> | M は TM であり、L(M) = Ø}REGULAR TM = {<M> | M は TM であり、L(M) は正規言語}A LBA = {<M, w> | M は文字列 w を受理する LBA}q * n * g^n 個の M の異なる計算状況が存在するq * n * g^n ステップ以内で停止しなければループしているとわかるE LBA = {<M> | M は L(M) = Ø}PCP = {<P> | P はマッチを持つ Post 対応問題の入力例}f: Σ* → Σ* について、任意の入力 w に対して Turing 機械 M が f(w) をテープ上に設定して停止するならば、その f を計算可能な関数であるというf: Σ* → Σ* が、任意の w に対して、w ∈ A ⇔ f(w) ∈ B を満たす時、言語 A は言語 B へ写像帰着可能性であるといい、A <=m B と表す。この関数 f を A の B への帰着というq: Σ* → Σ* が存在するt: Σ* × Σ* → Σ* を計算する Turing 機械とする。このとき、すべての w に対して r(w) = t(<R>, w) となる関数 r: Σ* → Σ* を計算する Turing 機械 R が存在する<R> を受け取り、それを使った計算を行える機械 T を作れる<M> を得る」という文章を含めることができる<M> の文字数であるとする。M と等価な、より短い記述を持つ Turing 機械がないならば、M は最小(minimal)であるというMIN TM = {<M> | M は最小 TM}K(x) = |d(x)| とする∃c∀x [K(x) <= |x| + c]∃c∀x [K(xx) <= |x| + c]∃c∀x,y [K(xy) <= 2 * K(x) + K(y) + c]K(x) = |x| - c であるとき、x は c 圧縮可能(c-compressible)であるというA = {w | V はある文字列 c に対して <w, c> を受理}NTIME(t(n)) = {L | L は Ｏ(t(n)) 時間の非決定性 Turing 機械で判定される言語}φ = (not x ∧ y) ∨ (x ∧ not z) という Boole 論理式があるとする。条件を満たす x, y, z が割り当てられる時、Boole 論理式は充足可能(satisfiable)であるというSAT = {<φ> | φ は充足可能な Boole 論理式}f: Σ* → Σ* は多項式時間計算可能関数であるというf: Σ* → Σ* が存在して、すべての w について、w ∈ A ⇔ f(w) ∈ B である時、A <=P B と書き、言語 A が言語 B に多項式時間写像帰着可能(polynomial time mapping reducible)、あるいは単に多項式時間帰着可能であるという。関数 f は A から B への多項式時間帰着(polynomial time reduction)と呼ばれるCLIQUE = {<G, k> | G は k クリークを持つ無向グラフ}VERTEX-COVER = {<G, k> | G は k 個の節点からなる頂点被覆を持つような無向グラフ}SUBSET-SUM = {<S, t> | S = {x1, ..., xk} で、ある {y1, ..., yl} ⊆ {x1, ..., xk} に対して Σyi = t}f: N → N と定義する。M の領域計算量が f(n) の時、M は領域 f(n) で動作するとも言うf: N → R+ を関数とする。領域計算量のクラス(space complexity class) SPACE(f(n)) と NSPACE(f(n)) を次のように定義するSPACE(f(n)) = {L | L は Ｏ(f(n)) 領域の決定性 Turing 機械によって判定される言語}NSPACE(f(n)) = {L | L は Ｏ(f(n)) 領域の非決定性 Turing 機械によって判定される言語}f: N → R+ に対して NSPACE(f(n)) ⊆ SPACE(f^2(n)) である∀x∃y[y > x] は真だが ∃y∀x[y > x] は偽となるTQBF = {<φ> | φ は値が真である完全に限定された Boole 論理式}φ = ∃x1 ∀x2 ∃x3 ... Qxk [ψ] を冠頭標準形の限定された Boole 論理式とするFORMULA-GAME = {<φ> | プレーヤ E が φ に対する論理式ゲームにおいて必勝戦略を持つ}GG = {<G, b> | プレーヤ 1 がグラフ G 上で節点 b で開始する一般化しりとりで必勝戦略を持つ}L = SPACE(log n)NL = NSPACE(log n)PATH = {<G, s, t> | G は s から t への有向パスを持つ有向グラフ}f: Σ* → Σ* を計算する