Polynomial-Time

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

See the complexity zoo entry here.

Known relationships