P と NP | 計算理論 | 天游ヶ丘数理学院

1 非決定性多項式時間

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

定義 1.1.§E15.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|)$ であり、一本の作業テープへ直しても§E15.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 (Hamilton 閉路の検証). 頂点集合を $\{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 帰着

§E15.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\}

である。したがって§E15.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$ の時間はその入力長の多項式であるため、§E15.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}$ は所属の否定に多項式長の証拠を要求するクラスである。

命題 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$ の決定器であり、§E15.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 (Hamilton 閉路をもたないグラフ).例 3.2 (Hamilton 閉路の検証)で扱った言語を $\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 つまずいたら

NP の N は nondeterministic を表す。指数時間や「多項式時間ではない」という意味ではない。
NP は決定問題のクラスである。最適化問題を扱う場合には、閾値以下の解が存在するかという決定問題との関係を別に定める必要がある。
非決定性機械の定義では、受理分枝だけでなく全分枝が共通の多項式時間上界内に停止する。
証明書長の多項式は入力長 $|x|$ の関数である。証明書自身が表す数値の大きさを変数にしない。
$A\le_{\mathrm p}B$ は、 $B$ の解法から $A$ の解法を得る向きである。 $A$ が容易であることから $B$ が容易であるとは結論することができない。
$\mathsf{coNP}$ は $\mathsf{NP}$ の補集合ではない。 $\mathsf{NP}$ に属さない言語のクラスではなく、補言語が $\mathsf{NP}$ に属する言語のクラスである。両者の共通部分は $\mathsf P$ を含むので、空ではない。
$\mathsf P=\mathsf{NP}$ も $\mathsf{NP}=\mathsf{coNP}$ も未解決である。本記事が証明したのは、前者から後者が従うという一方向の含意だけである。

7 演習

問題 7.1.

非決定性機械の全分枝停止という条件を外すと、検証器への変換のどの箇所で共通の証明書長上界を失うかを説明せよ。
二進分枝だけをもつ非決定性機械が $n^3$ 段以内に停止するとき、分枝選択証明書の長さを求め、検証器の構成を記述せよ。
検証器から非決定性機械を構成する証明で、証明書の終了位置を非決定的に選ぶ必要がある理由を説明せよ。
$A\le_{\mathrm p}B$ と $B\in\mathsf{NP}$ から $A\in\mathsf{NP}$ を導くとき、証明書長上界が多項式の合成になることを式で示せ。
有限証明書アルファベットを二進アルファベットへ変更しても NP の定義が変わらないことを、固定長符号の長さと変換時間を用いて証明せよ。
$L\in\mathsf{NP}\cap\mathsf{coNP}$ である言語について、 $x\in L$ の場合と $x\notin L$ の場合のそれぞれに多項式長の証拠が存在することを、定義から説明せよ。
命題 5.3の証明で、決定器が全入力で停止するという条件を用いる箇所を指摘せよ。同じ構成を認識器へ適用することができない理由も述べよ。

解答 (演習の要点).

証明書は受理分枝で選ばれた遷移番号の列であり、その長さは分枝の段数である。全分枝に共通の段数上界 $p(n)$ を外すと、定義 2.1 条件 (a)が要求する長さ上界 $p(|x|)$ を選ぶことができない。さらに、番号列が指定する分枝が停止しない場合には、検証器が $q(|x|)$ 段以内に停止するという定義 2.1 条件 (b)も失われる。
各段の候補が二つであるから、証明書は $\{0,1\}$ 上の長さ $n^3$ 以下の語である。検証器は初期配置から始め、証明書のビットが指定する遷移を一段ずつ実行する。受理状態に到達したら受理し、拒否状態に到達した場合、無効な番号を読んだ場合、 $n^3$ 段を超えた場合、および証明書を読み終えても停止していない場合には拒否する。多テープ上の直接模倣で $O(n^3)$ 時間である。
受理する証明書の長さは $p(|x|)$ 以下であるが、ちょうど $p(|x|)$ であるとは限らない。長さ $p(|x|)$ の語だけを生成する機械にすると、より短い証明書しか受理されない入力を受理する分枝が存在しなくなる。各段で生成を終了する選択を許すことにより、長さ $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}$ であるから、定理 3.1により $L$ の多項式時間検証器が存在し、 $x\in L$ のときに受理される多項式長の証明書が存在する。 $L\in\mathsf{coNP}$ であるから、命題 5.2により、 $x\notin L$ のときに受理される多項式長の反証書が存在する。したがって、どちらの答えについても多項式長の証拠を提示することができる。
停止性は二箇所で用いる。第一に、 $D'$ が全入力で停止することを結論する箇所である。第二に、 $D'$ が受理しないことと $D$ が拒否することを同値とする箇所である。認識器では、 $x\notin L$ のときに停止しない計算があり得るため、受理状態と拒否状態を入れ替えても、その入力上で $D'$ は受理しない。したがって、この構成から補言語の認識器を得ることはできない。

▨

§E15.11P と NP