P and NP: How hard is a problem?

In short: A classification of problems: P are those that can be solved quickly; with NP a proposed solution can be checked quickly, whether it can also be found quickly is open.

In more detail: Complexity theory asks how strongly the effort grows with the size of the input. “Fast” here means: at most polynomial, i.e. roughly n², n³ (n is the input size). An effort such as 2ⁿ (“exponential”) grows so strongly that even medium inputs become practically unsolvable.

In Depth

P: quickly solvable

P (polynomial time) contains problems that an algorithm solves in polynomial time: sorting, shortest paths in a network, checking whether a number is in a list. These problems are regarded as practically manageable.

NP: quickly checkable

NP contains problems where an offered solution can be checked in polynomial time. Example Sudoku: a filled-in grid is quickly verified, but finding a solution can be laborious (for large variants). Every problem in P is also in NP.

NP-complete and the big question

Some NP problems are NP-complete: they are among the hardest in NP, and a fast algorithm for one would yield fast algorithms for all NP problems. Examples: the travelling salesman problem (shortest round trip), knapsack problem (decision version), satisfiability of logical formulas (SAT), graph colouring. Whether P = NP holds is one of the best-known unsolved questions in computer science (one of the seven Millennium Problems). Most experts suspect that P ≠ NP.

Consequences in practice

For NP-complete problems one uses approximation methods, heuristics (good but not provably best solutions), restriction to small inputs or special cases. The security of modern encryption also rests on the assumption that certain problems are hard, though these problems (e.g. factoring) are not known to be NP-complete.

See also: Big O notation, Dynamic programming, Greedy algorithms