1
$\begingroup$

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.

$\endgroup$

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.