# Number of local maxima in MAX-2-SAT

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.

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}})$.
• In this case, aren't the described assignments actually also global maxima? But I suppose if you set $i=n/2 \pm 1$, then you will get the same asymptotic bound but have local maxima that are not globally maximum. Aug 8 '16 at 19:50