3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is $t$ seen as a heuristic for solving the problem? And how would we obtain $t$ originally. $\endgroup$ – Andrew Brick May 3 '15 at 16:38
  • $\begingroup$ also, the $3COL$ problem is in NP but does this mean that it's not computable, or it can be computable but by only using brute force methods, which aren't in polynomial time. $\endgroup$ – Andrew Brick May 3 '15 at 16:40
  • 2
    $\begingroup$ We don't obtain $t$. If a graph is 3-colorable then some good $t$ exists, otherwise there is no good $t$. That's all. $\endgroup$ – Yuval Filmus May 3 '15 at 17:32
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.