2
$\begingroup$

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')?

$\endgroup$
  • $\begingroup$ Nice question! The problem smells like it might be NP-hard to me. Based on some heuristic back-of-the-envelope calculations, I think a random matrix will, with high probability, have the desired property. So, I'm guessing that the promise about $A$ might not make much difference to the complexity of this problem. $\endgroup$ – D.W. Jun 14 '17 at 22:52

Your Answer

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

Browse other questions tagged or ask your own question.