<p>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}})$.  </p>

CC BY-SA 3.0
2016-08-08T19:48:09.960Z
Note that this is precisely the parity argument given in the original question (albeit clearly spelled out in the 2-SAT case and fully analyzed) :).
Joshua Grochow
CC BY-SA 3.0
2016-08-08T19:50:05.413Z
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.
Joshua Grochow
CC BY-SA 3.0
2016-08-08T21:09:20.260Z
I don't understand your second comment... But yes I am sure one can add some constant size gadgets to have roughly as many local maxima that are not global maxima.
daniello
CC BY-SA 3.0
2016-08-08T22:06:41.617Z
I see what you mean about my second comment - that doesn't really work. But I agree one should be able to add some small gadgets to make local but non-global maxima.
Joshua Grochow
CC BY-SA 3.0
2016-08-06T02:21:51.497Z
2016-08-08T15:39:27.983Z
2016-08-08T15:39:27.983Z
daniello
<p>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?</p>

<p>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.</p>

<p>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&gt;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.</p>

<co.combinatorics><max2sat>
Number of local maxima in MAX-2-SAT
Matt Hastings
# Number of local maxima in MAX-2-SAT

(Asked by: username_0 on 2016-08-04)

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.

**Tags:** co.combinatorics, max2sat

---

## 1 answers

### Answer by username_1 on 2016-08-06. Score: 6 | Accepted answer

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}})$.

> **Comments:**
> **username_2**: Note that this is precisely the parity argument given in the original question (albeit clearly spelled out in the 2-SAT case and fully analyzed) :).  
> **username_2**: 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.  
> **username_1**: I don't understand your second comment... But yes I am sure one can add some constant size gadgets to have roughly as many local maxima that are not global maxima.  
> **username_2**: I see what you mean about my second comment - that doesn't really work. But I agree one should be able to add some small gadgets to make local but non-global maxima.  

---

