Class Description

RPP: Restricted Pseudo Polynomial-Time

The class of decision problems (x,m) (where x is an input of length |x|=n and m is an integer parameter), that are solvable by a nondeterministic (i.e. NP) machine in poly(n+m) time and O(m+log n) space simultaneously.

Defined in [Mon80].

See also FPT.

Linked From

No class.