P (complexity)

Definition

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

Related concepts

2-EXPTIME 2-satisfiability AC0 ACC0 ALL (complexity)APX Advice (complexity)Alan Cobham (mathematician)Alternating Turing machine Arithmetical hierarchy Arthur–Merlin protocol BPP (complexity)BQP Boolean circuit Boolean hierarchy CC (complexity)Charles E. Leiserson Christos Papadimitriou Circuit complexity Clifford Stein Co-NP Co-NP-complete Cobham's thesis Complement (complexity)Complexity Zoo Complexity class Computation time Computational complexity theory Concatenation DLOGTIME DSPACE DTIME Decision problem Descriptive complexity Deterministic Turing machine Dexter Kozen ELEMENTARY EXPSPACE EXPTIME Exponential hierarchy FL (complexity)FNP (complexity)FO(LFP)FP (complexity)First-order logic Forbidden minor Formal language Function problem Grzegorczyk hierarchy Henry Cabourn Pocklington Homomorphism IP (complexity)Implicit computational complexity Ingo Wegener Interactive proof system Intersection (set theory)Introduction to Algorithms Jack Edmonds Jeffrey Ullman Jin-Yi Cai John Hopcroft Journal of Computer and System Sciences Kleene closure L (complexity)Larry Stockmeyer Least fixed point Linear programming List of complexity classes Logarithm Low (complexity)Manindra Agrawal Mathematical Proceedings of the Cambridge Philosophical Society Maximum matching Memory space (computational resource)Michael O. Rabin Michael Sipser Mitsunori Ogihara Moshe Vardi NC (complexity)NEXPTIME NL-complete NL (complexity)NONELEMENTARY NP-completeness NP-hardness NP (complexity)NSPACE NTIME Neil Immerman Non-deterministic Turing machine Nonconstructive proof P-complete P/poly PH (complexity)PP (complexity)PR (complexity)PSPACE PSPACE-complete P versus NP problem Parity P PolyL Polynomial Polynomial hierarchy Polynomial time Prime number Probabilistically checkable proof QMA Quasi-polynomial time RE (complexity)RL (complexity)RP (complexity)R (complexity)Rajeev Motwani Random access Range concatenation grammars Reachability Richard Johnsonbaugh Robertson–Seymour theorem Ron Rivest Rule of thumb SC (complexity)SL (complexity)Savitch's theorem Sparse language St-connectivity Stanford Encyclopedia of Philosophy Stephen Cook TC0 TC (complexity)TFNP Theoretical Computer Science (journal)Thomas H. Cormen Tractable problem UP (complexity)Undecidable problem Union (set theory)Yehoshua Bar-Hillel ZPP (complexity)♯P ♯P-complete

14 concepts already in your glossary