Assume we have a set of equations in $x \in \mathbb{R}^n$


$$|a\_i\cdot x|=b\_i$$


where $a\_i \in \mathbb{R}^n$ and $b\_i>0$ are given.
Could such a system be solved efficiently?


1. In a theoretical machine storing reals with perfect accuracy.
2. An approximate solution taking rounding errors into account.


This is equivalent to having $2$ possible values for each linear combination, which is a valid question over any field. Does this equivalent problem over a fixed finite field have an efficient solution? Or is it perhaps known to be NP-complete?


So far, I concluded that squaring both sides of the equation we get linear equations in $y\_{ij} = x\_i x\_j$. However, this helps only if the system is quadratically overdetermined.



Linear equations with absolute values
The problem is NP-hard over any field not of characteristic 2. We show this by reduction from an NP-complete NAE-3-SAT problem of checking satisfiability of a boolean formula $\land\_{i} \mathrm{NAE}(z\_{i, 1}, z\_{i, 2}, z\_{i, 3})$, where $z\_{i, j}$ are variables $x\_{\cdot}$ or their negations, and $\mathrm{NAE}(\ldots)$ is true iff not all of its arguments have the same value.


The reduction is as follows: introduce variables $x\_i$ subject to $x\_i = \pm 1$, where we interpret values $1$ and $-1$ as $\top$ and $\bot$, respectively. For each $\mathrm{NAE}(\ldots)$ we impose a condition $s\_a x\_a + s\_b x\_b + s\_c x\_c = \pm 1$, where $x\_a, x\_b, x\_c$ are variables in arguments of NAE, and each of the signs $s\_a, s\_b, s\_c$ is $\pm 1$ depending on whether the corresponding variable was taken with negation. It is easy to check that the imposed conditions are equivalent to the original formula, hence the reduction is proper (and of course, polynomial). The reduction works both for machines with precise and approximate real registers (as long as it handles numbers with $O(1 / n)$ relative precision). It also works for any field $F$ not of characteristic 2 if we take $1 \in F$ to be any element of order at least 3, or zero.


In fields of characteristic 2 the given equations (treated as $a\_i \cdot x = \pm b\_i$) are equivalent to $a\_i x = b\_i$, which can be solved with any standard LES solving algorithm (for instance, Gaussian elimination).


