[Solved]: Understanding definition of NP

Problem Detail: 

In my lecture notes, the definition of the class NP is given as:

A language $L$ is in the class NP, if there exists a turing machine $M$ and polynomials $T$ and $p$ such that:

• For every input $x$, $M$ terminates after at most $T(|x|)$ steps
• If $x\in L$, then there is a "proof"(or certificate) $t\in\{0,1\}^{p(|x|)}$ such that $M$ accepts the string $\langle x,t \rangle$
• If $x\notin L$, then for any string $t\in\{0,1\}^{p(|x|)}$, $M$ rejects $\langle x,t \rangle$

Firstly, are we saying that $M$ here is a universal turing machine, i.e. $M(\langle x,t\rangle)=M_x(t)$, also is it necessary to use the same $t$ for all $x$.
Also $M$ is checking whether or not $x$ lies in the $L$, so shouldn't we run just input $x$ on $M$, why is the $t$ necessary. Is there any particular reason why $t$ is called a certificate? Any help with understanding this definition would be greatly appreciated.

Asked By : Andrew Brick

Answered By : Yuval Filmus

Here is an example that will hopefully make things clearer. Consider the problem 3COL, which is the set of all graphs that can be legally colored using 3 colors. It is conjectured that no polynomial time algorithm can determine whether a graph belongs to 3COL (i.e., can be legally colored using 3 colors). However, given a 3-coloring of the graph, it is easy to check whether it is legal (that is, you can do it in polynomial time). In this case:

• $L$ is 3COL.
• $x$ is a graph.
• $t$ is a 3-coloring of $x$.
• $M$ is a machine that checks that $t$ is a valid 3-coloring of $x$.

If a graph $x$ is 3-colorable, then some witness $t$, namely a valid 3-coloring, will convince $M$ that $x$ is in 3COL. Conversely, if a graph $x$ is not 3-colorable, then no 3-coloring $t$ would be valid, and so $M$ will always reject given inputs $x$ and $t$ (for any $t$). This shows that 3COL is in NP.

What happens if $t$ is the same for all $x$? In this case we can hard-code $t$ into the algorithm, and do away with the witness. Under such a definition we get P rather than NP.

What if $t$ is allowed to depend only on the size of $x$? The corresponding class is known as P/poly, and is important in computational complexity. It is more generally known as the class of (languages accepted by) polysize circuits. If you find this interesting, many advanced textbooks discuss this topic.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42069

3.2K people like this

 Download Related Notes/Documents