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}$?
Asked
Active
Viewed 355 times
18
-
4related question: Is $\mathsf{AC^0}/poly \cap \mathsf{NP}$ contained in $\mathsf{P}$? – Kaveh Jan 15 '13 at 23:11
-
1also: Is there a candidate for a natural problem in $\mathsf{P}/poly−\mathsf{P}$? – Kaveh Jan 15 '13 at 23:12
-
I deleted my answer, because I realized that it was essentially the same as Yuval Filmus’ answer in the first link which Kaveh gave. – Tsuyoshi Ito Jan 30 '13 at 01:38
-
2You think maybe this question should be closed as a duplicate? – David Eppstein Jan 30 '13 at 08:40
-
2Squark, 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 Feb 03 '13 at 08:31
-
@Kaveh Yes, I think these answers are satisfactory, thank you – Vanessa Feb 11 '13 at 19:41