Generating hard random boolean formulas and disjunctive logic programs

Giovanni Amendola, Francesco Ricca, Miroslaw Truszczynski

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

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 publication26th International Joint Conference on Artificial Intelligence, IJCAI 2017
EditorsCarles Sierra
Pages532-538
Number of pages7
ISBN (Electronic)9780999241103
DOIs
StatePublished - 2017
Event26th International Joint Conference on Artificial Intelligence, IJCAI 2017 - Melbourne, Australia
Duration: Aug 19 2017Aug 25 2017

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume0
ISSN (Print)1045-0823

Conference

Conference26th International Joint Conference on Artificial Intelligence, IJCAI 2017
Country/TerritoryAustralia
CityMelbourne
Period8/19/178/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

Fingerprint

Dive into the research topics of 'Generating hard random boolean formulas and disjunctive logic programs'. Together they form a unique fingerprint.

Cite this