Lesson 4

Among the problems in the class NP, we can naturally define reductions: we say that a problem \(A\) reduces to a problem \(B\) if an efficient (i.e., polynomial-time) algorithm for the problem \(B\) can be used to efficiently solve the problem \(A\).

At first glance, this sounds surprising, but there are problems in NP to which all NP problems reduce! Such problems are called NP-complete. Around 1971, Stephen Cook and Leonid Anatolievich Levin independently proved that the Boolean satisfiability problem is NP-complete. And in 1972, Richard Karp proved that the decision versions of many other problems are also NP-complete: integer programming, clique, vertex cover, Hamiltonian cycle, knapsack, and maximum cut. The corresponding optimization problems are NP-hard.