<p>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.</p>

CC BY-SA 3.0
2018-02-28T12:07:43.033Z
The OP already said to not have enough reputation to comment directly below the original answer.
Nicola Gigante
CC BY-SA 3.0
2018-02-28T14:36:35.647Z
I thought it was to contact me directly, but ok I remove the question.
Denis
CC BY-SA 3.0
2018-02-28T12:00:54.623Z
2018-02-28T14:36:06.097Z
2018-02-28T14:36:06.097Z
Denis
<p>I'm trying to understand the answer by @Denis on this <a href="https://cstheory.stackexchange.com/questions/18220/binary-matrix-column-subset-selection-complexity/18222#18222">question</a>, 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.</p>

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

<cc.complexity-theory><complexity-classes><time-complexity><sat><boolean-matrix>
Reduction from SAT to binary matrix subset problem
CowNorris
# Reduction from SAT to binary matrix subset problem

(Asked by: username_0 on 2018-02-28)

I'm trying to understand the answer by @Denis on this [question](https://cstheory.stackexchange.com/questions/18220/binary-matrix-column-subset-selection-complexity/18222#18222), 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$.

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, sat, boolean-matrix

---

## 1 answers

### Answer by username_1 on 2018-02-28. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_2**: The OP already said to not have enough reputation to comment directly below the original answer.  
> **username_1**: I thought it was to contact me directly, but ok I remove the question.  

---

