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.
What a learner can do afterwards
- 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
1 · Read
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.
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.
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.
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.
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.
2 · Watch
به انگلیسیTake it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.