Class Description

βP: Limited-Nondeterminism NP

β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.

Linked From

LOGNP: Logarithmically-Restricted NP

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).

More about...


Σ2P: NP With NP Oracle

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].

More about...