Class Description

P-Close: Problems Close to P

The class of decision problems solvable by a polynomial-time algorithm that outputs the wrong answer on only a sparse (that is, polynomially-bounded) set of instances.

Defined in [Yes83].

Contains Almost-P and is contained in P/poly [Sch86].

Linked From

No class.