P, NP, and Reductions

Nearly every problem so far in this course has a fast algorithm: sorting in $O(n\log n)$, shortest paths in near-linear time, spanning trees almost for free. It is tempting to believe that every problem yields to a clever enough algorithm, but this is not so. There is a large, practical family of problems (scheduling, routing, packing, constraint satisfaction) for which, after more than half a century of effort, nobody has found an algorithm that is fast on every instance, and for which we have strong reasons to suspect none exists.

The theory of intractability is how we make that suspicion precise. Its central insight, due to Cook, Levin, and Karp, is that thousands of these problems are equivalent to one another. Solve any one of them quickly and you solve them all; prove any one of them hard and you have proved them all hard. This lesson assembles the three ideas needed to state that claim: decision problems, the classes $\mathsf{P}$ and $\mathsf{NP}$, and reductions.

Decision problems

To classify difficulty cleanly we restrict attention to problems with a yes-or-no answer. A decision problem asks, of each input, a single question whose answer is yes or no.

This seems like a severe restriction; surely we usually want to find a shortest tour, not merely learn whether a short one exists. But the two are rarely far apart. The optimization problem find the cheapest tour has a decision twin: is there a tour of cost at most $k$? If we can answer the decision question quickly for every $k$, a binary search over $k$ determines the optimal cost, and a little more work recovers the tour itself. Decision problems lose almost nothing and gain a clean theory, so they are the objects we classify.

from typing import Callable, Optional

def minimum_feasible_cost(
  feasible: Callable[[int], bool],
  low: int,
  high: int,
) -> Optional[int]:
  """
    The smallest threshold in `[low, high]` for which `feasible` is true,\n
    or None if even `high` is infeasible. `feasible` must be monotone:\n
    false up to some point, then true forever after.\n
  """
  if not feasible(high):
    return None

  # invariant: feasible(high) is true, feasible(low - 1) is false.
  while low < high:
    middle: int = (low + high) // 2
    if feasible(middle):
      high = middle
    else:
      low = middle + 1
  return low

def maximum_feasible_value(
  feasible: Callable[[int], bool],
  low: int,
  high: int,
) -> Optional[int]:
  """
    The largest threshold in `[low, high]` for which `feasible` is true,\n
    or None if even `low` is infeasible. Here `feasible` is monotone the\n
    other way: true up to some point, then false (e.g. "is there a solution\n
    of value at least `threshold`?").\n
  """
  if not feasible(low):
    return None

  # invariant: feasible(low) is true, feasible(high + 1) is false.
  while low < high:
    middle: int = (low + high + 1) // 2
    if feasible(middle):
      low = middle
    else:
      high = middle - 1
  return low

A word on encoding and size. An input is a string of bits; the size of an instance is the length of that string. We always assume a reasonable encoding (integers in binary, graphs as adjacency lists) because an artificially bloated encoding (say, integers in unary) could make a slow algorithm look fast. With reasonable encodings fixed, polynomial in the input size is a stable, machine-independent notion.

The class P

Some decision problems have algorithms whose running time is bounded by a polynomial in the input size. These are the problems we regard as tractable.

Why polynomial, and not, say, $n^2$ or better? Because polynomials are closed under the operations we constantly perform: addition, multiplication, and especially composition. If a polynomial-time algorithm calls a polynomial-time subroutine a polynomial number of times, the whole thing is still polynomial. This closure is what makes $\mathsf{P}$ stable: it does not depend on the particular machine model, the programming language, or whether we count $n^2$ as fast. Everything we have called efficient so far (sorting, shortest paths, matching, linear programming) lives in $\mathsf{P}$. The class is our formal stand-in for feasible.¹

The class NP

Now consider a problem like Hamiltonian Cycle: given a graph $G$, is there a cycle that visits every vertex exactly once? We know of no polynomial-time algorithm to decide this. But notice an asymmetry. If a benevolent oracle hands us a cycle and claims it is Hamiltonian, we can check the claim in linear time: walk the cycle, confirm it visits each vertex once and uses real edges. Finding the cycle seems hard; verifying a proposed cycle is easy.

This is the defining feature of the class $\mathsf{NP}$: a problem is in $\mathsf{NP}$ if every yes-instance has a short proof, a certificate, that can be checked quickly.

The two bullets restate the completeness and soundness of the verifier, read as a decision procedure for does $x$ have an accepting certificate? The first says $V$ is complete: every genuine yes is witnessed by some certificate it accepts (no false negatives). The second says $V$ is sound: no certificate can fool it into accepting a no-instance (no false positives). A verifier missing either guarantee fails to define the language.

The name $\mathsf{NP}$ stands for nondeterministic polynomial time: one can equivalently picture a machine that guesses the certificate $y$ and then verifies it. The verifier definition avoids speaking of magical guessing; it asks only that correct yes-answers come with checkable evidence.²

Three points deserve emphasis.

• The certificate must be short (polynomial length) and the check must be fast (polynomial time). For Hamiltonian Cycle the certificate is the cycle; for SAT (is a boolean formula satisfiable?) it is a satisfying assignment; for $\text{Subset-Sum}$ it is the subset that hits the target.
• The asymmetry between yes and no is real. $\mathsf{NP}$ guarantees a certificate only for yes-instances. The problem of certifying a no (there is no Hamiltonian cycle) need not be in $\mathsf{NP}$; that belongs to a companion class, $\mathsf{co}\text{-}\mathsf{NP}$.
• Every problem in $\mathsf{P}$ is in $\mathsf{NP}$. If we can solve a problem in polynomial time, we can ignore any offered certificate and just decide the answer directly; an empty certificate suffices. So $\mathsf{P}\subseteq \mathsf{NP}$.

from __future__ import annotations

from typing import Sequence

from graph import Graph

def verify_hamiltonian_cycle(
  graph: Graph[int],
  cycle: Sequence[int],
) -> bool:
  """
    Check whether `cycle` is a Hamiltonian cycle of `graph`: an ordering of\n
    every vertex exactly once such that consecutive vertices (and the last\n
    back to the first) are joined by edges. Runs in O(V + E).\n
  """
  vertex_count: int = len(graph)
  if vertex_count == 0:
    return False

  # the certificate must list every vertex exactly once.
  if len(cycle) != vertex_count:
    return False
  if set(cycle) != set(graph.labels):
    return False

  # every consecutive pair, wrapping around, must be a real edge.
  for position in range(vertex_count):
    current: int = cycle[position]
    following: int = cycle[(position + 1) % vertex_count]
    if graph.vertex(current).edge_to(following) is None:
      return False
  return True

def verify_sat_assignment(
  clauses: Sequence[Sequence[int]],
  assignment: dict[int, bool],
) -> bool:
  """
    Check whether `assignment` satisfies a CNF formula. Each clause is a\n
    sequence of literals; a literal is a non-zero integer whose magnitude is\n
    the variable and whose sign is its polarity (negative means negated). A\n
    clause is satisfied when at least one literal is true; the formula is\n
    satisfied when every clause is. Runs in O(total literals).\n
  """
  # a literal is true when the variable's value matches its polarity.
  def literal_is_true(literal: int) -> bool:
    return assignment.get(abs(literal), False) == (literal > 0)

  # every clause must have at least one true literal.
  for clause in clauses:
    if not any(literal_is_true(literal) for literal in clause):
      return False
  return True

def verify_subset_sum(
  numbers: Sequence[int],
  target: int,
  chosen_indices: Sequence[int],
) -> bool:
  """
    Check whether the items at `chosen_indices` of `numbers` sum to `target`.\n
    Indices must be valid and distinct (a real sub-collection). Runs in\n
    O(len(chosen_indices)).\n
  """
  # indices must be distinct and in range to name a real sub-collection.
  if len(set(chosen_indices)) != len(chosen_indices):
    return False
  if any(index < 0 or index >= len(numbers) for index in chosen_indices):
    return False

  # the chosen items must sum to the target.
  return sum(numbers[index] for index in chosen_indices) == target

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)

Reductions: comparing difficulty

We want to say problem $B$ is at least as hard as problem $A$ without knowing how hard either one actually is. The device that makes this possible is a reduction: a way to convert any instance of $A$ into an instance of $B$ that has the same answer, so that an algorithm for $B$ becomes an algorithm for $A$.

That biconditional is the core of every reduction proof, and it splits into the same two obligations we ask of any decision procedure. The forward direction ($\Rightarrow$) is completeness: every yes-instance of $A$ maps to a yes-instance of $B$, so no true case is lost in translation. The backward direction ($\Leftarrow$) is soundness: a yes out of $B$ can only have come from a yes of $A$, equivalently no-instances map to no-instances, so the reduction never manufactures a false yes. Proving a reduction correct always means discharging these two directions, and we will name them as such throughout. Read $A{\le }_{P}B$ as $A$ is no harder than $B$.³ Picture this as a transform–solve–transform pipeline: take the input, transform it into an input for the other problem, hand that to a solver for $B$, then transform the solver's output back into an answer for $A$. The solver for $B$ is used as a black-box subroutine, and we never look inside it.

The dashed box is the point: a fast solver for $B$, wrapped in the fast transformers on either side, is a fast solver for $A$. For a decision problem the right-hand transformer is trivial (pass the yes/no answer through unchanged), and the pipeline collapses to the textbook definition above: apply $f$, ask the $B$-question, report the answer. For a search problem (the warm-up below) the right-hand transformer does real work, turning $B$'s witness back into a witness for $A$. Either way, the diagram encodes the two ways every reduction is used, which are mirror images of each other.

• Upper bound (tractability flows forward). If $A{\le }_{P}B$ and $B\in \mathsf{P}$, then $A\in \mathsf{P}$. Tractability of the harder problem extends to the easier one: run $f$, then the fast solver for $B$; the composition of two polynomials is a polynomial.
• Lower bound (hardness flows backward). If $A{\le }_{P}B$ and $A$ is known to be hard, then $B$ is hard too. For if $B$ had a fast algorithm, the pipeline above would give $A$ one as well, a contradiction.

The second direction is the basis of the theory of intractability. To show a new problem $B$ is hard, we reduce a known-hard problem $A$ to it. The direction is a notorious source of error: we reduce from the hard problem to the new one. Getting the arrow backwards proves nothing.

Two structural facts make ${\le }_P$ behave like an ordering of difficulty.

• Reflexivity is trivial; the load-bearing fact is that transitivity holds: if $A{\le }_{P}B$ and $B{\le }_{P}C$, then $A{\le }_{P}C$, since we just compose the two translators, and a polynomial of a polynomial is still a polynomial. Chains of reductions are the raw material of the next lesson's reduction web.

A warm-up reduction: matching reduces to flow

Reductions are not a tool reserved for hardness arguments; we have already been using them to design algorithms. The cleanest example, motivating the whole idea, is bipartite matching. We are given a set of tasks $t_1,\dots ,t_m$, a set of workers $w_1,\dots ,w_n$, and a compatibility table, where $A[i,j]$ is true when task $t_i$ can be done by worker $w_j$. A matching assigns tasks to workers so that no task and no worker is used twice; we want a matching of maximum cardinality. There is a slogan worth remembering here:

We do not write a matching algorithm from scratch. Instead we reduce $\text{Bipartite-Matching}$ to $\text{Max-Flow}$, a problem we already know how to solve, and reuse that solver. This is the pipeline of the previous section made concrete, and because matching is a search problem, the output transformer is no longer trivial.

Transform the input. Build a flow network: add a source $s$ and a sink $t$. Direct an edge $s\to t_i$ for every task, an edge $w_j\to t$ for every worker, and an edge $t_i\to w_j$ whenever $A[i,j]$ is true. Give every edge capacity $1$. The unit capacities out of $s$ and into $t$ encode the budget constraints: each task and each worker can carry at most one unit.

Solve with the black box. Run any max-flow algorithm (Ford–Fulkerson or Edmonds–Karp) and let $f^{\ast }$ be the maximum flow. The value $|f^{\ast }|$ is the size of the largest matching.

Transform the output. A flow value is just a number; the matching is recovered by reading off which compatibility edges $t_i\to w_j$ carry one unit of flow. Those edges are the assignment.

Two claims make the reduction correct, and it's worth separating them.

So the reduction is valid. The transform–solve–transform diagram now does real work: build the network ($f$), call the flow solver ($B$), decompose the integral flow into paths (the output transformer). We obtained a matching algorithm without writing one, purely because $\text{Bipartite-Matching}{\le }_P\text{Max-Flow}$.

from collections import deque
from typing import Optional, Sequence

class FlowNetwork:
  """
    A flow network on integer-labelled nodes with a residual adjacency map.\n
    `residual[source][target]` is the remaining capacity on that arc; pushing\n
    flow decrements the forward arc and increments its reverse twin.\n
  """

  def __init__(self) -> None:
    self.residual: dict[int, dict[int, int]] = {}

  def add_edge(self, source: int, target: int, capacity: int) -> None:
    """
      Add a directed arc of `capacity`, plus its zero-capacity reverse twin\n
      so the residual graph can cancel flow later.\n
    """
    # ensure both endpoints exist in the residual map.
    self.residual.setdefault(source, {})
    self.residual.setdefault(target, {})

    # add forward capacity and seed the zero-capacity reverse twin.
    self.residual[source][target] = (
      self.residual[source].get(target, 0) + capacity
    )
    self.residual[target].setdefault(source, 0)

  def _augmenting_path(self, source: int, sink: int) -> Optional[list[int]]:
    """
      A shortest source-to-sink path with spare capacity, found by BFS, as a\n
      list of nodes; or None when the sink is unreachable in the residual.\n
    """
    # BFS from the source, recording each node's discoverer in `parent`.
    parent: dict[int, int] = {source: source}
    queue: deque[int] = deque([source])
    while queue:
      current: int = queue.popleft()
      if current == sink:
        break

      # enqueue undiscovered neighbors reachable with spare capacity.
      for neighbor, capacity in self.residual[current].items():
        if capacity > 0 and neighbor not in parent:
          parent[neighbor] = current
          queue.append(neighbor)

    if sink not in parent:
      return None

    # walk parents backwards from the sink to rebuild the path.
    path: list[int] = [sink]
    while path[-1] != source:
      path.append(parent[path[-1]])
    path.reverse()
    return path

  def max_flow(self, source: int, sink: int) -> int:
    """
      The value of a maximum source-to-sink flow, via Edmonds-Karp. Mutates\n
      the residual graph so saturated forward arcs reveal the chosen flow.\n
    """
    total_flow: int = 0
    while True:
      path: Optional[list[int]] = self._augmenting_path(source, sink)
      if path is None:
        return total_flow

      # the path's bottleneck is the most we can push along it.
      bottleneck: int = min(
        self.residual[path[index]][path[index + 1]]
        for index in range(len(path) - 1)
      )

      # push the bottleneck: drain forward arcs, refill their reverse twins.
      for upstream, downstream in zip(path, path[1:]):
        self.residual[upstream][downstream] -= bottleneck
        self.residual[downstream][upstream] += bottleneck
      total_flow += bottleneck

def maximum_bipartite_matching(
  compatible: Sequence[Sequence[bool]],
) -> list[tuple[int, int]]:
  """
    A maximum matching of tasks to workers, found by reducing to max-flow.\n
    `compatible[task][worker]` is True when that pairing is allowed. Returns\n
    the matched `(task, worker)` pairs; its length is the matching's size.\n
  """
  task_count: int = len(compatible)
  worker_count: int = len(compatible[0]) if task_count else 0

  # node numbering: source = 0, tasks = 1..task_count,
  # workers = task_count+1.., sink last.
  source: int = 0
  sink: int = task_count + worker_count + 1

  def task_node(task: int) -> int:
    return 1 + task

  def worker_node(worker: int) -> int:
    return 1 + task_count + worker

  # transform the input: seed every node so isolated ones still exist.
  network: FlowNetwork = FlowNetwork()
  for node in range(sink + 1):
    network.residual.setdefault(node, {})

  # source -> task, plus a unit arc for each compatible task-worker pair.
  for task in range(task_count):
    network.add_edge(source, task_node(task), 1)
    for worker in range(worker_count):
      if compatible[task][worker]:
        network.add_edge(task_node(task), worker_node(worker), 1)

  # worker -> sink, then solve with the black box.
  for worker in range(worker_count):
    network.add_edge(worker_node(worker), sink, 1)
  network.max_flow(source, sink)

  # transform the output: a saturated task->worker arc (residual 0) is a match.
  matching: list[tuple[int, int]] = []
  for task in range(task_count):
    for worker in range(worker_count):
      if not compatible[task][worker]:
        continue
      if network.residual[task_node(task)][worker_node(worker)] == 0:
        matching.append((task, worker))
        break
  return matching

A small reduction between decision problems

The matching reduction reused an easy solver to solve another easy problem. The reductions that drive intractability go the other way, relating two decision problems with no known fast solver, but the mechanism is identical. Here is a textbook example. $\text{Independent-Set}$ asks: given a graph $G$ and integer $k$, is there a set of $k$ vertices no two of which are adjacent? Clique asks: is there a set of $k$ vertices that are all pairwise adjacent? These are the same question asked of complementary graphs.

Given an instance $(G,k)$ of $\text{Independent-Set}$, build the complement graph $\bar{G}$ on the same vertices, where $uv$ is an edge of $\bar{G}$ exactly when it is not an edge of $G$. A set $S$ is independent in $G$ (no edges inside it) precisely when $S$ is a clique in $\bar{G}$ (all edges inside it). So $(G,k)\in \text{Independent-Set}\leftrightarrow (\bar{G},k)\in \text{Clique}.$ Constructing $\bar{G}$ takes time polynomial in the size of $G$, so this is a valid reduction $\text{Independent-Set}{\le }_P\text{Clique}$, and, since complementation is its own inverse, the reverse reduction holds too. The two problems are equivalent in difficulty: a fast algorithm for either yields one for the other.⁴

from __future__ import annotations

from itertools import combinations
from typing import Hashable, Optional, Sequence, TypeVar

from graph import Graph

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

def complement_graph(graph: Graph[Label]) -> Graph[Label]:
  """
    The complement of an undirected graph on the same vertices: a pair is\n
    joined in the result exactly when it is not joined in `graph`. This is\n
    the transform `f` of the reduction, computable in O(V^2) time.\n
  """
  # start with the same vertex set and no edges.
  complement: Graph[Label] = Graph(directed=False)
  for label in graph.labels:
    complement.add_vertex(label)

  # record G's adjacencies as unordered pairs.
  present_edges: set[frozenset[Label]] = {
    frozenset((edge.source.label, edge.target.label))
    for edge in graph.edges()
  }

  # join every pair G omits.
  for first, second in combinations(graph.labels, 2):
    if frozenset((first, second)) not in present_edges:
      complement.add_edge(first, second)
  return complement

def is_independent_set(graph: Graph[Label], chosen: Sequence[Label]) -> bool:
  """
    Whether `chosen` is an independent set of `graph`: distinct vertices, no\n
    two of which are adjacent.\n
  """
  # reject duplicates: a set needs distinct vertices.
  members: set[Label] = set(chosen)
  if len(members) != len(chosen):
    return False

  # no two members may be adjacent.
  for first, second in combinations(members, 2):
    if graph.vertex(first).edge_to(second) is not None:
      return False
  return True

def is_clique(graph: Graph[Label], chosen: Sequence[Label]) -> bool:
  """
    Whether `chosen` is a clique of `graph`: distinct vertices, every pair\n
    of which is adjacent.\n
  """
  # reject duplicates: a clique needs distinct vertices.
  members: set[Label] = set(chosen)
  if len(members) != len(chosen):
    return False

  # every pair of members must be adjacent.
  for first, second in combinations(members, 2):
    if graph.vertex(first).edge_to(second) is None:
      return False
  return True

def _brute_force_clique(
  graph: Graph[Label],
  size: int,
) -> Optional[list[Label]]:
  """
    A black-box decision solver for Clique: search every size-`size` subset\n
    for one that is a clique. Exponential, standing in for the (unknown)\n
    fast solver the reduction would call.\n
  """
  if size <= 0:
    return []
  for candidate in combinations(graph.labels, size):
    if is_clique(graph, candidate):
      return list(candidate)
  return None

def find_independent_set(
  graph: Graph[Label],
  size: int,
) -> Optional[list[Label]]:
  """
    Find an independent set of `size` vertices in `graph` by reduction to\n
    Clique. Transform the input (build the complement), solve Clique on it\n
    with a black-box solver, then transform the output back (a clique in the\n
    complement is an independent set in the original). Returns the set, or\n
    None when none exists.\n
  """
  complement: Graph[Label] = complement_graph(graph)
  clique: Optional[list[Label]] = _brute_force_clique(complement, size)
  if clique is None:
    return None

  # the witness needs no rewriting: the same vertices that form a clique in
  # the complement form an independent set in the original graph.
  return clique

def has_independent_set(graph: Graph[Label], size: int) -> bool:
  """
    Decide whether `graph` has an independent set of `size` vertices, via the\n
    same reduction collapsed to its yes/no answer.\n
  """
  return find_independent_set(graph, size) is not None

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 P versus NP question

We now have two classes with $\mathsf{P}\subseteq \mathsf{NP}$. Problems in $\mathsf{P}$ can be solved quickly; problems in $\mathsf{NP}$ can at least have their solutions checked quickly. The defining open question of theoretical computer science is whether checking is genuinely easier than solving.

Almost everyone believes the answer is no: that $\mathsf{P}\ne \mathsf{NP}$, and that finding a needle is fundamentally harder than recognizing one once found. But no proof is known in either direction, and the question carries a million-dollar Clay Millennium Prize.⁵ What makes it more than a curiosity is the next lesson's discovery: there are problems in $\mathsf{NP}$, the $\mathsf{NP}$-complete problems, that are universally hardest. Every problem in $\mathsf{NP}$ reduces to each of them. A polynomial-time algorithm for even one would collapse $\mathsf{P}$ and $\mathsf{NP}$ into a single class; a proof that even one requires super-polynomial time would settle the question the other way.

The sketch shows the conjectured world: $\mathsf{P}$ and the $\mathsf{NP}$-complete problems sit as disjoint regions inside $\mathsf{NP}$. If $\mathsf{P}=\mathsf{NP}$, all three regions coincide and the entire picture collapses to a single region. We do not know which world we live in, but we will see that the two regions, if separate, can never overlap.

Why the question is still open, and NP in practice

The textbooks state $\mathsf{P}\ne \mathsf{NP}$ as a conjecture and move on, but it is worth knowing why half a century of effort has not settled it — the failure is structured, not random. Every general proof technique tried so far runs into a formal barrier that provably cannot separate the classes:

• Relativization (Baker–Gill–Solovay, 1975): there exist oracles $A$ with ${\mathsf{P}}^A={\mathsf{NP}}^A$ and others with ${\mathsf{P}}^B\ne {\mathsf{NP}}^B$. Any proof that relativizes — treats the machine as a black box, as diagonal arguments do — must give the same answer relative to every oracle, so it cannot decide the unrelativized question.⁶
• Natural proofs (Razborov–Rudich, 1997): the circuit-complexity arguments that were the great hope of the 1980s share a common largeness + constructivity shape, and any proof of that shape would, paradoxically, break the very pseudorandom generators that cryptography assumes exist.⁷

A separating proof must therefore be non-relativizing and non-natural — it must exploit the specific structure of computation in a way no known method does.

In practice, there is another consideration the theory does not capture: $\mathsf{NP}$ -completeness is a worst-case statement, and the worst case is often not the case you have. Modern SAT solvers (CDCL: conflict-driven clause learning) and MILP solvers routinely dispatch industrial instances with millions of variables — hardware verification, planning, scheduling — that are formally $\mathsf{NP}$-complete.⁸ The hardness is real but concentrated on carefully constructed adversarial inputs; typical structured instances have enough exploitable regularity that heuristic search finds an answer fast. The lesson to carry into the rest of the module is that $\mathsf{NP}$-complete is a reason to stop looking for a guaranteed-polynomial exact algorithm, not a verdict that every instance is unsolvable — the reason the next lessons turn to approximation, parameter bounds, and heuristics.

Takeaways

• We study decision problems (yes/no answers); optimization problems reduce to them by binary search, so little is lost.
• $\mathsf{P}$ is the class of problems solvable in polynomial time; $\mathsf{NP}$ is the class of problems whose yes-answers admit a short, polynomial-time checkable certificate. Always $\mathsf{P}\subseteq \mathsf{NP}$.
• A polynomial-time reduction $A{\le }_{P}B$ is a transform–solve–transform pipeline: transform the input, call a black-box solver for $B$, transform its output back. It means $A$ is no harder than $B$: tractability flows forward ($B$ easy $\Rightarrow A$ easy), hardness flows backward ($A$ hard $\Rightarrow B$ hard). To prove $B$ hard, reduce a known hard problem to$B$.
• Reductions also build algorithms: $\text{Bipartite-Matching}{\le }_P\text{Max-Flow}$ solves matching by routing it through a flow solver, with the integrality theorem guaranteeing the flow decomposes back into a matching.
• Reductions compose, so ${\le }_P$ chains, building a web of equivalent difficulty.
• Whether $\mathsf{P}=\mathsf{NP}$, that is, whether checking is as easy as solving, is the central open question, and the hardest problems in $\mathsf{NP}$ decide it.