- P is the class of problems solvable in polynomial time — considered “efficiently solvable.”
- NP is the class of problems where a proposed solution can be verified in polynomial time.
- P ⊆ NP is known; whether P = NP is the most famous unsolved problem in computer science.
- A problem is NP-Hard if every problem in NP reduces to it in polynomial time.
- A problem is NP-Complete if it is both NP-Hard and in NP — the hardest problems in NP.
- SAT was the first NP-Complete problem (Cook-Levin Theorem, 1971); hundreds of others were subsequently proved NP-Complete by reduction from SAT or each other.
1. Time Complexity and Complexity Classes
Complexity theory shifts focus from what can be computed (computability) to how efficiently it can be computed (complexity). Two problems may both be decidable, but one requires milliseconds and the other would take longer than the age of the universe even on the fastest computer.
The time complexity of an algorithm is the function T(n) giving the worst-case number of steps as a function of input size n. Complexity classes group problems by the resources they require.
Why Polynomial vs Exponential Matters
| Complexity | n=10 | n=100 | n=1000 | Practical? |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1,000 | Yes |
| O(n2) | 100 | 10,000 | 1,000,000 | Yes |
| O(n3) | 1,000 | 106 | 109 | Marginal |
| O(2n) | 1,024 | 1030 | 10301 | No |
| O(n!) | 3.6M | 9.3×10157 | astronomic | No |
Polynomial algorithms scale gracefully as input grows; exponential algorithms become completely infeasible for even moderate inputs.
2. The Class P
P (Polynomial time) is the set of all decision problems (yes/no problems) solvable by a deterministic Turing machine in polynomial time — O(nk) for some constant k.
P represents “feasibly solvable” problems in practice. Examples:
- Sorting a list — O(n log n)
- Shortest path in a graph — Dijkstra’s algorithm O(E + V log V)
- Matrix multiplication — O(n3) naive, better with Strassen
- Testing whether a number is prime — AKS algorithm runs in polynomial time
- Linear programming — polynomial (ellipsoid/interior point methods)
- Maximum bipartite matching — polynomial
3. The Class NP
NP (Nondeterministic Polynomial time) is the set of decision problems where a proposed “yes” solution can be verified in polynomial time. Equivalently, NP contains the problems solvable by a nondeterministic TM in polynomial time.
The Verifier Definition (Most Intuitive)
A problem L is in NP if there is a polynomial-time algorithm V (the verifier) and a polynomial bound p(n) such that:
- If x ∈ L, there exists a certificate c with |c| ≤ p(|x|) and V(x, c) accepts.
- If x ∉ L, no certificate c makes V(x, c) accept.
Examples of NP Problems
- SAT: Given a boolean formula, does it have a satisfying assignment? (Certificate: the assignment itself; verify by plugging in — O(n))
- Travelling Salesman (Decision): Is there a tour of all cities with total cost ≤ k? (Certificate: the tour; verify cost — O(n))
- 3-Coloring: Can a graph be coloured with 3 colours so no adjacent nodes share a colour? (Certificate: the colouring; verify — O(E))
- Clique: Does the graph contain a clique (complete subgraph) of size k? (Certificate: the k nodes; verify all edges exist — O(k2))
- Subset Sum: Does a set of integers have a subset summing to exactly T? (Certificate: the subset; verify sum — O(n))
4. P vs NP — The Million-Dollar Question
We know P ⊆ NP (any problem you can solve efficiently you can also verify efficiently). The central unresolved question of theoretical computer science is:
If P = NP, then every problem whose solutions can be verified quickly can also be solved quickly. This would have enormous consequences:
- Cryptography would collapse: RSA, AES, and most public-key encryption rely on the assumed hardness of NP problems. If P = NP, these become breakable.
- Drug discovery and protein folding: Optimisation problems in biology would become tractable.
- Mathematical proof: Finding proofs might become as easy as verifying them.
The overwhelming consensus among researchers is that P ≠ NP, but this has never been proved. The Clay Mathematics Institute offers a $1 million prize for a proof in either direction.
5. Polynomial-Time Reductions
A polynomial-time many-one reduction from problem A to problem B (written A ≤p B) is a function f computable in polynomial time such that x ∈ A iff f(x) ∈ B.
Reductions transfer complexity: if A ≤p B and B ∈ P, then A ∈ P. Contrapositive: if A is NP-Hard (no poly-time algorithm unless P=NP) and A ≤p B, then B is also NP-Hard.
Think of a reduction as a translation: “solving B is at least as hard as solving A.” If I can quickly translate any A-question into a B-question, a fast B-solver immediately gives a fast A-solver.
6. NP-Complete Problems
A problem is NP-Complete if it is:
- In NP — solutions can be verified in polynomial time
- NP-Hard — every problem in NP reduces to it in polynomial time
NP-Complete problems are the hardest problems in NP. If any single NP-Complete problem has a polynomial-time algorithm, then P = NP (all NP problems become polynomial).
Cook-Levin Theorem
In 1971, Stephen Cook proved that SAT (Boolean Satisfiability) is NP-Complete — the first problem ever proved to be NP-Complete. The proof shows every NP problem can be expressed as a polynomial-size boolean formula; if SAT were in P, all of NP would collapse to P.
Subsequently, hundreds of NP-Complete problems were proved by reduction chains from SAT: SAT ≤p 3-SAT ≤p Clique ≤p Vertex Cover ≤p Hamiltonian Cycle ≤p TSP, etc.
7. NP-Hard Problems
NP-Hard means “at least as hard as NP-Complete” — every NP problem reduces to it. An NP-Hard problem may or may not be in NP itself.
- NP-Hard but in NP = NP-Complete (e.g., SAT, TSP-decision)
- NP-Hard but NOT in NP: Problems harder than NP-Complete, such as the Halting Problem, PSPACE-complete problems, optimisation versions of NP-Complete problems (e.g., “find the minimum cost tour” rather than “is there a tour of cost ≤ k?”).
| Class | In NP? | Every NP problem reduces to it? |
|---|---|---|
| P | Yes | No |
| NP | Yes | No (unless NP-Hard) |
| NP-Complete | Yes | Yes |
| NP-Hard (not NP) | No | Yes |
8. Famous NP-Complete Problems
| Problem | Description | Practical Relevance |
|---|---|---|
| SAT (3-SAT) | Satisfying assignment for boolean formula (3 literals per clause) | Electronic design automation, AI planning |
| Clique | Does graph G have a complete subgraph of size k? | Social network analysis |
| Vertex Cover | Can k vertices cover all edges? | Network security, biology |
| Independent Set | Does G have k mutually non-adjacent vertices? | Scheduling, register allocation |
| Hamiltonian Cycle | Does G have a cycle visiting every vertex exactly once? | Route planning, circuit board drilling |
| TSP (decision) | Tour visiting all cities with cost ≤ k? | Logistics, delivery routing |
| Graph Colouring (3-colour) | Can G be coloured with 3 colours with no adjacent same-colour vertices? | Compiler register allocation, scheduling |
| Subset Sum | Subset summing to exactly T? | Cryptography, resource allocation |
| Bin Packing | Can n items fit into k bins of capacity C? | Memory allocation, logistics |
| Integer Linear Programming | LP with integer constraints | Operations research, scheduling |
Reduction Chain to Remember
SAT ≤p 3-SAT ≤p Clique ≤p Independent Set ≤p Vertex Cover3-SAT ≤p Hamiltonian Cycle ≤p TSP9. Space Complexity — PSPACE and EXPTIME
Beyond P and NP, there are complexity classes defined by space (memory) usage:
| Class | Definition | Example |
|---|---|---|
| L (LOGSPACE) | Solvable in O(log n) space | Graph reachability |
| PSPACE | Solvable in polynomial space | TQBF (quantified boolean formulas) |
| EXPTIME | Solvable in exponential time 2poly(n) | Generalised chess, Go |
| EXPSPACE | Solvable in exponential space | Some verification problems |
Known Containments
P ⊆ NP ⊆ PSPACE ⊆ EXPTIMEIt is known that P ≠ EXPTIME (strict). Where exactly NP and PSPACE fit relative to each other is unknown.
10. Common Misconceptions
Misconception 1: NP stands for “Not Polynomial.”
NP stands for “Nondeterministic Polynomial” — problems solvable in polynomial time by a nondeterministic TM. It does not mean “hard” or “not in P.” Every problem in P is also in NP. We do not know if NP contains problems outside P.
Misconception 2: NP-Hard means “practically impossible to solve.”
NP-Hard means no polynomial-time algorithm is known (assuming P ≠ NP). In practice, NP-Hard problems are tackled with approximation algorithms (guaranteed near-optimal), heuristics (no guarantee), and exact algorithms that work well on practical instances (branch and bound, dynamic programming with pruning).
Misconception 3: Proving a problem NP-Complete means it is unsolvable.
NP-Complete problems are very much solvable — just not efficiently for all inputs. Exact TSP solvers handle hundreds of cities; SAT solvers routinely solve industrial instances with millions of variables. The NP-Completeness result is a worst-case statement, not a practical limitation for typical inputs.
Misconception 4: All NP-Hard problems are in NP.
NP-Hard only means “as hard as NP-Complete.” Some NP-Hard problems are even harder and not in NP — such as the Halting Problem, or PSPACE-Complete problems. NP-Complete = NP-Hard ∩ NP.
Misconception 5: If P = NP, computers would break all encryption instantly.
Only if the polynomial algorithm has practical constants. A hypothetical O(n1000) algorithm for NP problems is polynomial but completely impractical. However, most experts believe a proof of P = NP would come with a practically fast algorithm, making the concern real.
11. Frequently Asked Questions
What is the difference between P, NP, NP-Complete and NP-Hard?
P problems can be solved efficiently (polynomial time). NP problems can have solutions verified efficiently — P is a subset of NP. NP-Complete problems are the hardest in NP — every NP problem reduces to them, and they are themselves in NP. NP-Hard problems are at least as hard as NP-Complete — every NP problem reduces to them, but they may not be in NP themselves (they might be even harder).
Why do we care about NP-Completeness in practice?
When you prove your problem is NP-Complete, you know not to search for an efficient exact algorithm (decades of research by brilliant people have failed to find one). Instead you focus on approximation algorithms (provably near-optimal), heuristics, special-case algorithms, or problem reformulation. NP-Completeness proofs save wasted effort and redirect engineering toward practical solutions.
Is there any evidence that P ≠ NP?
There is strong circumstantial evidence. Thousands of natural, independently arising problems have been shown NP-Complete over 50+ years, yet none has been solved in polynomial time. Circuit lower bound results, random oracle separations, and algebraic arguments all suggest P ≠ NP. However, none constitute a proof — the mathematical difficulty is that proving super-polynomial lower bounds for any problem has proved extremely hard.
How do you prove a new problem is NP-Complete?
Two steps: (1) Show the problem is in NP — give a polynomial-time verifier. (2) Show it is NP-Hard — reduce a known NP-Complete problem to it in polynomial time. The reduction goes from the known NP-Complete problem TO your new problem (not the other way). The most common starting point is 3-SAT, since many combinatorial problems reduce naturally from boolean logic.