0
$\begingroup$

Are there any decision problems that have deterministic polynomial time algorithms and proven non-linear lower bounds?

Improve this question
$\endgroup$
2
  • $\begingroup$ cs.stackexchange.com/a/147968/755 $\endgroup$
    – D.W. ♦
    Commented Feb 27, 2022 at 22:40
  • $\begingroup$ thanks for the link. that answers my question. $\endgroup$
    – ajaykr
    Commented Mar 5, 2022 at 23:30

0

Reset to default