1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I seriously doubt this. I will wait for other clearer answers. $\endgroup$ – T.... Oct 23 '16 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 Oct 23 '16 at 8:58
  • $\begingroup$ I do not see any. I am not sure if it is possible though seems weird. $\endgroup$ – T.... Oct 23 '16 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$ – T.... Oct 23 '16 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 Oct 23 '16 at 10:20

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.