Abstract
This paper introduces the Adversarial Satisfiability Problem (AdSAT), a game-theoretic extension of the classic K-SAT problem. In AdSAT, an adversary strategically selects variable negations to maximize the difficulty of finding a satisfying assignment. By applying the cavity method from statistical physics, the authors demonstrate that the optimal adversarial strategy involves balancing negations. They identify the phase transitions where formulas become unsatisfiable under adversarial pressure, revealing that adversarial choice significantly lowers the satisfiability threshold compared to random configurations.
Introduction
Boolean Satisfiability (K-SAT) is a cornerstone of theoretical computer science. While standard random K-SAT assumes negations are distributed uniformly, real-world scenarios often involve adversarial actors. The Adversarial Satisfiability Problem (AdSAT) models this by introducing a two-player game: an adversary chooses the "setting" (the negations within clauses) to make the problem as difficult as possible for a solver. This framework is highly relevant to fields like network security and robust system design, where one must account for malicious interference.
Methodology
The researchers utilize the cavity method, a technique originally developed for studying spin glasses in statistical mechanics, to analyze the AdSAT problem.
One of the core innovations is the construction of auxiliary factor graphs. By treating the adversary's choices—the negations—as physical degrees of freedom, the problem can be mapped onto a "decorated" graph structure. This allows for the application of message-passing algorithms like Belief and Survey Propagation to solve the cavity equations on both random regular and Poissonian graphs.
The analysis also involves a large deviation approach, computing the probability of rare negation configurations that minimize the entropy (number of solutions) of the system. Theoretical predictions were validated using the relsat algorithm for exact solution counting on smaller instances.
Key Insights and Ideas
The study reveals that the optimal adversarial strategy is surprisingly simple: the "Balanced" Strategy. In the thermodynamic limit ($N \to \infty$), the adversary's most effective move is to ensure each variable is negated approximately as many times as it appears un-negated. This local balancing acts as a powerful global constraint.
Furthermore, adversarial pressure significantly shifts the satisfiability threshold. For random 3-SAT, the standard threshold is $\alpha_c \approx 4.27$. Under an adversary, this threshold drops to $\alpha_a \approx 3.39$, meaning formulas become unsatisfiable much earlier. The authors also identify "pre-asymptotic" effects in small systems ($N < 100$), where numerical results may deviate from theoretical predictions due to the scale of the system.
Key Results
The researchers quantified the impact of adversarial choice across different graph types:
- Regular Graphs: For 3-SAT on L-regular graphs, the adversary can force unsatisfiability at degree $L=11$, whereas standard random formulas remain satisfiable until $L=13$.
- Poissonian Graphs: The adversarial satisfiability threshold was calculated to be $\alpha_a = 3.399 \pm 0.001$.
- Quantum SAT: The findings provide a lower bound for the Quantum SAT problem, suggesting that Quantum SAT is even more constrained than AdSAT.
Conclusion and Future Work
While the cavity method provides robust asymptotic results, the authors note that finite-size corrections are necessary for practical applications. In industrial-scale problems, the "pre-asymptotic" effects mean theoretical thresholds might only be reached at very large system sizes. Future research directions include extending this framework to Quantified Satisfiability (QSAT) and optimization under uncertainty. Additionally, bridging the "algorithmic gap"—developing efficient ways for an adversary to find optimal configurations in finite time—remains an open challenge.
Summary updated