Generating Hard Random Boolean Formulas and Disjunctive Logic Programs

Giovanni Amendola, Francesco Ricca, Miroslaw Truszczynski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationProceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2017)
PublisherIJCAI Inc
Pages532-538
Number of pages7
ISBN (Electronic)978-0-9992411-0-3
Publication statusPublished - 25 Aug 2017
Event26th International Joint Conference on Artificial Intelligence - Melbourne, Australia
Duration: 19 Aug 201725 Aug 2017
https://ijcai-17.org/index.html
https://ijcai-17.org/
https://ijcai-17.org/

Conference

Conference26th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2017
CountryAustralia
CityMelbourne
Period19/08/1725/08/17
Internet address

Fingerprint

Dive into the research topics of 'Generating Hard Random Boolean Formulas and Disjunctive Logic Programs'. Together they form a unique fingerprint.

Cite this