Class Description

NLIN: Nondeterministic LIN

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

Linked From

LIN: Linear Time

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

Strictly Contained in NLIN. [PPS+83].

More about...