Adversarial satisfiability problem
Michele Castellana, Lenka Zdeborová · Journal of Statistical Mechanics Theory and Experiment · 2011
We study the adversarial satisfiability problem, where the adversary can choose whether the variables are negated in clauses or not, in order to make the resulting formula unsatisfiable. This problem belongs to a general class of adversarial optimization problems that often arise in practice and are algorithmically much harder than the standard optimization problems. We use the cavity method to compute large deviations of the entropy in the random satisfiability problem with respect to the configurations of negations. We conclude that in the thermodynamic limit the best strategy the adversary can adopt is to simply balance the number of times every variable is negated and the number of times it is not negated. We also conduct a numerical study of the problem, and find that there are very strong pre-asymptotic effects that may be due to the fact that for small sizes exponential and factorial growth is hardly distinguishable. As a side result we compute the satisfiability threshold for balanced configurations of negations, and also the random regular satisfiability, i.e. when all variables belong to the same number of clauses.