<p>Assuming $\mathsf{P} \ne \mathsf{NP}$ can we show $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? Obviously this would be the case if $\mathsf{P} \ne \mathsf{NP}$ and $\mathsf{P/poly} \supset \mathsf{NP}$ but this is unlikely. This is also true under the assumption $\mathsf{P} \ne \mathsf{BPP}$, however AFAIK it is commonly believed $\mathsf{P} = \mathsf{BPP}$. Can we prove $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$ under a weaker assumption? What evidence can be provided for/against? Is there a specific language which is believed to be in $\mathsf{P/poly} \cap \mathsf{NP}$ but not in $\mathsf{P}$?</p>

CC BY-SA 3.0
2013-01-15T23:11:46.103Z
related question: [Is $\mathsf{AC^0}/poly \cap \mathsf{NP}$ contained in $\mathsf{P}$?](http://cstheory.stackexchange.com/q/1982/186)
Kaveh
CC BY-SA 3.0
2013-01-15T23:12:59.427Z
also: [Is there a candidate for a natural problem in $\mathsf{P}/poly−\mathsf{P}$?](http://cstheory.stackexchange.com/q/1662/186)
Kaveh
CC BY-SA 3.0
2013-01-30T01:38:44.513Z
I deleted my answer, because I realized that it was essentially the same as [Yuval Filmus’ answer](http://cstheory.stackexchange.com/a/1989#1989) in the first link which Kaveh gave.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-30T08:40:35.850Z
You think maybe this question should be closed as a duplicate?
David Eppstein
CC BY-SA 3.0
2013-02-03T08:31:19.633Z
Squark, do the answers in the linked questions answer your question? If not then it would be nice if clarify the question and explain why they don't.
Kaveh
CC BY-SA 3.0
2013-02-11T19:41:51.113Z
@Kaveh Yes, I think these answers are satisfactory, thank you
Vanessa
<cc.complexity-theory><p-vs-np><advice-and-nonuniformity>
$\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$?
Vanessa
# $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$?

(Asked by: username_0 on 2013-01-15)

Assuming $\mathsf{P} \ne \mathsf{NP}$ can we show $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? Obviously this would be the case if $\mathsf{P} \ne \mathsf{NP}$ and $\mathsf{P/poly} \supset \mathsf{NP}$ but this is unlikely. This is also true under the assumption $\mathsf{P} \ne \mathsf{BPP}$, however AFAIK it is commonly believed $\mathsf{P} = \mathsf{BPP}$. Can we prove $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$ under a weaker assumption? What evidence can be provided for/against? Is there a specific language which is believed to be in $\mathsf{P/poly} \cap \mathsf{NP}$ but not in $\mathsf{P}$?

**Tags:** cc.complexity-theory, p-vs-np, advice-and-nonuniformity

> **Comments:**
> **username_1**: related question: [Is $\mathsf{AC^0}/poly \cap \mathsf{NP}$ contained in $\mathsf{P}$?](http://cstheory.stackexchange.com/q/1982/186)  
> **username_1**: also: [Is there a candidate for a natural problem in $\mathsf{P}/poly−\mathsf{P}$?](http://cstheory.stackexchange.com/q/1662/186)  
> **username_2**: I deleted my answer, because I realized that it was essentially the same as [Yuval Filmus’ answer](http://cstheory.stackexchange.com/a/1989#1989) in the first link which username_1 gave.  
> **username_3**: You think maybe this question should be closed as a duplicate?  
> **username_1**: Squark, do the answers in the linked questions answer your question? If not then it would be nice if clarify the question and explain why they don't.  
> **username_0**: @username_1 Yes, I think these answers are satisfactory, thank you  

---

## 0 answers

