Having problem understanding the formal definition of NP

Question

So I'm having a tad bit of a problem deciphering the formal definition of NP. In my text book (Algorithm Design, Tardos et al) it says that a problem $X$ belongs to $NP$ iff;

• there exists a "certificate" string $t$ such that $|t| \le p(|s|)$ for a polynomial function $p$ and an input string $s$.
• there exists an efficient certifier $B$ that takes $s$ and $t$ as inputs and has polynomial time complexity.

I'm having a hard time understanding this problem in a more practical sense. Say for example I had to verify a solution for a Graph Coloring problem. Then I would take the graph $G = (V, E)$ and the number of allowed colours $K$ as input (the problem instance) aswell as the proposed solution (Let's call it $S$) that consists of the coloring of the graph $G$. In this example, what would be $s$ and what would be $t$?

Answer 1

For Graph colouring problem

Input : A graph $G(V,E)$ and $k$.

Decide : Is $G$ $k$-colourable?

Certificate : A map $\phi : V \mapsto C $, where $C = \{R,B,Y,\cdots ,P\}$ is the set of colours and $|C| = k$.

For example for any $v \in V$, $\phi(v) = Y$ means $v$ has assigned color $Y$.

Example: let complete graph $K_4 (\{v_1,v_2,v_3,v_2\},E)$ is input graph and $k=4$ i.e. is it 4-colorable? A possible certificate in this case is $\{v_1(R),v_2(B),v_3(Y),v_4(P)\}$,($v_1(R)$ means vertex $v_1$ has color $R$), which is polynomial in input size.

Now you can see that the size of $|\phi| \le p(|G|)$, where $|G|$ is a input graph size. As you have given a map $\phi$, now you can verify in polynomial time whether colouring is valid or not.

Answer 2

Following the notation of the definition that you provide

• $s$ is the graph input $G=(V,E)$ and the number $K$ of the allowed colors encoded represented in some form of appropriate encoding
• $t$ is the proposed solution to the original problem for the input $s$. A coloring for that graph.

Therefore a verifier is an efficient algorithm that will take as inputs $s$ and $t$ and will decide in reasonable amount of time if $s\in X$, that is, if the suggested coloring is permitted by the problem statement.