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.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Raphael Nov 5 '18 at 14:37
  • 1
    $\begingroup$ @Raphael OK. I still think my answer is appropriate to the question body. $\endgroup$ – David Richerby Nov 5 '18 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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