Examples of Problems in P
You'll learn: Which concrete computational problems can be solved efficiently in polynomial time and why they belong to the class P.
What Makes a Problem Easy?
Recall that P is the complexity class containing problems solvable by a deterministic algorithm in polynomial time—that is, in time proportional to n^k for some constant k, where n is the input size. Let's examine real problems that fit this definition.
Classic Problems in P
Sorting
Given a list of n numbers, arrange them in order. Algorithms like merge sort run in O(n log n) time, which is polynomial. Since we can always sort efficiently regardless of input size, sorting is in P.
Shortest Path
Finding the shortest path between two nodes in a weighted graph (Dijkstra's algorithm) runs in O(n² log n) time (or better with optimizations). Despite seeming complex, it's still polynomial—firmly in P.
Matching
Determining whether a bipartite graph has a perfect matching can be solved in O(n³) time using the Hungarian algorithm or similar approaches. Again, polynomial time = membership in P.
Other Examples
- Linear programming (surprisingly!)
- Primality testing (checking if a number is prime)
- Graph connectivity (is the graph connected?)
Why This Matters
Think of P as the "tractable problems club"—problems we can realistically solve even as inputs grow large. A problem in P with n = 1,000,000 might take seconds or minutes, but it will finish. This distinguishes them from harder problems we'll encounter later.
Key Takeaway: Problems like sorting, shortest paths, and matching belong to P because we have polynomial-time algorithms for them, making them efficiently solvable in practice.