-matrix, and
b
is an integer
m
-vector.
.
[
152
].
for some
[
10
].
the problem over GF[
q
] is approximable within
q
, but
is not approximable within
for any
, even if the
number of variables in each equation is exactly three. The problem over GF[2]
with two variables in each equation is approximable within 1.383 but is
not approximable within 1.0909 [
164
].
The variation where the system consists of relations (> or
) is
A
PX
-complete and approximable within 2
[
10
].
If the variables are restricted to assume only binary values, the problem is
harder to approximate than M
AXIMUM
I
NDEPENDENT
S
ET
.
Approximability results for even more variants of the problem can be found in
[
10
].
Viggo Kann