Introduction

Let’s jump into NP-completeness territory with the Boolean Satisfiability Problem (SAT). Given a Boolean formula, can you find an assignment of true/false values to its variables that makes the formula evaluate to true? It’s the first problem proven NP-complete and a cornerstone of complexity theory.

Problem Statement

A Boolean formula is typically given in conjunctive normal form (CNF):

$$ f = C_1 \land C_2 \land \cdots \land C_m, $$

where each clause $C_j$ is a disjunction of literals (variables or their negations), e.g., $(x \lor \lnot y \lor z)$. The SAT question is:

Does there exist an assignment $v: {x_1,\dots,x_n} \to {\mathrm{True},\mathrm{False}}$ such that $f(v)=\mathrm{True}$?

Example

Consider

$$ f = (x \lor y) \land (\lnot x \lor z) \land (\lnot y \lor \lnot z). $$

  • Try assignment $x=\mathrm{True}, y=\mathrm{False}, z=\mathrm{False}$.

    • Clause 1: $x \lor y = \mathrm{True} \lor \mathrm{False} = \mathrm{True}.$
    • Clause 2: $\lnot x \lor z = \mathrm{False} \lor \mathrm{False} = \mathrm{False}.$
    • Clause 3: $\lnot y \lor \lnot z = \mathrm{True} \lor \mathrm{True} = \mathrm{True}.$

Clause 2 fails here, so try $x=\mathrm{True}, y=\mathrm{False}, z=\mathrm{True}$:

  • Clause 1: True, Clause 2: $\lnot x \lor z = \mathrm{False} \lor \mathrm{True} = \mathrm{True}$, Clause 3: $\lnot y \lor \lnot z = \mathrm{True} \lor \mathrm{False} = \mathrm{True}$. This assignment satisfies all clauses, so $f$ is satisfiable.

Algorithmic Landscape

  • SAT is NP-complete, meaning:

    1. It belongs to NP: given an assignment, we can check all clauses in $O(m\cdot k)$ time, where $k$ is max clause size.
    2. Every problem in NP can be polynomial-time reduced to SAT (Cook–Levin theorem).

  • Exact algorithms exist (e.g., DPLL, backtracking, clause learning) that work well in practice for many instances, but worst-case runtime is exponential.

Why It Matters

  • Industry Impact: SAT solvers power hardware verification, software testing, planning, and more.
  • Theoretical Significance: SAT’s NP-completeness opened the floodgates for identifying thousands of NP-complete problems via reductions.

Wrap-Up

SAT sits at the heart of NP-completeness, every problem in NP can be encoded as a SAT instance. Next up: the 3-SAT Problem and a deeper dive into why it’s NP-complete!