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.
Class of functions computable in nearly linear time n(log n)O(1) on nondeterministic random access machines. Equals NQL [GS89].
Defined in [GS89].
An unfortunate name collision. The class of problems nondeterministically recognized by Kondacs-Watrous Quantum Finite Automata. These are automata that undergo a unitary transformation for each symbol consumed, and are measured after each step to check for acceptance or rejection. The "nondeterminism" refers to the fact that the automaton will accept with positive probability if in the language, or with exactly zero probability otherwise.
Has the same caveats as NQP and EQP because of the exact acceptance probabilities.
Initially studied in <ref>A. Kondacs; J. Watrous. On the power of quantum finite state automata. https://ieeexplore.ieee.org/document/646094</ref>, where they show that it contains all regular languages. In <ref>Abuzer Yakaryılmaz and A.C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081v2</ref> it was shown that this inclusion was strict. Also showed that NQL = S≠
Contrast with QRL, which is a different model of quantum finite automaton, in which measurement only occurs at the end.
Unrelated to the other NQL above.
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].