NP-Hardness Part 1 (Decision Problems, P, Reductions, NP)

Lecture slides (PDF)

Decision Problems

So far we have studied the design and analysis of several algorithms. This part of the course will focus on when a problem is considered hard and unlikely to have an efficient algorithm.

Definition (Decision Problem). A decision problem is a computational problem whose output is either yes or no.

Examples.

Many optimization problems have a natural decision version. For instance, “find the shortest path” becomes “does a path of length at most $k$ exist?” Studying the decision version is without loss of generality in a complexity-theoretic sense: if the optimization problem is hard, so is its decision version, and vice versa.

Class P (Polynomial Time)

We say an algorithm runs in polynomial time if its worst-case running time is $O(n^c)$ for some constant $c$, where $n$ is the size of the input. Polynomial-time algorithms are considered efficient; exponential-time algorithms (e.g., $O(2^n)$) are considered intractable for large inputs.

Definition: $\mathbf{P}$ is the class of all decision problems that can be solved in polynomial time.

Examples of problems in P.

Reductions

A central idea in complexity theory is the notion of reducing one problem to another. Informally, problem $A$ reduces to problem $B$ if we can solve $A$ by using a solver for $B$ as a black box.

Definition (Polynomial-Time Reduction). We say problem $A$ polynomial-time reduces to problem $B$, written $A \le_p B$, if there exists a polynomial-time algorithm $f$ such that for every input $x$, the algorithm $f$ computes an instance $f(x)$ of $B$ where $x$ is a yes-instance if and only if $f(x)$ is a yes-instance. The algorithm $f$ is called the reduction.

In other words, we transform any instance of $A$ into an instance of $B$ in polynomial time, preserving the yes/no answer.

Example: Scheduling to Graph Coloring

Scheduling problem. We have $n$ tasks and $k$ time slots. Two tasks conflict if they cannot be scheduled in the same time slot (e.g., they share a resource or overlap). Given the conflict structure and a number $k$, can we assign every task to one of $k$ time slots such that no two conflicting tasks share a slot?

Graph Coloring problem. Given a graph $G = (V, E)$ and an integer $k$, can we assign each vertex a color from ${1, \ldots, k}$ such that no two adjacent vertices share the same color?

Reduction $\text{Scheduling} \le_p \text{Graph Coloring}$. Given a scheduling instance $(T, \text{conflicts}, k)$, construct a graph $G$ as follows:

This construction takes $O(n^2)$ time (polynomial). Now observe:

Hence, the scheduling instance is a yes-instance if and only if the graph coloring instance is a yes-instance. This completes the reduction. $\square$

Claim. If $A \le_p B$ and $B \in \mathbf{P}$, then $A \in \mathbf{P}$.

Proof. Suppose $A \le_p B$ via a polynomial-time reduction $f$, and suppose $B$ has a polynomial-time algorithm $\mathcal{A}_B$.

Given an instance $x$ of $A$, we solve it as follows:

  1. Compute $f(x)$ in polynomial time.
  2. Run $\mathcal{A}_B$ on $f(x)$ and return its answer.

Step 1 takes $O(n^c)$ time for some constant $c$, and the output $f(x)$ has size at most $O(n^c)$ (a polynomial-time computation can write at most polynomially many output bits). Step 2 runs in time polynomial in $\lvert f(x) \rvert$, which is $O((n^c)^d) = O(n^{cd})$ for some constant $d$. The total running time is polynomial in $n$. Since the answer is correct by the definition of the reduction, $A \in \mathbf{P}$. $\square$

Implication. If there is an efficient algorithm for $B$, then there is an efficient algorithm for $A$. Equivalently, if $A \le_p B$ and $A$ is hard, then $B$ is also hard.

Class NP

Consider the Graph Coloring problem. We don’t know how to solve it in polynomial time in general, but if someone hands us a proposed coloring, we can verify it in polynomial time: just check every edge to confirm its endpoints have different colors.

This observation motivates the class NP.

Definition (Class NP). $\mathbf{NP}$ is the class of all decision problems for which a yes-instance has a certificate (also called a witness) of this fact that can be verified in polynomial time.

Examples of problems in NP.

Think of this as a game. If the answer is no, then we are done. If the answer is yes and Alice knows this fact, she wants to convince Bob that this is the case too. The rule is that Alice cannot ask Bob to brute-force for the solution as he can only run polynomial time algorithms. So she has to give him something that he can easily verify.

Claim. $\mathbf{P} \subseteq \mathbf{NP}$.

Proof. Let $L \in \mathbf{P}$, so there is a polynomial-time algorithm $\mathcal{A}$ that decides $L$. We show $L \in \mathbf{NP}$ by constructing a verifier: on input $(x, c)$, ignore the certificate $c$ and run $\mathcal{A}$ on $x$. If $\mathcal{A}$ accepts, accept; otherwise reject. This verifier runs in polynomial time and accepts $x$ if and only if $x \in L$, so $L \in \mathbf{NP}$. $\square$

Intuitively, if you can solve a problem efficiently on your own, you do not need a certificate to verify a yes-answer. The central open question in computer science is whether the reverse holds: does $\mathbf{NP} \subseteq \mathbf{P}$, i.e., is $\mathbf{P} = \mathbf{NP}$?