<ul>
<li>The class <span class="math-container">$AWPP$</span> is not known to be closed under union, though it is easy to show it is closed under intersection</li>
<li>For the class <span class="math-container">$A_0PP$</span> it's the other way around: it is closed under intersection, but not known to be closed under union.</li>
</ul>

<p>These classes have nice machine model definitions, namely they are something akin to an abstract version of the quantum complexity classes <span class="math-container">$BQP$</span> and <span class="math-container">$QMA$</span>, respectively. These classes, in turn, are the quantum analogues of <span class="math-container">$P$</span> and <span class="math-container">$NP$</span>, respectively. Let me give <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#awpp" rel="nofollow noreferrer">the definition (The Zoo)</a> of <span class="math-container">$AWPP$</span>:</p>

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

<ol>
<li><strong>Soundness</strong> If <span class="math-container">$x\not\in L$</span> then <span class="math-container">$0\leq g(x)\leq 2^{-p(x)}f(x)$</span></li>
<li><strong>Completeness</strong> If <span class="math-container">$x\in L$</span> then <span class="math-container">$(1-2^{-p(x)})f(x)\leq g(x)\leq f(x)$</span></li>
</ol>

<p>These soundness and completeness conditions are precisely what you get if you were to (1) trace through the definition of <span class="math-container">$BQP$</span> 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 <span class="math-container">$x\in L$</span> or not.</p>

<p>It is interesting that this is not known, because both <span class="math-container">$BQP$</span> and <span class="math-container">$QMA$</span> 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.</p>

<p>Of course it is also unknown whether <span class="math-container">$AWPP$</span> and <span class="math-container">$A_0PP$</span> 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 <span class="math-container">$NP$</span> probably is.</p>

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

CC BY-SA 4.0
2019-11-09T12:29:25.783Z
2019-11-12T18:40:35.367Z
2019-11-12T18:40:35.367Z
Lieuwe Vinkhuijzen
<p>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?</p>

CC BY-SA 4.0
2019-10-30T05:37:57.357Z
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.
Joshua Grochow
CC BY-SA 4.0
2019-10-30T05:39:49.727Z
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.
Joshua Grochow
CC BY-SA 4.0
2019-10-30T19:30:43.047Z
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
Daniel
CC BY-SA 4.0
2019-10-31T06:43:52.933Z
The levels $\mathrm{BH}_k$ of the Boolean hierarchy are closed under neither intersections nor unions for $k\ge3$.
Emil Jeřábek
CC BY-SA 4.0
2019-10-31T14:33:48.977Z
@JoshuaGrochow is there a chance that "have nice machine model" is equivalent to closed under intersection and union? Is there a formal definition for "nice machine"?
DeeDee
CC BY-SA 4.0
2019-10-31T15:41:32.113Z
@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...)
Joshua Grochow
CC BY-SA 4.0
2019-10-31T15:53:32.870Z
@Ringminustwo: I meant "nice [machine model]" not "[nice machine] model" :). "Nice" is always hard to formalize; I can't find the reference I'm thinking of now, but I think there's a paper of Kozen, or Regan, or Mehlhorn, or Sipser, or ??? which talks about a nice kind of machine model (aka indexing) such that a class has such an indexing iff it has a complete problem. The easy direction is: given a complete problem $L$ under $\leq_m^p$, you get an indexing of the class by using an indexing of all poly-time machines to index the possible reductions from $L$.
Joshua Grochow
CC BY-SA 4.0
2019-10-31T16:18:25.357Z
@JoshuaGrochow Yes, I meant that it holds unless the BH (and PH) collapses, sorry for the imprecision.
Emil Jeřábek
CC BY-SA 4.0
2020-04-28T21:34:15.883Z
@Daniel i know not closed under inf union (singleton languages via infinite union can generate any language) but inf intersection? why not closed under inf version of intersection?
DeeDee
<cc.complexity-theory>
Complexity classes not closed under intersection and union
DeeDee
# Complexity classes not closed under intersection and union

(Asked by: username_0 on 2019-10-29)

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?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_2**: 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  
> **username_3**: The levels $\mathrm{BH}_k$ of the Boolean hierarchy are closed under neither intersections nor unions for $k\ge3$.  
> **username_0**: @JoshuaGrochow is there a chance that "have nice machine model" is equivalent to closed under intersection and union? Is there a formal definition for "nice machine"?  
> **username_1**: @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...)  
> **username_1**: @Ringminustwo: I meant "nice [machine model]" not "[nice machine] model" :). "Nice" is always hard to formalize; I can't find the reference I'm thinking of now, but I think there's a paper of Kozen, or Regan, or Mehlhorn, or Sipser, or ??? which talks about a nice kind of machine model (aka indexing) such that a class has such an indexing iff it has a complete problem. The easy direction is: given a complete problem $L$ under $\leq_m^p$, you get an indexing of the class by using an indexing of all poly-time machines to index the possible reductions from $L$.  
> **username_3**: @JoshuaGrochow Yes, I meant that it holds unless the BH (and PH) collapses, sorry for the imprecision.  
> **username_0**: @Daniel i know not closed under inf union (singleton languages via infinite union can generate any language) but inf intersection? why not closed under inf version of intersection?  

---

## 1 answers

### Answer by username_4 on 2019-11-09. Score: 2

* 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)](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:A#awpp) 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.


---

