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$
1
  • $\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, 2017 at 22:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.