Class Description

LIN: Linear Time

The class of decision problems solvable by a deterministic Turing machine in linear time.

Strictly Contained in NLIN. [PPS+83].

Linked From

NLIN: Nondeterministic LIN

Has the same relation to LIN as NP does to P.

More about...