How Do Polynomial-Time Reductions Prove NP-Hardness?

Polynomial-time many-one reductions, also known as Karp reductions, are the primary tool in classical complexity theory for proving that a new combinatorial problem is NP-hard. By showing that a known NP-hard problem can be efficiently transformed into the new problem, we establish that the new problem is at least as hard as the known one. If the new problem could be solved in polynomial time, then the known NP-hard problem could be solved in polynomial time as well.

What Is a Polynomial-Time Many-One Reduction?

Let \(A\) and \(B\) be two decision problems, formalized as languages \(A, B \subseteq \Sigma^*\) over an alphabet \(\Sigma\). We say that \(A\) is polynomial-time many-one reducible to \(B\), written \(A \le_p B\), if there exists a function \(f: \Sigma^* \to \Sigma^*\) computable by a deterministic Turing machine in polynomial time such that for every input string \(x \in \Sigma^*\):

\[x \in A \iff f(x) \in B\]

The function \(f\) must satisfy two key properties:

  1. Polynomial-time computability: There exists a constant \(c > 0\) such that \(f(x)\) can be computed in \(O(|x|^c)\) steps, where \(|x|\) is the length of the input \(x\).
  2. Correctness (equivalence): Every "yes" instance of \(A\) maps to a "yes" instance of \(B\), and every "no" instance of \(A\) maps to a "no" instance of \(B\).

The Direction of the Reduction

A common point of confusion is the direction of the reduction. To prove that a new problem \(B\) is NP-hard, you must reduce from a known NP-hard problem \(A\) to the new problem \(B\) (\(A \le_p B\)), not the other way around.

This direction works because it transfers hardness from \(A\) to \(B\). Suppose \(B\) had a polynomial-time algorithm \(\mathcal{M}_B\). We could then solve any instance \(x\) of \(A\) in polynomial time by:

  1. Computing \(y = f(x)\) in polynomial time.
  2. Running \(\mathcal{M}_B(y)\) in polynomial time and returning its answer.

Since \(f\) runs in polynomial time, the size of \(y\) is also bounded by a polynomial in \(|x|\), ensuring that \(\mathcal{M}_B(y)\) runs in time polynomial in \(|x|\). Therefore, if \(A\) is NP-hard, \(B\) must also be NP-hard; otherwise, every problem in NP would be solvable in polynomial time, implying \(\text{P} = \text{NP}\).

Steps to Prove a Combinatorial Problem Is NP-Hard

When proving that a new combinatorial problem \(B\) is NP-hard, researchers typically follow a standard four-step structure:

  1. Choose a known NP-hard problem \(A\): Select a problem whose structure closely resembles \(B\), such as \(3\text{-SAT}\), \(\text{CLIQUE}\), \(\text{VERTEX COVER}\), or \(\text{HAMILTONIAN CYCLE}\).
  2. Construct the reduction \(f\): Define a polynomial-time algorithm that transforms an arbitrary instance \(x\) of \(A\) into an instance \(f(x)\) of \(B\). In combinatorial settings, this often involves building "gadgets"—small structures in \(B\) that simulate variables, clauses, or constraints from \(A\).
  3. Prove correctness: Show both directions of the equivalence \(x \in A \iff f(x) \in B\). This usually requires proving that a valid solution for \(x\) can be converted into a valid solution for \(f(x)\), and vice versa.
  4. Verify polynomial running time: Confirm that the construction of \(f(x)\) takes time polynomial in \(|x|\), which also guarantees that the output size \(|f(x)|\) is polynomial in \(|x|\).

Why Many-One Reductions Suffice

While more general reductions exist, such as polynomial-time Turing reductions (Cook reductions), many-one reductions are the standard for defining NP-completeness and proving NP-hardness. Because \(A \le_p B\) preserves membership in NP when \(B \in \text{NP}\), a single many-one reduction from an NP-complete problem \(A\) to \(B\) immediately establishes that \(B\) is NP-hard, and if \(B\) is also in NP, that \(B\) is NP-complete.