Is there an efficient algorithm for the following problem?
Given: a $m$-vector $b \in \{0,1,2\}^m$, and a $m \times 2m$ matrix $A$, with the promise that for every $b' \in \{0,1,2\}^m$, there exists $x' \in \{0,1\}^{2m}$ such that $Ax'=b' \pmod 3$
Goal: find $x \in \{0,1\}^{2m}$ such that $Ax'=b' \pmod 3$
In more detail: I have a system of equations Ax (mod 3) = b. Each entry for A and each entry for b is 0, 1 or 2 ("ternary"). We're looking for a solution x where each entry is 0 or 1 ("binary"). For example:
p q r b
1 0 1 | 2
1 2 1 | 1
has one solution: p=1, q=1, r=1.
For square matrices A, this often has no solution. For example
p q r b
1 0 0 | 1
0 1 0 | 1
0 0 1 | 0
Does have a solution (p=1, q=1, r=0), but
p q r b
1 0 0 | 1
0 1 0 | 2
0 0 1 | 0
Does not have a solution, since q can only be 0 or 1 (as x should be binary).
I found from practice that practical/useful NP-complete problem instances can often be written in this way with an m x n matrix with m << n << 2m (often n is about 1.5m), but in this question, I'm only interested in cases where n=2m and the equation does have solution. This is at least the case when something stronger than linear independency holds. I think the right condition is that matrix A is such that Ax (mod 3) = b has a binary solution for every ternary vector b. For example, the matrix A with n=2m:
1 1 0 0 0 0 | ?
0 0 1 1 0 0 | ?
0 0 0 0 1 1 | ?
always has a binary solution. Unfortunately, even if the rows are linearly independent, row operations can generally not achieve such a matrix (with 2 pivot columns in each row) except for trivial problems.
Take for example
b
1 1 0 0 0 0 | ?
0 0 1 1 0 0 | ?
2 0 0 0 1 1 | ?
Then there is a binary solution for every b, but the question now is, is there a quick algorithm so that we can find it for any given A and b (where A meets the requirement that a solution exists for every b')?
