The class of problems that can be decided in quasi-linear time by a multitape deterministic Turing machine. Quasi-linear time here means n(log n)k + k, for some k.
Defined in [Sch78].
Class of functions computable in nearly linear time n(log n)O(1) on deterministic random access machines.
Defined in [GS89].
See also QL.
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].
Unrelated to the other NQL below.