Course contentsShow
← Computer Science
Lesson 1917 of 2,87243. Complexity TheoryFree lesson

3-SAT Problem

Exploring 3-SAT, where clauses contain exactly three literals, and its NP-completeness.

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:

  1. It's simpler structurally than general SAT
  2. Yet remains just as hard computationally
  3. 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.