# Is this problem NP-hard?

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.

• Do you want to find all solutions ? Or do you just want to decide whether there is a solution ? Dec 23, 2020 at 10:33
• whether it exist one solution Dec 23, 2020 at 10:33
• What's the definition that you're using about NP?
– user798113
Dec 23, 2020 at 10:36
• NP given a solution $(x_1, \ldots , x_n)$ it can be verified in polynomial time. But I want to proof it is at least NP-Hard. Dec 23, 2020 at 10:39
• Also if it isn't and you know a way to find a solution in polynomial time let me know. Dec 23, 2020 at 10:42

## 1 Answer

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.

• Thanks. Could you please explain briefly (or if you can with detail) how are they equivalent? The exact cover is for subsets while the above problem is a linear system of boolean variables. Dec 23, 2020 at 19:05
• I updated my answer with more detail just now. Dec 23, 2020 at 19:18
• Thank you! Thank you! Dec 23, 2020 at 19:21