3-SAT Problem
You'll learn what 3-SAT is and why it's a cornerstone problem in computational complexity theory.
What is 3-SAT?
3-SAT is a restricted version of the general Boolean satisfiability problem (SAT) where every clause contains exactly three literals. A literal is either a variable (like x) or its negation (¬x). The question remains: can you assign TRUE/FALSE values to variables so that every clause has at least one true literal?
The Structure
In 3-SAT, a formula looks like:
(x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ x₄) ∧ (x₂ ∨ ¬x₃ ∨ ¬x₄)
Each parenthesized group is a clause with precisely three literals connected by OR (∨), and clauses are connected by AND (∧).
Why 3-SAT Matters
While general SAT is NP-complete (Cook-Levin Theorem), you might wonder if restricting clauses to exactly three literals makes the problem easier. It doesn't. 3-SAT is also NP-complete! This is remarkable because:
- It's simpler structurally than general SAT
- Yet remains just as hard computationally
- It's often easier to reduce from when proving other problems NP-complete
Think of it like this: if you're trying to prove a new puzzle is hard, it's easier to transform 3-SAT (with its uniform structure) into your puzzle than to transform the messier general SAT.
Verification Still Easy
Given a proposed solution, verifying it takes polynomial time—just substitute the values and check each clause. But finding that solution? No known polynomial-time algorithm exists.
Key Takeaway: 3-SAT proves that even highly restricted versions of SAT remain NP-complete, making it a powerful tool for proving hardness of other problems through reductions.