<p>Can NP-complete language be in monotone <span class="math-container">$P/poly$</span>?</p>

CC BY-SA 4.0
2022-06-09T06:50:04.780Z
Isn't it unlikely since otherwise we would have $NP \subseteq P/poly$ which would imply $PH = \Sigma_2$ by Karp-Lipton Theorem?
holf
CC BY-SA 4.0
2022-06-09T09:35:12.030Z
Can we say something stronger, based on Razborov,Alon,Boppana result that SAT cannot be in mP\poly?

The question is can we deduce from SAT$\notin$ mP/poly, that any NP-complete language is outside of mP/poly?
qwerty43
CC BY-SA 4.0
2022-06-09T10:51:00.660Z
SAT is not a monotone language, hence it is trivially outside mP/poly. The Razborov/Alon–Boppana results state that certain *monotone* NP languages (Clique, or the dual of Colourability) are outside mP/poly. But yes, I think the question whether we can *unconditionally* (or at least, under a weaker assumption than $\mathrm{NP\nsubseteq P/poly}$) prove at the moment that no NP-complete language is in mP/poly is interesting. (This does not follow automatically from Alon–Boppana, as polynomial-time reductions between monotone NP-complete languages may not preserve monotone circuit size.)
Emil Jeřábek
CC BY-SA 4.0
2022-06-09T13:42:23.147Z
I should perhaps point out that the Razborov/Alon–Boppana result is not so much about the complexity of NP-complete problems, but rather about the difference between monotone and non-monotone circuits: the lower bound applies to all functions separating graphs with clique size $k+1$ from $k$-colourable graphs where $k=\sqrt n$ or so, and as shown by Tardos, there is a *polynomial-time* monotone function that fits the bill.
Emil Jeřábek
<circuit-complexity><np-complete><monotone>
Can NP-complete language be in $mP/poly$?
qwerty43
# Can NP-complete language be in $mP/poly$?

(Asked by: username_0 on 2022-06-08)

Can NP-complete language be in monotone $P/poly$?

**Tags:** circuit-complexity, np-complete, monotone
> **Comments:**
> **username_1**: Isn't it unlikely since otherwise we would have $NP \subseteq P/poly$ which would imply $PH = \Sigma_2$ by Karp-Lipton Theorem?  
> **username_0**: Can we say something stronger, based on Razborov,Alon,Boppana result that SAT cannot be in mP\poly?  The question is can we deduce from SAT$\notin$ mP/poly, that any NP-complete language is outside of mP/poly?  
> **username_2**: SAT is not a monotone language, hence it is trivially outside mP/poly. The Razborov/Alon–Boppana results state that certain *monotone* NP languages (Clique, or the dual of Colourability) are outside mP/poly. But yes, I think the question whether we can *unconditionally* (or at least, under a weaker assumption than $\mathrm{NP\nsubseteq P/poly}$) prove at the moment that no NP-complete language is in mP/poly is interesting. (This does not follow automatically from Alon–Boppana, as polynomial-time reductions between monotone NP-complete languages may not preserve monotone circuit size.)  
> **username_2**: I should perhaps point out that the Razborov/Alon–Boppana result is not so much about the complexity of NP-complete problems, but rather about the difference between monotone and non-monotone circuits: the lower bound applies to all functions separating graphs with clique size $k+1$ from $k$-colourable graphs where $k=\sqrt n$ or so, and as shown by Tardos, there is a *polynomial-time* monotone function that fits the bill.  

---

## 0 answers

