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 language | English |
---|---|
Title of host publication | 26th International Joint Conference on Artificial Intelligence, IJCAI 2017 |
Editors | Carles Sierra |
Pages | 532-538 |
Number of pages | 7 |
ISBN (Electronic) | 9780999241103 |
DOIs | |
State | Published - 2017 |
Event | 26th International Joint Conference on Artificial Intelligence, IJCAI 2017 - Melbourne, Australia Duration: Aug 19 2017 → Aug 25 2017 |
Publication series
Name | IJCAI International Joint Conference on Artificial Intelligence |
---|---|
Volume | 0 |
ISSN (Print) | 1045-0823 |
Conference
Conference | 26th International Joint Conference on Artificial Intelligence, IJCAI 2017 |
---|---|
Country/Territory | Australia |
City | Melbourne |
Period | 8/19/17 → 8/25/17 |
Bibliographical note
Funding Information:This work was partially supported by the Italian Ministry MISE under projects “PIUCultura“ (n. F/020016/01-02/X27), and “Smarter Solutions in the Big Data World” (PON 2014-2020), and by EPSRC grant N023056.
ASJC Scopus subject areas
- Artificial Intelligence