# If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?

I came across this question while studying for an exam:

T/F: Suppose we can show for some fixed $$k$$, an NP-complete problem P has a time $$O(n^k)$$ algorithm. Then every problem in NP has a $$O(n^k)$$ time algorithm.

I think the answer is false, since we can't reduce NP-complete to NP-hard in linear time, right? Or am I completely misunderstanding reductions/NP problems? Any help would be greatly appreciated. Thank you.

Yes, the answer the the question is "false".

By contradiction, assume every problem in $$NP$$ has a $$O(n^k)$$ algorithm, for some fixed $$k$$. That is, $$NP \subseteq {\sf DTIME}(O(n^k))$$

This would contradict the time hierarchy theorem, which implies the strict inclusion

$${\sf DTIME}(O(n^k)) \subset {\sf DTIME}(O(n^{2k}))$$

However, we also have

$${\sf DTIME}(O(n^{2k})) \subseteq NP \subseteq {\sf DTIME}(O(n^{k}))$$

which contradicts the previous strict inclusion.

If $$\mathbf{P} = \mathbf{NP}$$, can all $$\mathbf{NP}$$ problems be solved within time $$O(n^k)$$ for fixed $$k$$?

No, because the time hierarchy theorem says that there are problems that can be solved in time $$O(n^{k+1})$$ that can't be solved in time $$O(n^k)$$.

we can't reduce NP-complete to NP-hard in linear time

Any $$\mathbf{NP}$$-complete problem is $$\mathbf{NP}$$-hard by definition.

• Note that the title is my attempt at creating a more snappy yet accurate one than the OP's. For that, I assumed that P = NP as a consequence of the problem statement was obvious.
– Raphael
Nov 5 '18 at 14:37
• @Raphael OK. I still think my answer is appropriate to the question body. Nov 5 '18 at 14:38