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

Problem Detail: 

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

Asked By : Mill

Answered By : Tom van der Zanden

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.

Best Answer from StackOverflow

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