<p>I have 2 type of decision problems: either in <span class="math-container">$\mathsf{BPP}$</span> or in <span class="math-container">$\mathsf{NP}$</span>; and I want to decide fixed Boolean combinations of them. Since <span class="math-container">$\mathsf{BPP}$</span> is closed under Boolean combinations and Boolean combinations of <span class="math-container">$\mathsf{NP}$</span> problems yield the definition of <span class="math-container">$\mathsf{BH}$</span>, I am looking for the smallest class containing <span class="math-container">$\mathsf{BPP} \cup \mathsf{BH}$</span> and closed under fixed Boolean combinations. A possible definition for such class <span class="math-container">$C$</span> could be:</p>
<ul>
<li><span class="math-container">$L \in \mathsf{BPP} \cup \mathsf{BH}$</span>, then <span class="math-container">$L \in C$</span></li>
<li><span class="math-container">$L_1, L_2 \in C$</span>, then <span class="math-container">$L_1 \wedge L_2 \in C$</span> and <span class="math-container">$L_1 \vee L_2 \in C$</span></li>
</ul>
<p>Studying subset relations in the Complexity Zoo I have found that:</p>
<ul>
<li><p><span class="math-container">$C \subseteq S_2^{\mathsf{P}}$</span>, <span class="math-container">$C \subseteq \mathsf{P}^{QMA}$</span>, <span class="math-container">$C \subseteq \mathsf{BPP}_{path}$</span></p>
</li>
<li><p><span class="math-container">$\mathsf{P}^{\mathsf{NP}[log]} \subseteq S_2^{\mathsf{P}}$</span>, <span class="math-container">$\mathsf{P}^{\mathsf{NP}[log]} \subseteq \mathsf{P}^{QMA}$</span>, <span class="math-container">$\mathsf{P}^{\mathsf{NP}[log]} \subseteq \mathsf{BPP}_{path}$</span>.</p>
</li>
</ul>
<p>But I think <span class="math-container">$\mathsf{P}^{\mathsf{NP}[log]} \not \subseteq C$</span> holds, so It would be interesting to find a similar class to <span class="math-container">$C$</span>.</p>
<p>Also, <span class="math-container">$C$</span> should be subset of something like <span class="math-container">$\mathsf{BPP}^{\mathsf{NP}[1]}$</span> (a candidate for <span class="math-container">$C$</span>) or something like <span class="math-container">$\mathsf{P}^{\mathsf{NP}\cup\mathsf{BPP}}$</span>.
It is worth mentioning that my problems in <span class="math-container">$\mathsf{BPP}$</span> are polynomial size Boolean combinations of problems in <span class="math-container">$\mathsf{RP}$</span>, so my original problem is also contained in <span class="math-container">$\mathsf{P}^{\mathsf{NP}}$</span>. But the idea of <span class="math-container">$C$</span> is that it is more tracktable than <span class="math-container">$\mathsf{P}^{\mathsf{NP}}$</span>, because I have to solve a fixed amount of <span class="math-container">$\mathsf{NP}$</span> problems and a polynomial amount of them that I can approximate in polynomial time.</p>

CC BY-SA 4.0
2024-04-04T07:39:58.550Z
There clear *is* such a class: you just defined it. But I haven’t seen this in the literature. In terms of common classes, you probably won’t get better upper bounds than what you already discovered.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T14:40:31.443Z
In the final para, when you write $\mathsf{BPP}^{\mathsf{NP}[1]}$ do you mean just *one* query to the oracle (the usual meaning of that notation, e.g. https://doi.org/10.1006/jcss.1999.1647), or did you want to write something like $\mathsf{BPP}^{\mathsf{NP}[O(1)]}$? Also, $D=\mathsf{P}^{\mathsf{NP} \cup \mathsf{BPP}}$ usually means $L \in D$ iff there exists $L' \in \mathsf{NP} \cup \mathsf{BPP}$ such that $L \in \mathsf{P}^{L'}$. I think you meant more like $\mathsf{P}^{\mathsf{NP} \oplus \mathsf{BPP}}$ (meaning the tagged disjoint union / pairing operation on languages).
Joshua Grochow
CC BY-SA 4.0
2024-04-04T14:42:22.433Z
And actually, even with just one query, I think maybe your class is incomparable to $\mathsf{BPP}^{\mathsf{NP}[1]}$...since that class contains $\mathsf{MA}$, but it doesn't look to me like your class contains $\mathsf{MA}$.
Joshua Grochow
CC BY-SA 4.0
2024-04-04T18:11:33.763Z
Yes I meant $\mathsf{BPP}^{\mathsf{NP}[O(1)]}$. As for the second class $D$, I meant that if a TM had 2 oracle tapes (one for $\mathsf{BPP}$ and one for $\mathsf{NP}$) I could resolve the problem generating a fixed-size truth table that maps a fixed amount of nonadaptive queries (to those oracles) to the correct output. Since in $\mathsf{BPP}^{\mathsf{NP}[O(1)]}$ I could solve a polynomial amount of $\mathsf{BPP}$ problems, seems like a subset could be enough (the $C$ class).
DiegoEmilio
CC BY-SA 4.0
2024-04-05T15:01:06.167Z
Oh sorry, I shouldn't have said incomparable. I just meant that $\mathsf{BPP}^{\mathsf{NP}[1]}$ already seems to strictly contain your class since it contains MA but your class doesn't seem to. For the class D, what you describe is equivalent to $\mathsf{P}^{\mathsf{NP} \oplus \mathsf{BPP}}$ (but not to $\mathsf{P}^{\mathsf{NP} \cup \mathsf{BPP}}$, which is equal to $\mathsf{P}^{\mathsf{NP}} \cup \mathsf{P}^\mathsf{BPP} = \mathsf{P}^{\mathsf{NP}} \cup \mathsf{BPP}$, essentially by definition).
Joshua Grochow
CC BY-SA 4.0
2024-04-05T17:07:41.743Z
Thanks! Do you have any reference for MA in relation with some of this classes? I think since MA does not contain $\mathsf{BH}$, $C \subseteq MA$ should not hold. I think $\mathsf{BPP}^{\mathsf{NP}[O(1)]}$ is indeed a good upperbound for $C$.
DiegoEmilio
CC BY-SA 4.0
2024-04-05T17:10:08.860Z
I am thinking $L \in \mathsf{BH}^{\mathsf{NP}[O(1)]}$ iff there exists a polynomial time randomized algorithm $M$ with input $x$ and coin toss $s \in \{0,1\}^{poly(|x|)}$, and a language $L' \in \mathsf{NP}$ such that:

1) $M$ produces $q \in O(1)$ nonadaptive query strings $(z_1, ..., z_q)$ and a truth table $t: \{0,1\}^{q} \to \{0,1\}$ such that $M(x) = t(L'(z_1), ..., L'(z_q))$.

2) $M(x) = L(x)$ with a probability of at least $\frac{2}{3}$ over all $s$.
DiegoEmilio
<cc.complexity-theory><complexity-classes><oracles>
Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?
DiegoEmilio
# Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

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

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and Boolean combinations of $\mathsf{NP}$ problems yield the definition of $\mathsf{BH}$, I am looking for the smallest class containing $\mathsf{BPP} \cup \mathsf{BH}$ and closed under fixed Boolean combinations. A possible definition for such class $C$ could be:

* $L \in \mathsf{BPP} \cup \mathsf{BH}$, then $L \in C$
* $L\_1, L\_2 \in C$, then $L\_1 \wedge L\_2 \in C$ and $L\_1 \vee L\_2 \in C$

Studying subset relations in the Complexity Zoo I have found that:

* $C \subseteq S\_2^{\mathsf{P}}$, $C \subseteq \mathsf{P}^{QMA}$, $C \subseteq \mathsf{BPP}\_{path}$
* $\mathsf{P}^{\mathsf{NP}[log]} \subseteq S\_2^{\mathsf{P}}$, $\mathsf{P}^{\mathsf{NP}[log]} \subseteq \mathsf{P}^{QMA}$, $\mathsf{P}^{\mathsf{NP}[log]} \subseteq \mathsf{BPP}\_{path}$.

But I think $\mathsf{P}^{\mathsf{NP}[log]} \not \subseteq C$ holds, so It would be interesting to find a similar class to $C$.

Also, $C$ should be subset of something like $\mathsf{BPP}^{\mathsf{NP}[1]}$ (a candidate for $C$) or something like $\mathsf{P}^{\mathsf{NP}\cup\mathsf{BPP}}$.
It is worth mentioning that my problems in $\mathsf{BPP}$ are polynomial size Boolean combinations of problems in $\mathsf{RP}$, so my original problem is also contained in $\mathsf{P}^{\mathsf{NP}}$. But the idea of $C$ is that it is more tracktable than $\mathsf{P}^{\mathsf{NP}}$, because I have to solve a fixed amount of $\mathsf{NP}$ problems and a polynomial amount of them that I can approximate in polynomial time.

**Tags:** cc.complexity-theory, complexity-classes, oracles
> **Comments:**
> **username_1**: There clear *is* such a class: you just defined it. But I haven’t seen this in the literature. In terms of common classes, you probably won’t get better upper bounds than what you already discovered.  
> **username_2**: In the final para, when you write $\mathsf{BPP}^{\mathsf{NP}[1]}$ do you mean just *one* query to the oracle (the usual meaning of that notation, e.g. https://doi.org/10.1006/jcss.1999.1647), or did you want to write something like $\mathsf{BPP}^{\mathsf{NP}[O(1)]}$? Also, $D=\mathsf{P}^{\mathsf{NP} \cup \mathsf{BPP}}$ usually means $L \in D$ iff there exists $L' \in \mathsf{NP} \cup \mathsf{BPP}$ such that $L \in \mathsf{P}^{L'}$. I think you meant more like $\mathsf{P}^{\mathsf{NP} \oplus \mathsf{BPP}}$ (meaning the tagged disjoint union / pairing operation on languages).  
> **username_2**: And actually, even with just one query, I think maybe your class is incomparable to $\mathsf{BPP}^{\mathsf{NP}[1]}$...since that class contains $\mathsf{MA}$, but it doesn't look to me like your class contains $\mathsf{MA}$.  
> **username_0**: Yes I meant $\mathsf{BPP}^{\mathsf{NP}[O(1)]}$. As for the second class $D$, I meant that if a TM had 2 oracle tapes (one for $\mathsf{BPP}$ and one for $\mathsf{NP}$) I could resolve the problem generating a fixed-size truth table that maps a fixed amount of nonadaptive queries (to those oracles) to the correct output. Since in $\mathsf{BPP}^{\mathsf{NP}[O(1)]}$ I could solve a polynomial amount of $\mathsf{BPP}$ problems, seems like a subset could be enough (the $C$ class).  
> **username_2**: Oh sorry, I shouldn't have said incomparable. I just meant that $\mathsf{BPP}^{\mathsf{NP}[1]}$ already seems to strictly contain your class since it contains MA but your class doesn't seem to. For the class D, what you describe is equivalent to $\mathsf{P}^{\mathsf{NP} \oplus \mathsf{BPP}}$ (but not to $\mathsf{P}^{\mathsf{NP} \cup \mathsf{BPP}}$, which is equal to $\mathsf{P}^{\mathsf{NP}} \cup \mathsf{P}^\mathsf{BPP} = \mathsf{P}^{\mathsf{NP}} \cup \mathsf{BPP}$, essentially by definition).  
> **username_0**: Thanks! Do you have any reference for MA in relation with some of this classes? I think since MA does not contain $\mathsf{BH}$, $C \subseteq MA$ should not hold. I think $\mathsf{BPP}^{\mathsf{NP}[O(1)]}$ is indeed a good upperbound for $C$.  
> **username_0**: I am thinking $L \in \mathsf{BH}^{\mathsf{NP}[O(1)]}$ iff there exists a polynomial time randomized algorithm $M$ with input $x$ and coin toss $s \in \{0,1\}^{poly(|x|)}$, and a language $L' \in \mathsf{NP}$ such that:  1) $M$ produces $q \in O(1)$ nonadaptive query strings $(z_1, ..., z_q)$ and a truth table $t: \{0,1\}^{q} \to \{0,1\}$ such that $M(x) = t(L'(z_1), ..., L'(z_q))$.  2) $M(x) = L(x)$ with a probability of at least $\frac{2}{3}$ over all $s$.  

---

## 0 answers

