P と NP | 計算理論

1 非決定性多項式時間

非決定性機械では、各配置から有限個の次配置を許す。機械の遷移表は有限であるため、全配置に共通する分枝数の定数上界が存在する。

定義 1.1.§E18.10 定義 1.1の読取り専用入力テープと固定有限本の作業テープをもつ機械で、遷移先を有限集合として与えるものを非決定性 Turing 機械 (nondeterministic Turing machine) とする。入力 $x$ 上の計算木は、初期配置を根とし、一段で到達することができる配置を子とする有限分枝木である。少なくとも一つの分枝が受理状態で終わるとき、 $N$ は $x$ を受理する。

ある多項式 $p\in\mathbb N[n]$ が存在して、長さ $n$ の各入力に対するすべての計算分枝が高々 $p(n)$ 段で受理または拒否するとき、 $N$ を多項式時間非決定性決定器 (polynomial-time nondeterministic decider) という。

受理分枝だけが多項式時間であればよいのではない。拒否入力を含むすべての入力において、すべての分枝が共通の多項式上界内で停止することが定義に含まれる。

定義 1.2. 有限アルファベット $\Sigma$ 上の言語 $L\subseteq\Sigma^*$ が NP (NP) に属するとは、 $L$ を受理する多項式時間非決定性決定器が存在することをいう。

Cook–Levin の符号化では、入力と作業領域を同じテープ上に置く標準単テープ機械が便利である。次の命題により、機械を標準単テープ機械へ変更しても NP は変わらない。

命題 1.3. 読取り専用入力テープと固定有限本の作業テープをもつ多項式時間非決定性決定器と、入力を初期テープ内容としてもつ一方向無限の単テープ多項式時間非決定性決定器は、同じ言語のクラスを受理する。

証明. 最初に、読取り専用入力テープと $k$ 本の作業テープをもつ非決定性機械 $N$ を、標準単テープ非決定性機械 $S$ で模倣する。 $S$ は入力 $x$ を有限回走査して、

\#u_{\mathrm{in}}\#u_1\#\cdots\#u_k\#

という複数トラックの符号へ書き換える。 $u_{\mathrm{in}}$ は変更しない入力トラックであり、各トラックのヘッド位置を印付き記号で表す。

元の一段を模倣するとき、 $S$ は符号全体を走査して各ヘッド下の記号を有限制御へ記録する。元の配置で選ぶことができる各遷移規則に対して、 $S$ にも対応する非決定的選択を一つ置く。選択後にもう一度符号を走査し、作業記号とヘッド印を更新する。初期符号は $O(|x|^2+1)$ 時間で構成することができる。元の計算が $t$ 段以内であれば、符号長は $O(|x|+t+1)$ であり、一段の模倣には $O(|x|+t+1)$ 時間しか要らない。したがって、各分枝の全模倣時間は

O\bigl(|x|^2+t(|x|+t+1)+1\bigr)

である。 $t$ が入力長の多項式なら、この上界も多項式である。遷移選択を一対一に対応させたため、受理分枝の存在が保存され、全分枝の時間にも同じ上界が成り立つ。

逆に、標準単テープ非決定性機械 $S$ を資源モデルで模倣するには、読取り専用入力を一度だけ第一作業テープへ複写し、その後は $S$ の各非決定的遷移を同じ一段で実行する。複写に $O(|x|+1)$ 時間を要するだけなので、多項式時間性と受理分枝の存在は保存される。▨

決定性機械は、各配置からの次配置が一つである非決定性機械とみなすことができる。

命題 1.4.

\mathsf P\subseteq\mathsf{NP}

である。

証明. $L\in\mathsf P$ とし、 $D$ を $L$ の多項式時間決定器とする。 $D$ の各配置から出る遷移を唯一の非決定的選択とみなせば、計算木は一本の分枝だけからなる。 $D$ は全入力で多項式時間内に停止し、その分枝が受理することと入力が $L$ に属することは同値である。したがって $L\in\mathsf{NP}$ である。▨

逆向きの包含 $\mathsf{NP}\subseteq\mathsf P$ が成り立つかどうかは知られていない。 $\mathsf P=\mathsf{NP}$ であるかどうかは未解決の問題である。本記事でも本単元でも、この問いに対するどちらの結論も主張しない。以下で示す包含関係はすべて、この問いを解くことなく証明することができるものである。

2 多項式長の証明書

入力と証明書のアルファベットを分けて固定する。異なる有限アルファベット間の符号化には、各文字を同じ長さの二進語へ写す固定長符号を用いる。この変換は語の長さを定数倍しか増やさず、線形時間で実行することができる。

定義 2.1. $L\subseteq\Sigma^*$ とする。固定有限アルファベット $\Gamma_c$ 、多項式 $p,q\in\mathbb N[n]$ 、および決定性 Turing 機械 $V$ が存在し、次の二条件を満たすとき、 $V$ を $L$ の多項式時間検証器 (polynomial-time verifier) という。

任意の $x\in\Sigma^*$ について $x\in L \quad\Longleftrightarrow\quad \text{ある }y\in\Gamma_c^*\text{ が存在して } |y|\le p(|x|)\text{ かつ }V(x,y)\text{ が受理する}.$
$|y|\le p(|x|)$ を満たすすべての組 $(x,y)$ について、 $V(x,y)$ は高々 $q(|x|)$ 段で停止する。

語 $y$ を証明書 (certificate) という。入力対 $(x,y)$ は、二本の読取り専用テープに分けて与えるか、区切り記号を用いた固定符号 $\langle x,y\rangle$ として与える。

条件 (b)の時間上界を $q(|x|+|y|)$ と書く定義も同値である。証明書長が $p(|x|)$ 以下であるため、多項式の合成によって $q(|x|+p(|x|))$ も $|x|$ の多項式になる。

3 二つの定義の同値性

非決定性から検証器への向きでは、計算分枝で選んだ遷移番号を証明書に記録する。逆向きでは、非決定性機械が証明書を一文字ずつ生成してから検証器を実行する。

定理 3.1. 有限アルファベット上の言語 $L$ について、次の二条件は同値である。

$L\in\mathsf{NP}$ 。
$L$ は多項式時間検証器をもつ。

証明.(1)を仮定する。 $N$ を $L$ の非決定性決定器とし、長さ $n$ の入力上の全分枝が $p(n)$ 段以内に停止するとする。 $N$ の遷移表は有限であるため、各配置からの遷移候補に $0,\ldots,b-1$ の番号を付けることができる。ここで $b$ は機械だけに依存する定数であり、存在しない候補番号は無効とする。

証明書アルファベットを $\Gamma_c=\{0,\ldots,b-1\}$ とする。検証器 $V$ は入力 $(x,y)$ を受け取り、 $N(x)$ の初期配置から始める。 $y$ の文字を左から読み、各文字が指定する遷移を一段ずつ実行する。無効な番号を読んだ場合、拒否状態へ到達した場合、または $p(|x|)$ 文字を超えた場合には拒否する。受理状態へ到達した場合には受理し、証明書を読み終えても非停止配置にいる場合には拒否する。

$N$ に $x$ の受理分枝が存在するなら、その分枝で選ばれた高々 $p(|x|)$ 個の番号列を証明書にすれば $V$ は受理する。逆に、 $V$ が証明書 $y$ を受理したなら、 $y$ が指定した遷移列は $N(x)$ の実在する受理分枝である。証明書長は $p(|x|)$ 以下である。一段の遷移の直接模倣を多テープ上で行えば時間は $O(p(|x|)+|x|)$ であり、一本の作業テープへ直しても§E18.10 系 4.2により多項式時間である。

$\Gamma_c$ を二進アルファベットへ統一する場合には、一文字を $\ell=\lceil\log_2\max\{2,b\}\rceil$ ビットで符号化する。証明書長は $\ell p(|x|)$ 以下となり、 $\ell$ は正の固定定数であるため多項式長のままである。したがって、(1) $\Rightarrow$ (2)が従う。

次に(2)を仮定し、検証器 $V$ と多項式 $p,q$ をとる。非決定性機械 $N$ は入力 $x$ 上で、最初に証明書テープを空にする。続いて高々 $p(|x|)$ 回、次の二種類の選択を行う。

証明書の生成を終了する。
$\Gamma_c$ の一文字を非決定的に選び、証明書テープへ書く。

$p(|x|)$ 文字を書いた場合には強制的に生成を終了し、その後で $V(x,y)$ を決定的に模倣する。 $V$ が受理した場合に限って受理する。

各 $y\in\Gamma_c^*$ で $|y|\le p(|x|)$ を満たすものについて、ちょうど $y$ を生成して終了する分枝が存在する。したがって、 $N$ に受理分枝が存在することと、長さが $p(|x|)$ 以下の証明書を $V$ が受理することは同値であり、この受理分枝の存在条件は $x\in L$ と同値である。

入力長 $n$ を二進計数し、固定した多項式 $p(n)$ を計算して反復回数を管理する処理は多項式時間で実行することができる。証明書の生成は $O(p(n))$ 段であり、検証は $q(n)$ 段以内で停止する。したがって、全分枝に共通する多項式上界が存在する。必要なら命題 1.3によって標準単テープ機械へ変換しても、多項式時間性を保つ。よって $N$ は多項式時間非決定性決定器であり、(2) $\Rightarrow$ (1)が従う。▨

例 3.2. 頂点集合を $\{1,\ldots,m\}$ とする有向グラフ $G$ を隣接行列で符号化し、全頂点を一度ずつ通って始点へ戻る有向閉路が存在するかを問う。

証明書を頂点列 $(v_1,\ldots,v_m)$ とする。各頂点番号には $\lceil\log_2(m+1)\rceil$ ビットを用いるため、証明書長は $O(m\log m)$ である。検証器は、各番号が $1,\ldots,m$ に属すること、番号が重複しないこと、全頂点が現れること、および

(v_i,v_{i+1})\quad(1\le i<m),\qquad (v_m,v_1)

がすべて辺であることを調べる。単純な二重走査でも $O(m^2\log m)$ 時間であり、隣接行列の符号長は $\Theta(m^2)$ なので入力長の多項式である。したがって、この言語は NP に属する。

4 多項式時間 many-one 帰着

§E18.6 定義 1.1では帰着関数に全計算可能性だけを要求した。計算量理論では、その変換時間も入力長の多項式で制限する。

定義 4.1. 言語 $A\subseteq\Sigma^*$ と $B\subseteq\Gamma^*$ に対し、関数

f\colon\Sigma^*\longrightarrow\Gamma^*

が決定性 Turing 機械によって多項式時間で計算され、任意の $x\in\Sigma^*$ について

x\in A\quad\Longleftrightarrow\quad f(x)\in B

を満たすとする。このとき、 $A$ は $B$ に多項式時間 many-one 帰着 (polynomial-time many-one reduction) するといい、

A\le_{\mathrm p}B

と書く。

出力を明示的に書く機械では、帰着関数の出力長は計算時間以下である。したがって、多項式時間帰着の出力長も入力長の多項式で抑えられる。

命題 4.2. $A\le_{\mathrm p}B$ かつ $B\in\mathsf P$ ならば、 $A\in\mathsf P$ である。

証明. 帰着関数を $f$ とすると、

A=\{x:f(x)\in B\}

である。したがって§E18.10 命題 5.1を適用すれば結論を得る。▨

命題 4.3. $A\le_{\mathrm p}B$ かつ $B\in\mathsf{NP}$ ならば、 $A\in\mathsf{NP}$ である。

証明. $f$ を帰着関数とし、長さ $n$ の入力上の計算時間を $r(n)$ 以下とする。出力長について

|f(x)|\le r(|x|)+c

となる機械依存の定数 $c$ が存在する。 $B$ の検証器を $V_B$ 、証明書長上界を $p(m)$ 、検証時間上界を $q(m)$ とする。

$A$ の検証器 $V_A$ は入力 $(x,y)$ に対し、最初に $z=f(x)$ を計算する。次に、 $|y|>p(|z|)$ ならば直ちに拒否し、 $|y|\le p(|z|)$ の場合に限って $V_B(z,y)$ を実行する。 $V_A$ に許す証明書長の上界を

p(r(|x|)+c)

とする。この上界は $|x|$ の多項式であり、 $|z|\le r(|x|)+c$ と $p$ の単調性から、 $B$ の受理証明書に必要な長さ $p(|z|)$ 以上である。

$x\in A$ ならば $z\in B$ である。したがって、 $|y|\le p(|z|)$ かつ $V_B(z,y)$ が受理する証明書 $y$ が存在する。この $y$ は上の全体上界も満たし、長さ検査を通るので $V_A$ が受理する。逆に $x\notin A$ ならば $z\notin B$ である。全体上界を満たす任意の $y$ について、 $|y|>p(|z|)$ なら $V_A$ は直ちに拒否し、 $|y|\le p(|z|)$ なら $B$ の検証器の健全性により $V_B(z,y)$ が拒否する。したがって $V_A$ も拒否する。

停止性と時間上界も確認する。 $f$ の計算は $r(|x|)$ 段以内で停止する。長さ検査は $p(|z|)+1$ 文字まで調べれば終わり、検査を通った場合だけ $V_B$ を実行する。この場合には検証器の定義から $V_B(z,y)$ は $q(|z|)$ 段以内に停止する。したがって、全体上界を満たす証明書上で $V_A$ は必ず停止し、その時間は

r(|x|) +O\bigl(p(r(|x|)+c)+1\bigr) +q(r(|x|)+c)

以下であり、 $|x|$ の多項式である。

$V_A$ の証明書アルファベットには $V_B$ と同じ固定有限アルファベットを用いることができる。二進アルファベットへ統一する場合には固定長符号で一文字ずつ変換すればよく、証明書長と検証時間は定数倍しか増えない。したがって $A$ は多項式時間検証器をもち、定理 3.1により $A\in\mathsf{NP}$ である。▨

命題 4.4. $A\le_{\mathrm p}B$ かつ $B\le_{\mathrm p}C$ ならば、 $A\le_{\mathrm p}C$ である。

証明. 二つの帰着関数を $f,g$ とする。合成 $g\circ f$ は

x\in A\Longleftrightarrow f(x)\in B \Longleftrightarrow g(f(x))\in C

を満たす。 $f$ の出力長は $|x|$ の多項式であり、 $g$ の時間はその入力長の多項式であるため、§E18.10 命題 5.1と同じ合成評価により $g\circ f$ は多項式時間で計算される。▨

5 補言語のクラス co-NP

$\mathsf{NP}$ の二つの定義は、いずれも受理分枝または証明書の存在という形をとる。存在の否定を、一般に存在の形へ書き直すことはできない。したがって、 $L\in\mathsf{NP}$ から補言語 $\Sigma^*\setminus L$ が $\mathsf{NP}$ に属することは従わない。補言語の側が $\mathsf{NP}$ に属する言語のクラスを、別に定める。

定義 5.1. 有限アルファベット $\Sigma$ 上の言語 $L\subseteq\Sigma^*$ に対し、

\overline L=\Sigma^*\setminus L

を $L$ の補言語 (complement language) という。 $\overline L\in\mathsf{NP}$ であるとき $L$ は coNP (coNP) に属するといい、 $\mathsf{coNP}$ をこのような言語全体のクラスとする。

$\overline{\overline L}=L$ であるから、定義より直ちに、 $L\in\mathsf{coNP}$ と $\overline L\in\mathsf{NP}$ は同値であり、 $L\in\mathsf{NP}$ と $\overline L\in\mathsf{coNP}$ も同値である。補言語をとる操作は、 $\mathsf{NP}$ と $\mathsf{coNP}$ を互いに移す。

命題 5.2. 有限アルファベット $\Sigma$ 上の言語 $L$ について、次の二条件は同値である。

$L\in\mathsf{coNP}$ 。
固定有限アルファベット $\Gamma_c$ 、多項式 $p,q\in\mathbb N[n]$ 、および決定性 Turing 機械 $W$ が存在して、任意の $x\in\Sigma^*$ について $x\notin L \quad\Longleftrightarrow\quad \text{ある }y\in\Gamma_c^*\text{ が存在して } |y|\le p(|x|)\text{ かつ }W(x,y)\text{ が受理する}$ であり、 $|y|\le p(|x|)$ を満たすすべての組 $(x,y)$ について $W(x,y)$ は高々 $q(|x|)$ 段で停止する。

証明.(2)は、定義 2.1の二条件において $L$ を $\overline L$ に置き換えたものにほかならない。実際、 $x\notin L$ と $x\in\overline L$ は同値である。したがって、(2)が成り立つことと、 $W$ が $\overline L$ の多項式時間検証器であることは同値である。定理 3.1により、これは $\overline L\in\mathsf{NP}$ と同値であり、定義 5.1により $L\in\mathsf{coNP}$ と同値である。▨

(2)の $y$ は、 $x$ が $L$ に属さないことの証拠である。この意味で、 $\mathsf{coNP}$ は、言語 $L$ に属さないどの入力 $x$ についても、 $x$ が $L$ に属さないことを示す多項式長の証拠が存在するような言語 $L$ のクラスである。

命題 5.3. $L\in\mathsf P$ ならば $\overline L\in\mathsf P$ である。

証明. $D$ を $L$ の決定器で最悪時間が $O(n^k)$ であるものとする。 $D$ の受理状態と拒否状態を入れ替えた機械を $D'$ とする。 $D'$ の遷移関数は $D$ と同一であるから、各入力 $x$ 上の配置列も停止までの遷移数も $D$ と同一である。とくに $D'$ は全入力で停止し、最悪時間は $O(n^k)$ のままである。 $D'$ が $x$ を受理することと $D$ が $x$ を拒否すること、すなわち $x\notin L$ は同値である。よって $D'$ は $\overline L$ の決定器であり、§E18.10 定義 1.4により $\overline L\in\mathsf P$ である。▨

命題 5.4.

\mathsf P\subseteq\mathsf{NP}\cap\mathsf{coNP}

である。

証明. $L\in\mathsf P$ とする。命題 1.4により $L\in\mathsf{NP}$ である。また命題 5.3により $\overline L\in\mathsf P$ であり、再び命題 1.4により $\overline L\in\mathsf{NP}$ である。定義 5.1により $L\in\mathsf{coNP}$ である。▨

命題 5.5. $A\le_{\mathrm p}B$ かつ $B\in\mathsf{coNP}$ ならば、 $A\in\mathsf{coNP}$ である。

証明. $A\subseteq\Sigma^*$ 、 $B\subseteq\Gamma^*$ とし、 $f$ を帰着関数とする。任意の $x\in\Sigma^*$ について $x\in A$ と $f(x)\in B$ が同値であるから、両辺を否定して、 $x\in\overline A$ と $f(x)\in\overline B$ も同値である。 $f$ は同じ多項式時間計算可能関数であるから、 $\overline A\le_{\mathrm p}\overline B$ である。 $B\in\mathsf{coNP}$ から $\overline B\in\mathsf{NP}$ であり、命題 4.3により $\overline A\in\mathsf{NP}$ である。よって定義 5.1により $A\in\mathsf{coNP}$ である。▨

命題 5.6. $\mathsf P=\mathsf{NP}$ ならば $\mathsf{NP}=\mathsf{coNP}$ である。対偶により、 $\mathsf{NP}\ne\mathsf{coNP}$ ならば $\mathsf P\ne\mathsf{NP}$ である。

証明. $\mathsf P=\mathsf{NP}$ と仮定する。 $L\in\mathsf{NP}$ をとると $L\in\mathsf P$ であり、命題 5.3により $\overline L\in\mathsf P=\mathsf{NP}$ である。よって $L\in\mathsf{coNP}$ であり、 $\mathsf{NP}\subseteq\mathsf{coNP}$ を得る。逆に $L\in\mathsf{coNP}$ をとると $\overline L\in\mathsf{NP}=\mathsf P$ であり、同じ命題により $L=\overline{\overline L}\in\mathsf P=\mathsf{NP}$ である。よって $\mathsf{coNP}\subseteq\mathsf{NP}$ であり、二つのクラスは等しい。▨

例 5.7.例 3.2で扱った言語を $\mathsf{HAM}\subseteq\Sigma^*$ とする。ここで $\Sigma$ は隣接行列の符号に用いる有限アルファベットである。補言語

\overline{\mathsf{HAM}}=\Sigma^*\setminus\mathsf{HAM}

は、Hamilton 閉路をもたない有向グラフの符号と、有向グラフの符号ではない語からなる。同例により $\mathsf{HAM}\in\mathsf{NP}$ であるから、定義 5.1により $\overline{\mathsf{HAM}}\in\mathsf{coNP}$ である。

$\overline{\mathsf{HAM}}$ が $\mathsf{NP}$ に属するかどうかは、本記事の結果からは従わない。全頂点を通る閉路が一つも存在しないことを示す多項式長の証明書として何を与えればよいかは、この時点で与えられていない。 $\mathsf{NP}=\mathsf{coNP}$ であるかどうかも未解決である。

6 演習

問題 6.1.

非決定性 Turing 機械 $N$ と多項式 $p$ について、停止しない分枝があってもよいが、 $N$ が受理する各入力 $x$ には $p(|x|)$ 段以内に受理状態で終わる分枝が存在するとする。 $N$ が受理する言語が $\mathsf{NP}$ に属することを示せ。
二進分枝だけをもつ非決定性機械が $n^3$ 段以内に停止するとき、分枝選択証明書の長さを求め、検証器の構成を記述せよ。
$V$ を $L$ の多項式時間検証器とし、証明書アルファベットを $\Gamma_c$ 、長さ上界を $p$ とする。新しい記号 $\square\notin\Gamma_c$ を加えたアルファベット上の検証器 $V'$ で、任意の $x$ について「 $x\in L$ であることと、長さがちょうど $p(|x|)$ の証明書 $y'$ で $V'(x,y')$ が受理するものが存在することが同値」となるものを構成せよ。
$A\le_{\mathrm p}B$ と $B\in\mathsf{NP}$ から $A\in\mathsf{NP}$ を導くとき、証明書長上界が多項式の合成になることを式で示せ。
有限証明書アルファベットを二進アルファベットへ変更しても NP の定義が変わらないことを、固定長符号の長さと変換時間を用いて証明せよ。
$\mathsf{NP}\cap\mathsf{coNP}$ が補言語、和集合、および共通部分をとる操作について閉じていることを示せ。
$\mathsf P$ が和集合と共通部分について閉じていることを示せ。また、認識可能な言語の全体は補言語をとる操作について閉じていないことを、具体的な言語を挙げて示せ。

解答 (演習の要点).

$N$ の各配置からの遷移候補に $0,\ldots,b-1$ の番号を付け、証明書アルファベットを $\Gamma_c=\{0,\ldots,b-1\}$ とする。検証器 $V$ は入力 $(x,y)$ について、 $N(x)$ の初期配置から $y$ の文字が指定する遷移を一段ずつ実行し、受理状態へ到達したら受理し、無効な番号を読んだ場合、拒否状態へ到達した場合、および $y$ を読み終えても受理状態に到達していない場合には拒否する。 $V$ が実行する遷移は $|y|$ 段以下であるから、 $|y|\leq p(|x|)$ ならば $V(x,y)$ は $O(p(|x|)+|x|)$ 段で停止し、定義 2.1 条件 (b)を満たす。 $N$ の停止しない分枝は、 $V$ が有限の証明書の分だけ模倣した時点で打ち切られる。

$x$ を $N$ が受理するならば、仮定により $p(|x|)$ 段以内の受理分枝があり、その遷移番号の列 $y$ は $|y|\leq p(|x|)$ を満たして $V(x,y)$ に受理される。逆に $V(x,y)$ が受理すれば、 $y$ は $N(x)$ の実在する受理分枝を指定するので、 $N$ は $x$ を受理する。よって $V$ は $N$ の受理言語の多項式時間検証器であり、定理 3.1によりこの言語は $\mathsf{NP}$ に属する。
各段の候補が二つであるから、証明書は $\{0,1\}$ 上の長さ $n^3$ 以下の語である。検証器は初期配置から始め、証明書のビットが指定する遷移を一段ずつ実行する。受理状態に到達したら受理し、拒否状態に到達した場合、無効な番号を読んだ場合、 $n^3$ 段を超えた場合、および証明書を読み終えても停止していない場合には拒否する。多テープ上の直接模倣で $O(n^3)$ 時間である。
$V'(x,y')$ を次のように定める。 $|x|$ から $p(|x|)$ を計算し、 $|y'|\neq p(|x|)$ ならば拒否する。 $y'$ が $y\square^{m}$ （ $y\in\Gamma_c^*$ 、 $m\geq0$ ）の形でなければ拒否する。この形ならば末尾の $\square$ を除いた $y$ について $V(x,y)$ を模倣し、その結論を出力する。 $p(|x|)$ の計算、長さと形の検査、および末尾の除去は多項式時間で行うことができ、 $|y|\leq p(|x|)$ であるから $V(x,y)$ の模倣は $q(|x|)$ 段以内で終わる。長さが $p(|x|)$ 以下のすべての $y'$ についても同じ手順は多項式時間で停止するので、 $V'$ は長さ上界 $p$ の多項式時間検証器である。

$x\in L$ ならば、 $|y|\leq p(|x|)$ で $V(x,y)$ が受理する $y$ があり、 $y'=y\square^{p(|x|)-|y|}$ は長さがちょうど $p(|x|)$ で $V'(x,y')$ に受理される。逆に、長さ $p(|x|)$ の $y'$ を $V'$ が受理すれば、 $y'=y\square^m$ で $V(x,y)$ が受理し、 $|y|\leq p(|x|)$ であるから $x\in L$ である。この $V'$ に対しては、定理 3.1の証明の非決定性機械は、生成を終了する選択をせずにちょうど $p(|x|)$ 文字を生成すればよい。
出力長について $|f(x)|\le r(|x|)+c$ である。 $B$ の証明書長上界を $p$ とすると、 $p$ の係数が非負であるため単調であり、 $p(|f(x)|)\le p(r(|x|)+c)$ が成り立つ。右辺は多項式の合成であるから $|x|$ の多項式である。
$|\Gamma_c|=b$ の各文字を長さ $\ell=\lceil\log_2\max\{2,b\}\rceil$ のビット列へ写す固定長符号をとる。証明書長は $\ell p(|x|)$ 以下となり、 $\ell$ が定数であるから多項式のままである。検証器は二進証明書を左から $\ell$ ビットずつ読んで元の文字へ復号すればよく、復号は一文字あたり定数時間である。したがって検証時間も多項式のままであり、定義により定められるクラスは変わらない。
補言語について、 $L\in\mathsf{NP}\cap\mathsf{coNP}$ ならば、定義 5.1により $L\in\mathsf{NP}$ から $\overline L\in\mathsf{coNP}$ 、 $L\in\mathsf{coNP}$ から $\overline L\in\mathsf{NP}$ であり、 $\overline L\in\mathsf{NP}\cap\mathsf{coNP}$ である。

次に $\mathsf{NP}$ が和集合と共通部分について閉じていることを示す。 $L_1,L_2\in\mathsf{NP}$ の多項式時間検証器を $V_1,V_2$ 、証明書アルファベットを $\Gamma_1,\Gamma_2$ 、長さ上界を $p_1,p_2$ 、時間上界を $q_1,q_2$ とする。検証器の条件は $|y|\le p_i(|x|)$ を満たす証明書 $y$ だけを拘束するので、新しい検証器は模倣の前に証明書の長さを検査する。和集合の検証器 $V_\cup$ は、証明書が $iy$ （ $i\in\{1,2\}$ ）の形で $y\in\Gamma_i^*$ かつ $|y|\le p_i(|x|)$ であるときに限り $V_i(x,y)$ を模倣してその結論を返し、それ以外の証明書は拒否する。共通部分の検証器 $V_\cap$ は、証明書が新しい区切り記号 $\#$ を用いた $y_1\#y_2$ の形で、 $j=1,2$ について $y_j\in\Gamma_j^*$ かつ $|y_j|\le p_j(|x|)$ であるときに限り $V_1(x,y_1)$ と $V_2(x,y_2)$ を順に模倣して、ともに受理するとき受理し、それ以外の証明書は拒否する。いずれも証明書アルファベットは $\Gamma_1\cup\Gamma_2$ に固定個の記号を加えたものであり、長さ上界を $p_1+p_2+1$ とする。長さの検査は、 $p_j(|x|)$ を一進で書き出し、証明書を高々 $p_j(|x|)+1$ 記号まで読んで比べればよいので、 $|x|$ の多項式時間で終わる。検査を通った証明書では、模倣する $V_j$ への入力が $V_j$ の時間上界の条件の範囲にあるので、模倣は $q_j(|x|)$ 段の多項式倍で終わる。よって時間上界は $|x|$ の多項式である。

正しさを確かめる。 $x\in L_1\cup L_2$ ならば、ある $i$ と $|y|\le p_i(|x|)$ を満たす $y\in\Gamma_i^*$ について $V_i(x,y)$ が受理し、 $|iy|\le p_1(|x|)+p_2(|x|)+1$ を満たす $iy$ を $V_\cup$ は受理する。逆に $V_\cup$ が $iy$ を受理すれば、 $|y|\le p_i(|x|)$ かつ $V_i(x,y)$ が受理するので $x\in L_i$ である。 $x\in L_1\cap L_2$ ならば、 $|y_j|\le p_j(|x|)$ を満たす $y_j$ で $V_j(x,y_j)$ が受理するものがあり、 $|y_1\#y_2|\le p_1(|x|)+p_2(|x|)+1$ である。逆に $V_\cap$ が $y_1\#y_2$ を受理すれば、検査と模倣から $x\in L_1$ かつ $x\in L_2$ である。よって $L_1\cup L_2,L_1\cap L_2\in\mathsf{NP}$ である。

$L_1,L_2\in\mathsf{NP}\cap\mathsf{coNP}$ とする。前段により $L_1\cup L_2\in\mathsf{NP}$ である。また $\overline{L_1},\overline{L_2}\in\mathsf{NP}$ であるから $\overline{L_1\cup L_2}=\overline{L_1}\cap\overline{L_2}\in\mathsf{NP}$ 、すなわち $L_1\cup L_2\in\mathsf{coNP}$ である。よって $L_1\cup L_2\in\mathsf{NP}\cap\mathsf{coNP}$ である。共通部分は $L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$ であり、補言語と和集合について閉じていることから従う。
$L_1,L_2\in\mathsf P$ の決定器を $D_1,D_2$ とし、最悪時間をそれぞれ $O(n^a)$ 、 $O(n^b)$ とする。入力テープは読取り専用であるから、決定器 $D$ は入力ヘッドを左端へ戻しながら $D_1$ を模倣して結論を有限制御に記憶し、作業テープを空白に戻してから入力ヘッドを左端へ戻して $D_2$ を模倣する。和集合では一方が受理すれば受理し、共通部分では両方が受理すれば受理する。作業テープの清掃と入力ヘッドの巻き戻しは、それぞれの模倣の時間と入力長の定数倍で終わるので、 $D$ の時間は $O(n^a+n^b+n+1)$ であり多項式である。よって $L_1\cup L_2,L_1\cap L_2\in\mathsf P$ である。

§E18.5 命題 3.2により $\mathsf{HALT}_{TM}$ は認識可能であるが、§E18.5 系 4.2によりその補言語は認識可能でない。よって認識可能な言語の全体は補言語について閉じていない。とくに、 $\mathsf{HALT}_{TM}$ の認識器の受理状態と拒否状態を入れ替えた機械は補言語の認識器にならない。命題 5.3の構成が $\mathsf P$ で成り立つのは、決定器が全入力で停止するからである。

▨

§E18.11P と NP