[Solved]: What is the difference between "Decision" and "Verification" in complexity theory?

Problem Detail: 

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

Asked By : BrotherJack

Answered By : Raphael

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).

Best Answer from StackOverflow

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