Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
