Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all possible linear combinations of the equations in $B$.Given $S_i \subset B$ for $i=1,\cdots,m$, is that possible to compute, in polynomial time, a$K \subset M$ with minimum size such that $S_i \cup K$ is a full rank system of equations (i.e., the values of all of the variables can be obtained by solving $S_i \cup K$)?An example: Let $B=\{b_1=1,b_2=0,b_3=1\}$, $S_1=\{b_1=1,b_2=0\}$, and $S_2=\{b_2=0,b_3=1\}$. $K=\{b_1+b_3=0\}$ is the solution because both $S_1\cup K$ and $S_2 \cup K$ can be solved uniquely and $K$ has the minimum size 1.
Is this problem in P: Finding a common key for a collection of systems of equations?
complexity theory;time complexity;np hard;polynomial time;linear algebra