Linked from

The 16 pages that link to Boolean satisfiability problem, each with the reason it gives.

• Propositional logicRelated: It is the central computational problem expressed in propositional logic.

• NegationRelated: Negated variables and clauses shape the formulas tested for satisfiability.

• Automated theorem provingRelated: SAT solvers automate propositional reasoning and support many proof procedures.

• Computational complexity theoryBroader topic: Cook's theorem used it as the first problem proved NP-complete.

• NP-completenessBroader topic: Its NP-completeness is the starting point for many hardness proofs.

• P versus NP problemBroader topic: Its efficient solvability would resolve the P versus NP question.

• George BooleRelated: Modern computational logic studies questions about formulas in the algebraic tradition Boole helped establish.

• Logical equivalenceRelated: Equivalence checking can be reduced to testing whether a formula for their disagreement is unsatisfiable.

• SAT solverNarrower topic: A SAT solver is an algorithmic tool for this decision problem.

• SatisfiabilityBroader topic: SAT is the computational form of propositional satisfiability.

• Cook–Levin theoremBroader topic: The theorem proves this problem NP-complete by encoding computations as formulas.

• NP-hardnessBroader topic: Its NP-completeness makes it a common source problem in hardness proofs.

• Mathematical optimizationCompared with: It asks whether any solution exists, rather than which feasible solution is best.

• Leonid LevinBroader topic: Its completeness became a central consequence of Levin’s reductions.

• Stephen CookBroader topic: This is the specific problem Cook proved NP-complete.

• Theory of computationBroader topic: It was the first problem proved NP-complete and remains a practical solver benchmark.