Theorem. Certificates and Verifiers [certificates-verifiers]

NP has two main, equivalent definitions:

There exists a nondeterministic polytime TM $M$ that decides $L$ .
There exists a deterministic polytime TM $V$ and a constant $c$ s.t.:
- $L = \left\{ {x \in \Sigma \ast :\exists y \in \Sigma \ast \text{s.t.}\ |y| \leq |x|^{c} \land V\ \text{accepts}\ \left( {x,y} \right)} \right\}$
- where $x$ is the “input”, $y$ is the “certificate”, $V$ is the “verifier”

i.e. for the three color graph, give us a colored graph and we can verify it

The certificate $y$ serves as the verifier $V$ ’s substitute for nondeterminism.

Example. Verifying 3colormap

$\left\{ {\left\langle G \right\rangle:G\ \text{is 3-colorable}} \right\}$
Must find a deterministic polytime TM V s.t. $\text{3COLOR} = \left\{ {x:\exists y,|y| \leq |x|^{c},V\ \text{accepts}\ \left( {x,y} \right)} \right\}$
Code for $V$ : on input $\left( {x,y} \right)$
- If $x$ not of form , where is a Graph, reject
- From $y$ , extract values $\text{color}(v) \in \left\{ {1,2,3} \right\}$ for each $v \in V$
- For every edge $\left\{ {u,v} \right\} \in E$ : if color(u) == color(v), reject
- Otherwise accept
$y$ does exist, it’s simply a valid coloring of the graph

To show correctness of $V$ , we need three things:

If $x = \left\langle G \right\rangle$ and G is 3-colorable: need $\exists y\ \text{s.t.}\ |y| \leq |x|^{c}$ and $V\ \text{accepts}\ \left( {x,y} \right)$ .
- It does exist, $y$ can be a valid 3 coloring of $G$ . Note: $|y| = O(n)$ and $|x| = \Omega(n)$
If $x \neq \left\langle G \right\rangle$ where G is 3-colorable: then no certificate $y$ should make $V$ erroneously accept.
- If $x$ not of form $\left\langle G \right\rangle$ : $v$ definitely rejects.
- If $x$ of form $\left\langle G \right\rangle$ by not 3-colorable, then $V$ must reject because it always checks that $y$ is a valid coloring.
Must check that $V$ runs in time polynomial in $|xy|$ .
- Decoding takes polytime, checking neighbors takes polytime.

Example. Proofs of equivalence of our NP definitions

Proof. $(2)\Rightarrow(1)$

Given verifier $V$ , must construct a NTM $M$ deciding $L$
Inputs to the verifier are $x$ and $y$ , with $|y| \leq |x|^{c}$
- $x$ : input string
- $y$ : certificate (like a proof that $x$ is in the language)
Code for $M$ :
- On input $x$ , nondeterministically pick $y \in \Sigma \ast$ with $|y| \leq |x|^{c}$
- Run $V$ on input $\left( {x,y} \right)$
- Accept if $V$ accepts. Reject if $V$ rejects.
i.e. Suppose $x \in L\Rightarrow\exists y\ \text{s.t.}\ V\ \text{accepts}\ \left( {x,y} \right)\Rightarrow\text{there is a leaf where}\ M\ \text{accepts}$ . If $x \notin L\Rightarrow\nexists y\ \text{s.t}.V\ \text{accepts}\ \left( {x,y} \right)\Rightarrow\nexists\ \text{leaf}$ , so $M$ does not accept $x$ .

Proof. $(1)\Rightarrow(2)$

Given an NTM $M$ , you can convert that into a verifier $V$ for $L$ .
Input to $M$ is $x$ , runtime is at most $|x|^{c}$
Idea: $V$ simulates the tree, but only on a single branch of configuration tree. $y$ specifies which branch. nondeterminism comes into play by letting us pick the correct branch.
- our nondeterminism lets us pick the correct branch: then the $c$ term is the depth of the path, which is at most polynomial
Code for $M$ :
- Simulate $M$ deterministically on input $x$ , using $y$ as the sequence of nondeterministic decisions
- Accept if $M$ accepts. Reject if $M$ rejects.