4
$\begingroup$

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$?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I see, thank you very much. So B has to be of polynomial time complexity and the size of t has to be upper bounded by a polynomial function with regard to the problem input s? $\endgroup$ – Nyfiken Gul Apr 11 '17 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.