In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time . This is often taken to be the class of computational problems which is "efficient" or "tractable".

A generalization of P is NP, which is the class of languages decidable in polynomial time on a nondeterministic Turing machine. We then trivially have . One of the largest open problems currently in theoretical computer science has to do with whether P = NP; see Complexity classes P and NP.

P is known to contain many natural problems, including linear programming and calculating the greatest common divisor. P is also known to be at least as large as L, the class of problems decidable in a logarithmic amount of memory space. A decider using O(log n) space cannot use more than 2^{O(log n)}=n^O(1) time, because this is the total number of possible configurations; thus, . Another important problem is whether L = P. We do know that P = ALOGSPACE , the set of problems solvable in logarithmic memory by alternating Turing machines.

P is also known to be no larger than PSPACE, the class of problems decidable in polynomial space. Again, whether P = PSPACE is an open problem.

The related class of function problems is FP.

References

Papadimitriou, Computational Complexity Theory