Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?
$\mathsf{3LIN}$ is the following problem:


  Given a set of linear equations of the form $x_i \oplus x_j \oplus x_k = b$, where $1 \leq i,j,k \leq n$ and $b$ is a bit, find an assignment for the bits $x_1,\ldots,x_n$ that satisfies the largest number of equations.


There is a simple 1/2-approximation algorithm, which simply chooses a random assignment. Such an assignment satisfies half of the equations in expectation, and so at least 1/2 of the optimum. Using the method of conditional expectations, it is routine to derandomize this algorithm.

Håstad, in his paper Some optimal inapproximability results, showed that it is NP-hard to approximate 3LIN to within $1/2+\epsilon$ for any $\epsilon &gt; 0$. In other words, the trivial algorithm mentioned above gives the optimal approximation ratio.