Class Description

QL: Quasi-Linear

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

See also: Q, NQL.

Linked From

NLT: Nearly Linear Time

Class of functions computable in nearly linear time n(log n)^O(1) on deterministic random access machines.

Defined in [GS89].

See also QL.

More about...

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