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.
What relations has different bounds for NP?
cc.complexity theory;np;bounds
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.