Complexity Class Θ2P\Theta_2^{\mathsf{P}}

The decision problems decidable by a deterministic polynomial-time algorithm that may make O(log⁡∣x∣)O(\log |x|) calls to an NP\mathsf{NP} oracle, written Θ2P=PNP[log⁡]\Theta_2^{\mathsf{P}} = \mathsf{P}^{\mathsf{NP}}[\log]. Equivalently, the algorithm may make polynomially many non-adaptive oracle calls, all evaluated in parallel; the class is then also written P∥NP\mathsf{P}^{\mathsf{NP}}_{\parallel}.

Further reading

  • (Wagner, 1990): characterises the class in several equivalent ways and names it.
  • (Hemachandra, 1989): shows the equivalence with polynomially many non-adaptive calls.
  • (Buss & Hay, 1991): proves the same equivalence independently.

Reference

Eiter, T. & Gottlob, G. (1997). The Complexity Class Θ₂ᵖ: Recent Results and Applications in AI and Modal Logic. In: Fundamentals of Computation Theory (FCT 1997), LNCS 1279, pp. 1–18. Springer.