Class Description

QPLIN: Linear Quasipolynomial-Time

Equals DTIME(n^{O(log n)}).

Has the same relationship to QP that E does to EXP.

Linked From

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

More about...