Generating Hard Random Boolean Formulas and Disjunctive Logic Programs
Abstract
We propose a model of random quantified boolean formulas and their natural random disjunctive logic program counterparts. The model extends the standard models for random SAT and 2QBF. We provide theoretical bounds for the phase transition region in the new model, and show experimentally the presence of the easy-hard-easy pattern. Importantly, we show that the model is well suited for assessing solvers tuned to real-world instances. Moreover, to the best of our knowledge, our model and results on random disjunctive logic programs are the first of their kind.
Cite
Text
Amendola et al. "Generating Hard Random Boolean Formulas and Disjunctive Logic Programs." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/75Markdown
[Amendola et al. "Generating Hard Random Boolean Formulas and Disjunctive Logic Programs." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/amendola2017ijcai-generating/) doi:10.24963/IJCAI.2017/75BibTeX
@inproceedings{amendola2017ijcai-generating,
title = {{Generating Hard Random Boolean Formulas and Disjunctive Logic Programs}},
author = {Amendola, Giovanni and Ricca, Francesco and Truszczynski, Miroslaw},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {532-538},
doi = {10.24963/IJCAI.2017/75},
url = {https://mlanthology.org/ijcai/2017/amendola2017ijcai-generating/}
}