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.

  • 1
    $\begingroup$ Isn't it NP-complete to even determine if there's another satisfying assignment, let alone one of a particular cost? $\endgroup$ – David Richerby Mar 9 '18 at 11:21
  • $\begingroup$ @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). $\endgroup$ – derpy Mar 9 '18 at 11:26
  • $\begingroup$ 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.) $\endgroup$ – D.W. Mar 9 '18 at 17:10
  • $\begingroup$ @DavidRicherby Sorry I cannot get your point. Could you please explain more why the determine version is NP-complete? $\endgroup$ – xskxzr Mar 10 '18 at 3:40
  • $\begingroup$ @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). $\endgroup$ – Willard Zhan Mar 10 '18 at 4:04

Your Answer

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

Browse other questions tagged or ask your own question.