<p>If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class <span class="math-container">$\textsf{P}^{\textsf{NP}[\log]}$</span>, also known as <span class="math-container">$\Theta_2^{\textsf{P}}$</span>, sits at the top of the Boolean hierarchy <span class="math-container">$\textsf{BH} = \bigcup_k \textsf{BH}_2(k)$</span>, just below <span class="math-container">$\Delta_2^P$</span>. So we have <span class="math-container">$\Theta_2^{\textsf{P}} = \textsf{P}^{\parallel\textsf{NP}} = \textsf{P}^{\textsf{NP}[\log]} = \textsf{BH}$</span>.</p>
<p>I've seen in an answer to <a href="https://cstheory.stackexchange.com/questions/18147/an-analog-of-dp-for-the-second-level-of-the-polynomial-hierarchy/">this question</a> (and in the cited papers) that Boolean Hierarchies have been defined over <span class="math-container">$\Sigma_2^{\textsf{P}}$</span> instead of <span class="math-container">$\textsf{NP}$</span>. So now I am wondering if we have the same relationships higher up as well. Is the following equality known?</p>
<p><span class="math-container">$P^{\parallel\Sigma_i^{\textsf{P}}} = P^{\Sigma_i^{\textsf{P}}[\log]} = \textsf{BH}_{i+1}$</span></p>
<p>Where I used the following notation:</p>
<ul>
<li><span class="math-container">$\textsf{BH}_i = \bigcup_k \textsf{BH}_{i}(k)$</span> where <span class="math-container">$\textsf{BH}_{i+1}(1) = \Sigma_i^{\textsf{P}}$</span> and <span class="math-container">$\textsf{BH}_{i+1}(k+1) =\{L_1 - L_2 \mid L_1 \in \Sigma_i^{\textsf{P}} \text{ and } L_2 \in \textsf{BH}_{i+1}(k)\}$</span>.</li>
<li><span class="math-container">$P^{\Sigma_i^{\textsf{P}}[\log]}$</span> to be the class of problems that can be solved in polynomial time by a deterministic Turing machine making no more than logarithmic oracle queries to a <span class="math-container">$\Sigma_i^{\textsf{P}}$</span> solver.</li>
<li><span class="math-container">$\textsf{P}^{\parallel\Sigma_i^{\textsf{P}}}$</span> is the class of problems that can be solved in <span class="math-container">$\textsf{P}$</span> with parallel (non-adaptive) queries to <span class="math-container">$\Sigma_i^{\textsf{P}}$</span>.</li>
</ul>
<p>Where can I find a definition of the notation <span class="math-container">$\Theta_i^{\textsf{P}}$</span> for <span class="math-container">$i \geq 3$</span>?</p>

CC BY-SA 4.0
2021-02-07T11:38:08.833Z
You must have misread something: BH actually coincides with $\mathrm{P}^{\mathrm{NP}[O(1)]}$, and it is likely a strict subclass of $\Theta^P_2$. The remaining properties indeed relativize to higher levels of the polynomial hierarchy in a straightforward way.
Emil Jeřábek
CC BY-SA 4.0
2021-02-07T11:43:05.867Z
$\Theta^P_k$ is explicitly treated in Wagner, On restricting the access to an NP-oracle, https://doi.org/10.1007/3-540-19488-6_150.
Emil Jeřábek
CC BY-SA 4.0
2021-02-07T12:36:44.267Z
Fair enough, I had misread or drawn the wrong inferences. Thanks for the Wagner reference, it does indeed define $\Theta_{k+1}^{\textsf{P}} = L^{\Sigma_k^{\textsf{P}}}$.  If you turn your comments to a answer, I'll accept it. If you have time, would you mind adding a sentence or two expanding on the relativization argument?
Abdallah
<reference-request><complexity-classes><oracles><polynomial-hierarchy>
Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies
Abdallah
# Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies

(Asked by: username_0 on 2021-02-07)

If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class $\textsf{P}^{\textsf{NP}[\log]}$, also known as $\Theta\_2^{\textsf{P}}$, sits at the top of the Boolean hierarchy $\textsf{BH} = \bigcup\_k \textsf{BH}\_2(k)$, just below $\Delta\_2^P$. So we have $\Theta\_2^{\textsf{P}} = \textsf{P}^{\parallel\textsf{NP}} = \textsf{P}^{\textsf{NP}[\log]} = \textsf{BH}$.

I've seen in an answer to [this question](https://cstheory.stackexchange.com/questions/18147/an-analog-of-dp-for-the-second-level-of-the-polynomial-hierarchy/) (and in the cited papers) that Boolean Hierarchies have been defined over $\Sigma\_2^{\textsf{P}}$ instead of $\textsf{NP}$. So now I am wondering if we have the same relationships higher up as well. Is the following equality known?

$P^{\parallel\Sigma\_i^{\textsf{P}}} = P^{\Sigma\_i^{\textsf{P}}[\log]} = \textsf{BH}\_{i+1}$

Where I used the following notation:

* $\textsf{BH}\_i = \bigcup\_k \textsf{BH}\_{i}(k)$ where $\textsf{BH}\_{i+1}(1) = \Sigma\_i^{\textsf{P}}$ and $\textsf{BH}\_{i+1}(k+1) =\{L\_1 - L\_2 \mid L\_1 \in \Sigma\_i^{\textsf{P}} \text{ and } L\_2 \in \textsf{BH}\_{i+1}(k)\}$.
* $P^{\Sigma\_i^{\textsf{P}}[\log]}$ to be the class of problems that can be solved in polynomial time by a deterministic Turing machine making no more than logarithmic oracle queries to a $\Sigma\_i^{\textsf{P}}$ solver.
* $\textsf{P}^{\parallel\Sigma\_i^{\textsf{P}}}$ is the class of problems that can be solved in $\textsf{P}$ with parallel (non-adaptive) queries to $\Sigma\_i^{\textsf{P}}$.

Where can I find a definition of the notation $\Theta\_i^{\textsf{P}}$ for $i \geq 3$?

**Tags:** reference-request, complexity-classes, oracles, polynomial-hierarchy
> **Comments:**
> **username_1**: You must have misread something: BH actually coincides with $\mathrm{P}^{\mathrm{NP}[O(1)]}$, and it is likely a strict subclass of $\Theta^P_2$. The remaining properties indeed relativize to higher levels of the polynomial hierarchy in a straightforward way.  
> **username_1**: $\Theta^P_k$ is explicitly treated in Wagner, On restricting the access to an NP-oracle, https://doi.org/10.1007/3-540-19488-6_150.  
> **username_0**: Fair enough, I had misread or drawn the wrong inferences. Thanks for the Wagner reference, it does indeed define $\Theta_{k+1}^{\textsf{P}} = L^{\Sigma_k^{\textsf{P}}}$.  If you turn your comments to a answer, I'll accept it. If you have time, would you mind adding a sentence or two expanding on the relativization argument?  

---

## 0 answers

