Is it true to say that any NP-Complete problem can be reduced to any other NP-Complete problem in polynomial time?
Asked
Active
Viewed 9,308 times
2 Answers
10
Yes. By definition any NP problem can be reduced to an NP-complete problem in polynomial time. Since NP-complete problems are themselves NP problems, all NP-complete problems can be reduced to each other in polynomial time.
Kyle Jones
- 1,871
3
Yes. By definition, a problem $A$ is NP-hard if any problem $B$ in NP has a polynomial-time reduction to $A$. Thus if $A$ and $B$ are NP-complete, $B$ has a polynomial-time reduction to $A$ since $A$ is NP-hard and $B$ is in NP. (Obviously $A$ has a polynomial-time reduction to $B$ as well, since $A$ is in NP and $B$ is NP-hard.)
Michael M
- 2,448