3
$\begingroup$

$\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}$?

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Jun 5 '18 at 12:28
5
$\begingroup$

$\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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Raphael Jun 5 '18 at 12:28
  • $\begingroup$ 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. $\endgroup$ – Ariel Jun 30 '18 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.