4
$\begingroup$

Suppose we have a system of $n$ linear equations in $m$ unknowns over $\mbox{GF}(2)$ (binary field) $$Av=b$$ Let $V = \mbox{GF}(2)^m$ be the vector space of possible assignments of the variables. For $v \in V$, let $|v|$ be the number of non-zero values in the vector $v$.

Is there an easy way to find a solution $s \in S = \{v \in V : Av = b \}$ so that $|s|$ is its minimum possible value, even if $0 < n \ll m$?

If this is a classic problem in computer science, what is it called?

$\endgroup$
1
  • $\begingroup$ You could perform Gaussian elimination, reduce $A$ to RREF, then do exhaustive search over the $d$-dimensional (finite) affine space, where $d \geq m - n$, whose cardinality is $2^d$. $\endgroup$ – Rodrigo de Azevedo May 18 '19 at 10:00
3
$\begingroup$

The answer to you question "Is there an easy way..." should be No.

Your problem is related to the minimum distance problem in coding theory.

For $b = 0$, the solution space $C$ of $Ax = 0$ is the binary linear code given by the check matrix $A$. The number of non-zero entries of a vector is called its Hamming weight.

The problem to determine the minimum Hamming weight of the nonzero vectors in $C$ is a central problem in coding theory, and it has been shown to be NP-hard (Alexander Vardy, Algorithmic Complexity in Coding Theory and the Minimum Distance Problem, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (1997), 92-109).

It is not exactly your problem, as the answer to your question would be the zero vector, which is forbidden for the minimum distance problem. However, it is very close, and I'd guess that the same methods could be used to show that your problem is NP-hard, too.

$\endgroup$
2
$\begingroup$

If $b$ is the zero vector, this is known as sparse nullspace problem.

In the case of base field $\mathbb{R}$, the problem of finding a single sparsest null vector is NP-complete. See T.F. Coleman's paper in SIAM Journal on Algebraic and Discrete Methods October 1986.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.