# On SUBEXP ⊆ P/poly

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?

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

• I seriously doubt this. I will wait for other clearer answers. – T.... Oct 23 '16 at 8:06
• 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. – Ariel Oct 23 '16 at 8:58
• I do not see any. I am not sure if it is possible though seems weird. – T.... Oct 23 '16 at 8:59
• I think $SUBEXP^{NP}\subsetneq P/poly$ so either $SUBEXP\subsetneq P/poly$ or ${NP}\subsetneq P/poly$ should hold. Here we get both. – T.... Oct 23 '16 at 9:47
• @AJ. That's the beauty of mathematical proof: it's equipped to convince you of the falsehood of your intuitions. – Raphael Oct 23 '16 at 10:20