The Satisfiability Problem (SAT)
You'll learn: What the Boolean satisfiability problem is and why it's central to understanding computational complexity.
What Is SAT?
The Satisfiability Problem (SAT) asks a fundamental question: Given a Boolean formula made up of variables, ANDs, ORs, and NOTs, does there exist an assignment of TRUE/FALSE values to the variables that makes the entire formula evaluate to TRUE?
If such an assignment exists, we say the formula is satisfiable. If no assignment works, it's unsatisfiable.
A Simple Example
Consider the formula: (x OR y) AND (NOT x OR z)
Can we find values for x, y, and z that make this TRUE?
Let's try x=TRUE, y=FALSE, z=TRUE:
- First part: (TRUE OR FALSE) = TRUE ✓
- Second part: (NOT TRUE OR TRUE) = (FALSE OR TRUE) = TRUE ✓
- Overall: TRUE AND TRUE = TRUE ✓
Yes! This formula is satisfiable.
Now consider: (x) AND (NOT x)
No matter what value we assign to x, one clause will be FALSE, so the whole formula is FALSE. This is unsatisfiable.
Why SAT Matters
SAT is the first problem ever proven to be NP-complete (we'll explore this soon). This means:
- It's in NP (solutions can be verified quickly)
- Every other NP problem can be transformed into SAT
- Finding efficient solutions to SAT would solve countless real-world problems in scheduling, circuit design, AI planning, and more
Think of SAT as a "universal puzzle" — if you can solve it efficiently, you can solve a vast universe of other hard problems.
Key Takeaway: SAT determines whether a Boolean formula has a satisfying assignment; it's the cornerstone problem in NP-completeness theory.