# Is there a super-linear lower bound on the time complexity of all solutions of NP complete problems?

$$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?

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