Cook's theorem establishes that the satisfiability problem (SAT) is NP-complete. A propositional logic formula is considered satisfiable if there exists an assignment of its variables that evaluates it to true, such as "p AND q" being true when both p=1 and q=1. Boolean expressions use 0 for false, 1 for true, with operators like NOT having precedence over AND or OR. The popular variant "3-SAT" involves formulas in conjunctive normal form (CNF), where each clause contains exactly three literals—variables or their negations connected by logical operations. Cook’s proof outlines two steps: converting a polynomial-time non-deterministic Turing machine execution into well-formed formulas satisfied only if the machine accepts input; then showing these formula lengths are polynomial relative to problem size. This demonstrates SAT belongs to NP and can reduce any arbitrary NP-problem within this framework.