Adversarial Satisfiability Problem

Abstract

We study the adversarial satisfiability problem, where the adversary can choose whether variables are negated in clauses or not in order to make the resulting formula unsatisfiable. This is one case of 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 negation-configurations. We conclude that in the thermodynamic limit the best strategy the adversary can adopt is extremely close to simply balancing the number of times every variable is and is not negated. We also conduct a numerical study of the problem, and find that there are very strong pre-asymptotic effects that are due to the fact that for small sizes exponential and factorial growth is hardly distinguishable.

References in corpus (7)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On product, generic and random generic quantum satisfiability
• Large Deviations of the Free-Energy in Diluted Mean-Field Spin-Glass
• Matching between typical fluctuations and large deviations in disordered systems : application to the statistics of the ground state energy in the SK spin-glass model
• Bounds on the quantum satisfiability threshold
• Statistical physics of optimization under uncertainty

Cited by in corpus (3)

• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• An alternate view of complexity in k-SAT problems
• The SAT-UNSAT transition in the adversarial SAT problem