It is known that $EXP$ doesn't have circuits of size $n^k$. On the other hand proving $10 n$ lower bound on circuit size for $E$, $NE$ or even $E^{NP}$ is a known open problem.

My question is following: do we know any non-trivial lower bounds for any of the following classes?

  • $Time(2^{n \sqrt{\log(n)}})$
  • $NTime(2^{n \sqrt{\log(n)}})$
  • $Time(2^{n \sqrt{\log(n)}})^{NP}$

Instead of $n \sqrt{\log(n)}$ could be any function in $o(n \log{n})$. After $n \log{n}$ the straightforward diagonalization should start working.



Your Answer

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