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.
