Integer Linear Programming is NP-Complete
Statement
The decision problem 0/1 integer linear programming — given \(A \in \mathbb{Z}^{m \times n}\), \(b \in \mathbb{Z}^m\), decide whether there exists \(x \in \{0, 1\}^n\) with \(A x \le b\) — is NP-complete (Karp 1972; Garey and Johnson 1979).
Membership in NP
A satisfying \(x \in \{0, 1\}^n\) has length \(n\), polynomial in the input size. Verifying \(A x \le b\) amounts to computing a matrix-vector product and comparing component-wise, both polynomial time. So 0/1 ILP \(\in \mathsf{NP}\).
NP-hardness via reduction from 3-SAT
We exhibit a polynomial-time reduction \(f : \text{3-SAT} \to \text{0/1 ILP}\) such that a 3-SAT formula \(\varphi\) is satisfiable iff the ILP instance \(f(\varphi)\) has a feasible 0/1 solution. Since 3-SAT is NP-complete (Cook 1971), this proves 0/1 ILP is NP-hard.
Construction
Let \(\varphi\) be a 3-SAT formula over Boolean variables \(z_1, \dots, z_n\), with \(m\) clauses \(C_1, \dots, C_m\), each a disjunction of three literals. Build the ILP as follows.
Variables. One 0/1 ILP variable \(x_i\) per Boolean variable \(z_i\), with the intended meaning \(x_i = 1 \iff z_i = \text{true}\).
Constraints. For each clause \(C_j\), build one linear inequality. Replace each literal:
- \(z_i\) becomes \(x_i\).
- \(\neg z_i\) becomes \((1 - x_i)\).
The clause \(C_j = \ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3}\) is satisfied iff at least one of the three terms takes value \(1\), equivalently \[ \ell_{j,1} + \ell_{j,2} + \ell_{j,3} \ge 1 \] (after substituting the rewriting above). Multiply through by \(-1\) to fit the standard form \(A x \le b\).
For example, the clause \(z_1 \lor \neg z_2 \lor z_3\) becomes \[ x_1 + (1 - x_2) + x_3 \ge 1, \quad \text{i.e.,} \quad -x_1 + x_2 - x_3 \le 0. \]
Cost vector. Irrelevant for the decision version (any objective works); take \(c = 0\).
Correctness
By construction, an assignment of Boolean values \(z_i \in \{\text{true}, \text{false}\}\) satisfies clause \(C_j\) iff the corresponding 0/1 vector \(x\) satisfies the inequality for \(C_j\). Therefore:
- If \(\varphi\) is satisfiable by some assignment, set \(x_i = 1\) if \(z_i = \text{true}\) and \(x_i = 0\) otherwise; every clause inequality holds, and \(x \in \{0, 1\}^n\) is a feasible ILP solution.
- If the ILP has a feasible \(x \in \{0, 1\}^n\), set \(z_i = \text{true}\) iff \(x_i = 1\); every clause is satisfied by the same correspondence.
So \(\varphi\) is satisfiable iff \(f(\varphi)\) is ILP-feasible.
Polynomial time
The reduction creates \(n\) variables and \(m\) inequalities, each of size \(O(1)\), total \(O(n + m)\). So \(f\) runs in linear time in the size of \(\varphi\).
Conclusion
0/1 ILP is in NP and is NP-hard, so it is NP-complete. A polynomial-time algorithm for 0/1 ILP would yield a polynomial-time algorithm for SAT and prove \(\mathsf{P} = \mathsf{NP}\).
Stronger forms
The reduction above produces an ILP with binary variables and clause-style inequalities. Several stronger variants of the result hold:
- General ILP (variables in \(\mathbb{Z}\) rather than \(\{0, 1\}\)) is NP-hard by the same reduction (add the constraints \(0 \le x_i \le 1\)).
- ILP feasibility with two variables per inequality is also NP-hard.
- The mixed-integer version, which allows some variables continuous and others integer, is at least as hard as ILP and is therefore NP-hard.
The contrast with linear programming — solvable in polynomial time once the integrality constraint is dropped — is the central motivation for LP relaxation and rounding-based approximation algorithms.