P (complexity)

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, or polynomial 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 <math>P \subseteq NP<math>. One of the largest open problems currently in theoretical computer science has to do with whether <math>P = NP<math>; 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, <math>L \subseteq P<math>. Another important problem is whether <math>L = P<math>. 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 <math>P = PSPACE<math> is an open problem.

The related class of function problems is FP.

References

Papadimitriou, Computational Complexity Theory