3
$\begingroup$

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

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

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