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](http://en.wikipedia.org/wiki/Hamming_weight) of $x$ ($x\ne 0$) ? (I.e. minimal number of $1$ in vector $x$ such that Ax=0).

Equivalently
------------

Consider [bipartite graph](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Parity-check_matrix) 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]

---