Mathematics
The P vs NP Problem and Cook-Levin Theorem
Quick fact
The Cook-Levin theorem (1971) proved that the Boolean satisfiability problem (SAT) is NP-complete, meaning if you could solve SAT quickly, you could solve every NP problem quickly—yet no one has found a fast algorithm for any of them.
Why this is interesting
You've probably heard that some problems are 'hard' and some are 'easy'. But what if a problem that is easy to check is actually hard to solve? That's the mystery behind the most famous unsolved question in computer science.
Read the full explanation
Understanding The P vs NP Problem and Cook-Levin Theorem
Imagine you're given a large jigsaw puzzle. Solving it takes time, but if someone shows you the completed picture, you can verify it quickly. In computer science, we classify problems by how fast we can solve them versus how fast we can check a solution. The class P contains problems that can be solved in polynomial time (like sorting a list). The class NP contains problems whose solutions can be verified in polynomial time (like checking a Sudoku solution). The big question: Is every problem in NP also in P? If yes, then solving a puzzle would be as easy as checking it. The Cook-Levin theorem showed that the Boolean satisfiability problem (SAT) is the 'hardest' problem in NP: any NP problem can be transformed into a SAT instance in polynomial time. So if SAT can be solved quickly, then all NP problems can. This made SAT the first NP-complete problem and gave us a way to prove other problems are equally hard.
A deeper explanation
The Cook-Levin theorem works by encoding the computation of a nondeterministic Turing machine as a Boolean formula. For any problem in NP, there is a nondeterministic machine that guesses a solution and verifies it in polynomial time. Cook showed that the question 'does this machine accept its input?' can be expressed as a SAT instance whose size is polynomial in the input length. If SAT had a polynomial-time algorithm, you could use it to simulate any NP machine: feed the SAT formula into the algorithm, and if it says satisfiable, the machine accepts. This polynomial-time reduction means SAT is at least as hard as every NP problem. Thus, SAT is NP-complete. The significance is enormous: thousands of practical problems (scheduling, routing, circuit design) are NP-complete. If P = NP, they would all have efficient solutions, revolutionizing optimization and cryptography. Conversely, if P ≠ NP, then no efficient algorithm exists for any of them. The theorem is the foundation of complexity theory, and the P vs NP question remains one of the Millennium Prize Problems, with a $1 million reward for a proof.