The Class P (Polynomial Time)
You'll learn what P is and why polynomial-time problems are considered "efficiently solvable" in practice.
What is the Class P?
The complexity class P (for Polynomial time) is the set of all decision problems that can be solved by a deterministic Turing machine in polynomial time. In other words, if there exists an algorithm that solves a problem in time bounded by O(n^k) for some constant k (where n is the input size), that problem belongs to P.
Why Polynomial Time?
Think of it like this: Imagine you're organizing books on shelves. If you have 10 books, a task that takes 100 seconds (10²) is manageable. Even with 100 books taking 10,000 seconds (100²) is feasible—about 2.7 hours. This is polynomial growth.
Compare this to exponential time like 2^n. With 10 books, that's 1,024 seconds (~17 minutes). With just 100 books? Over 10³⁰ seconds—longer than the age of the universe!
P as "Efficiently Solvable"
P represents practical computability. Problems in P scale reasonably as inputs grow larger. Examples include:
- Sorting a list of numbers (O(n log n))
- Finding the shortest path in a graph (O(n²))
- Checking if a number is prime (polynomial time)
These problems might take longer with bigger inputs, but they remain tractable. The algorithm's running time grows predictably and manageably.
The Formal View
A language L is in P if there exists a deterministic Turing machine M and a polynomial p(n) such that M decides L in time O(p(n)) for all inputs of length n.
Key Takeaway: The class P captures all problems solvable in polynomial time—these are the problems we consider efficiently computable in practice, because their runtime scales manageably with input size.