As a problem with similar properties to Minimum Bisection, we consider the following: given a homogeneous system of linear equations over Z_2^{} , with exactly k variables in each equation, find a balanced assignment that minimizes the number of satisfied equations. A balanced assignment is one which contains an equal number of 0s and 1s.

When k = 2, this is the Minimum Bisection problem. We consider the case k = 3. In this case, it is NP-complete to determine whether the object function is zero [6], so the problem is not approximable at all. However, we prove that it is NP-hard to determine distinguish between the cases that all but a fraction \varepsilon of the equations can be satisfied and that at least a fraction ?-\varepsilon of all equations cannot be satisfied. A similar result for Minimum Bisection would imply that the problem is hard to approximate within any constant. For the problem of approximating the maximum number of equations satisfied by a balanced assignment, this implies that the problem is NP-hard to approximate within 4/3-\varepsilon , for any \varepsilon > 0.