"The language SAT of satisfiable Boolean formulas is NP-complete."

This is a lndmark theorem, proven by Stephen Cook in 1971 that won him the Turing award. Finding the first problem that is NP-complete is immensely useful in that to prove another problem X is NP-Complete, you merely need to do two things: prove that X is in NP, and reduce SAT to X. Within the first few months of the publication of Cook's theorem, dozens of problems were proven NP complete. Today, more than ten thousand problems have been proven NP-complete.

The problem of satisfiability (SAT) is: given a boolean expression (an expression of boolean variables in conjunctive normal form) is there a truth assignment to the variables that will result in the expression being evaluated to "true"?

A few examples of NP-complete problems:

  • The traveling salesman problem
  • Hamiltonian tour
  • Clique
  • independent set