According to answers here Are there subexponential-time algorithms for NP-complete problems? $\mathsf{NP}$ complete problems can be in $DTIME[2^{n^{1/\alpha}}]$ for $\alpha>1$.

Now supposing $DTIME[2^{n^{1/\alpha}}]\subseteq\mathsf{P/Poly}$ holds for every $\alpha>1$ then does it mean $\mathsf{NP}\subseteq\mathsf{P/Poly}$ holds?

What are the consequences of $DTIME[2^{n^{1/\alpha}}]\subseteq\mathsf{P/Poly}$?

Would this impact $\mathsf{subexp}\subseteq\mathsf{P/poly}$ problem?


1 Answer 1


If $DTIME\left[2^{n^{\frac{1}{\alpha}}}\right]\subseteq P/Poly$ for some $\alpha>1$ then $NP\subseteq P/Poly$, since this means we can put an NP-complete problem in $P/Poly$, because as you mentioned, for all $\alpha>1$ there exists some NP complete problem in $DTIME\left[2^{n^{\frac{1}{\alpha}}}\right]$. To see why the inclusion holds in that case, notice that for any other language in $NP$ you can first compute the reduction in polynomial time, and then work with the machine taking advice for the complete problem.

In order for the above to work, the reduction $f$ to our NP-Complete problem must have the property that $|f(x)|$ depends only on $|x|$ (the length of the output depends only on the length of the input, and not structure). However, we need not worry, since the reduction in Cook-Levin theorem has this property (verify), and the reduction from $SAT$ to padded SAT:

$SAT' = \{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \}$

also has this property.

A well known consequence of $NP\subseteq P/Poly$ is the Karp-Lipton theorem.

As for your second question, use the fact that $SUBEXP=\bigcap\limits_{\epsilon>0}DTIME\left[2^{n^\epsilon}\right]\subseteq DTIME\left[2^{n^{\frac{1}{\alpha}}}\right] $, for all $\alpha>1$.

  • $\begingroup$ I seriously doubt this. I will wait for other clearer answers. $\endgroup$
    – Turbo
    Commented Oct 23, 2016 at 8:06
  • $\begingroup$ Well, there is nothing much i can do with this kind of comment. If you see a flaw in my proof, please point it out, I don't see any. $\endgroup$
    – Ariel
    Commented Oct 23, 2016 at 8:58
  • $\begingroup$ I do not see any. I am not sure if it is possible though seems weird. $\endgroup$
    – Turbo
    Commented Oct 23, 2016 at 8:59
  • $\begingroup$ I think $SUBEXP^{NP}\subsetneq P/poly$ so either $SUBEXP\subsetneq P/poly$ or ${NP}\subsetneq P/poly$ should hold. Here we get both. $\endgroup$
    – Turbo
    Commented Oct 23, 2016 at 9:47
  • 2
    $\begingroup$ @AJ. That's the beauty of mathematical proof: it's equipped to convince you of the falsehood of your intuitions. $\endgroup$
    – Raphael
    Commented Oct 23, 2016 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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