Any of a set of computational problems with the same bounds (Θ(n)) on time and space, for deterministic and nondeterministic machines.