If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete say anything about it being more difficult than other polynomial problems? In particular:

  1. Does it mean that $X$ cannot be solved in linear time? (alternatively, are there NP-complete problems that can be solved in linear time if $P=NP$)?
  2. Does it mean that $X$ cannot be solved in quadratic time? (alternatively, are there NP-complete problems that can be solved in quadratic time if $P=NP$)?
  3. If $X$ is NP-complete, and I prove a lower bound of $\Omega(n^2)$ on the run time of $X$ (a lower bound that does not depend on whether $P=NP$), did I prove anything new?
  • $\begingroup$ I'm not aware of any $\Omega(n^2)$ proofs for any problem in NP. Do you have such problem? see my question here. $\endgroup$
    – R B
    Feb 2, 2015 at 11:25

1 Answer 1


Yes, but without further information, only that $X$ has a lower bound of $\Omega(n^{2})$. (I'm assuming that, in line with the title, you're interested in what happens if it turns out that $P=NP$) The problem with transferring this information elsewhere is with the reductions used. As the only constraint is that they're computable in polynomial time, we can easily have the case that we simply solve the problem as part of the reduction (again assuming $P=NP$), so we can reduce it to any other problem in $P$ (this is why $P$-completeness is defined using more restrictive reductions - $NC$ reductions or logspace reductions, or similar, depending on exactly what version you're going for).

With some more specific information we can say something. If we have a problem $W$ where $X \leq_{P} W$ and we can compute the reduction in $O(n^{c})$ where $c < 2$, then we know that $W$ has a lower bound of $\Omega(n^{2/c})$ essentially because an upper bound on the problem tells us something. Say $A$ has an upper bound of $O(n^{c_1})$ for some $c_1$, we have a problem $B$ such that $B \leq_{P} A$ and we can compute this reduction in $O(n^{c_{2}})$, then $B$ has, at worst, a $O(n^{c_{1}c_{2}})$ algorithm - at worst we can convert the instance of $B$ to an instance of $A$ and solve that instead. So in our case, if $W$ had an upper bound of $O(n^{2/c - \varepsilon})$ for any $\varepsilon > 0$, then $X$ could be solved in $O(n^{c\cdot (2/c - \varepsilon)}) = O(n^{2-c\varepsilon})$, contradicting the lower bound.

Note of course that none of this really has anything to do with $X$ being $NP$-complete, it's true for any problem in $P$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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