5
$\begingroup$

To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), and to demonstrate that some known NP-complete problem $B$ can be reduced to $A$ (such that we can write $B \leq_p A$), by some kind of appropriate reduction in polynomial time. We can then say that we can solve $B$ in polynomial time with an oracle for $A$.

One famous example of this would be the reduction of 3SAT to 3-coloring.

So sure, I understand that with an oracle for 3-coloring, one could solve arbitrary instances of 3SAT in polynomial time. But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT? The 3SAT $\leq_p$ 3-coloring reduction, of course, requires the use of special and restricted graphs where a 3-coloring exists iff a satisfying assignment for the 3SAT problem exists.

Doesn't this conflict with statements (at least I thought I heard in CS classes) saying that an oracle for 3SAT would prove P = NP? Might it not be the case that such an algorithm would be worthless for solving families of 3-coloring problems?

Doesn't this imply some kind of hierarchy of NP-complete problems?

(Said a bit differently: If an oracle that allows one to solve a single NP-complete problem in polynomial time must necessarily be an oracle that allows one to solve all NP-complete problems in polynomial time, shouldn't we need to show $B \leq_p A$ AND $A \leq_p B$, where $B$ is some known NP-complete problem, to prove that some problem $A$ is NP-complete?)

$\endgroup$
  • $\begingroup$ In Proof that SAT is NPC I explained in detail why a polynomial-time solution to SAT would provide a polynomial-time solution for any other problem in NP, such as 3-coloring. $\endgroup$ – Mark Dominus Dec 12 '14 at 18:01
4
$\begingroup$

But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT?

3-SAT is $NP$-complete, by the Cook-Levin theorem. This means that any problem in $NP$ (such as 3-coloring) can be solved in polynomial time given an oracle for 3-SAT.

shouldn't we need to show $Q \leq_p P$ AND $P \leq_p Q$, where $Q$ is some known NP-complete problem, to prove that some problem $P$ is NP-complete?

Yes, but you essentially get the $P \leq_p Q$ for free because $P$ is in $NP$ and $Q$ is $NP$-complete.

$\endgroup$
  • $\begingroup$ I believe you, but why do I get $P \leq_p Q$ for free? There is just some existence (and not constructive) proof right? $\endgroup$ – Mill Dec 12 '14 at 10:51
  • $\begingroup$ It's because of the Cook-Levin theorem, which is constructive (to some degree). A problem is in $NP$, if there exists a polynomially verifiable certificate (informally: we can check whether a potential answer is correct with a polynomial algorithm). Cook-Levin shows how to encode this polynomial verification algorithm as a polynomial size 3-SAT formula, and then (by quantifying over the certificate in the formula) that the original problem can be reduced to 3-SAT. $\endgroup$ – Tom van der Zanden Dec 12 '14 at 10:54
  • $\begingroup$ Ok, so here $X$ be some routine for solving an arbitrary polynomial size 3SAT formula in polynomial time. How in practice does one now solve an arbitrary 3-coloring problem in polynomial time? I can believe that perhaps such a routine must exist, but do we have to do a lot of work to find the routine? $\endgroup$ – Mill Dec 12 '14 at 11:00
  • $\begingroup$ In theory, you would apply the Cook-Levin theorem to your 3-coloring instance and transform it to an equivalent, polynomial size 3-SAT problem which you then solve in polynomial time using $X$. In practice you wouldn't use Cook-Levin because it increases the problem size dramatically (a $\Theta(n)$ size 3-coloring instance would get transformed to a $\Theta(n^3)$ size 3-SAT instance) and you would need to come up with a cleverer reduction. The Cook-Levin theorem constructs a polynomial reduction, but is not very efficient (but you usually don't care about efficiency when showing hardness). $\endgroup$ – Tom van der Zanden Dec 12 '14 at 11:05
  • $\begingroup$ Fantastic. So the Cook-Levin theorem always lets us use the verification method for a solution to "cook" a 3SAT instance, and only requires of us that some problem $A$ is in $NP$ and that $3SAT \leq_p A$ (or $B \leq_p A$ where $3SAT \leq_p B$ was shown elsewhere)? $\endgroup$ – Mill Dec 12 '14 at 11:10
2
$\begingroup$

To prove that some decision problem $P$ is NP-complete, my understanding is that it suffices to show that the problem is in NP [...] and to demonstrate that some known NP-complete problem $Q$ can be reduced to $P$ [...] by some kind of appropriate reduction in polynomial time. We can then say that we can solve $Q$ in polynomial time with an oracle for $P$.

This is correct.

So sure, I understand that with an oracle for 3-coloring, one could solve arbitrary instances of 3SAT in polynomial time. But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT?

Yes, the converse holds, because 3SAT is also NP-complete. But that is a separate fact, which requires a separate proof. Of course, that proof exists: it's typically proven by taking an arbitrary NP Turing machine and writing a Boolean formula that says "That machine accepts its input." Indeed something has to be proven NP-complete by this kind of method. We couldn't claim that all problems in NP can be reduced to complete problems just by reducing complete problems between themselves: at some point, you do have to prove that all NP problems do reduce to some specific complete problem.

To see why don't get the converse for free, consider reductions outside NP. Because NP$\,\subset\,$NEXP (nondeterministic exponential time), any problem in NP can be reduced to any NEXP-complete problem. However, we know that the converse reduction, from a NEXP-complete problem to an NP problem, cannot exist: that would imply that NP=NEXP but we know that those two classes are different, by the time hierarchy theorem.

The 3SAT $\leq_p$ 3-coloring reduction, of course, requires the use of special and restricted graphs where a 3-coloring exists iff a satisfying assignment for the 3SAT problem exists.

Doesn't this conflict with statements (at least I thought I heard in CS classes) saying that an oracle for 3SAT would prove P = NP? Might it not be the case that such an algorithm would be worthless for solving families of 3-coloring problems?

What you (should have!) heard in class is that having a deterministic polynomial time algorithm for 3SAT would prove that P=NP. But remember what an oracle is. An oracle is an add-on to your Turing machine with the following property: if you write a 3SAT instance onto the oracle's tape, you can "push a button" and, in one time step, the oracle will tell you whether that formula is satisfiable or not. So, the fact that 3SAT is NP-complete means that NP is equal to the class of problems that can be solved in polynomial time by a deterministic Turing machine with an oracle for 3SAT. However, that is not P: P is the class of problems that can be solved in polynomial time by a deterministic Turing machine with no oracle at all. In symbols, you've proved that NP=P3SAT, not that NP=P.

However, if you can prove that 3SAT is in P, i.e., that there is a deterministic polynomial time algorithm (without using oracles) for 3SAT, then you have proven that P=NP. The reason is that, now, you can go back to your proof that NP=P3SAT and replace all the oracle calls with a "subroutine" that just solves the 3SAT instance you wrote to the oracle's tape.

Doesn't this imply some kind of hierarchy of NP-complete problems?

Not really, no. However, there is a hierarchy of NP-complete problems. I already alluded to that above by using the time hierarchy theorem to separate NP and NEXP. But the time hierarchy theorem is a little more powerful than that: it also tells us that NTIME($n^k$)$\neq$NTIME($n^{k+1}$). That is, for all $k$, there are things that you can do nondeterministically in $O(n^{k+1})$ steps that you can't do in $O(n^{k})$ steps (the same is true for deterministic machines). That gives you a hierarchy right away.

In practice, you don't hear about this hierarchy very often. I think the reason is that, by the time you've said that a problem is NP-complete, that already means that it's hard enough that you probably don't care about its exact complexity. For deterministic algorithms, we do care about the hierarchy: $\Theta(n^{10})$ is impractical, $\Theta(n^3)$ is OK on smallish datasets, $\Theta(n\log n)$ is great unless you're Google and $n$ is the whole web, etc. But for NP-complete problems, they're almost all at the "impractical" end so we normally don't bother to distinguish.

(Footnote for the experts: yes, we often distinguish between NP-complete problems in terms of, say, fixed-parameter tractability and the W-hierarchy but I think that's not really the direction this question is going.)

$\endgroup$
1
$\begingroup$

A problem $P$ is NP-hard if all NP-problems can be solved with an oracle for $P$ in polynomial time. $P$ is NP-complete if $P$ is NP-hard and in NP.

So sure, I understanding that with an oracle for 3-coloring, one could solve arbitrary instances of 3SAT in polynomial time.

Here, you are showing that 3-coloring is at least as hard as 3SAT: 3SAT can be solved if we know a solution for some special kinds of instances of 3-coloring - but we don't know whether there are instances of 3-coloring that are harder than 3SAT. (A)

Technically, if you already know that 3SAT is NP-hard, this shows that 3-coloring is NP-hard: If you can solve any NP problem with an oracle for 3SAT in polynomial time, you can now solve any NP problem with an oracle for 3-coloring in polynomial time.

But why would I assume the converse holds, that I can solve arbitrary instances of 3-coloring provided an oracle for 3SAT? [...] Doesn't this conflict with statements (at least I thought I heard in CS classes) saying that an oracle for 3SAT would prove P = NP?

You don't need to assume, but you can prove that (1) 3-coloring is in NP, and (2) 3SAT is NP-hard. These two proofs need not be (and most likely are not) similar to the other direction.

These proofs show that 3SAT is at least as hard as 3-coloring: 3-coloring can be solved if we know a solution to some special kinds of instances of 3SAT - but with this alone we don't know whether there exists instances of 3SAT that are harder than 3-coloring. (B)


To combine, (A) means that all instances of 3SAT can be solved if we know how to solve some specific instances of 3-coloring, and (B) means that all instances of 3-coloring can be solved if we know how to solve some specific instances of 3SAT. These two separate pieces of knowledge tell us that being able to solve all instances of 3SAT is "equivalent" to being able to solve all instances of 3-coloring.


The standard method of proving that $P$ is NP-complete.

  • Show that $P$ is in NP.
  • Pick an NP-complete problem $Q$, for example 3SAT. Because we already know (someone else has proved) that $Q$ is NP-complete, we know that $Q$ is at least as hard as $P$.
  • Show that $Q$ can be solved in polynomial time with an oracle for $P$. Now we know that $P$ is at least as hard as $Q$.
$\endgroup$
  • $\begingroup$ Everything you've just said here is correct to the best of my knowledge. I just do not know why the standard method of proving something NP-complete makes sense. Aren't you just showing that some special case of one problem (3-coloring) is as hard as the general case of another problem 3SAT? Why have we shown that general case 3-coloring is as hard as 3SAT and/or that an oracle for arbitrary 3SAT instances is just as good as an oracle for arbitrary 3-coloring instances? $\endgroup$ – Mill Dec 12 '14 at 10:01
  • $\begingroup$ Let's also just be clear that this is a "I don't understand, please lend me some intuition" type of question. I'm not challenging fundamental practices in computer science. $\endgroup$ – Mill Dec 12 '14 at 10:02
  • $\begingroup$ @Mill I edited the answer to a bit more intuitive language. $\endgroup$ – JiK Dec 12 '14 at 10:39
  • $\begingroup$ Why do we know that $Q$ is "at least" as hard as $P$? Why couldn't $P$ be "at least" as hard as $Q$? Showing something is in NP just means showing that solutions can verified or rejected in polynomial time, right? $\endgroup$ – Mill Dec 12 '14 at 10:45
  • $\begingroup$ @Mill "$Q$ is NP-hard" means (by definition) that $Q$ is at least as hard as any NP problem, including $P$. $\endgroup$ – JiK Dec 12 '14 at 10:47

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.