6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) :). $\endgroup$ – Joshua Grochow Aug 8 '16 at 19:48
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Aug 8 '16 at 19:50
  • $\begingroup$ 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. $\endgroup$ – daniello Aug 8 '16 at 21:09
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Aug 8 '16 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.