Is this problem NP-hard?

Question

Is the following problem NP-hard?

Let $Ax=b$, where $a_{i,j} \in \{0,1\}, b_i \in \{0,1\}, x_j \in \{0,1\}$.
Decide, wether there is a solution or not.

Answer 1

Assuming you are given $A$ and $b$ and want to find $x$, this is the exact cover problem, which is one of the original 21 NP-complete problems. Row $i$ corresponds to an element, and column $j$ corresponds to a subset. The (constant) value of $a_{i,j}$ indicates whether element $i$ appears in set $j$. The (variable) value of $x_j$ indicates whether set $j$ is selected. If $b_i = 0$, then $x_j=0$ for all $j$ with $a_{i,j}=1$, and row $i$ can be removed.