$P \ne NP$ would imply that any polynomial is a lower bound on the time complexity of any NP complete problem.

Is some non-trivial lower bound known at all?

  • $\begingroup$ In a single-tape Turing machine, any language recognizable by a TM working in $o(n\log n)$ is regular. So you have a lower bound of $\Omega(n\log n)$ on every NP-complete problem (none of them are regular languages). $\endgroup$
    – Shaull
    Nov 13, 2020 at 10:00
  • $\begingroup$ There are some results for sublinear space, e.g. Williams' time-space tradeoff. There are also some circuit lower bounds, but they are only linear; see for example this recent work. $\endgroup$ Nov 13, 2020 at 10:26
  • $\begingroup$ Forget your requirements. Non-trivial lower bounds in general are incredibly rare. $\endgroup$
    – orlp
    Nov 14, 2020 at 13:45


Your Answer

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

Browse other questions tagged or ask your own question.