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

The Satisfiability Problem (SAT)

Introducing the Boolean satisfiability problem: determining if a logical formula has a satisfying assignment.

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.