Let $M$ be a square matrix with entries that are 0ドル$ or 1ドル$ and let $v$ be a vector with values that are also 0ドル$ or 1ドル$. If we are given $M$ and $y = Mv,ドル we can computer $v$ if $M$ is non-singular.
Now let us take the second bit (from the right) of the binary representation of each $y_i$ as another vector $z$. So $z$ also has entries which are 0ドル$ or 1ドル$. If $y_i$ has fewer than two bits we just let $z_i=0$.
If we are given $z$ and $M,ドル how (and when) can you find a $v$ so that $Mv$ would produce $z$ under this operation?
Here is an example
$$M = \begin{pmatrix} 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1\\ \end{pmatrix} , v = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 1\\ \end{pmatrix} \implies Mv=\begin{pmatrix} 1 \\ 2 \\ 2 \\ 3\\ \end{pmatrix} .$$
So in this case
$$z = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 1 \\ \end{pmatrix}. $$
Is this problem in fact NP-hard?
1 Answer 1
This problem can be cast into a familiar form: it's an example of what is known as a 0-1 linear programming problem. You have a set of variables $v_1, v_2, \dots v_n$ subject to constraints of the form $m\le a_1v_1+a_2v_2+\cdots +a_nv_n\le M$. In your particular problem, we also have $a_i \in \{0, 1\}$. You are looking for any feasible solutions, namely tuples $(v_1, \dots, v_n)$ which satisfy all the constraints.
For example, suppose we have $$ M = \left( \begin{array}{cccc} 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 \end{array} \right), \quad{\text{and}}\quad z= \left( \begin{array}{c} 0\1円\0円\1円 \end{array}\right) $$ then you want $$ v= \left( \begin{array}{c} a\\b\\c\\d \end{array}\right) $$ such that $Mv$ will be, in binary (with the lower-order bit unspecified) $$ Mv=\left(\begin{array}{c} c \\ a+b+d \\ a + b + c \\ b + c + d \end{array}\right) =\left(\begin{array}{c} \mathtt{0\_}\\ \mathtt{1\_}\\ \mathtt{0\_}\\ \mathtt{1\_} \end{array}\right) $$ From this we have the constraints $$ \begin{array}{c} 0\le a, b, c, d\le 1\\ 2\le a + b + d\le 3\\ 0\le a + b + c\le 1\\ 2\le b + c + d\le 3 \end{array} $$ and you want to find $a, b, c, d$ such that all the constraints are simultaneously satisfied. We've moved into 0-1 LP land because there are established procedures for solving problems like this, though sadly there's nowhere near enough room in this post to introduce them, so you'll have to do the legwork yourself. Be aware that problems like this are very compute-intensive (by which I mean NP-hard) and as far as I know you're not going to get anything like an elegant formulation of the form "This can be solved if and only if $z$ is of the form ..."
By the way, the example I used does indeed have a solution, $v,ドル and in this particular case is unique, though in general you'll have several solutions (if there are any at all).