Class Description

Q: Quasi-Realtime Languages

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.

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


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.

More about...