NP 完全性と Cook–Levin の定理 | 計算理論

1 Boolean 論理式と SAT

変数記号を $z_1,z_2,\ldots$ とする。式は有限文字列として符号化し、変数の添字と括弧を含む符号長を式の長さとする。

定義 1.1. Boolean 論理式 (Boolean formula) は、変数 $z_i$ 、定数 $0,1$ 、否定 $\neg$ 、論理和 $\lor$ 、論理積 $\land$ から有限回の構成で得られる式である。式に現れる変数への割当 (truth assignment) は、各変数へ $0$ または $1$ を対応させる写像であり、演算

\neg 0=1,\quad \neg1=0,\quad a\lor b=\max\{a,b\},\quad a\land b=\min\{a,b\}

によって式の値を定める。値が $1$ となる割当が存在する式を充足可能 (satisfiable) という。

変数または変数の否定をリテラル (literal) という。リテラルの有限個の論理和を節 (clause) といい、節の有限個の論理積である式を連言標準形 (conjunctive normal form)（CNF）という。

正しく符号化された充足可能な Boolean 論理式全体の言語を

\mathsf{SAT}

とする。不正な式の符号は $\mathsf{SAT}$ に含めない。

CNF の節に含めるリテラル数には上限を置かない。特に、本記事では各節のリテラル数を高々三に制限した問題 3SAT を扱わない。

命題 1.2.

\mathsf{SAT}\in\mathsf{NP}

である。

証明. 入力 $\varphi$ が正しい Boolean 論理式の符号でなければ拒否する。正しい式なら、 $\varphi$ に現れる相異なる変数を出現順に列挙する。証明書を各変数の値を表すビット列とし、列挙した変数数と同じ長さであることを確認する。

検証器は構文木の葉から根へ値を計算する。各変数葉には証明書の対応するビットを置き、各否定・論理和・論理積の頂点では子の値から一回の Boolean 演算で値を得る。変数名を表へ登録して参照する処理を単純な逐次探索で実装しても、式の符号長を $m$ とすれば $O(m^2)$ 時間で終わる。証明書長は式に現れる変数数以下であり、高々 $m$ である。

$\varphi$ が充足可能なら、その充足割当を証明書にすれば検証器は受理する。検証器が受理したなら、証明書が定める割当の下で構文木の根の値が $1$ であるため、 $\varphi$ は充足可能である。§E18.11 定理 3.1により $\mathsf{SAT}\in\mathsf{NP}$ である。▨

2 NP 困難性と NP 完全性

定義 2.1. 言語 $B$ がNP 困難 (NP-hard) であるとは、任意の言語 $A\in\mathsf{NP}$ について

A\le_{\mathrm p}B

が成り立つことをいう。 $B$ が NP 困難かつ $B\in\mathsf{NP}$ であるとき、 $B$ をNP 完全 (NP-complete) という。

NP 困難性の定義には、対象の言語自身が NP に属するという条件は含まれない。言語が NP 完全であることを示すときは、NP への所属と NP の全言語からの帰着を別々に確認する。

命題 2.2. $B$ が NP 完全で $B\in\mathsf P$ ならば、

\mathsf P=\mathsf{NP}

である。

証明.§E18.11 命題 1.4により $\mathsf P\subseteq\mathsf{NP}$ である。任意の $A\in\mathsf{NP}$ をとる。 $B$ の NP 困難性から $A\le_{\mathrm p}B$ であり、 $B\in\mathsf P$ と§E18.11 命題 4.2から $A\in\mathsf P$ である。したがって $\mathsf{NP}\subseteq\mathsf P$ であり、二つのクラスは等しい。▨

3 有界計算表

Cook–Levin の帰着では、帰着元の言語ごとに非決定性機械 $N$ を一つ固定する。入力 $x$ だけが帰着関数の入力であり、 $N$ の状態集合、テープアルファベット、遷移規則は式サイズに対する定数として扱われる。

$N$ を一方向無限の単テープ非決定性 Turing 機械とする。§E18.11 命題 1.3により、NP の定義で用いた読取り専用入力テープと作業テープのモデルから、この標準単テープモデルへ変更しても多項式時間性と受理分枝の存在は保たれる。

長さ $n$ の入力上の全分枝が $p(n)$ 段以内に停止するとする。

T(n)=\max\{p(n),n,1\}

と置く。固定多項式 $p$ の値を二進筆算で求めて $n,1$ と比較することにより、 $T(n)$ は $n$ から多項式時間で計算することができる。また、

T(n)\le p(n)+n+1

であるため、 $T(n)$ は $n$ の多項式で上から抑えられる。受理または拒否で早く停止した配置には、記号、ヘッド位置、状態を変えない仮想的な停止後遷移を加える。この規約のもとで、受理分枝の有無は変わらず、すべての分枝はちょうど $T(n)$ 段の配置列へ延長される。

テープアルファベットを $\Gamma$ 、状態集合を $Q$ とし、

\mathcal A=\Gamma\cup(Q\times\Gamma)

をセル記号集合とする。 $a\in\Gamma$ はヘッドがないセルの内容を表し、 $(q,a)\in Q\times\Gamma$ は状態が $q$ でヘッドがそのセルを走査し、セル内容が $a$ であることを表す。

時刻 $t$ と位置 $i$ が $0\le t,i\le T=T(n)$ を満たす格子を考える。初期ヘッドは位置 $0$ にあり、一段で高々一マス動くため、時刻 $T$ までの実際の計算が位置 $T$ より右へ到達することはない。

定義 3.1 (計算表変数). 各 $0\le t,i\le T$ と $a\in\mathcal A$ に対して Boolean 変数

X_{t,i,a}

を置く。 $X_{t,i,a}=1$ は、時刻 $t$ 、位置 $i$ のセル記号が $a$ であることを表す。

さらに、 $N$ の有限な遷移規則集合を $\mathcal R$ とし、各 $0\le t<T$ と $d\in\mathcal R$ に対して変数

C_{t,d}

を置く。 $C_{t,d}=1$ は、時刻 $t$ から $t+1$ への遷移で規則 $d$ を選ぶことを表す。停止後の仮想的な自己遷移も $\mathcal R$ に含める。これらの Boolean 変数を総称して計算表変数 (computation-tableau variable) という。

遷移選択変数を時刻ごとに一つ置くことにより、隣接するセルの更新に別々の非決定的な規則を用いた誤った計算表を排除する。

4 CNF 制約の構成

有限集合の変数 $u_1,\ldots,u_m$ のうちちょうど一つを真にする条件は、CNF

(u_1\lor\cdots\lor u_m) \land \bigwedge_{1\le r<s\le m}(\neg u_r\lor\neg u_s)

で表すことができる。この形式を以下で繰り返し用いる。

4.1 セルとヘッドの一意性

各 $(t,i)$ について、 $a\in\mathcal A$ にわたる $X_{t,i,a}$ のうちちょうど一つが真であるという節を加える。また、各時刻 $t$ について

\{X_{t,i,(q,a)}:0\le i\le T,\ q\in Q,\ a\in\Gamma\}

のうちちょうど一つが真であるという節を加える。後者の節により、各行にヘッドと状態の印がちょうど一つ存在することが保証される。

4.2 初期配置

入力 $x=x_0\cdots x_{n-1}$ に対し、時刻 $0$ の各セルを単位節で固定する。 $n>0$ なら位置 $0$ を $(q_0,x_0)$ 、位置 $1,\ldots,n-1$ をそれぞれ $x_i$ 、位置 $n,\ldots,T$ を空白記号 $\sqcup$ とする。 $n=0$ なら位置 $0$ を $(q_0,\sqcup)$ とし、残りを空白にする。

4.3 遷移規則の一意性と適用可能性

各 $0\le t<T$ について、 $d\in\mathcal R$ にわたる $C_{t,d}$ のうちちょうど一つが真であるという節を加える。規則 $d$ の左辺が状態 $q$ と走査記号 $a$ でない場合には、各位置 $i$ について

\neg X_{t,i,(q,a)}\lor\neg C_{t,d}

を加える。各行にはヘッド印が一つだけ存在するため、真に選ばれた規則はその配置へ適用することができる規則に限られる。

4.4 局所更新

規則 $d$ を固定する。位置 $i$ の次のセル記号は、時刻 $t$ の位置 $i-1,i,i+1$ の三つのセル記号と $d$ だけから一意に定まる。実際、ヘッドが三セルの外にあれば中央セルは変化しない。ヘッドが中央にあれば、書込み記号と移動方向に従って中央の印を消すか残す。ヘッドが左隣から右へ、または右隣から左へ移る場合には、中央セルへ新状態の印を付ける。位置 $0$ で左移動を命じた場合には、ヘッドは位置 $0$ にとどまる。

この局所更新関数を

F_d\colon\mathcal A^3\longrightarrow\mathcal A

と書く。規則 $d$ が三セル内のヘッド印へ適用することができない組や、複数のヘッド印を含む組には、 $F_d$ の値を任意に定めて全域関数にする。実際の行ではヘッド印と規則の適用可能性が別の節により保証されるため、適用不能な組に割り当てた任意の値は充足可能性に影響しない。

左端の外側にはセル記号集合 $\mathcal A$ に属さない固定境界記号 $\triangleleft$ を置く。左端専用の局所更新関数

F_d^{\mathrm L}\colon\mathcal A^2\longrightarrow\mathcal A

を、現在の位置 $0,1$ のセル記号から位置 $0$ の次のセル記号を返す関数として定める。この関数では、位置 $0$ で左移動を命じられたヘッドを位置 $0$ にとどめる。適用することができない組には値を任意に定めて全域関数にする。 $t<T$ ではヘッド位置が高々 $t$ であるため、位置 $T+1$ はまだ訪問されていない。そこで、位置 $T$ の右隣には固定空白記号を置いて $F_d$ を用いる。

各 $0\le t<T$ 、 $1\le i<T$ 、 $d\in\mathcal R$ 、および三つのセル記号 $a_{-1},a_0,a_{+1}\in\mathcal A$ に対して、含意

C_{t,d}\land X_{t,i-1,a_{-1}}\land X_{t,i,a_0}\land X_{t,i+1,a_{+1}} \ \Longrightarrow\ X_{t+1,i,F_d(a_{-1},a_0,a_{+1})}

を CNF の一つの節

\neg C_{t,d}\lor \neg X_{t,i-1,a_{-1}}\lor \neg X_{t,i,a_0}\lor \neg X_{t,i+1,a_{+1}}\lor X_{t+1,i,F_d(a_{-1},a_0,a_{+1})}

として加える。左端 $i=0$ では、各 $a_0,a_{+1}\in\mathcal A$ に対して

\neg C_{t,d}\lor \neg X_{t,0,a_0}\lor \neg X_{t,1,a_{+1}}\lor X_{t+1,0,F_d^{\mathrm L}(a_0,a_{+1})}

を加える。右端 $i=T$ では、各 $a_{-1},a_0\in\mathcal A$ に対して

\neg C_{t,d}\lor \neg X_{t,T-1,a_{-1}}\lor \neg X_{t,T,a_0}\lor X_{t+1,T,F_d(a_{-1},a_0,\sqcup)}

を加える。各行のセル記号が一意であるため、前件が真になる節は実際の三セルの値に対応する節だけであり、次行の値はその節によって定まる。

4.5 受理条件

時刻 $T$ に受理状態の印が存在するという一つの節

\bigvee_{\substack{0\le i\le T\\a\in\Gamma}} X_{T,i,(q_{\mathrm{acc}},a)}

を加える。停止後の自己遷移によって、時刻 $T$ で受理状態にあることは、時刻 $T$ 以前に受理したことと同値である。

以上のすべての節の論理積を

\Phi_{N,x}

とする。

5 計算表と充足割当の同値性

補題 5.1. 時刻 $t$ と $t+1$ の二行がセル・ヘッドの一意性を満たし、時刻 $t$ で選ばれた規則 $d$ が唯一のヘッド印へ適用可能であるとする。この二行がすべての局所更新節を満たすことと、第二行が規則 $d$ による第一行の正しい次配置であることは同値である。

証明. 第二行が正しい次配置なら、内点 $1\le i<T$ のセル記号は $F_d(a_{i-1},a_i,a_{i+1})$ 、左端のセル記号は $F_d^{\mathrm L}(a_0,a_1)$ 、右端のセル記号は $F_d(a_{T-1},a_T,\sqcup)$ である。したがって、前件が真になる局所更新節の後件も真であり、他の局所更新節は前件の少なくとも一つのリテラルが偽である。よってすべての節が満たされる。

逆に、すべての局所更新節が満たされるとする。内点 $1\le i<T$ では、一意性によって第一行の位置 $i-1,i,i+1$ の実際のセル記号 $a_{i-1},a_i,a_{i+1}$ が一つずつ定まる。選択規則も $d$ に一意に定まるため、実際の三セル記号と選択規則 $d$ を前件とする節ではすべての否定リテラルが偽になり、

X_{t+1,i,F_d(a_{i-1},a_i,a_{i+1})}=1

でなければならない。同じ議論を左端では実際の二セル $a_0,a_1$ と $F_d^{\mathrm L}$ に、右端では実際の二セル $a_{T-1},a_T$ と $F_d(a_{T-1},a_T,\sqcup)$ に適用する。第二行の各位置におけるセル記号も一意であるため、第二行の唯一のセル記号は対応する局所更新関数が指定した記号に等しい。対応する等式がすべての位置で成り立つので、第二行は規則 $d$ による正しい次配置である。▨

定理 5.2. 任意の入力 $x$ について、

N\text{ が }x\text{ を受理する} \quad\Longleftrightarrow\quad \Phi_{N,x}\text{ は充足可能である}.

証明. $N$ が $x$ を受理するとする。受理分枝を一つ選び、停止後の自己遷移によって長さ $T$ まで延長する。各時刻と位置について、その計算表に実際に現れるセル記号に対応する $X$ だけを真にする。各時刻で実際に選ばれた遷移規則に対応する $C$ だけを真にする。

各セルには一つの記号があり、各配置には一つのヘッドがあるため、一意性制約を満たす。時刻 $0$ は初期配置制約を満たし、選んだ規則は実際に適用した規則なので適用可能性制約を満たす。連続する二行は正しい一段遷移であるため、補題 5.1により局所更新制約を満たす。分枝は時刻 $T$ までに受理し、その後は受理配置にとどまるので受理節も満たす。したがって $\Phi_{N,x}$ は充足可能である。

逆に、 $\Phi_{N,x}$ を満たす割当が存在するとする。セル一意性により、各 $(t,i)$ にはセル記号が一つ定まり、ヘッド一意性により各行は状態とヘッド位置を一つもつ配置を表す。初期配置節により第 $0$ 行は $N(x)$ の初期配置である。

各 $t<T$ では遷移選択制約により規則 $d_t$ が一つ定まる。適用可能性節により $d_t$ は第 $t$ 行の状態と走査記号へ適用することができる。補題 5.1により、第 $t+1$ 行は $d_t$ による第 $t$ 行の正しい次配置である。 $t$ に関する帰納法によって、全行が初期配置から始まる一つの実在する計算分枝をなす。受理節により最終行の状態は $q_{\mathrm{acc}}$ であるため、この分枝は $x$ を受理する。▨

6 式サイズと帰着の計算時間

補題 6.1. $N$ を固定すると、 $\Phi_{N,x}$ の変数数、節数、符号長、および $\Phi_{N,x}$ を出力する時間は、 $T(|x|)$ の多項式である。

証明. $|\mathcal A|$ と $|\mathcal R|$ は固定機械 $N$ だけに依存する定数である。セル変数は

(T+1)^2|\mathcal A|=O(T^2)

個であり、遷移選択変数は $T|\mathcal R|=O(T)$ 個である。

セル記号の一意性には各セル当たり定数個の節しか要らないため、節数は $O(T^2)$ である。ヘッドの存在には各行一つ、ヘッドの一意性には各行で $O(T^2)$ 個の二リテラル節を用いるため、全体で $O(T^3)$ 個である。遷移選択、初期配置、適用可能性、および局所更新の節数は、各時刻・位置と固定有限集合を走査して作るので $O(T^2)$ 個である。受理条件は一つの長い節であり、リテラル数は $O(T)$ である。

したがって節とリテラルの総数は $O(T^3)$ である。添字 $t,i$ を二進表記する変数名には $O(\log(T+2))$ ビットを要するため、式全体の符号長は

O\bigl(T^3\log(T+2)\bigr)

である。

帰着機械は入力長 $n$ から固定多項式 $T(n)$ を計算し、上で列挙した順に変数名と節を書き出す。各節の生成には添字に関する多項式時間しか要らず、出力長自体も $T$ の多項式である。 $T(n)$ は $n$ の多項式なので、出力時間と出力長はいずれも $n$ の多項式である。▨

7 Cook–Levin の定理

定理 7.1 (Cook–Levin の定理). 充足可能性問題 $\mathsf{SAT}$ は NP 完全である。

証明.命題 1.2により、 $\mathsf{SAT}\in\mathsf{NP}$ である。

任意の言語 $A\in\mathsf{NP}$ をとる。§E18.11 定義 1.2により、 $A$ を受理する多項式時間非決定性 Turing 機械 $N$ が存在する。 $N$ を固定し、入力 $x$ に対して

f(x)=\langle\Phi_{N,x}\rangle

と定める。補題 6.1により、 $f$ は多項式時間で計算される。定理 5.2により、

x\in A \Longleftrightarrow N\text{ が }x\text{ を受理する} \Longleftrightarrow \Phi_{N,x}\text{ は充足可能である} \Longleftrightarrow f(x)\in\mathsf{SAT}.

したがって $A\le_{\mathrm p}\mathsf{SAT}$ である。 $A\in\mathsf{NP}$ は任意であったため、 $\mathsf{SAT}$ は NP 困難である。NP への所属と合わせて、 $\mathsf{SAT}$ は NP 完全である。▨

例 7.2. CNF

(z_1\lor z_2)\land(\neg z_1\lor z_2)

を考える。割当 $(z_1,z_2)=(0,1)$ では二つの節がともに真になり、式全体が真になる。 $(1,0)$ では第二節が偽になる。

計算表の符号化でも、各節により同じように許されない局所選択が排除される。一意性節により二つのセル記号を同時に選ぶ割当が排除され、局所更新節により前の三セルと選択規則が定まったときに誤った次セルを選ぶ割当が排除される。個々の節は局所的であるが、すべての節の論理積により計算表全体の整合性が保証される。

8 演習

問題 8.1.

命題 1.2の検証器について、変数名が二進添字で符号化される場合にも証明書長が入力長以下になる理由を説明せよ。
変数 $u_1,\ldots,u_m$ （ $m\geq2$ ）について、「CNF 制約の構成」の節の冒頭の CNF を満たす割当は $u_1,\ldots,u_m$ のちょうど一つを真にする割当に限ることを示し、その節の個数を求めよ。また、新しい変数 $s_1,\ldots,s_{m-1}$ を用いた CNF $(\neg u_1\lor s_1)\land(\neg u_m\lor\neg s_{m-1})\land\bigwedge_{1<r<m}\bigl((\neg u_r\lor s_r)\land(\neg s_{r-1}\lor s_r)\land(\neg u_r\lor\neg s_{r-1})\bigr)$ について、 $u_1,\ldots,u_m$ への割当がこの CNF を満たす割当へ拡張されることと、真である $u_r$ が高々一つであることが同値であることを示し、節の個数を求めよ。
規則 $d$ が、状態 $q$ で記号 $a$ を読むと $b$ を書き、ヘッドを右へ動かして状態 $q'$ へ移る規則であるとする。 $c,e,f\in\Gamma$ について、局所更新関数の値 $F_d(c,(q,a),e)$ 、 $F_d((q,a),c,e)$ 、 $F_d(c,e,(q,a))$ 、 $F_d(c,e,f)$ を求めよ。さらに、ヘッド印を位置 $h$ （ $1\leq h\leq T-2$ ）にただ一つもつ行に $F_d$ を各内点で適用して得る行が、規則 $d$ による正しい次配置であることを確かめよ。
ヘッドの一意性を素朴な二変数節で表した場合に $O(T^3)$ 個の節を要することを計算せよ。節数が $O(T^3)$ であっても帰着が多項式時間である理由を述べよ。
早く受理した配置を停止後の自己遷移で延長する規約が、受理分枝の有無を変えないことを証明せよ。

解答 (演習の要点).

証明書は、式に現れる相異なる変数それぞれに対する一ビットである。各変数は式の符号の中で少なくとも一文字を占めるので、相異なる変数の個数は符号長 $m$ 以下である。したがって証明書長も $m$ 以下であり、入力長の多項式である。二進添字を用いる符号では一つの変数が複数文字を占めるため、変数の個数はさらに小さくなる。
第一の節 $u_1\lor\cdots\lor u_m$ は少なくとも一つが真であることと同値であり、各節 $\neg u_r\lor\neg u_s$ は $u_r,u_s$ がともに真ではないことと同値である。後者がすべての $r<s$ で成り立つことは真である変数が高々一つであることと同値であるから、CNF を満たす割当はちょうど一つを真にする割当に限る。節の個数は $1+\binom m2=1+m(m-1)/2$ である。

次に第二の CNF を考える。真である $u_r$ が高々一つであるとし、 $s_r$ を「ある $j\leq r$ で $u_j$ が真」のとき $1$ 、そうでないとき $0$ と定める。 $\neg u_r\lor s_r$ は $u_r$ が真ならば $s_r=1$ であることから成り立ち、 $\neg s_{r-1}\lor s_r$ は $s$ が $r$ について単調であることから成り立つ。 $\neg u_r\lor\neg s_{r-1}$ （ $1<r\leq m$ で $r=m$ の節も含む）は、 $u_r$ が真ならば $j<r$ で $u_j$ は偽であり $s_{r-1}=0$ であることから成り立つ。逆に、拡張した割当が CNF を満たし、 $i<j$ について $u_i,u_j$ がともに真であると仮定する。 $\neg u_i\lor s_i$ により $s_i=1$ であり、 $\neg s_{r-1}\lor s_r$ を $r=i+1,\ldots,j-1$ に順に用いると $s_{j-1}=1$ である。すると $j<m$ ならば節 $\neg u_j\lor\neg s_{j-1}$ 、 $j=m$ ならば節 $\neg u_m\lor\neg s_{m-1}$ が偽になり矛盾する。よって真である $u_r$ は高々一つである。節の個数は $2+3(m-2)=3m-4$ である。第一の CNF の $\binom m2$ 個の二変数節をこの CNF と節 $u_1\lor\cdots\lor u_m$ で置き換えると、ちょうど一つの条件を $3m-3$ 個の節で表すことができ、(4)のヘッドの一意性は各行 $O(T)$ 個、全体で $O(T^2)$ 個の節で表される。
「局所更新」の節で定めた規則による。 $F_d(c,(q,a),e)=b$ である。ヘッドが中央にあり、右へ動くので中央の印を消して書込み記号 $b$ を残す。 $F_d((q,a),c,e)=(q',c)$ である。ヘッドが左隣から右へ移るので、中央セルの内容 $c$ に新状態の印を付ける。 $F_d(c,e,(q,a))=e$ である。ヘッドは右隣にあり、右へ動くので中央セルへは来ない。 $F_d(c,e,f)=e$ である。ヘッドが三セルの外にあるので中央セルは変化しない。

位置 $h$ にだけヘッド印 $(q,a)$ をもち、他の位置 $j$ にテープ記号 $a_j$ をもつ行を考える。 $1\leq h\leq T-2$ であるから、位置 $h-1,h,h+1$ はいずれも内点の範囲 $1\leq i<T$ か左端に入る。各内点 $i$ について、窓 $(a_{i-1},a_i,a_{i+1})$ の型は、 $i=h$ では第一の型、 $i=h+1$ では第二の型、 $i=h-1$ では第三の型、それ以外では第四の型である。したがって次の行は、位置 $h$ が $b$ 、位置 $h+1$ が $(q',a_{h+1})$ 、他の内点は元のままである。左端 $i=0$ については $F_d^{\mathrm L}$ を用いるが、 $h\geq1$ であるから $h=1$ の場合に位置 $0$ は右隣にヘッドをもつ型となり変化せず、 $h\geq2$ でも変化しない。右端 $i=T$ の窓 $(a_{T-1},a_T,\sqcup)$ にはヘッド印が現れないので、位置 $T$ も変化しない。この行は、位置 $h$ に $b$ を書き、ヘッドを $h+1$ へ動かし、状態を $q'$ にした配置であり、規則 $d$ による正しい次配置である。
各行のヘッド印の候補は、位置 $0\le i\le T$ と $(q,a)\in Q\times\Gamma$ の組であり、 $|Q||\Gamma|$ が定数なので $O(T)$ 個である。そのうち二つを選ぶ組は $O(T^2)$ 個であり、行は $T+1$ 個あるから、全体で $O(T^3)$ 個の二変数節を要する。 $T(n)$ は $n$ の多項式であるから $O(T^3)$ も $n$ の多項式であり、各節の書き出しに要する時間も添字に関する多項式である。したがって帰着関数は多項式時間で計算される。
停止後の自己遷移は記号、ヘッド位置、状態のいずれも変えない。したがって、時刻 $t_0\le T$ で受理状態に到達した分枝は時刻 $T$ まで受理状態にとどまり、延長後の分枝は時刻 $T$ で受理状態にある。逆に、延長後の分枝が時刻 $T$ で受理状態にあるとする。自己遷移は状態を変えないので、受理状態に初めて入る時刻 $t_0$ が存在し、時刻 $t_0$ までの配置列は自己遷移を含まない。よって、それは元の機械の受理分枝である。ゆえに、延長の前後で受理分枝の有無は変わらない。

▨

§E18.12NP 完全性と Cook–Levin の定理

1 Boolean 論理式と SAT

2 NP 困難性と NP 完全性

3 有界計算表

4 CNF 制約の構成

4.1 セルとヘッドの一意性

4.2 初期配置

4.3 遷移規則の一意性と適用可能性

4.4 局所更新

4.5 受理条件

5 計算表と充足割当の同値性

6 式サイズと帰着の計算時間

7 Cook–Levin の定理

8 演習

参考文献

前提記事