[Solved]: Reconciling NP and the decision problem

Problem Detail: 

So I've seen that most NP-Complete problems seem to take the form of decision problems - problems which require only a yes/no answer. However, how can this be reconciled with the requirement that the solution of an NP problem can be checked in polynomial time?

For example, for a graph G, the max cut decision problem: "Does a cut of size at least k exist?" is NP-Complete. However, given a particular solution, "yes", the problem of checking that the solution is "yes" would require you to find a max cut of size k, so how can this be in NP?

Asked By : SamTheTomato

Answered By : Yuval Filmus

By definition, all NP-complete problems are decision problems. In fact, the category of NP-completeness only applies to decision problems. Any other kind of problem cannot be NP-complete any more than an apple.

A decision problem A is in NP if there is an integer $m$ and a decision problem B, which can be decided in polynomial time, such that:

• If $x \in A$ then there exists $y$ of size at most $m|x|^m$ (here $|x|$ is the size of $x$ in bits) such that $\langle x,y \rangle \in B$.

• If $x \notin A$ then for every $y$ of size at most $m|x|^m$ it holds that $\langle x,y \rangle \notin B$.

The string $y$ is called a witness.

This definition is a bit abstract, so let me explain it using your example, the Max Cut problem. The Max Cut problem, as a set, consists of all pairs $\langle G,k \rangle$ such that $G$ is a graph containing a cut which cuts at least $k$ edges. The desired witness $y$ is a cut which cuts at least $k$ edges. The decision problem B consists of all pairs $\langle \langle G,k \rangle, C \rangle$ in which $G$ is a graph and $C$ is a cut in $G$ which cuts at least $k$ edges. The problem Q can be decided in polynomial time – that is, given a graph $G$, a cut $C$ in $G$, and an integer $k$, it is easy to check whether $C$ cuts at least $k$ edges. The size of $C$ is also polynomial in the size of $\langle G,k \rangle$.

As jmite explains in the other answer, this definition is equivalent to the more usual one: NP consists of all decision problems which can be decided using non-deterministic polynomial time machines. Let me sketch why the two definitions are equivalent.

Suppose first that A is in NP according to the definition stated above. The non-deterministic polynomial time machine deciding A guesses the witness $y$ and then verifies it (using the polynomial time algorithm for B), accepting if the verification succeeded.

For the other direction, the sequence of non-deterministic choices functions as the witness $y$. We can verify that a specific sequence leads to acceptance by running the non-deterministic polynomial time machine using $y$ as its choices.

Best Answer from StackOverflow

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