$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 '20 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$ – Yuval Filmus Nov 13 '20 at 10:26
  • $\begingroup$ Forget your requirements. Non-trivial lower bounds in general are incredibly rare. $\endgroup$ – orlp Nov 14 '20 at 13:45

Your Answer

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

Browse other questions tagged or ask your own question.