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.


Your Answer

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

Browse other questions tagged or ask your own question.