0
$\begingroup$

I'm trying to understand the answer by @Denis on this question, where he showed a way to reduce from SAT to the binary matrix column subset selection problem. The reason I'm having to post a new question is because I have not an account on cstheory.stackexchange before, so I'm unable to ask him directly.

In his explanation of his method in the comments, he mentioned that by the construction of the matrix, one is forced to pick only 1 of the $x_i, \neg x_i$ columns for all $i \in [1,m]$, i.e. forcing an assignment to the CNF (I believe due to the earlier claim that one must choose $m$ out of the $2m$ columns). I am struggling to understand as to why this is the case - I see nothing wrong at the moment with choosing more than $m$ columns or choosing both the columns representing $x_i$ and $\neg x_i$.

$\endgroup$
0
$\begingroup$

The original problem asks for a given $k$ whether there is a solution with this $k$, so we can choose to instantiate $k=m$. This means we are forced to pick $m$ columns. Then if you choose both $x_i$ and $\neg x_i$, there will be a $j$ so that the line number $j$ is left with only zeros, so this choice cannot be good.

$\endgroup$
  • $\begingroup$ The OP already said to not have enough reputation to comment directly below the original answer. $\endgroup$ – gigabytes Feb 28 '18 at 12:07
  • $\begingroup$ I thought it was to contact me directly, but ok I remove the question. $\endgroup$ – Denis Feb 28 '18 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.