|
|
|
|
|
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. 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 ; 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, . Another important problem is whether . 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 is an open problem. The related class of function problems is FP. References Papadimitriou, Computational Complexity Theory
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|