15

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?

R B
  • 9,448
  • 5
  • 34
  • 74
Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
  • 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 http://en.wikipedia.org/wiki/ZPP_(complexity)#Intersection_definition. – Sadeq Dousti Apr 02 '12 at 08: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 02 '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? – Sadeq Dousti Apr 03 '12 at 00:32
  • 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 Apr 03 '12 at 03:21
  • @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: "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 Apr 03 '12 at 08:03
  • 1
    @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 09:18

0 Answers0