patternMinor
Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$
Viewed 0 times
maximummathbbdistancefindingfromvectorsubspacehamming
Problem
Let $W$ be a linear subspace of the vector space $V = (\mathbb{Z}/2\mathbb{Z})^n$. Let $k = \dim(W)$. For $v \in V$, define the distance from $v$ to $W$ to be $d(v,W):=\min_{w\in W} d(v,w)$ where $d(v,w)$ is the Hamming distance.
Given such a subspace $W$ (more precisely, receiving a basis of $k$ vectors as input), how can I find a vector $v \in V$ such that $d(v,W)$ is as large as possible?
The cases I'm interested in have $n$ in the thousands, but $k$ being quite small, usually less than 20. I have been able to solve some smaller instances of this problem ($n$ being a few hundred, $k$ being at most 6 or so) using the SAT/SMT solver Z3 by creating $n$ Boolean variables and explicitly writing out $d(v,w)\geq r$ for all $2^k$ elements of $W$ as clauses. The inequality is encoded using a pseudo-boolean constraint (
Example: Let $n = 100$ and $W$ be the subspace spanned by the following three elements (I'll compress the notation a bit and write a vector like $(a,b,c)$ as $abc$):
1011000001001001000110000000110010000010111011100101010000010101001000000011001000011001110010000000
0100101000001010101011010000000001001000101111100010000010000001011101000001100100010001000100010010
1110010000000000110001011000110001000010011000001000101001001100100110100001010000011000001000110100
Then a solution to the problem is given by the following vector $v$:
1101101110110101010011101111011100111101110000010110110111111011101110011101100011101110110001101011
which has Hamming distance at least 64 from every linear combination of the three vectors above. Distance 65 from every linear combination is not possible.
Some additional questions:
Given such a subspace $W$ (more precisely, receiving a basis of $k$ vectors as input), how can I find a vector $v \in V$ such that $d(v,W)$ is as large as possible?
The cases I'm interested in have $n$ in the thousands, but $k$ being quite small, usually less than 20. I have been able to solve some smaller instances of this problem ($n$ being a few hundred, $k$ being at most 6 or so) using the SAT/SMT solver Z3 by creating $n$ Boolean variables and explicitly writing out $d(v,w)\geq r$ for all $2^k$ elements of $W$ as clauses. The inequality is encoded using a pseudo-boolean constraint (
pb-ge in Z3) stating that at least $r$ of the $n$ literals must be true in each clause. I then use a binary search to find the maximum value of $r$ where the formula is satisfiable.Example: Let $n = 100$ and $W$ be the subspace spanned by the following three elements (I'll compress the notation a bit and write a vector like $(a,b,c)$ as $abc$):
1011000001001001000110000000110010000010111011100101010000010101001000000011001000011001110010000000
0100101000001010101011010000000001001000101111100010000010000001011101000001100100010001000100010010
1110010000000000110001011000110001000010011000001000101001001100100110100001010000011000001000110100
Then a solution to the problem is given by the following vector $v$:
1101101110110101010011101111011100111101110000010110110111111011101110011101100011101110110001101011
which has Hamming distance at least 64 from every linear combination of the three vectors above. Distance 65 from every linear combination is not possible.
Some additional questions:
- Does this problem have a name?
- Is there a faster (in practise, not necessarily in theory) algorithm than what I am currently doing?
- If so, is there an i
Solution
Your problem is very likely NP-hard. If you don't add the restriction that $W$ is sub-space, but just receive a set of boolean vectors $W$, then it is NP-hard and known as a Covering Radius proven NP-hard by Frances and Litman. Of course it might be that $W$ being a sub-space somehow makes the problem easier, but I can't see a particular way for that to happen.
Context
StackExchange Computer Science Q#161186, answer score: 2
Revisions (0)
No revisions yet.