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).
β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
LOGSNP0 is the subclass in which φ is a first-order predicate without quantifiers and x is a bounded lists of indices of input bits. LOGSNP is also the closure of LOGSNP0 under polynomial-time many-one reductions. See LOGNP and SNP for the motivation.
Defined in [PY96].
Contained in LOGNP, and therefore QPLIN.
If P = LOGSNP, then for every constructible f(n) > n, NTIME(f(n)) is contained in DTIME(g(n)sqrt(g(n))), where g(n) = O(f(n) logf(n)) [FK97].