06 Nondeterminism by certificates

In nondeterministic computational models, a program is allowed to make ‘guesses’ in the course of computation.
We use an equivalent definition via the notion of ‘certificate’:

Definition

$\mathbf{NP}$ is the set of languages $L\subseteq \{0,1{\}}^{\star }$ for which there is a polynomial-time algorithm $A(x,y)$ (algorithm takes 2 inputs $x$ and $y$) and a polynomial $p(n)$ such that:

\large x \in L \iff \exists y \cdot (\lvert y \rvert \lt p(\lvert x \rvert)) \text{ and } A(x,y) \text{ accepts}

For a given $x \in L$, we may call such a witness $y$ the **certificate** of acceptance. The algorithm $A(x,y)$ is the verifier.

Example: Satisfiability again

SAT = $\{A\text{ Boolean formula }\mid \exists \alpha \text{ assignment }\alpha (A)=1\}$

$$\begin{array}{rl}\mathcal{A}(x,y)x& \text{ is an assignment and }y\text{ is a formula}\\ |A|& =n\\ A\in \text{ SAT }⟺& \exists \underset{\text{cerificate }|\cdot |\le n}{\underbrace{\alpha \cdot \text{ assignment to }A}}\underset{O(n)\text{ polytime verifier}}{\underbrace{\alpha (A)=1}}\\ \text{finally SAT}& \in NP\end{array}$$

Example: Clique

A Clique is a set of nodes $C$ such that $\forall u,v\in C\text{ distinct }(u-v\text{ in }G)$ (any 2 nodes in $C$ has edge between them)

K-Clique = $\{(G,K):G\text{ has a clique of size}\ge K\}$

For the graph above:

• $(G,3)$ is in the set
• $(G,2)$ is in the set
• $(G,4)$ is not in the set

Another Definition

$$(G,K)\in K-\text{Clique}⟺\exists \underset{\text{certificate}}{\underbrace{C}}\underset{\begin{array}{c}\text{polynomial}\\ \text{time}\end{array}}{\underbrace{\begin{array}{c}\text{ set of nodes in G}\\ \text{of size}\ge K\end{array}}}\underset{\begin{array}{c}\text{verifier}\\ O(n^2)\end{array}}{\underbrace{(\begin{array}{c}\forall u,v\in C\text{ distinct}\\ \text{u-v in G}\end{array})}}$$

So, we have concluded that the problem (K-Clique) $\in$ NP