Class Description

LOGSNP: Logarithmically-Restricted SNP

The class of decision problems expressible in logical form as

The set of I for which there exists a subset S={s₁,...,s_{log n}} of {1,...,n} of size log n, such that for all x there exists j in S such that the predicate φ(I,s_j,x,j) holds. Here x is a logarithmic-length string, or equivalently a polynomially bounded number, and φ is computable in P.

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

Linked From

βP: Limited-Nondeterminism NP

β_kP is the class of decision problems solvable by a polynomial-time Turing machine that makes O(log^kn) nondeterministic transitions, with the same acceptance mechanism as NP. Equivalently, the machine receives a purported proof of size O(log^kn) 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].

β₂P contains LOGNP and LOGSNP.

More about...

LOGNP: Logarithmically-Restricted NP

The class of decision problems expressible in logical form as

The set of I for which there exists a subset S={s₁,...,s_{log n}} of {1,...,n} of size log n, such that for all x there exists y such that for all j in S, the predicate φ(I,s_j,x,y,j) holds. Here x and y are logarithmic-length strings, or equivalently polynomially bounded numbers, and φ is computable in P.

LOGNP₀ 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 LOGNP₀ under polynomial-time many-one reductions.

The motivation is that the analogue of LOGNP₀ 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:

Vapnik-Chervonenkis (V-C) Dimension. Given a family F of subsets of a set U, find a subset of S of U of maximum cardinality, such that every subset of S can be written as the intersection of S with some set in F.

Contains LOGSNP, and is contained in βP (indeed β₂P).

More about...