What is the difference between “Decision” and “Verification” in complexity theory?

Question

In Michael Sipser's Theory of Computation on page 270 he writes:

P = the class of languages for which membership can be decided quickly.
NP = the class of languages for which membership can be verified quickly.

What is the difference between "decided" and "verified"?

Answer 1

The task of deciding membership is: given any input $x$, decide wether $x \in L$, i.e. compute the following function:

$\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

On the other hand, the task of verifying membership is: given any input $x$ and a (proposed) proof (or witness) of membership, check quickly wether $x\in L$ by that proof¹.

For example, consider prime factorisation. Given $n \in \mathbb{N}$, compute all prime factors of $n$. On the other hand, given $(n, \{i_1, \dots, i_k\})$, verify that $\prod_{j=1}^k i_j = n$. Which is easier?

Another example: Given a weighted graph $G = (V,E)$, decide wether there is a Hamilton circle (that visits all nodes) with weight at most $k$. On the other hand, given $(G, (v_1, \dots, v_n))$, verify wether the path $v_1 \to \dots \to v_n$ visits all nodes exactly once and has weight at most $k$. Which is harder?

---

1. So you will say "no" if $x \in L$ but the proof is wrong. That is fine, though, as we consider nondeterministic machines in this context; it is only important that we can guess the correct proof and verify it (quickly).

Answer 2

If we ignore efficiency issues, there is another example that illustrates the difference by analogy. We know that the halting problem is not decidable: given a code $e$ for a Turing machine, there is no effective way to determine whether the machine stops if it is run with no input.

But if a machine does halt, it is not hard to prove to someone else: just tell them how many steps the machine runs before it stops. They can run the machine for that many steps and know if you told the truth (ignoring efficiency, of course).

So the set of halting Turing machines is not decidable, but it is verifiable. Note that no proof has to be given for machines that don't halt. Verification is asymmetric in the sense that only membership in the set has the be verifiable, membership out of the set does not.

The situation with P and NP is analogous. A language is in NP if there is a system of proofs such that each object that is in the language has a short proof (bounded by a polynomial in the size of the object) that can be verified efficiently (with a number of steps bounded by a polynomial in the size of the input).

On the other hand, a language is in P if there is a way to tell whether an arbitrary object is or is not in the language using a number of steps bounded by a polynomial in the size of the object. Now we have to worry about arbitrary inputs, not just objects in the language. But this problem is symmetric: if a language is in P then so is its complement. The question whether the complement of every NP language is also an NP language is unsolved.

(This analogy mught suggest that NP problems are to P problems like r.e. sets are to computable sets. That is somewhat true, but it can be misleading. It is a basic fact that a set that is r.e. and co-r.e. is computable, while it is not known whether every set that is NP and Co-NP is in P).