Skip to main content
⚡ Calmops
🤖 AI 🏗️ Architecture 🌐 Web 🗃️ Database ⚙️ DevOps 🌍 Network 💻 Programming 🧮 Algorithms 📐 Software Eng. ☁️ Cloud 🔒 Security 📈 Finance More →

Boolean Satisfiability (SAT) Problem: Computational Complexity

Created: December 20, 2025 6 min read

Introduction

The Boolean satisfiability (SAT) problem is one of the most fundamental problems in computer science. It asks: given a Boolean formula, does there exist an assignment of truth values to variables that makes the formula true? Despite its simple statement, SAT is NP-complete, meaning it’s among the hardest problems in computer science. Yet modern SAT solvers can handle formulas with millions of variables, making them invaluable for practical applications.

This article explores the SAT problem, its complexity, algorithms, and applications.

Historical Context

The SAT problem was the first problem proved to be NP-complete by Stephen Cook in 1971. This foundational result established the P vs NP problem as central to computer science. For decades, SAT was considered impractical for large instances. However, starting in the 1990s, dramatic improvements in SAT solver algorithms and heuristics made them practical for real-world problems. Modern SAT solvers are among the most successful automated reasoning tools.

Problem Definition

Boolean Satisfiability

Definition: Given a Boolean formula φ over variables x₁, x₂, …, xₙ, determine whether there exists an assignment of truth values such that φ evaluates to true.

Notation: SAT(φ) = true iff ∃ assignment σ such that φ(σ) = true

Example:

φ = (x ∨ y) ∧ (¬x ∨ z)
Assignment: x = true, y = false, z = true
φ(assignment) = (true ∨ false) ∧ (false ∨ true) = true ∧ true = true
So SAT(φ) = true

Conjunctive Normal Form (CNF)

Definition: A formula in CNF is a conjunction of clauses, where each clause is a disjunction of literals

Format: (L₁ ∨ L₂ ∨ … ∨ Lₖ) ∧ (M₁ ∨ M₂ ∨ … ∨ Mₘ) ∧ …

Literal: A variable or its negation (x or ¬x)

Clause: A disjunction of literals

Conversion: Any Boolean formula can be converted to CNF

Example:

Original: (x → y) ∧ (y → z)
CNF: (¬x ∨ y) ∧ (¬y ∨ z)

k-SAT

Definition: SAT restricted to formulas where each clause has at most k literals

2-SAT: Each clause has at most 2 literals (polynomial time solvable) 3-SAT: Each clause has at most 3 literals (NP-complete) k-SAT: Each clause has at most k literals (NP-complete for k ≥ 3)

Computational Complexity

NP-Completeness

Definition: A problem is NP-complete if:

  1. It’s in NP (solution can be verified in polynomial time)
  2. Every NP problem can be reduced to it in polynomial time

SAT is NP-Complete:

  • Verification: Given assignment, check if formula is satisfied (polynomial time)
  • Reduction: Cook’s theorem shows all NP problems reduce to SAT

Implication: If P = NP, then SAT is solvable in polynomial time. If P ≠ NP, then SAT requires exponential time in worst case.

Worst-Case Complexity

Brute Force: Try all 2ⁿ assignments

  • Time: O(2ⁿ)
  • Space: O(n)

DPLL Algorithm: Systematic search with pruning

  • Time: O(2ⁿ) worst case
  • Space: O(n)

Practical Performance: Modern solvers handle millions of variables despite worst-case exponential complexity

SAT Solving Algorithms

DPLL Algorithm (Davis-Putnam-Logemann-Loveland)

Procedure:

Algorithm DPLL(formula F, assignment σ)
1. If F is empty, return SAT
2. If F contains empty clause, return UNSAT
3. Unit propagation: If clause has single literal, assign it
4. Pure literal elimination: If variable appears only positive/negative, assign it
5. Choose variable x
6. Try x = true:
   a. Recursively call DPLL(F[x/true], σ ∪ {x=true})
   b. If SAT, return SAT
7. Try x = false:
   a. Recursively call DPLL(F[x/false], σ ∪ {x=false})
   b. Return result

Optimizations:

  • Unit propagation: Simplify formula
  • Pure literal elimination: Remove redundant variables
  • Backjumping: Skip irrelevant branches
  • Learning: Remember conflicts

Unit Propagation

Idea: If a clause has only one unassigned literal, that literal must be true

Example:

Clause: (x ∨ y ∨ ¬z)
Assignment: x = false, y = false
Remaining: ¬z
Conclusion: z must be false

Pure Literal Elimination

Idea: If a variable appears only in positive or negative form, assign it to satisfy all clauses

Example:

Formula: (x ∨ y) ∧ (¬y ∨ z) ∧ (x ∨ ¬z)
Variable x appears only positive
Assignment: x = true
Simplified: (¬y ∨ z) ∧ (¬z ∨ true) = (¬y ∨ z)

Modern SAT Solvers

Techniques:

  • Conflict-driven clause learning (CDCL): Learn from conflicts
  • Variable ordering heuristics: Choose most constrained variables
  • Restart strategies: Restart search with learned clauses
  • Preprocessing: Simplify formula before solving

Examples: MiniSat, CaDiCaL, Glucose

Practical Applications

Hardware Verification

Application: Verify circuits satisfy specifications Process: Encode circuit as SAT formula, check satisfiability Benefit: Catches design errors before fabrication

Software Verification

Application: Verify programs satisfy properties Process: Encode program and property as SAT, check satisfiability Benefit: Finds bugs automatically

Constraint Satisfaction

Application: Solve constraint satisfaction problems Process: Encode constraints as SAT formula Benefit: Leverages powerful SAT solvers

Planning and Scheduling

Application: Find valid plans or schedules Process: Encode constraints as SAT formula Benefit: Optimal solutions

Satisfiability vs Unsatisfiability

Satisfiable Formulas

Definition: Formula has at least one satisfying assignment

Example:

(x ∨ y) ∧ (¬x ∨ z)
Satisfying assignment: x = true, y = false, z = true

Unsatisfiable Formulas

Definition: No assignment satisfies the formula

Example:

(x ∨ y) ∧ (¬x ∨ ¬y) ∧ (¬x ∨ ¬z) ∧ (x ∨ z)
No assignment satisfies all clauses

Proof of Unsatisfiability

Resolution Proof: Derive empty clause through resolution

Example:

1. (x ∨ y)
2. (¬x ∨ ¬y)
3. (¬x ∨ ¬z)
4. (x ∨ z)
5. y ∨ ¬y        (resolve 1, 2)
6. ¬x ∨ z        (resolve 2, 4)
7. z ∨ z         (resolve 3, 6)
8. z              (simplify 7)
9. ¬z             (from 3, 4)
10. □             (resolve 8, 9)

Glossary

Assignment: Mapping of variables to truth values

Clause: Disjunction of literals

CNF: Conjunctive normal form

DPLL: Davis-Putnam-Logemann-Loveland algorithm

Literal: Variable or its negation

NP-Complete: Hardest problems in NP

Pure Literal: Variable appearing only positive or negative

SAT: Boolean satisfiability problem

Satisfiable: Formula has satisfying assignment

Unit Clause: Clause with single literal

Unsatisfiable: No satisfying assignment

Practice Problems

Problem 1: Convert (x → y) ∧ (y → z) to CNF.

Solution:

(x → y) ∧ (y → z)
= (¬x ∨ y) ∧ (¬y ∨ z)
Already in CNF

Problem 2: Determine if (x ∨ y) ∧ (¬x ∨ ¬y) is satisfiable.

Solution:

Try x = true, y = false:
(true ∨ false) ∧ (false ∨ true) = true ∧ true = true
Satisfiable with assignment x = true, y = false

Problem 3: Apply unit propagation to (x ∨ y ∨ z) ∧ (¬x) ∧ (¬y ∨ w).

Solution:

Clause (¬x) is unit, so x = false
Simplify (x ∨ y ∨ z) with x = false: (y ∨ z)
Result: (y ∨ z) ∧ (¬y ∨ w)

Conclusion

The Boolean satisfiability problem represents a fundamental challenge in computer science. Despite being NP-complete, modern SAT solvers have become remarkably effective at solving practical instances. Understanding SAT—its complexity, algorithms, and applications—is essential for anyone working in automated reasoning, formal verification, or constraint solving.

The success of SAT solvers demonstrates that theoretical hardness doesn’t preclude practical effectiveness. By combining algorithmic insights, heuristics, and engineering, SAT solvers have become indispensable tools in modern computing.

Comments