Linked from

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

• 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.

• 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.

• 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.