# Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies

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 (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$$?

• 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. Feb 7, 2021 at 11:38
• $\Theta^P_k$ is explicitly treated in Wagner, On restricting the access to an NP-oracle, doi.org/10.1007/3-540-19488-6_150. Feb 7, 2021 at 11:43
• 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? Feb 7, 2021 at 12:36