# Finding same-cost assignments for 3-SAT formulas

Suppose I have a 3-SAT formula in CNF with $m$ clauses on $n$ variables, $$F = C_1 \wedge \dotsb \wedge C_m,$$ with each clause $C_i = l_{i_1} \vee l_{i_2} \vee l_{i_3}$ and each literal $l_k \in \{x_1, \bar{x}_1, \dotsc, x_n, \bar{x}_n\}$.

Define the cost $E$ of each assignment $\mathbf{l} = (l_1 \dotsb l_n)$ as the number of clauses not satisfied by it, so that $$E(\mathbf{l}) \in \{0, 1, \dotsc, m\}$$ (zero cost corresponding to satisfying assignments).

Finally, suppose the clause density $m/n$ is sufficiently high so that most (or even all) assignments have nonzero cost (one can show that for large enough $n, m$, clauses can be deemed independent and the cost distribution becomes a binomial distribution with mean $m/8$).

I'm trying to answer the following question: given an assignment $\mathbf{l}$ with cost $E(\mathbf{l}) > 0$, what is the quickest way of finding another assignment $\mathbf{l}^\prime$ such that $E(\mathbf{l}^\prime) = E(\mathbf{l})$?

I haven't been able to find this problem in the literature, and right now I can't do better than random search. Thank you for any insight or even just referrals to some article I might have missed.

• Isn't it NP-complete to even determine if there's another satisfying assignment, let alone one of a particular cost? – David Richerby Mar 9 '18 at 11:21
• @DavidRicherby I don't expect there to be a polynomial algorithm solving this even for $E = m/8$ (the most likely cost for an assignment). But I also expect that an algorithm should exist that performs better than random search --- either in the sense that it's faster on typical formulas (like DPLL for the $E = 0$ case), or that it is $O(\omega^n)$ with $\omega < 2$ (RandomWalkSAT comes to mind). – derpy Mar 9 '18 at 11:26
• Are you looking for a practical solution or its theoretical complexity? (If the former look into MaxSAT solvers and pseudoboolean constraints. If the latter, it is NP-hard, as David Richerby explains.) – D.W. Mar 9 '18 at 17:10
• @DavidRicherby Sorry I cannot get your point. Could you please explain more why the determine version is NP-complete? – xskxzr Mar 10 '18 at 3:40
• @xskxzr Adding a variable $x_0$ into every clause and adding clauses $x_i\vee \bar{x}_0$ (and maybe have to put more effort in converting this CNF into a 3CNF). – Willard Zhan Mar 10 '18 at 4:04