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 2O(log n)=nO(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.
Papadimitriou, Computational Complexity Theory
|Important complexity classes (more)|
|P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NC | P-C|
|PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH|