01Overview

In 1965 Cobham and Edmonds separately proposed polynomial time as the rough standard for an efficient algorithm. In 1971 Cook proved that Boolean satisfiability (SAT) is NP-complete: every NP problem reduces to it in polynomial time. Karp’s 21 problems in 1972 showed how widespread that difficulty is.

P vs NP is still open and is one of the Millennium Prize problems. Complexity theory also draws a finer picture: randomised algorithms, interactive proofs, approximation and parameterised algorithms are all ways out when exact solutions are too hard. And the security of cryptography rests precisely on some problems staying hard.

02History

  1. 1965

    Polynomial time as the yardstick

    Proposed independently by Cobham and Edmonds.

  2. 1971

    Cook's theorem

    SAT is NP-complete.

  3. 1972

    Karp's 21 problems

    NP-completeness turns out to be everywhere.

  4. 1992

    The PCP theorem

    A deep link between approximation and proof verification.

  5. 2000

    P vs NP becomes a Millennium Problem

    A one-million-dollar prize on the table.

03Core concepts

P and NP

Solvable in polynomial time, versus verifiable in polynomial time.

NP-complete

The hardest problems in NP; SAT is the first example.

Complexity class

A set of problems grouped by the resources they need: time, space, randomness.

04Hands-on

Do it once — it beats reading it ten times

Reduce 3-SAT to independent set: give the construction and check on a small instance that the two answers agree

05Self-check

Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.

Can you explain "P and NP"?

Solvable in polynomial time, versus verifiable in polynomial time.

Can you explain "NP-complete"?

The hardest problems in NP; SAT is the first example.

Can you explain "Complexity class"?

A set of problems grouped by the resources they need: time, space, randomness.

What problem did it solve, and why was there nothing better at the time?

Go back to the history section: how was this done before, and what did it cost?

If you had to build it today, how would you break it down?

Use the hands-on task above: write a plan of at most three steps before you start.

06Key people

S

Stephen Cook

1939 –

Proved the NP-completeness of SAT.

R

Richard Karp

1935 –

Showed with 21 problems how common NP-completeness is.

07Further reading

  • Computers and IntractabilityGarey & Johnson · 1979
  • Computational Complexity: A Modern ApproachArora & Barak · 2009