Given an instance of MAX-2-SAT, let us call an assignment of variables a local maximum if changing the value of any variable reduces the number of satisfied clauses.  My question is, how many local maxima can an instance of MAX-2-SAT have?  Clearly it must be less than $2^N$, but how large can it be?To illustrate, suppose instead of considering MAX-2-SAT, we considered MAX-k-CSP with $k=N$ and a single clause.  This means that we can choose any function of $N$ variables as the truth value of the clause.  If we pick, for example, the parity function so that the clause is true if parity is odd, then there are $2^{N-1}$ local maxima (any odd parity configuration is a local maximum as flipping any spin makes it even parity).  On the other hand, I would guess that going from MAX-k-CSP to MAX-2-SAT will significantly reduce the maximum possible number of local maxima.I would also be interested if anyone knows the answer to the number of local maximum for MAX-k-SAT and MAX-k-CSP for $k>2$ but $k=O(1)$.  I would also be interested in the answer in the case of bounded ratio of number of clauses to number of variables.
Number of local maxima in MAX-2-SAT
co.combinatorics;max2sat
One can get a $n \choose n/2$ lower bound by considering the $n$ variable formula that for every pair $x$, $y$, of variables contains the clauses $(x \vee y)$ and $(\neg x \vee \neg y)$. The total number of clauses is $2 \cdot {n \choose 2}$. Every assignment will satisfy one of the two clauses on $x$ and $y$. Both clauses are satisfied exactly when $x$ and $y$ get different values. Hence, if $i$ variables are set to true the total number of satisfied clauses is$${n \choose 2} + i \cdot (n-i).$$This is maximized when $i = n/2$. Thus, for even $n$, every assignment that sets exactly $n/2$ variables to true is a local maxima. The total number of such assignments is $n \choose n/2$, which is $\Theta(\frac{2^n}{\sqrt{n}})$.  