Class Description

NNLT: Nondeterministic Nearly Linear Time

Class of functions computable in nearly linear time n(log n)^O(1) on nondeterministic random access machines. Equals NQL [GS89].

Defined in [GS89].

Linked From

NQL: Nondet Quasi-Linear

The class of problems that can be decided in quasi-linear time by a multitape nondeterministic Turing machine. Quasi-linear here means n(log n)^k + k, for some k.

Equals NNLT.

SAT is NQL-complete under quasi-linear-time reductions (which can be computed in deterministic quasi-linear time) [Sch78].

Defined in [Sch78].

See also: NLT, Q, QL.

Unrelated to the other NQL below.

More about...