<p>Emil Jeřábek' comment answers the question:</p>

<blockquote>
  <p>P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly</p>
</blockquote>

<p>Note the corollary</p>

<blockquote>
  <p>P/poly $\neq$ NP/poly implies P $\neq$ NP.</p>
</blockquote>

<p>Proof of corollary: </p>

<ol>
<li>P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly $\ $ (Emil's comment)</li>
<li>NP $\subseteq$ P/poly implies P/poly $=$ NP/poly $\ $ (implied by 1.)</li>
<li>P/poly $\neq$ NP/poly implies NP $\not\subseteq$ P/poly $\ $ (equivalent to 2.)</li>
<li>NP $\not\subseteq$ P/poly implies P $\neq$ NP $\ $ (P $\subseteq$ P/poly)</li>
<li>P/poly $\neq$ NP/poly implies P $\neq$ NP $\ $ (implied by 3. and 4.)</li>
</ol>

<p>Proof of Emil's comment:
It is sufficient to show that NP $\subseteq$ P/poly implies P/poly $=$ NP/poly.</p>

<ol>
<li>So let's assume NP $\subseteq$ P/poly.</li>
<li>Because SAT $\in$ NP there exists $p_{SAT}\geq k_{SAT}&gt;0$ and a sequence of advice strings $s_n$ with $\left|s_n\right|\leq n^{k_{SAT}}$, a deterministic algorithm that can decide SAT instances of size $n$ in time $\leq n^{p_{SAT}}$, if it has access to $s_n$. WLOG, that algorithm can also decide SAT instances of size $\leq n$, because we can define a modified sequence $s'_n=s'_{n-1}s_n$ with $\left|s'_n\right|\leq n^{k_{SAT}+1}$, where all previous advice strings are included in $s'_n$.</li>
<li>Now let $L\in$ NP/poly be an arbitrary language, for which we need to show $L\in$ P/poly. There exists $p_L\geq k_L&gt;0$ and a sequence of advice strings $l_n$ with $\left|l_n\right|\leq n^{k_L}$ and a nondeterministic algorithm that can decide $L$ instances of size $n$ in time $\leq n^{p_L}$, if it has access to $l_n$.</li>
<li>For each $w$ with $|w|=n$, a SAT instance of size $\leq c\cdot n^{p_L}$ can be computed (in time $O(n^{p_L})$) that is satisfiable exactly if $w\in L$.</li>
<li>So for the sequence of advice strings $t_n=l_ns_{c\cdot n^{p_L}}$ with $|t_n|\leq n^{k_L}+(c\cdot n^{p_L})^{k_{SAT}}$, the combination of the deterministic algorithms from 2. and 4. gives a deterministic algorithm that can decide $L$ instances of size $n$ in time $O((c\cdot n^{p_L})^{p_{SAT}})$, if it has access to $t_n$.</li>
<li>Because $L\in$ NP/poly was an arbitrary language, this shows NP/poly $\subseteq$ P/poly, under the assumption that NP $\subseteq$ P/poly.</li>
</ol>

<hr>

<p>All the above proofs relativize, because the existence of NP-complete problems is also true in relativized worlds. This suggests that it is fruitless to search for a proof that P/poly $\neq$ NP/poly. However let's summarize the <a href="https://cstheory.stackexchange.com/revisions/31838/2">removed motivation section</a> from the question as "The advice string could be a formal axiomatic system (automatically guaranteed to be consistent, evil grin) whose strength is quickly increasing with input length, and NP is extermely good at exploiting this advice." If one is not very careful that "existence of a sequence of advice stings" only has "formal" meaning relative to a fixed formal system, that setup is likely to allow the construction of apparent paradoxes. But the construction of such paradoxes might be fun nevertheless, and perhaps they might even suggests ways how to construct independence proofs (for sufficiently weak formal systems).</p>

CC BY-SA 3.0
2015-06-28T12:57:46.963Z
2015-06-28T12:57:46.963Z
2017-04-13T12:32:28.743Z
Thomas Klimpel
<p>$P/poly = NP/poly$ implies $NP \subseteq P/poly$, which in turn has interesting consequences like the collapse of the polynomial hierarchy.</p>

<p>Are there interesting implications for $P/poly \neq NP/poly$?</p>

CC BY-SA 3.0
2015-06-26T09:44:16.610Z
I removed the long motivation part because it is not useful and distracting and the question is interesting enough by itself that it would not need such motivation.
Kaveh
CC BY-SA 3.0
2015-06-26T12:37:54.067Z
$\mathrm{P}/\mathrm{poly}=\mathrm{NP}/\mathrm{poly}$ is *equivalent* to $\mathrm{NP}\subseteq\mathrm{P}/\mathrm{poly}$.
Emil Jeřábek
CC BY-SA 3.0
2015-06-26T13:55:26.787Z
@EmilJeřábek So you say P/poly $\neq$ NP/poly implies NP $\not\subseteq$ P/poly. Do you have any reference for this, or can you explain me how to see this? If yes, then this definitively qualifies as an answer.
Thomas Klimpel
CC BY-SA 3.0
2015-06-26T17:08:06.780Z
@Kaveh: is removing the motivation really the kind of thing we should be doing?  It introduced me to things I hadn't come across before, and it's not like it wasn't sectioned off.  This isn't Twitter.
András Salamon
CC BY-SA 3.0
2015-06-26T18:09:25.333Z
@AndrásSalamon I guess the motivation was too long, compared to the question itself. It would have been enough motivation to just say that the advice string could be a formal axiomatic system (automatically guaranteed to be consistent, grin) whose strength is quickly increasing with input length and that NP is extermely good at exploiting this advice.
Thomas Klimpel
CC BY-SA 3.0
2015-06-26T18:28:13.930Z
@EmilJeřábek I think I got it now. NP $\subseteq$ P/poly implies P/poly = NP/poly, because the deterministic algorithm can get both its own advice string for becoming as powerful as NP, together with the advice-string for the language from NP/poly, and this is enough for deciding that language.
Thomas Klimpel
CC BY-SA 3.0
2015-06-26T19:09:12.673Z
@András, I think it was justified for the reason I wrote above, it wasn't helping the question.
Kaveh
CC BY-SA 3.0
2015-06-27T13:40:52.390Z
@ThomasKlimpel: Yes, exactly.
Emil Jeřábek
CC BY-SA 3.0
2015-06-27T19:36:06.637Z
@András, btw, just in case you haven't checked, the referred result was published by a publisher which is infamous for fake journals (including P=NP proofs with obvious mistakes).
Kaveh
CC BY-SA 3.0
2015-06-27T23:14:53.280Z
@Kaveh: ah, thanks, I hadn't picked that up.
András Salamon
<cc.complexity-theory><conditional-results><advice-and-nonuniformity>
Does P/poly $\neq$ NP/poly have any interesting implications?
Thomas Klimpel
# Does P/poly $\neq$ NP/poly have any interesting implications?

(Asked by: username_0 on 2015-06-26)

$P/poly = NP/poly$ implies $NP \subseteq P/poly$, which in turn has interesting consequences like the collapse of the polynomial hierarchy.

Are there interesting implications for $P/poly \neq NP/poly$?

**Tags:** cc.complexity-theory, conditional-results, advice-and-nonuniformity
> **Comments:**
> **username_1**: I removed the long motivation part because it is not useful and distracting and the question is interesting enough by itself that it would not need such motivation.  
> **username_2**: $\mathrm{P}/\mathrm{poly}=\mathrm{NP}/\mathrm{poly}$ is *equivalent* to $\mathrm{NP}\subseteq\mathrm{P}/\mathrm{poly}$.  
> **username_0**: @EmilJeřábek So you say P/poly $\neq$ NP/poly implies NP $\not\subseteq$ P/poly. Do you have any reference for this, or can you explain me how to see this? If yes, then this definitively qualifies as an answer.  
> **username_3**: @Kaveh: is removing the motivation really the kind of thing we should be doing?  It introduced me to things I hadn't come across before, and it's not like it wasn't sectioned off.  This isn't Twitter.  
> **username_0**: @AndrásSalamon I guess the motivation was too long, compared to the question itself. It would have been enough motivation to just say that the advice string could be a formal axiomatic system (automatically guaranteed to be consistent, grin) whose strength is quickly increasing with input length and that NP is extermely good at exploiting this advice.  
> **username_0**: @EmilJeřábek I think I got it now. NP $\subseteq$ P/poly implies P/poly = NP/poly, because the deterministic algorithm can get both its own advice string for becoming as powerful as NP, together with the advice-string for the language from NP/poly, and this is enough for deciding that language.  
> **username_1**: @András, I think it was justified for the reason I wrote above, it wasn't helping the question.  
> **username_2**: @ThomasKlimpel: Yes, exactly.  
> **username_1**: @András, btw, just in case you haven't checked, the referred result was published by a publisher which is infamous for fake journals (including P=NP proofs with obvious mistakes).  
> **username_3**: @Kaveh: ah, thanks, I hadn't picked that up.  

---

## 1 answers

### Answer by username_0 on 2015-06-28. Score: 13 | Accepted answer

Emil Jeřábek' comment answers the question:

> P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly

Note the corollary

> P/poly $\neq$ NP/poly implies P $\neq$ NP.

Proof of corollary:

1. P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly $\ $ (Emil's comment)
2. NP $\subseteq$ P/poly implies P/poly $=$ NP/poly $\ $ (implied by 1.)
3. P/poly $\neq$ NP/poly implies NP $\not\subseteq$ P/poly $\ $ (equivalent to 2.)
4. NP $\not\subseteq$ P/poly implies P $\neq$ NP $\ $ (P $\subseteq$ P/poly)
5. P/poly $\neq$ NP/poly implies P $\neq$ NP $\ $ (implied by 3. and 4.)

Proof of Emil's comment:
It is sufficient to show that NP $\subseteq$ P/poly implies P/poly $=$ NP/poly.

1. So let's assume NP $\subseteq$ P/poly.
2. Because SAT $\in$ NP there exists $p\_{SAT}\geq k\_{SAT}>0$ and a sequence of advice strings $s\_n$ with $\left|s\_n\right|\leq n^{k\_{SAT}}$, a deterministic algorithm that can decide SAT instances of size $n$ in time $\leq n^{p\_{SAT}}$, if it has access to $s\_n$. WLOG, that algorithm can also decide SAT instances of size $\leq n$, because we can define a modified sequence $s'\_n=s'\_{n-1}s\_n$ with $\left|s'\_n\right|\leq n^{k\_{SAT}+1}$, where all previous advice strings are included in $s'\_n$.
3. Now let $L\in$ NP/poly be an arbitrary language, for which we need to show $L\in$ P/poly. There exists $p\_L\geq k\_L>0$ and a sequence of advice strings $l\_n$ with $\left|l\_n\right|\leq n^{k\_L}$ and a nondeterministic algorithm that can decide $L$ instances of size $n$ in time $\leq n^{p\_L}$, if it has access to $l\_n$.
4. For each $w$ with $|w|=n$, a SAT instance of size $\leq c\cdot n^{p\_L}$ can be computed (in time $O(n^{p\_L})$) that is satisfiable exactly if $w\in L$.
5. So for the sequence of advice strings $t\_n=l\_ns\_{c\cdot n^{p\_L}}$ with $|t\_n|\leq n^{k\_L}+(c\cdot n^{p\_L})^{k\_{SAT}}$, the combination of the deterministic algorithms from 2. and 4. gives a deterministic algorithm that can decide $L$ instances of size $n$ in time $O((c\cdot n^{p\_L})^{p\_{SAT}})$, if it has access to $t\_n$.
6. Because $L\in$ NP/poly was an arbitrary language, this shows NP/poly $\subseteq$ P/poly, under the assumption that NP $\subseteq$ P/poly.

---

All the above proofs relativize, because the existence of NP-complete problems is also true in relativized worlds. This suggests that it is fruitless to search for a proof that P/poly $\neq$ NP/poly. However let's summarize the [removed motivation section](https://cstheory.stackexchange.com/revisions/31838/2) from the question as "The advice string could be a formal axiomatic system (automatically guaranteed to be consistent, evil grin) whose strength is quickly increasing with input length, and NP is extermely good at exploiting this advice." If one is not very careful that "existence of a sequence of advice stings" only has "formal" meaning relative to a fixed formal system, that setup is likely to allow the construction of apparent paradoxes. But the construction of such paradoxes might be fun nevertheless, and perhaps they might even suggests ways how to construct independence proofs (for sufficiently weak formal systems).


---

