I reduced a problem I was working on to determining whether a system of linear of equations over $GF(2)$ has a separable solution. I was wondering what would be the most efficient way of deciding this.
Given $A \in \mathbb{Z}_2^{nm} \times \mathbb{Z}_2^{nm}$, and $\textbf{b} \in \mathbb{Z}_2^{nm}$, is there a poly-time algorithm to decide whether there are some $\textbf{x} \in \mathbb{Z}_2^{n}$ and $\textbf{y} \in \mathbb{Z}_2^{m}$ such that $A(\textbf{x} \otimes \textbf{y}) = \textbf{b}$?
I know how to do it when $A$ is invertible, but if not, it's not clear to me how one could check exponentially many cases in polynomial time.
P.S. I tried to find a related result in the literature, but I couldn't find it, probably because I'm not quite familiar with the terminology. I'm sorry if this is a trivial question.