  MAX NAE-SAT is a natural optimization problem, closely related to its
better-known relative MAX SAT. The approximability status of MAX NAE-SAT is
almost completely understood if all clauses have the same size $k$, for some
$k\ge 2$. We refer to this problem as MAX NAE-$\{k\}$-SAT. For $k=2$, it is
essentially the celebrated MAX CUT problem. For $k=3$, it is related to the MAX
CUT problem in graphs that can be fractionally covered by triangles. For $k\ge
4$, it is known that an approximation ratio of $1-\frac{1}{2^{k-1}}$, obtained
by choosing a random assignment, is optimal, assuming $P\ne NP$. For every
$k\ge 2$, an approximation ratio of at least $\frac{7}{8}$ can be obtained for
MAX NAE-$\{k\}$-SAT. There was some hope, therefore, that there is also a
$\frac{7}{8}$-approximation algorithm for MAX NAE-SAT, where clauses of all
sizes are allowed simultaneously.
  Our main result is that there is no $\frac{7}{8}$-approximation algorithm for
MAX NAE-SAT, assuming the unique games conjecture (UGC). In fact, even for
almost satisfiable instances of MAX NAE-$\{3,5\}$-SAT (i.e., MAX NAE-SAT where
all clauses have size $3$ or $5$), the best approximation ratio that can be
achieved, assuming UGC, is at most $\frac{3(\sqrt{21}-4)}{2}\approx 0.8739$.
Using calculus of variations, we extend the analysis of O'Donnell and Wu for
MAX CUT to MAX NAE-$\{3\}$-SAT. We obtain an optimal algorithm, assuming UGC,
for MAX NAE-$\{3\}$-SAT, slightly improving on previous algorithms. The
approximation ratio of the new algorithm is $\approx 0.9089$.
  We complement our theoretical results with some experimental results. We
describe an approximation algorithm for almost satisfiable instances of MAX
NAE-$\{3,5\}$-SAT with a conjectured approximation ratio of 0.8728, and an
approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a
conjectured approximation ratio of 0.8698.
