Complexity Classes (P vs NP) — Mathematics Knowledge System

Overview

Complexity theory classifies decidable problems not by whether they CAN be solved, but by how much time or space an algorithm needs as a function of input size. The most famous open question in computer science — whether P equals NP — asks whether every problem whose solution can be quickly VERIFIED can also be quickly FOUND. It's one of the seven Clay Millennium Prize Problems, with a $1 million reward for its resolution.

Intuition

Solving a jigsaw puzzle can take a long time, but CHECKING that a completed puzzle is correct is fast — just look at it. P vs NP asks: is there always a fast (polynomial-time) way to solve any problem whose solutions can be fast-checked? For problems like sorting, the answer is yes (P). For problems like the Traveling Salesman Problem, no efficient solving method is known — only efficient checking — and most computer scientists believe none exists (P ≠ NP), though this remains unproven.

Formal Definition

Definition

The core complexity classes:

P = \{L : L \text{ is decided by some deterministic Turing machine in time } O(n^k) \text{ for some constant } k\}

P

NP = \{L : L \text{ is decided by some nondeterministic Turing machine in polynomial time}\}

NP

NP = \{L : \text{membership in } L \text{ can be VERIFIED in polynomial time given a certificate}\}

Equivalent 'verifier' characterization of NP

Notation

Notation	Meaning
$P$	Problems solvable in polynomial time
$NP$	Problems verifiable in polynomial time
$\text{NP-complete}$	The hardest problems in NP — every NP problem reduces to them in polynomial time

Properties

P is a subset of NP

P \subseteq NP

Example: Anything solvable quickly is also checkable quickly (just re-solve it).

NP-completeness

L \text{ is NP-complete} \iff L \in NP \text{ and every } L' \in NP \text{ reduces to } L \text{ in polynomial time}

P=NP consequence

\text{If any single NP-complete problem is in P, then } P = NP

Applications

Cryptography (e.g. RSA) relies on certain problems (factoring large numbers) being hard to solve but easy to verify — closely related to the P vs NP question.

Worked Examples

Checking a filled grid against the rules takes time proportional to the number of cells — polynomial. Finding a valid filling, in the worst case, may require searching exponentially many candidate assignments.
$\text{Verify} \in P, \quad \text{Solve (generalized)} \in \text{NP-complete}$

Answer: Verification is fast (P); solving is NP-complete for the generalized n²×n² version.

Practice Problems

Difficulty 6/10

If someone proved P = NP tomorrow, what would that mean for modern cryptography?

Difficulty 6/10

A delivery company wants the shortest route visiting 30 cities exactly once (the Traveling Salesman Problem). Why can't they just check every possible route, and how does this relate to NP-hardness?

Difficulty 5/10

A password has 10 characters from a 90-symbol set. Brute-forcing it is 90¹⁰ attempts. Verifying a guessed password is instant. Which complexity idea does this illustrate?

Difficulty 5/10

A completed Sudoku can be CHECKED for validity quickly, but SOLVING a large blank one seems hard. This 'easy to verify, hard to solve' pattern is the defining feature of:

PNPconstant timesorting

Common Mistakes

Common Mistake

Believing NP stands for 'not polynomial'.

NP stands for 'nondeterministic polynomial time' — it does NOT mean a problem takes non-polynomial time; it means a solution can be verified in polynomial time (and P is itself a subset of NP).

Common Mistake

Assuming P ≠ NP has been proven.

It's widely believed but remains an open problem — one of the most famous unsolved questions in mathematics and computer science.

Quiz

Flashcards

1 / 3

Historical Background

The classes P and NP were formalized in the early 1970s. Stephen Cook's 1971 paper introduced NP-completeness and proved the Boolean satisfiability problem (SAT) is NP-complete — the Cook-Levin theorem (independently discovered by Leonid Levin). Richard Karp's 1972 paper showed 21 other important problems (including Traveling Salesman) are also NP-complete, revealing that an enormous range of practical problems are all equally hard, in a precise sense.

1971
Stephen Cook proves SAT is NP-complete (Cook-Levin theorem)
Stephen Cook
1972
Richard Karp shows 21 further problems are NP-complete
Richard Karp
2000
The Clay Mathematics Institute lists P vs NP as one of seven Millennium Prize Problems

Summary

P: solvable in polynomial time. NP: solutions verifiable in polynomial time.
P ⊆ NP always; whether P = NP is a famous open problem (Millennium Prize).
NP-complete problems are the hardest in NP — solving one quickly would solve all of NP quickly.
Most practitioners believe P ≠ NP, motivating heuristics/approximations for NP-complete problems in practice.

References

WebsiteWikipedia — P versus NP problem