3
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Do you want to find all solutions ? Or do you just want to decide whether there is a solution ? $\endgroup$
    – Peter
    Dec 23, 2020 at 10:33
  • 1
    $\begingroup$ whether it exist one solution $\endgroup$
    – yugikaiba
    Dec 23, 2020 at 10:33
  • $\begingroup$ What's the definition that you're using about NP? $\endgroup$
    – user798113
    Dec 23, 2020 at 10:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – yugikaiba
    Dec 23, 2020 at 10:39
  • $\begingroup$ Also if it isn't and you know a way to find a solution in polynomial time let me know. $\endgroup$
    – yugikaiba
    Dec 23, 2020 at 10:42

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – yugikaiba
    Dec 23, 2020 at 19:05
  • $\begingroup$ I updated my answer with more detail just now. $\endgroup$
    – RobPratt
    Dec 23, 2020 at 19:18
  • $\begingroup$ Thank you! Thank you! $\endgroup$
    – yugikaiba
    Dec 23, 2020 at 19:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .