Understanding definition of NP

Question

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.

Answer 1

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.

Answer 2

No, $M$ is not universal. The notation $\langle x,t\rangle$ just denotes the pair whose two elements are $x$ and $t$ (this is often written $(x,t)$).

We could use a machine to determine directly if $x\in L$ but doing so is computationally expensive. In particular, assuming that P$\,\neq\,$NP, it can't be done in polynomial time. Instead, we ask that more information be supplied with the problem instance: this is $t$. For example, it's hard to determine whether a Boolean formula is satisfiable but, if I give you something that I claim is a satisfying truth assignment, it's easy to test that I was telling the truth.

The alternative definition of NP is that it's the class of languages $L$ such that there is a nondeterministic Turing machine $N$ and a polynomial $T$ such that $N$ always terminates in at most $T(|x|)$ steps and $N$ accepts $x$ if, and only if, $x\in L$.

$t$ is a certificate in the sense of a certificate of authenticity. It's a "document" that proves that $x$ really is a member of the language.

Answer 3

We are not "saying that $M$ here is a universal" Turing machine. It is not "necessary to use the same $t$ for all $x$." What would running "input $x$ on $M$" mean when $M$ would use its other input?

The certificate $t$ certifies $x$'s membership in the NP language that corresponds to $M$ and $T$ if and only if $M$ accepts the string $\langle x,t\rangle$ after at most $T(|x|)$ steps.