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]




---



Ax=0, estimate min(Hamming(x)) ? Equivalently: Bipartite graph. How to find (estimate) minimal number of vertices1 which are connected with EVEN number of vertices2 ? Equivalently: estimate minimal weight of error correcting code ?
It is known that to determine the minimal weight of a nonzero code word (i.e., the minimum distance of the code) is a hard problem. 


Here is a part of the abstract of a paper by Vardy (The intractability of computing the minimum distance of a code, IEEE Information Theory, 1997):



> 
> It is shown that the problem of computing the minimum distance of a binary linear code is NP-hard, and the corresponding decision problem is NP-complete. This result constitutes a proof of the conjecture of Berlekamp, McEliece, and van Tilborg (1978).
> 
> 
> 


However, you ask for an estimation not the exact value. Now, of course it depends what precisely this should mean. Yet, in certain senses the problem stays hard. From the abstract of a paper by Dumer, Micciancio, Sudan ([Hardness of Approximating the Minimum Distance of a Linear
Code](http://cseweb.ucsd.edu/~daniele/papers/DMS.pdf)) 



> 
> We show that the minimum distance d of a linear code is not approximable to within any
>  constant factor in random polynomial time (RP), unless NP (nondeterministic polynomial time)
>  equals RP.
> 
> 
> 


In addition, on Sudan's webapage there are slides from a talk on this, see <http://people.csail.mit.edu/madhu/talks.html> and towards the very end you find 'Hardness of approximating the minimum distance of a linear code'.


ps. I am not certain that this type of answer is what you were looking for, but since your question is not very specific I had to guess a bit. 


