2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Feb 7, 2021 at 11:38
  • 3
    $\begingroup$ $\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. $\endgroup$
    – Emil Jeřábek
    Commented Feb 7, 2021 at 11:43
  • 1
    $\begingroup$ 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? $\endgroup$
    – Abdallah
    Commented Feb 7, 2021 at 12:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.