<p>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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/q/1050/873">this topic</a> for more info.</p>

CC BY-SA 2.5
2011-01-03T22:18:58.563Z
That answers the whole question and gives me pointers to where to go for further information, Thank you very much!
Valmond
CC BY-SA 2.5
2011-01-03T22:30:21.300Z
@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.
Sadeq Dousti
CC BY-SA 2.5
2011-01-03T22:14:00.773Z
2011-01-05T13:01:56.560Z
2017-04-13T12:32:28.743Z
Sadeq Dousti
<p>this is my first question here so I hope I've done everything correctly.</p>

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

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

<p>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 "!" ?</p>

<p>Please point me in the right direction if you can.</p>

<p>Thanks for your time and I hope my question is clear enough.</p>

CC BY-SA 2.5
2011-01-05T02:37:58.613Z
Removed “[Solved]” from the question title.  Please accept the answer by clicking the check mark on the left of the answer instead.
Tsuyoshi Ito
<cc.complexity-theory><np><bounds>
What relations has different bounds for NP?
Valmond
# What relations has different bounds for NP?

(Asked by: username_0 on 2011-01-03)

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.

**Tags:** cc.complexity-theory, np, bounds

> **Comments:**
> **username_1**: Removed “[Solved]” from the question title.  Please accept the answer by clicking the check mark on the left of the answer instead.  

---

## 1 answers

### Answer by username_2 on 2011-01-03. Score: 4 | Accepted answer

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](https://cstheory.stackexchange.com/q/1050/873) for more info.

> **Comments:**
> **username_0**: That answers the whole question and gives me pointers to where to go for further information, Thank you very much!  
> **username_2**: @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.  

---

