NP-Completeness

The previous lesson left us with a claim: inside $NP$ there are problems that are universally hardest, and they decide the $P$ versus $NP$ question. This lesson makes that claim precise. We define what it means to be hardest, identify the first such problem (SAT, via the Cook–Levin theorem), and then show how a single starting problem yields many more equally hard problems through reductions. Finally we state the four-step recipe for proving a new problem $NP$ -complete.

NP-hard and NP-complete

Recall that $A \leq_{P} B$ means $A$ is no harder than $B$ . Now imagine a problem $B$ that every problem in $NP$ is no harder than. Such a $B$ is at least as hard as everything in $NP$ , a ceiling on the whole class.

The distinction matters. $NP$ -hardness is a pure lower bound: $B$ is as hard as anything in $NP$ , but $B$ need not itself be in $NP$ ; it could be far harder, even undecidable. $NP$ -complete problems are the ones that are hardest and still belong to $NP$ : they sit exactly at the frontier. They are the hardest problems whose solutions we can still efficiently check.¹

NP

-complete is the intersection of

NP

and

NP

-hard; some

NP

-hard problems lie outside

NP

Two consequences follow.

All $NP$ -complete problems stand or fall together. Suppose $B$ is $NP$ -complete and someone finds a polynomial-time algorithm for $B$ . Then for any $A \in NP$ we have $A \leq_{P} B$ , so $A$ is solvable in polynomial time too, every $A$ at once. Hence $any NP -complete problem \in P ⟹ P = NP .$ Conversely, proving any single $NP$ -complete problem requires super-polynomial time would prove $P \neq = NP$ . In this sense the thousands of known $NP$ -complete problems are a single problem in many guises.
Transitivity bootstraps the class. If $C$ is $NP$ -complete and we show $C \leq_{P} D$ for some $D \in NP$ , then $D$ is $NP$ -complete too: every $A \in NP$ satisfies $A \leq_{P} C \leq_{P} D$ , and $\leq_{P}$ composes. This is how one $NP$ -complete problem yields many.

Transitivity bootstrap: every

A \in NP

already reduces to the known-complete

C

; one new reduction

C \leq_{P} D

extends the chain, so

D

inherits hardness from the whole class.

Transitivity spreads $NP$ -completeness from one problem to the next, but it presupposes we already have a first $NP$ -complete problem to start from. Where does the first one come from?

The first one: Cook–Levin

The breakthrough, proved independently by Stephen Cook (1971) and Leonid Levin, is that a natural problem is $NP$ -complete from scratch, without reducing from anything, by reasoning directly about computation itself.

The problem is boolean satisfiability, or SAT.

Proof sketch. That SAT is in $NP$ is easy: a satisfying assignment is a certificate, and evaluating $φ$ on it takes linear time. The deep half is $NP$ -hardness: showing that every $A \in NP$ reduces to SAT, by encoding computation as logic. Any $A \in NP$ has a polynomial-time verifier $V$ . For an input $x$ , the question does some certificate make $V$ accept $x$ ? is just a restatement of is $A$ 's answer yes? Cook and Levin build, in polynomial time, a boolean formula $φ_{x}$ whose variables describe the verifier's entire step-by-step execution, with clauses that force the variables to obey the machine's rules. Then $φ_{x}$ is satisfiable if and only if some certificate makes $V$ accept — the clauses are engineered so that a satisfying assignment is sound (it can only encode a genuinely accepting run) and complete (every accepting run yields one). So deciding SAT on $φ_{x}$ decides $A$ on $x$ . Because this works for an arbitrary problem in $NP$ , SAT is $NP$ -hard.² $□$

Cook–Levin encodes a verifier's whole computation on

(x, y)

as one formula

F_{x}

, satisfiable iff some

y

accepts.

sat.pypython

from itertools import product
from typing import Iterable, Iterator, NamedTuple, Optional

# A truth assignment maps each variable name to True or False.
Assignment = dict[str, bool]

class Literal(NamedTuple):
  """
    One occurrence of a variable in a clause: its name and whether it is\n
    negated. `Literal("x", False)` is the literal x; `Literal("x", True)`\n
    is the literal not-x.\n
  """
  variable: str
  negated: bool

  def is_satisfied_by(self, assignment: Assignment) -> bool:
    """
      Whether this literal evaluates to true under `assignment`.\n
    """
    value: bool = assignment[self.variable]
    return (not value) if self.negated else value

  def __repr__(self) -> str:
    return f"{'¬' if self.negated else ''}{self.variable}"

class Clause(NamedTuple):
  """
    A disjunction (OR) of literals; true when any one literal is true.\n
  """
  literals: tuple[Literal, ...]

  def is_satisfied_by(self, assignment: Assignment) -> bool:
    """
      Whether some literal in this clause is true under `assignment`.\n
    """
    return any(literal.is_satisfied_by(assignment) for literal in self.literals)

class Formula(NamedTuple):
  """
    A CNF formula: a conjunction (AND) of clauses, true only when every\n
    clause is true.\n
  """
  clauses: tuple[Clause, ...]

  @property
  def variables(self) -> list[str]:
    """
      Every distinct variable name, in first-seen order.\n
    """
    # a dict preserves first-seen order while collapsing duplicates.
    seen: dict[str, None] = {}
    for clause in self.clauses:
      for literal in clause.literals:
        seen.setdefault(literal.variable, None)

    return list(seen)

  def is_three_cnf(self) -> bool:
    """
      Whether every clause holds exactly three literals (the 3-SAT shape).\n
    """
    return all(len(clause.literals) == 3 for clause in self.clauses)

  def is_satisfied_by(self, assignment: Assignment) -> bool:
    """
      Whether `assignment` makes every clause — and so the whole formula —\n
      true.\n
    """
    return all(clause.is_satisfied_by(assignment) for clause in self.clauses)

def make_formula(clauses: Iterable[Iterable[tuple[str, bool]]]) -> Formula:
  """
    Build a Formula from a lightweight description: an iterable of clauses,\n
    each an iterable of `(variable, negated)` pairs. Convenient for tests\n
    and callers that would rather not nest the NamedTuples by hand.\n
  """
  # wrap each (variable, negated) pair into a Literal, each clause into a Clause.
  built: list[Clause] = []
  for raw_clause in clauses:
    literals: tuple[Literal, ...] = tuple(
      Literal(variable, negated) for variable, negated in raw_clause
    )
    built.append(Clause(literals))

  return Formula(tuple(built))

def verify(formula: Formula, assignment: Assignment) -> bool:
  """
    The SAT verifier: check that `assignment` is a satisfying certificate\n
    for `formula`. Runs in time linear in the formula's size — this is the\n
    proof that SAT lies in NP.\n
  """
  return formula.is_satisfied_by(assignment)

def all_assignments(variables: list[str]) -> Iterator[Assignment]:
  """
    Yield every truth assignment over `variables` — all 2^k of them.\n
  """
  for values in product((False, True), repeat=len(variables)):
    yield dict(zip(variables, values))

def satisfiable(formula: Formula) -> Optional[Assignment]:
  """
    Decide SAT by exhaustive search: return a satisfying assignment if one\n
    exists, otherwise None. Takes O(2^k) over k variables — the brute force\n
    no polynomial algorithm is known to beat. The empty formula (no clauses)\n
    is vacuously satisfiable, witnessed by the empty assignment.\n
  """
  # try every truth assignment; return the first that satisfies the formula.
  for assignment in all_assignments(formula.variables):
    if formula.is_satisfied_by(assignment):
      return assignment

  return None

With one $NP$ -complete problem in hand, transitivity takes over.

The reduction web

Karp's 1972 paper reduced SAT to twenty-one other problems, showing them all $NP$ -complete and launching the field.³ A convenient intermediate is 3-SAT, the special case of SAT in which the formula is in conjunctive normal form with exactly three literals per clause, a big AND of small ORs such as $(x_{1} \lor \neg x_{2} \lor x_{3}) \land (\neg x_{1} \lor x_{2} \lor x_{4})$ . One can show $SAT \leq_{P} 3-SAT$ , so 3-SAT is itself $NP$ -complete, and its rigid structure makes it the favorite starting point for further reductions.

The $SAT \leq_{P} 3-SAT$ reduction is a small gadget worth seeing, because it shows how a clause of the wrong width is padded or split to exactly three literals using fresh variables. A clause with one literal $(a)$ becomes $(a \lor y_{1} \lor y_{2}) \land (a \lor \neg y_{1} \lor y_{2}) \land (a \lor y_{1} \lor \neg y_{2}) \land (a \lor \neg y_{1} \lor \neg y_{2})$ with new variables $y_{1}, y_{2}$ : the four clauses together force $a$ true regardless of $y_{1}, y_{2}$ . A long clause $(a_{1} \lor a_{2} \lor a_{3} \lor a_{4} \lor a_{5})$ is chained with fresh variables $z_{i}$ into $(a_{1} \lor a_{2} \lor z_{1}) \land (\neg z_{1} \lor a_{3} \lor z_{2}) \land (\neg z_{2} \lor a_{4} \lor a_{5})$ : a satisfying assignment of the original picks some true $a_{j}$ , and the $z_{i}$ can be set to carry the still unsatisfied signal down the chain until that $a_{j}$ discharges it. Each new clause has exactly three literals, the blow-up is linear, and satisfiability is preserved in both directions — a clean polynomial reduction.

From 3-SAT the web branches out. A small portion:

Reduction web of NP-complete problems branching out from SAT and 3-SAT.

Every arrow $X \to Y$ is a reduction $X \leq_{P} Y$ ; following arrows back to SAT certifies each box as $NP$ -complete. (The arrows above record one route to each result, not the only one; many of these problems also reduce to each other directly, as we saw with $Independent-Set$ and Clique last lesson.)

A worked reduction: 3-SAT to Independent-Set

Let us actually build one arrow, the classic $3-SAT \leq_{P} Independent-Set$ . We are given a 3-CNF formula $φ$ with $m$ clauses and must produce a graph $G$ and integer $k$ such that $G$ has an independent set of size $k$ exactly when $φ$ is satisfiable.

The construction. For each clause, create a triangle of three vertices, one per literal. So clause $(x_{1} \lor \neg x_{2} \lor x_{3})$ becomes three mutually-connected vertices labeled $x_{1}$ , $\neg x_{2}$ , $x_{3}$ . Then add a conflict edge between any two vertices in different triangles that hold contradictory literals: one labeled $x_{i}$ and another labeled $\neg x_{i}$ . Finally set $k = m$ , the number of clauses. This is clearly polynomial: $3 m$ vertices and at most $O (m^{2})$ edges. The construction is correct in both directions.

Proof (correctness). The two directions of the biconditional are the soundness and completeness of the reduction. Soundness ( $G$ has the set $\Rightarrow φ$ satisfiable): an independent set may pick at most one vertex from each triangle (the three are mutually adjacent), so an independent set of size $k = m$ must pick exactly one literal from every clause. The conflict edges forbid choosing both $x_{i}$ and $\neg x_{i}$ anywhere, so the chosen literals are mutually consistent — they describe a partial truth assignment. Setting each chosen literal true satisfies one literal in every clause, hence satisfies $φ$ ; the yes for $G$ never arises from an unsatisfiable formula. Completeness ( $φ$ satisfiable $\Rightarrow G$ has the set): a satisfying assignment picks, from each clause, one true literal; those $m$ vertices form an independent set, since two true literals can never be a variable and its negation, so every satisfiable formula does map to a yes. Therefore $φ is satisfiable \leftrightarrow G has an independent set of size m,$ which is what a valid reduction requires.⁴ $□$

Clause triangles with dashed conflict edges for the 3-SAT to Independent-Set reduction.

Solid edges are the per-clause triangles; dashed edges connect contradictory literals ( $x_{1}$ vs. $\neg x_{1}$ , and $\neg x_{2}$ vs. $x_{2}$ ). Picking one non-conflicting vertex per triangle amounts to a consistent satisfying choice.

A fully worked instance. Take the concrete formula $φ = (x_{1} \lor \neg x_{2} \lor x_{3}) \land (\neg x_{1} \lor x_{2} \lor x_{4}) .$ It has $m = 2$ clauses, so the construction builds $3 m = 6$ vertices in two triangles and sets $k = 2$ . The conflict edges join $x_{1}$ (clause 1) to $\neg x_{1}$ (clause 2), and $\neg x_{2}$ (clause 1) to $x_{2}$ (clause 2) — the two variable/negation collisions across the triangles. Now find a size- $2$ independent set: pick $x_{1}$ from the first triangle and $x_{2}$ from the second. These two are not joined by a conflict edge (the conflicts are $x_{1}$ – $\neg x_{1}$ and $\neg x_{2}$ – $x_{2}$ , neither of which is the pair ${x_{1}, x_{2}}$ ), and they sit in different triangles, so the two vertices are non-adjacent — an independent set of size $2 = k$ . Reading the chosen literals back as an assignment gives $x_{1} = true$ , $x_{2} = true$ (and $x_{3}, x_{4}$ free): the first clause is satisfied by $x_{1}$ , the second by $x_{2}$ , so $φ$ is satisfiable. The reduction turned a logic question into a graph question and back, exactly as the correctness proof requires.

Choosing

{x_{1}, x_{2}}

— one vertex per triangle, no conflict edge between them — is a size-

2

independent set, i.e. a satisfying assignment.

three_sat_to_independent_set.pypython

from itertools import combinations
from typing import NamedTuple, Optional

from graph import Graph

from sat import Assignment, Formula, Literal

# A vertex label names the clause index, the literal's position within that
# clause, and the literal itself. Including the position keeps the three corners
# of every triangle distinct even when a clause repeats a literal (e.g.
# x ∨ x ∨ x), so each clause always contributes exactly three vertices.
VertexLabel = tuple[int, int, Literal]

class Reduction(NamedTuple):
  """
    The output of the reduction: the constructed graph, the target size k,\n
    and the source formula kept for decoding a witness back to an assignment.\n
  """
  graph: Graph[VertexLabel]
  target_size: int
  formula: Formula

def reduce_three_sat_to_independent_set(formula: Formula) -> Reduction:
  """
    Build the Independent-Set instance for a 3-CNF `formula`. Returns the\n
    graph, the target k = m (number of clauses), and the formula. Polynomial:\n
    3m vertices and O(m²) edges.\n
  """
  graph: Graph[VertexLabel] = Graph(directed=False)

  # one vertex per literal occurrence; remember each clause's three labels.
  clause_labels: list[list[VertexLabel]] = []
  for clause_index, clause in enumerate(formula.clauses):
    labels: list[VertexLabel] = [
      (clause_index, position, literal)
      for position, literal in enumerate(clause.literals)
    ]
    for label in labels:
      graph.add_vertex(label)
    clause_labels.append(labels)

  # triangle edges: every pair of vertices inside the same clause.
  for labels in clause_labels:
    for first_label, second_label in combinations(labels, 2):
      graph.add_edge(first_label, second_label)

  # conflict edges: pair up vertices from two different clauses.
  for first_clause, second_clause in combinations(clause_labels, 2):
    for first_label in first_clause:
      for second_label in second_clause:
        # join contradictory literals x and ¬x on the same variable.
        first_literal, second_literal = first_label[2], second_label[2]
        if (
          first_literal.variable == second_literal.variable
          and first_literal.negated != second_literal.negated
        ):
          graph.add_edge(first_label, second_label)

  return Reduction(graph, len(formula.clauses), formula)

def is_independent_set(
  graph: Graph[VertexLabel],
  chosen: set[VertexLabel],
) -> bool:
  """
    Whether `chosen` is an independent set: no edge joins two of its members.\n
  """
  # reject if any edge has both endpoints inside the chosen set.
  for edge in graph.edges():
    if edge.source.label in chosen and edge.target.label in chosen:
      return False

  return True

def maximum_independent_set(
  graph: Graph[VertexLabel],
) -> set[VertexLabel]:
  """
    A largest independent set, found by brute force over all vertex subsets.\n
    Exponential — Independent-Set is itself NP-complete — and used here only\n
    to exercise the reduction on small graphs.\n
  """
  labels: list[VertexLabel] = [vertex.label for vertex in graph.vertices]

  # scan subsets largest-first; the first independent one is a maximum set.
  for size in range(len(labels), -1, -1):
    for candidate in combinations(labels, size):
      chosen: set[VertexLabel] = set(candidate)
      if is_independent_set(graph, chosen):
        return chosen

  # unreachable: the empty set is always independent and is tried at size 0.
  return set()

def assignment_from_independent_set(
  reduction: Reduction,
  chosen: set[VertexLabel],
) -> Assignment:
  """
    Decode a size-k independent set back into a satisfying assignment: set\n
    each chosen literal true, then fill any untouched variable arbitrarily.\n
    Assumes `chosen` is a valid witness (one consistent literal per clause).\n
  """
  # each chosen literal pins its variable to whatever makes that literal true.
  assignment: Assignment = {}
  for _clause_index, _position, literal in chosen:
    assignment[literal.variable] = not literal.negated

  # fill any variable the witness never touched with an arbitrary value.
  for variable in reduction.formula.variables:
    assignment.setdefault(variable, False)

  return assignment

def solve_via_independent_set(formula: Formula) -> Optional[Assignment]:
  """
    Decide 3-SAT through the reduction: build the graph, find a maximum\n
    independent set, and accept iff it reaches size k = m, decoding it into\n
    a satisfying assignment. Returns None when no such set exists.\n
  """
  # build the graph and find its largest independent set.
  reduction: Reduction = reduce_three_sat_to_independent_set(formula)
  chosen: set[VertexLabel] = maximum_independent_set(reduction.graph)

  # accept iff the set reaches size k = m, then decode it into an assignment.
  if len(chosen) < reduction.target_size:
    return None

  return assignment_from_independent_set(reduction, chosen)

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

The recipe: proving a new problem NP-complete

Once a stockpile of $NP$ -complete problems exists, classifying a new problem $X$ follows a fixed procedure. To prove $X$ is $NP$ -complete, carry out four steps.

Show $X \in NP$ . Describe a polynomial-size certificate for yes-instances and argue it can be checked in polynomial time. This is usually the easy step, but skipping it is a real error: an $NP$ -hard problem outside $NP$ is hard but not complete.
Choose a known $NP$ -complete problem $Y$ to reduce from. Pick one whose structure resembles $X$ — 3-SAT for logical or gadget-style constraints, $Vertex-Cover$ or $Independent-Set$ for graph selection, $Subset-Sum$ or $Partition$ for numeric targets, $Hamiltonian-Cycle$ for routing.
Give a polynomial-time reduction $Y \leq_{P} X$ . Construct, from an arbitrary instance of $Y$ , an instance of $X$ . This is the creative step of the proof. Mind the direction: you transform $Y$ 's instance into $X$ 's, so that solving $X$ would solve $Y$ . Reducing the wrong way ( $X \leq_{P} Y$ ) proves nothing about $X$ 's hardness.
Prove the reduction correct. Establish the if and only if, which is exactly the completeness and soundness of the map. Completeness: a yes-instance of $Y$ maps to a yes-instance of $X$ (no true case lost). Soundness: conversely every yes-instance of $X$ comes only from a yes-instance of $Y$ (no false yes invented). Both directions are mandatory; dropping completeness lets false negatives slip through, dropping soundness lets false positives.

Steps 1 and 2 are bookkeeping; steps 3 and 4 are the substance.⁵ The worked reduction above is this recipe applied with $Y = 3-SAT$ and $X = Independent-Set$ : the triangles-and-conflicts gadget is step 3, and the two-direction argument is step 4.

The tractability boundary and what hard costs

The reduction web draws a line, and the sharpest way to see where it falls is a pair of problems that look nearly identical yet land on opposite sides. 2-SAT, the restriction of SAT to two literals per clause, is solvable in linear time: build the implication graph (each clause $(a \lor b)$ becomes $\neg a \Rightarrow b$ and $\neg b \Rightarrow a$ ), and the formula is satisfiable exactly when no variable $x$ and its negation $\neg x$ share a strongly connected component — one pass of the SCC algorithm, worked out in full in the 2-SAT lesson. Add one literal per clause and 3-SAT becomes $NP$ -complete. The jump from $2$ to $3$ is the whole story, and it is not an accident: Schaefer's dichotomy theorem (1978) proves that every boolean constraint-satisfaction problem is either in $P$ or $NP$ -complete, with nothing in between, and it names the exact conditions that put a problem in $P$ .⁶

Trace the linear-time test on $ψ = (x_{1} \lor x_{2}) \land (\neg x_{1} \lor x_{2}) \land (\neg x_{2} \lor x_{3})$ . Each clause $(a \lor b)$ contributes both implications $\neg a \Rightarrow b$ and $\neg b \Rightarrow a$ , giving six directed edges: from the first clause, $\neg x_{1} \Rightarrow x_{2}$ and $\neg x_{2} \Rightarrow x_{1}$ ; from the second, $x_{1} \Rightarrow x_{2}$ and $\neg x_{2} \Rightarrow \neg x_{1}$ ; from the third, $x_{2} \Rightarrow x_{3}$ and $\neg x_{3} \Rightarrow \neg x_{2}$ . Every path in this graph forces truth values: following the edges out of $x_{1}$ , we reach $x_{2}$ then $x_{3}$ , and no path ever leads from a literal to its own negation, so no variable shares an SCC with its complement. The formula is satisfiable — indeed $x_{1} = x_{2} = x_{3} = true$ works. Had we instead added the clauses $(\neg x_{2}) \land (x_{2})$ , the graph would route $x_{2} \Rightarrow \neg x_{2} \Rightarrow x_{2}$ , collapsing $x_{2}$ and $\neg x_{2}$ into one SCC and certifying unsatisfiability — all detected by a single SCC pass, never any search.

A knife-edge boundary: 2-SAT is linear-time, 3-SAT is NP-complete; Schaefer's theorem says CSPs are always one or the other, never in between.

Two deeper results sharpen how hard. The Exponential Time Hypothesis (ETH), conjectured by Impagliazzo and Paturi, says 3-SAT cannot be solved in $2^{o (n)}$ time — not merely that it is not polynomial, but that even sub-exponential time is out of reach.⁷ ETH is now the standard tool for proving that specific problems need $2^{Ω (n)}$ or $n^{Ω (k)}$ time, giving fine-grained lower bounds far below the crude $P$ -versus- $NP$ divide. And the PCP theorem (Arora–Safra and Arora–Lund–Motwani–Sudan–Szegedy, 1998) recharacterizes $NP$ so strongly that it makes approximation itself hard: for many problems, even finding a solution within some constant factor of optimal is $NP$ -complete.⁸ That result leads to the approximation lesson, where we ask not can we solve it exactly but how close can we provably get.

Takeaways

$X$ is $NP$ -hard if every problem in $NP$ reduces to it (a lower bound); it is $NP$ -complete if it is also in $NP$ , hardest among the efficiently-checkable problems.
All $NP$ -complete problems share one fate: a polynomial-time algorithm for any of them would prove $P = NP$ and solve them all.
Cook–Levin anchors the theory: SAT is $NP$ -complete, proved directly by encoding any verifier's computation as a boolean formula. From it, 3-SAT and a vast reduction web follow by transitivity.
The $3-SAT \leq_{P} Independent-Set$ reduction (a triangle per clause plus conflict edges, with $k = m$ ) is the model gadget reduction.
To prove a new problem $NP$ -complete: (1) show membership in $NP$ , (2) pick a known $NP$ -complete $Y$ , (3) reduce $Y \leq_{P} X$ in polynomial time, (4) prove the equivalence both ways, always reducing from the hard problem.

CLRS, Ch. 34 — NP-Completeness (§34.1): the definitions of $NP$ -hard (a lower bound) and $NP$ -complete (hard and in $NP$ ). ↩
CLRS, Ch. 34 — NP-Completeness (§34.3): the Cook–Levin theorem that SAT is $NP$ -complete, proved by encoding a verifier's computation as a boolean formula. ↩
Skiena, §11 — NP-Completeness: Karp's 1972 reductions and the web of $NP$ -complete problems growing from satisfiability. ↩
Erickson, Ch. 12 — NP-Hardness: the gadget reduction $3-SAT \leq_{P} Independent-Set$ (clause triangles plus conflict edges, $k = m$ ). ↩
CLRS, Ch. 34 — NP-Completeness (§34.4): the standard four-step recipe for proving a new problem $NP$ -complete. ↩
Thomas J. Schaefer, The Complexity of Satisfiability Problems, STOC 1978 — every boolean CSP is either in $P$ or $NP$ -complete, with the exact tractable cases characterized (2-SAT, Horn-SAT, affine, and duals). ↩
Russell Impagliazzo and Ramamohan Paturi, On the Complexity of $k$ -SAT, Journal of Computer and System Sciences 62(2), 2001 — the Exponential Time Hypothesis, that 3-SAT has no $2^{o (n)}$ algorithm. ↩
Sanjeev Arora and Shmuel Safra, Probabilistic Checking of Proofs, and Arora, Lund, Motwani, Sudan, Szegedy, Proof Verification and the Hardness of Approximation Problems, Journal of the ACM, 1998 — the PCP theorem and inapproximability. ↩

NP-hard and NP-complete

The first one: Cook–Levin

The reduction web

A worked reduction: 3-SAT to Independent-Set

The recipe: proving a new problem NP-complete

The tractability boundary and what hard costs

Takeaways

Footnotes