NP-Hardness Part 1 (Decision Problems, P, Reductions, NP)
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.
- Graph Coloring: Given a graph $G$ and an integer $k$, can the vertices of $G$ be colored with at most $k$ colors such that no two adjacent vertices share the same color?
- Hamiltonian Cycle: Given a graph $G$, does $G$ contain a cycle that visits every vertex exactly once?
- Subset Sum: Given a set of integers $S$ and a target $t$, does there exist a subset of $S$ whose elements sum to exactly $t$?
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.
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.
- Shortest Path: Does a path of length at most $k$ exist between $s$ and $t$?. If the edges have non-negative lengths, use Dijkstra’s algorithm which runs in $O((V+E) \log V)$ time. Otherwise, use Bellman-Ford algorithm which runs in $O(VE)$ time. Both are polynomial.
- Strongly connected component: Given a directed graph $G$ and an integer $k$, does $G$ have at most $k$ strongly connected components? We can use Depth-first-search to count the number of strongly connected components in $O(V+E)$ time.
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:
- Create one vertex $v_i$ for each task $t_i$.
- Add an edge $(v_i, v_j)$ for every pair of conflicting tasks $t_i$ and $t_j$.
- Use the same integer $k$.
This construction takes $O(n^2)$ time (polynomial). Now observe:
- If we can schedule the tasks into $k$ slots with no conflicts, then assigning each vertex the color equal to its slot gives a valid $k$-coloring of $G$.
- Conversely, if $G$ has a valid $k$-coloring, assigning each task to the time slot corresponding to its vertex’s color gives a valid schedule.
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:
- Compute $f(x)$ in polynomial time.
- 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.
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.
- Graph 3-coloring: Consider the 3-coloring problem that asks if the input graph is 3-colorable. While it’s not clear how to tell if a graph is 3-colorable without brute-forcing, if the graph is 3-colorable, the certificate is a 3-coloring of the graph. To verify, go through every edge and check that 2 end points have different colors and there are at most 3 colors.
- Independent Set: A set $S$ of vertices in a graph $G$ is an independent set if no two vertices in $S$ are adjacent. The decision problem asks: given $G$ and an integer $k$, does $G$ contain an independent set of size at least $k$? The certificate is simply the set $S$ itself. To verify, check that $\lvert S \rvert \ge k$ and that no edge of $G$ has both endpoints in $S$ — both checks run in $O(V + E)$ time. The figure below shows the generalized Petersen graph $GP(12, 4)$. It is not obvious whether it has an independent set of size $8$, but the certificate (the 8 highlighted vertices) makes it easy to verify.
- Subset Sum: Given a set of integers $S$ and a target $t$, does some subset of $S$ sum to exactly $t$? It is not obvious how to decide this without trying all $2^n$ subsets, but if the answer is yes the certificate is the subset itself. Verification takes $O(n)$ time: sum the elements and compare to $t$.
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}$?