# What relations has different bounds for NP?

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.

• Removed “[Solved]” from the question title. Please accept the answer by clicking the check mark on the left of the answer instead. – Tsuyoshi Ito Jan 5 '11 at 2:37

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.