Cook-Levin Theorem

The Cook-Levin theorem states that the Boolean satisfiability problem, the question of whether there exists some assignment of true and false values to the variables of a given Boolean logical formula that makes the whole formula evaluate to true, is NP-complete, meaning it belongs to the complexity class NP and that every other problem in NP can be transformed into an instance of it using only a polynomial amount of additional computation. Computer scientist Stephen Cook proved the result independently in a 1971 paper, and mathematician Leonid Levin, working separately in the Soviet Union, proved an equivalent result published in 1973. The theorem established the first problem ever proven to be NP-complete, and its significance was substantially extended the following year when computer scientist Richard Karp published a 1972 paper showing that twenty-one other well-known combinatorial problems could each be reduced to Boolean satisfiability, and were therefore also NP-complete. The Cook-Levin theorem is considered the founding result of NP-completeness theory, the branch of computational complexity theory concerned with identifying which computational problems are, in a precise formal sense, at least as hard as the hardest problems whose solutions can be efficiently checked once found.