Is 0-1 integer linear programming with only equality constraints NP-Hard?

Question

We know that 0-1 integer linear programming is NP-Hard. What about 0-1 integer linear programming with only equality constraints? If so, how to prove it

$$\min c^T x \text{ s.t. } Ax = b \quad x_i \in \{0,1\}\quad (i=1,2,...,n)$$

Answer 1

Consider the Maximum Independent Set problem ($\mathcal{NP}$-hard): given a graph $G=(V,E)$, find the maximum independent set in $G$, i.e., the subset of vertices $I \subseteq V$ such that every two vertices in $I$ are not adjacent $\forall v_1,v_2 \in I, (v_1,v_2) \notin E$.

This problem has a well known Integer programming formulation: let $x_i$ be a binary variable for every $i \in V$ and equal one if $i \in I$. \begin{align} \max & \sum\limits_{i=1}^n x_i \\ \text{subject to} & \\ & x_i + x_j \leq 1 \text{ for all } (i,j) \in E \\ & x_i \in \{0,1\} \text{ for all } i \in V \end{align}

If $|V| = n$, this problem has $n$ variables and $O(n^2)$ constraints.

To transform it to equality form (a.k.a. standard form) one might introduce slack variables for every constraint. Generally, if you have $Ax <= b$ you can write $Ax + x_s = b$ where $x_s \geq 0$ and $x_s$ are called slack variables.

It appears that for Independent Set slack variables are actually binary! Thus, you have the formulation \begin{align} \max & \sum\limits_{i=1}^n x_i \\ \text{subject to} & \\ & x_i + x_j +y_{ij} = 1 \text{ for all } (i,j) \in E \\ & x_i \in \{0,1\} \text{ for all } i \in V \\ & y_{ij} \in \{0,1\} \text{ for all } i,j \in V \end{align}

This formulation exactly satisfies yours

0-1 integer linear programming with only equality constraints (ILPEQ)

Now, you have a basic reduction argument. Suppose, you can solve ILPEQ fast, that means you can solve independent set fast, but it is known to be $\mathcal{NP}$-hard, so ILPEQ is also $\mathcal{NP}$-hard. The formal argument as well as checking that this is in fact a polynomial reduction I leave to the reader.