15
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ What is the definition of (NP ∩ coNP)/poly? What is a NP ∩ coNP machine? $\endgroup$
    – Henry Yuen
    Mar 31, 2012 at 18:59
  • $\begingroup$ @HenryYuen: Maybe the definition of ZPP helps: ZP = RP ∩ CoRP. See en.wikipedia.org/wiki/ZPP_(complexity)#Intersection_definition. $\endgroup$
    – Sadeq Dousti
    Apr 2, 2012 at 8:07
  • $\begingroup$ 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? $\endgroup$
    – Henry Yuen
    Apr 2, 2012 at 18:17
  • $\begingroup$ @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? $\endgroup$
    – Sadeq Dousti
    Apr 3, 2012 at 0:32
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Vanessa
    Apr 10, 2015 at 9:18

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.