In the last post, I illustrated how the 0-1 integer linear programming problem can be reduced to solving a multivariate system of linear and quadratic polynomials over the complex numbers, demonstrating that the latter problem is NP-hard. Let’s see what other problems we can prove are NP-hard by reduction from 0-1 integer programming.
0-1 affine subspace intersection
Recall again the definition of the 0-1 integer programming problem:
Input: \(m\)-by-\(n\) integer matrix \(A\) and length-\(m\) integer vector \(b\)
Output: true if and only if there exists a length-\(n\) 0-1 vector \(x\) such that \(Ax = b\)
A solution vector \(x\) needs to meet two criteria: it must be contain only zeros and ones, and it must satisfy \(Ax = b\). It is easy to generate a vector that meets either of these two criteria on their own; it is only the combination of the two that makes the problem hard.
For the second criterion, generating a vector that satisfies \(Ax = b\) can be done by reducing the augmented matrix \((A|b)\) to reduced row echelon form (RREF). This gives us another system of linear equations that has the same solution set as the original, but with the coefficients in a structured format. Once the matrix is in RREF, it is easy to determine whether the system of linear equations has a solution, and if it does to substitute the remaining free parameters with arbitrary values and read off a solution vector.
If a system of linear equations over \(n\) variables has any solutions at all, its solution space is an affine subspace of the \(n\)-dimensional Euclidean space. It can be a point, a line, a plane, or in general an \(m\)-hyperplane with \(m \leq n\). This suggests the following reformulation of the 0-1 integer linear programming problem, which might be called 0-1 affine subspace intersection:
Input: description of an affine subspace \(S\) of \(n\)-dimensional Euclidean space
Output: true if and only if \(S\) contains any corner of the unit \(n\)-hypercube
This geometric rephrasing of 0-1 integer programming emphasizes how easy this hard problem might seem at first glance. The difficulty comes from the \(n\)-hypercube having a number of corners exponential in \(n\), which means we can’t get an efficient algorithm by just individually testing every corner for membership in the subspace. Any polynomial time algorithm for this problem would have to exploit some nontrivial geometric property of the problem.
0-1 lattice intersection
Traditionally, converting a matrix to RREF is done by Gaussian elimination. What is the time complexity of Gaussian elimination? Most sources give it as \(O(n^3)\) for a matrix with maximum side length \(n\). However, this is actually misleading: \(O(n^3)\) is the arithmetic complexity of Gaussian elimination. Gaussian elimination is an example of an algorithm that is weakly polynomial time, but not strongly polynomial time, meaning that it runs in polynomial time in the real RAM model but does not in general run in polynomial time when implemented on a Turing machine. The worst-case bit complexity of standard Gaussian elimination is actually exponential!
Fortunately, there are known algorithms with worst-case polynomial bit complexity for converting matrices of rational numbers to RREF. Even better for our purposes, there are known algorithms with worst-case polynomial bit complexity for computing a description of the set of all integer solutions to a system of linear equations, as discussed in a fascinating 2015 article on the Gödel’s Lost Letter blog.
As described in this 2009 article referenced from the GLL blog post, the solution space of an integer matrix equation \(AX = B\) looks like this, where all of the variables are integer matrices and \(Z\) is a matrix of free parameter integer variables:
\[X = Q \begin{bmatrix} \overline{D}\,^{-1}\,\overline{PB} \\ Z \end{bmatrix}\]
This implies that the set of integer solutions to a system of linear equations is an \(m\)-dimensional lattice of integer points embedded in \(n\)-dimensional Euclidean space. This lattice can be written as the span of a basis of linearly-independent integer vectors, plus an integer affine offset from the origin.
This suggests another representation of the 0-1 integer programming problem, which might be called 0-1 lattice intersection:
Input: set of length-\(n\) integer vectors \(U\) and length-\(n\) integer vector \(v\)
Output: true if and only if there exists a length-\(n\) 0-1 vector \(x\) such that \(x - v\) is a member of the integer lattice spanned by \(U\)
This is reminiscent of the class of lattice problems in cryptography, some of which are likewise known to be NP-hard.
