TL;DR
This paper introduces a novel framework for generating random Boolean formulas and disjunctive logic programs, extending existing models for SAT and QBF. The proposed "multi-component" models allow for controlled generation of instances with varying hardness, exhibiting an "easy-hard-easy" pattern and showing promise for developing more robust AI solvers.
What Problem Does This Paper Address?
The field of Artificial Intelligence heavily relies on solving complex search and optimization problems. To effectively develop and test algorithms for these problems, researchers need reliable ways to generate "hard" instances – problems that are challenging for current solvers. While models for generating random Boolean Satisfiability (SAT) and Quantified Boolean Formulas (QBF) exist, they often produce instances that don't behave like real-world problems. Furthermore, there's a lack of established models for generating random disjunctive logic programs, a powerful formalism used in Answer Set Programming (ASP). This paper aims to fill this gap by proposing new models that generate random formulas and programs with controllable hardness and structure, making them more relevant for practical solver development and evaluation.
Methods
The core innovation is the "multi-component" model. Instead of generating a single complex formula, this approach combines multiple simpler formulas (e.g., k-CNF formulas for SAT, or specific QBF structures) into a larger one. For SAT, this involves creating disjunctions of $t$ k-CNF formulas. For QBF, it extends the Chen-Interian model by considering disjunctions of $t$ QBFs. A key theoretical contribution is showing that these multi-component models exhibit similar phase transition properties to their single-component counterparts, with the phase transition region shifting predictably with the number of components ($t$).
Crucially, the paper leverages the Eiter-Gottlob translation to connect QBFs to disjunctive logic programs. This allows the multi-component QBF models to directly inspire multi-component models for random disjunctive logic programs. The authors also provide theoretical bounds for the phase transition regions in these new models.
Datasets
The paper does not rely on pre-existing datasets for training. Instead, it introduces new benchmarks generated by its proposed multi-component models. These generated instances are then used to evaluate the performance of various SAT, QBF, and ASP solvers. The authors specifically mention submitting instances to the QBF Evaluation 2016, where they were classified as hard.
Key Insights and Ideas
- Controllable Hardness: The number of "components" ($t$) in the generated formulas/programs directly influences their hardness. Increasing $t$ makes instances significantly harder, offering a new dimension for controlling difficulty beyond just the ratio of clauses to variables.
- Bridging Random and Real-World Instances: The multi-component models, especially for $t > 2$, generate instances that are better solved by solvers tuned for real-world problems, unlike traditional random models. This suggests the component structure mimics some hidden structure present in practical instances.
- Phase Transition Predictability: The phase transition (the point where instances shift from easily solvable to difficult) in these models is theoretically predictable and shifts predictably with the number of components.
- First for Disjunctive Logic Programs: This work provides the first known models for generating random disjunctive logic programs with controllable hardness, which is significant for the development of ASP solvers.
- Impact on ASP Solver Behavior: The models allow for controlled generation of instances that can emphasize the model checking phase in ASP solvers, offering insights into their internal workings.
Key Results
- Phase Transition Shift: Theoretical results and experimental plots (Figure 1a, 1b) demonstrate that increasing the number of components ($t$) shifts the phase transition region to higher ratios of clauses to variables, and sharpens the transition.
- Hardness Increase: Experiments show that increasing $t$ leads to a dramatic increase in solver running times. For SAT, instances with 11 components took about 3 orders of magnitude longer than those with 1 component. For QBF, similar exponential increases in difficulty were observed.
- Solver Specialization: For $t > 2$, solvers specialized for real-world instances (e.g., GLUCOSE, LINGELING) outperform solvers specialized for random instances (e.g., KCNFS) on the generated problems (Figure 2a).
- QBF Instance Classification: Instances generated for the QBF evaluation were classified as hard, validating the model's ability to produce challenging problems.
- ASP Model Checking Emphasis: For ASP solvers, the ratio of model checking time to total execution time increases significantly with $t$, reaching up to 88% for $t=11$ (Figure 2b).
Limitations and Future Work
- Theoretical Conjecture: The paper notes that for the single-component k-CNF model, it is conjectured that the satisfiability bounds $\rho_t(k)$ and $\rho_u(k)$ are equal, but this remains an open problem. This conjecture also extends to the multi-component models.
- Real-World Instance Similarity: While the models show promise in generating instances solved better by industrial solvers, the exact nature of the "hidden structure" that makes real-world instances behave differently is still an area of active research. The authors conjecture that the component structure plays a role.
- Future Work: The authors suggest further investigation into the theoretical properties of these models, particularly concerning the phase transition conjecture. They also highlight the potential for these models to aid in the development and testing of ASP solvers by allowing control over the emphasis on model checking.
Summary updated