The class of problems solvable by a nondeterministic multitape Turing machine in linear time. Defined in [BG69], where it was shown that Q equals the class of problems solvable by a nondeterministic multitape Turing machine in exactly n steps (as opposed to O(n) steps).
Contains GCSL.
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.
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].