3
$\begingroup$

Some of the better known complexity classes: PP, NP, P... are closed under intersection and union. What are some counter-examples? Is there a natural reason for the common complexity classes to be closed under these operations?

$\endgroup$
  • 2
    $\begingroup$ Subsets is waaay too permissive. Note that for a given infinite language, say SAT, it has uncountably many subsets, so most of its subsets aren't even computable! Considering intersection guarantees you are intersecting two sets where you have control over both of them. $\endgroup$ – Joshua Grochow Oct 30 at 5:37
  • 5
    $\begingroup$ The classes you mention all have nice machine models, and (almost equivalently) all have complete problems. Most classes w/ a natural machine model will allow you to combine two such machines with AND or OR, leading to closure under intersection/union. This suggests looking to semantic classes for counterexamples. E.g. UP is closed under intersection, but I'm not sure it's closed under union. $\endgroup$ – Joshua Grochow Oct 30 at 5:39
  • 1
    $\begingroup$ Just to add to the discussion, we have to differentiate between finite and infinite union/intersection since most classes are not closed under the infinite variant $\endgroup$ – Daniel Oct 30 at 19:30
  • 2
    $\begingroup$ The levels $\mathrm{BH}_k$ of the Boolean hierarchy are closed under neither intersections nor unions for $k\ge3$. $\endgroup$ – Emil Jeřábek supports Monica Oct 31 at 6:43
  • 1
    $\begingroup$ @EmilJeřábek: Nice example! (I think what you say is true precisely if BH doesn't collapse. But if BH collapses then PH collapses, so I'm happy to use this assumption...) $\endgroup$ – Joshua Grochow Oct 31 at 15:41
1
$\begingroup$
  • The class $AWPP$ is not known to be closed under union, though it is easy to show it is closed under intersection
  • For the class $A_0PP$ it's the other way around: it is closed under intersection, but not known to be closed under union.

These classes have nice machine model definitions, namely they are something akin to an abstract version of the quantum complexity classes $BQP$ and $QMA$, respectively. These classes, in turn, are the quantum analogues of $P$ and $NP$, respectively. Let me give the definition (The Zoo) of $AWPP$:

Definition$^{(\ast)}$ (AWPP) A language $L\subseteq \{0,1\}^\ast$ is in $AWPP$ when there is a Gap function $g\colon \{0,1\}^\ast\to \mathbb{Z}$ satisfying the following Soundness and Completeness properties for a polynomial $p(x)$ and a polynomial-time computable function $f(x)$:

  1. Soundness If $x\not\in L$ then $0\leq g(x)\leq 2^{-p(x)}f(x)$
  2. Completeness If $x\in L$ then $(1-2^{-p(x)})f(x)\leq g(x)\leq f(x)$

These soundness and completeness conditions are precisely what you get if you were to (1) trace through the definition of $BQP$ using only the Hadamard gate and classical gates and then (2) interpret the acceptance probabilities as "paths", and then (3) impose that there is a large gap in acceptance probabilities depending on whether $x\in L$ or not.

It is interesting that this is not known, because both $BQP$ and $QMA$ are known to be closed under intersection and union. As far as I know, there have been no publications exploring the closure properties of these classes; perhaps they are a bit niche, or perhaps I am simply ignorant.

Of course it is also unknown whether $AWPP$ and $A_0PP$ are closed under complement, because this would imply the other closures as well; the converse does not hold; they may be closed under union and intersection but not complement, like $NP$ probably is.

$^{(\ast)}$In this definition, the polynomial $p(x)$ can be replaced by a polynomial $p^\prime(n)$ which depends only on $n=|x|$ the length of the string; similarly the function $f(x)$ can also be replaced by such a polynomial $f^\prime(n)$. This may make certain things easier to prove.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.