# Intersecting Complexity Classes with Advice

In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote:

$(\mathsf{NP/poly} \cap \mathsf{co\text-NP}{/poly})$ ... is not known to be equal to $(\mathsf{NP} ∩ \mathsf{co\text-NP}){/poly}$.

They highlighted that in the conference paper, they mistook the two classes. Apparently, the latter is a subset of the former, but we don't know if the containment is strict.

Assuming $X$ and $Y$ are complexity classes, and $F$ is a set of functions specifying the length of the advice strings, are there recent results comparing $(X_{/F} \cap Y_{/F})$ and $(X \cap Y)_{/F}$, resolving issues like the one pointed above?

• What is the definition of (NP ∩ coNP)/poly? What is a NP ∩ coNP machine? – Henry Yuen Mar 31 '12 at 18:59
• @HenryYuen: Maybe the definition of ZPP helps: ZP = RP ∩ CoRP. See en.wikipedia.org/wiki/ZPP_(complexity)#Intersection_definition. – M.S. Dousti Apr 2 '12 at 8:07
• If you take the definition that ZPP = RP ∩ coRP, that doesn't immediately give you a model of computation that accepts only ZPP languages: it only says that every language in ZPP has both an RP machine and a coRP machine (which is well defined). You have to prove that ZPP is the class of languages that admit Las Vegas algorithms. Similarly -- NP ∩ coNP defines a set of languages that have both NP and coNP machines, but is there a model of computation that accepts precisely NP ∩ coNP? – Henry Yuen Apr 2 '12 at 18:17
• @HenryYuen: I actually don't know if there's an underlying model of computation, but the definitions of complexity classes are clear, as in the case of ZPP. Besides being a very interesting problem, is there any significance (to my question) if NP ∩ coNP does (or does NOT) admit a computation model? – M.S. Dousti Apr 3 '12 at 0:32
• @HenryYuen: I think that a Language $L$ is in $(NP \cap coNP)/poly$ iff there is a language $K$ in $NP \cap coNP$ and $a_i$ advice of polynomial length s.t. $x \in L$ iff $(x, a_{|x|}) \in K$. – Vanessa Apr 10 '15 at 9:18