$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?
Is there a super-linear lower bound on the time complexity of all solutions of NP complete problems?
3
-
$\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$– ShaullNov 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$– Yuval FilmusNov 13, 2020 at 10:26
-
$\begingroup$ Forget your requirements. Non-trivial lower bounds in general are incredibly rare. $\endgroup$– orlpNov 14, 2020 at 13:45
Add a comment
|