# CIRCUITSAT ∈ DTIME(2^n/n^c) ⟹ NP ≠ EXP?

$$\mathsf{EXP}\not\subseteq \mathsf{DTIME}(2^{n})$$ and $$\mathrm{CIRCUITSAT}\in \mathsf{DTIME}({2^{n}})$$ holds and so why does $$\mathsf{NP}\neq \mathsf{EXP}$$ not hold while we know $$\mathsf{NP}\subseteq \mathsf{DTIME}({2^{n}})\implies \mathsf{NP}\neq \mathsf{EXP}$$?

Does $$\mathrm{CIRCUITSAT}$$ in any of $$\mathsf{DTIME}(\frac{2^{n}}{n^c})$$, $$\mathsf{DTIME}({2^{\sqrt n}})$$ or $$\mathsf{DTIME}({2^{(\log n)^2}})$$ $$\implies \mathsf{NP}\neq \mathsf{EXP}$$?

• 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