# Is $NP\subseteq DTIME(2^{\theta(\sqrt n)})$ never possible?

$DTIME(2^{\sqrt n})$ is not closed under polynomial changes of $n$ however $DTIME(2^{polylog(n)})$ is.

So if $3SAT$ were in $DTIME(2^{polylog(n)})$ then $NP\subseteq DTIME(2^{polylog(n)})$ holds.

However if $3SAT$ were in $DTIME(2^{\sqrt n})$ then we cannot say $NP\subseteq DTIME(2^{O( n^{O(1)}{}\mbox{ })})$.

This would be really nice property since we will have $NP\neq EXP$ automatically even with modest speedups to $3SAT$ of form $DTIME(2^{o(n)})$ and simply violating ETH gives $NP\neq EXP$ result.

1. So is $NP\subseteq DTIME(2^{( n^{\theta(1)}{}\mbox{ })})$ never a strict possibility?

2. That is does $NP\subseteq DTIME(2^{O( n^{O(1)}{}\mbox{ })})$ imply $NP\subseteq DTIME(2^{O( n^{o(1)}{}\mbox{ })})$ always?

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Jun 5 '18 at 12:28

$\mathsf{CircuitSat\in DTIME(2^n)}$ does not imply $\mathsf{NP\subseteq DTIME(2^n)}$ since the reduction might increase the input's size. Suppose for example that $L\in NP$ and the reduction from $L$ to $\mathsf{CircuitSat}$ maps strings of length $n$ to strings of length $n^c$ (for all $n\in\mathbb{N}$), then applying the reduction and using a naive exponential time algorithm for circuit sat yields a $2^{n^c}$ time algorithm for $L$.
If however you can place an NP-complete problem in a subexponential time class, e.g. $n^{\log n}$, then $NP\neq EXP$, since $n^{O(\log n)}$ is closed under polynomial transformations, i.e. $n\mapsto n^c$.
• Suppose $L$ lies in NP and the reduction from it to SAT requires $n^c$ time, then in order to obtain a $2^{n^\epsilon}$ time algorithm for $L$ you can apply the reduction and use a $2^{n^\frac{\epsilon}{c}}$ time algorithm for SAT. – Ariel Jun 30 '18 at 11:18