クラス NP（検証器による定義）

定義 4.1（「P≠NP 予想とは何か」§4）

言語 $L \subseteq \Sigma^{*}$ が $\mathrm{NP}$ に属するとは、多項式 $p$ と、多項式時間で動く決定性チューリング機械 $V$ （検証器と呼びます）が存在して、すべての $x \in \Sigma^{*}$ に対して

x \in L \iff \exists y \in \Sigma^{*} \ \bigl[\, |y| \le p(|x|) \ \text{かつ} \ V(x, y) = 1 \,\bigr]

が成り立つことをいいます。この $y$ を $x$ に対する証明書（certificate、witness）と呼びます。ここで「 $V$ が多項式時間」とは、 $V$ が入力 $(x, y)$ に対して $|x| + |y|$ の多項式時間で停止することを意味します。

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。