<p>In <a href="http://linkinghub.elsevier.com/retrieve/pii/0022000089900184" rel="nofollow">on hiding information from an oracle</a>, the authors (Abadi, Feigenbaum, and Kilian) wrote:</p>

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

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2012-03-31T18:59:20.193Z
What is the definition of (NP ∩ coNP)/poly? What is a NP ∩ coNP machine?
Henry Yuen
CC BY-SA 3.0
2012-04-02T08:07:13.047Z
@HenryYuen: Maybe the definition of ZPP helps: ZP = RP ∩ CoRP. See http://en.wikipedia.org/wiki/ZPP_(complexity)#Intersection_definition.
Sadeq Dousti
CC BY-SA 3.0
2012-04-02T18:17:05.500Z
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
CC BY-SA 3.0
2012-04-03T00:32:25.500Z
@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?
Sadeq Dousti
CC BY-SA 3.0
2012-04-03T03:21:52.170Z
The reason I ask about the computational model is because I don't know what (NP ∩ coNP)/poly means. NP/poly is the set of languages that are accepted by NP machines with polynomial amount of advice. Presumably, (NP ∩ coNP)/poly is the set of languages accepted by (NP ∩ coNP) machines with polynomial advice -- or is there another definition that isn't machine-definition-dependent?
Henry Yuen
CC BY-SA 3.0
2012-04-03T08:03:45.623Z
@HenryYuen: Oh, I got your point. Strangely, the definition of (NP ∩ coNP)/poly in Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#npiconppoly) does not mention machines with advice, but "languages" with advice. However, quoting from [An Oracle's Builder Toolkit](http://people.cs.uchicago.edu/~fortnow/papers/obt.ps): "NP ∩ coNP is defined by the enumeration $M_1,M_2,\ldots$, where $M_i$ with $i = \langle i_1,i_2 \rangle$ is the pair of non-deterministic oracle Turing machines $N_{i_1}$ and $N_{i_2}$ such that both machines run in time $n^i$..." (Read page 27 for more info)
Sadeq Dousti
CC BY-SA 3.0
2015-04-10T09:18:02.610Z
@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
<cc.complexity-theory><reference-request><complexity-classes><advice-and-nonuniformity>
Intersecting Complexity Classes with Advice
Sadeq Dousti
# Intersecting Complexity Classes with Advice

(Asked by: username_0 on 2011-04-03)

In [on hiding information from an oracle](http://linkinghub.elsevier.com/retrieve/pii/0022000089900184), 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?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, advice-and-nonuniformity

> **Comments:**
> **username_1**: What is the definition of (NP ∩ coNP)/poly? What is a NP ∩ coNP machine?  
> **username_0**: @HenryYuen: Maybe the definition of ZPP helps: ZP = RP ∩ CoRP. See http://en.wikipedia.org/wiki/ZPP_(complexity)#Intersection_definition.  
> **username_1**: 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?  
> **username_0**: @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?  
> **username_1**: The reason I ask about the computational model is because I don't know what (NP ∩ coNP)/poly means. NP/poly is the set of languages that are accepted by NP machines with polynomial amount of advice. Presumably, (NP ∩ coNP)/poly is the set of languages accepted by (NP ∩ coNP) machines with polynomial advice -- or is there another definition that isn't machine-definition-dependent?  
> **username_0**: @HenryYuen: Oh, I got your point. Strangely, the definition of (NP ∩ coNP)/poly in Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#npiconppoly) does not mention machines with advice, but "languages" with advice. However, quoting from [An Oracle's Builder Toolkit](http://people.cs.uchicago.edu/~fortnow/papers/obt.ps): "NP ∩ coNP is defined by the enumeration $M_1,M_2,\ldots$, where $M_i$ with $i = \langle i_1,i_2 \rangle$ is the pair of non-deterministic oracle Turing machines $N_{i_1}$ and $N_{i_2}$ such that both machines run in time $n^i$..." (Read page 27 for more info)  
> **username_2**: @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$.  

---

## 0 answers

