Consider system of linear equations Ax=0 over $F_2$ (field with two elements {0,1}). Where number of variables is bigger than equations - so we have many solutions $x$.
Question How to estimate minimal Hamming weight of $x$ ($x\ne 0$) ? (I.e. minimal number of $1$ in vector $x$ such that Ax=0).
Equivalently
Consider bipartite graph of vertexes of two type 1 and 2. How to estimate minimal size of subset A of vertexes of type 1, such that: for each vertex $V$ of type 2 we have EVEN number of edges which starts at $V$ and finishes at $A$.
Equivalence can be seen like this: take matrix $A$ of size $n\times m$ over $F_2$ and bipartite graph of with $n$ and $m$ number of vertexes of types 1 and 2. Connect two vertexes if $A_{ij}=1$.
Exercise to see equivalence.
Equivalently
Take $A$ as parity check of linear block code. I.e. code is exactly subspace x: Ax=0. Code is good than Hamming distance between codewords is big. We have code word x = 0, so the minimal Hamming weight of non-zero x will measure the "quality" of code.
Comment. Let Let dim(ker(A))=k, any linear map $F_2^k \to ker(A)$ is called "encoder".
[EDIT] As "quid" answered - questions are NP - problems. So
a) what approximate algorithms are used for questions ?
b) If corresponding bipartite graph is tree - is the problem still NP ? (From coding theory it is very simple-degenerate case and bad codes). More generally can we control complexity somehow - if matrix is of special form (e.g. sparse or whatever) or graph is tree/treelike. In what terms we might hope to control complexity ?
[END EDIT]
