Edinburgh Research Explorer

Generating Hard Random Boolean Formulas and Disjunctive Logic Programs

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

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

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.

Event

26th International Joint Conference on Artificial Intelligence

19/08/1725/08/17

Melbourne, Australia

Event: Conference

ID: 36168653