βkP is the class of decision problems solvable by a polynomial-time Turing machine that makes O(logkn) nondeterministic transitions, with the same acceptance mechanism as NP. Equivalently, the machine receives a purported proof of size O(logkn) that the answer is 'yes.'
Then βP is the union of βkP over all constant k.
Defined in [KF84]. See also the survey [GLM96].
There exist oracles relative to which basically any consistent inclusion structure among the βkP's can be realized [BG98].
β2P contains LOGNP and LOGSNP.
The class of decision problems expressible in logical form as
LOGNP0 is the subclass in which φ is a first-order predicate without quantifiers and x and y are bounded lists of indices of input bits. LOGNP is also the closure of LOGNP0 under polynomial-time many-one reductions.
The motivation is that the analogue of LOGNP0 without the logarithmic bound on |S| is SO-E, which by Fagin's theorem equals NP [Fag74].
Defined in [PY96], where it was also shown that the following problem is complete for LOGNP under many-one reductions:
Contains LOGSNP, and is contained in βP (indeed β2P).
Contains languages whose complements are in Π2P.
Along with Π2P, comprises the second level of PH, the polynomial hierarchy.
Note that this is equal to NP with a coNP oracle.
[Uma98] has shown that the following problems are complete for Σ2P:
The problem of deciding if a perfect graph is 2-clique-colorable (defined in [FMF16]) has been shown to be complete for Σ2P.
For any fixed k, there is a problem in Σ2P ∩ Π2P that cannot be solved by circuits of size nk [Kan82].