  As a natural variant of the $k$-SAT problem, NAE-$k$-SAT additionally
requires the literals in each clause to take not-all-equal (NAE) truth values.
In this paper, we study the worst-case time complexities of solving NAE-$k$-SAT
and MAX-NAE-$k$-SAT approximation, as functions of $k$, the number of variables
$n$, and the performance ratio $\delta$. The latter problem asks for a solution
of at least $\delta$ times the optimal. Our main results include:
  (1) A deterministic algorithm for NAE-$k$-SAT that is faster than the best
deterministic algorithm for $k$-SAT on all $k \ge 3$. Previously, no
NAE-$k$-SAT algorithm is known to be faster than $k$-SAT algorithms. For $k =
3$, we achieve an upper bound of $1.326^n$. The corresponding bound for $3$-SAT
is $1.328^n$.
  (2) A randomized algorithm for MAX-NAE-$k$-SAT approximation, with upper
bound $(2 - \epsilon_k(\delta))^n$ where $\epsilon_k(\delta) > 0$ only depends
on $k$ and $\delta$. Previously, no upper bound better than the trivial $2^n$
is known for MAX-NAE-$k$-SAT approximation on $k \ge 4$. For $\delta = 0.9$ and
$k = 4$, we achieve an upper bound of $1.947^n$.
  (3) A deterministic algorithm for MAX-NAE-$k$-SAT approximation. For $\delta
= 0.9$ and $k = 3$, we achieve an upper bound of $1.698^n$, which is better
than the upper bound $1.731^n$ of the exact algorithm for MAX-NAE-$3$-SAT.
  Our finding sheds new light on the following question: Is NAE-$k$-SAT easier
than $k$-SAT? The answer might be affirmative at least on solving the problems
exactly and deterministically, while approximately solving MAX-NAE-$k$-SAT
might be harder than MAX-$k$-SAT on $k \ge 4$.
