Is P the ultimate definition of efficiency, or just a useful rule of thumb?
In short: In computer science, P represents problems solvable in polynomial time. While often equated with tractability via Cobham's thesis, this classification is more of a practical guide than a perfect rule. Some problems outside P are manageable, while some within it are not, revealing the nuance behind computational complexity.
At its core, P—or PTIME—defines decision problems solvable by a deterministic Turing machine within polynomial time. This class is remarkably robust, remaining consistent whether viewed through Turing machines, uniform Boolean circuits, or descriptive complexity logic. It is closed under various operations, including composition, meaning complex algorithms built from polynomial-time components remain efficient. This machine-independence is why P is considered a foundational concept in the field.
The origins of this classification date back to the mid-1960s, with Alan Cobham, Jack Edmonds, and Michael Rabin independently formalizing the notion of polynomial time. However, the distinction between polynomial and exponential growth was noted as early as 1910 by H. C. Pocklington, who contrasted algorithms based on logarithmic versus linear scales. Today, P serves as a critical benchmark in the hierarchy of complexity, sitting between logarithmic space (L) and exponential time (EXPTIME).
Despite its importance, P remains surrounded by major open questions. While we know P is strictly contained in EXPTIME, the relationship between P and other classes like NP, PSPACE, and BQP remains unproven. Most experts suspect these containments are strict, but formal proof is elusive. Furthermore, some problems exist in P through nonconstructive proofs, such as those derived from the Robertson-Seymour theorem, where we know a polynomial-time algorithm exists without actually knowing what that algorithm is.
The study of P extends beyond standard decision problems into areas like function problems (FP) and nonuniform complexity (P/poly). While P/poly contains nearly all practical problems, it also includes undecidable ones, highlighting the complexity of these classifications. As research continues, the boundaries of P remain a central focus, with researchers exploring whether specific conditions—such as the existence of sparse P-complete languages—could collapse these hierarchies entirely.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: P (complexity)
To cite this card, link to https://intellectplus.co.uk/app/science-p-complexity.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Theoretical computer science · More in Science · Latest · A–Z · All topics