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$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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