Il matematico americano Stephen Cook, mentre completa il suo dottorato in Computer Science alla University of California at Berkeley, scopre il la SAT (Satisfiability) per i problemi NP-Completi (Non-deterministic, Polynomially time bounded): risolvere qualsiasi problema NP-completo equivale a risolvere una qualsiasi instanza di SAT (all’anno 2000 erano conosciuti oltre 2000 differenti problemi NP-completi)
