this is my first question here so I hope I've done everything correctly.

I know that if someone finds a polynomial solution to any of the famous NP problems, all of them has one (polynomial solution).

Does this hold for say a k^n solution (and if, must they all have the same exponent) ?

And my real question, is there some relation among NP problems in the sense that say one solution is n! then another can't be (n²)! or is that (the n²) 'eaten up' by the "!" ?

Please point me in the right direction if you can.

Thanks for your time and I hope my question is clear enough.

  • 2
    $\begingroup$ Removed “[Solved]” from the question title. Please accept the answer by clicking the check mark on the left of the answer instead. $\endgroup$ Jan 5, 2011 at 2:37

1 Answer 1


NP-complete problems can be polynomial-time reduced to each other via Karp/Cook/Levin reductions. Since polynomials are closed under composition, if there's a polynomial bound $f(\cdot)$ on the running time of an algorithm to solve NP-complete problem $A$, then for every NP-complete problem $B$ which reduces to $A$ in polynomial-time $g(\cdot)$, there will be an algorithm which solves $B$ in time bounded by $f(g(\cdot))$ which is a polynomial.

This does not hold for bounds other than polynomial. For instance, if there's a $2^n$ bound on solving $A$, there can be a $2^{n^{10}}$ bound on solving $B$. See this topic for more info.

  • $\begingroup$ That answers the whole question and gives me pointers to where to go for further information, Thank you very much! $\endgroup$
    – Valmond
    Jan 3, 2011 at 22:18
  • 10
    $\begingroup$ @user1707: You're welcome! And one more thing: The convention is to accept the answer (by clicking the "check mark" besides the answer), rather than adding [Solved] to the title. $\endgroup$ Jan 3, 2011 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.