--- title: "SAT Solvers and What Makes Search Practical" description: "SAT asks whether a Boolean formula has a satisfying assignment. Conflict-driven clause learning derives clauses implied by the formula to rule out conflicting assignments. It can help practical search" canonical: https://lightmysky.com/learn/computing/sat-solvers-and-what-makes-search-practical-mt_d46m2LD443 source: https://lightmysky.com/learn/computing/sat-solvers-and-what-makes-search-practical-mt_d46m2LD443.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # SAT Solvers and What Makes Search Practical SAT asks whether a Boolean formula has a satisfying assignment. Conflict-driven clause learning derives clauses implied by the formula to rule out conflicting assignments. It can help practical search, but supplies no general polynomial-time guarantee for this NP-complete problem. Subject: Computing · Area: Algorithms & Data Structures · Ages 22 to 24 Page: https://lightmysky.com/learn/computing/sat-solvers-and-what-makes-search-practical-mt_d46m2LD443 ## Ready when they can - Encode a small constraint problem into clauses and say what a satisfying assignment means for it - Explain what conflict-driven clause learning adds to plain backtracking - Say why a solver being fast on real instances contradicts nothing about NP-completeness ## Lesson: Search that learns from failure SAT asks whether a Boolean formula has a satisfying assignment. Here formulas are in conjunctive normal form: every clause must be true. A clause joins literals with or. A literal is a variable such as A, or its negation not-A. A is true when its variable is true; not-A is true when that variable is false. A correct encoding makes satisfying assignments correspond to choices obeying the original rules. **Example.** Two jobs need an order. Let A mean job A goes first and B mean job B goes first. A or B requires at least one to go first. Not-A or not-B forbids both from going first. Together they require exactly one. A true and B false represents A followed by B; A false and B true represents the reverse. *(drawing: Here 0 means false and 1 means true. Test each assignment against both clauses.)* Plain backtracking tries assignments and retreats when they cannot work. CDCL also propagates forced values: when a clause has one unset literal and all others false, that literal must be true. On conflict, it analyzes implications and learns a clause implied by the original formula. While retained, that clause excludes its forbidden combination. Backtracking can skip several levels. Solvers may later discard learned clauses. **Example.** Consider not-X or Y and not-X or not-Y. If X is true, the first clause forces Y true and the second forces Y false. They cannot both hold. The two clauses imply the learned clause not-X. It excludes every assignment with X true without removing any satisfying assignment. Define variables by what they mean. If A means task A is complete and C means task C is complete, the rule C implies A is not-C or A. It forbids C true with A false. This describes a completion-state requirement; it does not by itself encode start times or a complete schedule. You have seen that NP-completeness concerns polynomial-time algorithms over all inputs. Fast SAT runs on selected scheduling formulas do not settle P versus NP. Structure and search choices can help, but not every industrial input is easy. Clause learning alone gives no polynomial worst-case guarantee. No general polynomial-time SAT algorithm is known, and no proof rules one out. **Recap.** Define each Boolean variable, encode every rule and satisfy every clause. CDCL learns implied clauses from conflicts. Successful runs do not prove a polynomial worst-case bound. *Original lesson, questions and flashcards written for this learning dataset.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Complexity Beyond NP: Space, Randomness and the Hierarchy](https://lightmysky.com/learn/computing/complexity-beyond-np-space-randomness-and-the-hierarchy-mt_ADfgl9UGpO) - [P, NP and What NP-Complete Means](https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB) ## Opens up - [Specifying Correctness: Safety, Liveness and Invariants](https://lightmysky.com/learn/computing/specifying-correctness-safety-liveness-and-invariants-mt_4_KaoDSHZF)