Course contentsShow
← Computer Science
Lesson 1900 of 2,87243. Complexity TheoryFree lesson

Examples of Problems in P

Examine concrete problems in P: sorting, graph connectivity, shortest paths, and prime testing.

Examples of Problems in P

What you'll learn: You'll see concrete problems that can be solved efficiently in polynomial time, solidifying what it means for a problem to be in the class P.

The Practical Side of P

While we've defined P as the class of decision problems solvable in polynomial time, it's crucial to see real examples. These problems represent tasks we can solve efficiently, even as input size grows.

Classic Problems in P

Sorting

Given a list of numbers, arrange them in ascending order. Algorithms like merge sort run in O(n log n) time—polynomial. Since sorting is deterministic and always completes in polynomial time, it belongs to P.

Graph Connectivity

Decision problem: "Is there a path from vertex A to vertex B in graph G?"

Depth-first search or breadth-first search answers this in O(V + E) time (vertices plus edges)—clearly polynomial. We can efficiently decide whether any two nodes are connected.

Shortest Paths

Decision problem: "Is there a path from A to B with length ≤ k?"

Dijkstra's algorithm finds shortest paths in O((V + E) log V) time for non-negative weights. Checking if the shortest path meets a threshold is polynomial and decidable.

Prime Testing

Decision problem: "Is integer n prime?"

While once thought difficult, the AKS primality test (2002) proved this is in P, running in polynomial time relative to the number of digits in n. Modern implementations can efficiently test primality for very large numbers.

Why These Matter

These examples show P contains many practical problems we solve daily: organizing data, navigating networks, optimizing routes, and cryptographic checks. They're tractable—computers can handle them even with large inputs.

Key Takeaway: Problems in P like sorting, graph connectivity, shortest paths, and prime testing can all be solved by deterministic algorithms that run in polynomial time, making them computationally feasible in practice.