6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ In your example, "given a particular solution" means "given a max cut of size at least k" -- it does not mean "given the string YES" or anything like that. Once you are given the solution (more commonly called certificate or witness), you only need to be able to check that the witness is indeed a witness, e.g. in your case check that what you're given is indeed a max cut of size ≥ k. You don't have to find a max cut. $\endgroup$ – ShreevatsaR May 20 '16 at 18:37
  • $\begingroup$ Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael May 20 '16 at 19:14
  • 2
    $\begingroup$ You need to read more carefully: we don't check the solution but a certificate for the answer. That can but does not have to be a solution of the associated computation/optimization problem (if there is indeed one) but it does not have to be. $\endgroup$ – Raphael May 20 '16 at 19:15
  • $\begingroup$ Related: Why isn't this undecidable problem in NP? $\endgroup$ – BlueRaja - Danny Pflughoeft May 20 '16 at 21:55
  • $\begingroup$ Thanks. I should note that I have zero background in computer science, but work in a field that overlaps slightly, so I'm sorry if my question was trivial. $\endgroup$ – SamTheTomato May 21 '16 at 6:16
14
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Thanks! So to summarize (please correct if wrong), although NP Problems have yes/no answers by definition, the polynomial verification requires an actual solution (witness), and simply verifies if the solution is valid or not. $\endgroup$ – SamTheTomato May 20 '16 at 20:07
  • $\begingroup$ Right. That's a good summary. $\endgroup$ – Yuval Filmus May 20 '16 at 21:36
6
$\begingroup$

Saying that the problems can be checked in polynomial time is a simplification that people use to give intuition as to what NP is without nondeterministic Turing Machines, but it's incomplete.

The actual definition is that there is an algorithm which, given a certifier string polynomial in the length of your input can we check if it is a valid certification that a given string is in the language in polynomial time?

For example, in your example of cut size, a certifier is a possible cut. We can't find a cut of size k, but if you give us a some set, we can check if it's a cut and if it has size k, in polynomial time.

This structure is common to the "Does there the x such that y" problems: we use as a certifier a potential x, and then check if y holds. In general, since NP is defined as polynomial time, we can use the trace of a nondeterministic Turing Machine, accepting our language, when run on our input, as certifier to polynomially verify that a given input is accepted.

$\endgroup$
  • $\begingroup$ You can alternatively say the verifier runs in polynomial time in the size of the original input (without certificate). Then we don't need to talk about the size of the certificate since the verifier can only read a polynomially many bits of it. $\endgroup$ – Kaveh Jun 1 '16 at 14:20

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.