  In MaxSat, we are given a CNF formula $F$ with $n$ variables and $m$ clauses
and asked to find a truth assignment satisfying the maximum number of clauses.
Let $r_1,..., r_m$ be the number of literals in the clauses of $F$. Then
$asat(F)=\sum_{i=1}^m (1-2^{-r_i})$ is the expected number of clauses satisfied
by a random truth assignment (the truth values to the variables are distributed
uniformly and independently). It is well-known that, in polynomial time, one
can find a truth assignment satisfying at least $asat(F)$ clauses. In the
parameterized problem MaxSat-AA, we are to decide whether there is a truth
assignment satisfying at least $asat(F)+k$ clauses, where $k$ is the parameter.
We prove that MaxSat-AA is para-NP-complete and, thus, MaxSat-AA is not
fixed-parameter tractable unless P$=$NP. This is in sharp contrast to
MaxLin2-AA which was recently proved to be fixed-parameter tractable by
Crowston et al. (arXiv:1104.1135v3). In fact, we consider a more refined
version of {\sc MaxSat-AA}, {\sc Max-$r(n)$-Sat-AA}, where $r_j\le r(n)$ for
each $j$. Alon {\em et al.} (SODA 2010) proved that if $r=r(n)$ is a constant,
then {\sc Max-$r$-Sat-AA} is fixed-parameter tractable. We prove that {\sc
Max-$r(n)$-Sat-AA} is para-NP-complete for $r(n)=\lceil \log n\rceil.$ We also
prove that assuming the exponential time hypothesis, {\sc Max-$r(n)$-Sat-AA} is
not in XP already for any $r(n)\ge \log \log n +\phi(n)$, where $\phi(n)$ is
any unbounded strictly increasing function. This lower bound on $r(n)$ cannot
be decreased much further as we prove that {\sc Max-$r(n)$-Sat-AA} is (i) in XP
for any $r(n)\le \log \log n - \log \log \log n$ and (ii) fixed-parameter
tractable for any $r(n)\le \log \log n - \log \log \log n - \phi(n)$, where
$\phi(n)$ is any unbounded strictly increasing function. The proof uses some
results on {\sc MaxLin2-AA}.
