Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

Question

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

Answer 1

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.

Answer 2

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=P^3SAT, 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=P^3SAT 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.)

Answer 3

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