SAT Solvers and What Makes Search Practical
Satisfiability is the canonical hard problem, and yet solvers decide industrial instances with millions of clauses. They search, and when they fail they learn a clause explaining the failure, which prunes the region that produced it. The worst case is unchanged; practice is not.
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
Satisfiability asks for one assignment making every clause true. Encoding a constraint problem means writing each rule as clauses over true-or-false variables. A satisfying assignment is then a valid schedule, layout, or plan: one choice per variable that obeys every rule at once.
Two jobs share one machine. Let A mean job A goes first. The clause A or B forces one of them first, while not-A or not-B forbids both first. An assignment satisfying both, say A true and B false, is exactly the valid order: A, then B.
Plain backtracking tries values and retreats on conflict. Conflict-driven clause learning records why each failure happened as a brand-new clause, so search never re-enters any region that fails the same way. The worst case is unchanged, but real runs skip whole dead zones at once.
Speed on industrial instances contradicts nothing about NP-completeness, which speaks only about worst cases over all inputs. Real instances carry structure, few distinct conflicts, and learning exploits exactly that. Judge the solver by the instances you run, not by the hardest imaginable one.
Encode rules as clauses; learn each failure as a clause; worst case stays, practice leaps.
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.