Abstract: The circumscription of a propositional formula T may not be representable in polynomial space, unless the polynomial hierarchy collapses. This depends on the specific formula T, as some can be circumscribed in little space and others cannot. The problem considered in this article is whether this happens for a given formula or not. In particular, the complexity of deciding whether CIRC(T) is equivalent to a formula of size bounded by k is studied. This theoretical question is relevant as circumscription has applications in temporal logics, diagnosis, default logic and belief revision.

Paolo Liberatore, “Checking the Size of Circumscribed Formulae” International Journal of Advanced Research in Artificial Intelligence(IJARAI), 3(12), 2014. http://dx.doi.org/10.14569/IJARAI.2014.031205

@article{Liberatore2014,
title = {Checking the Size of Circumscribed Formulae},
journal = {International Journal of Advanced Research in Artificial Intelligence},
doi = {10.14569/IJARAI.2014.031205},
url = {http://dx.doi.org/10.14569/IJARAI.2014.031205},
year = {2014},
publisher = {The Science and Information Organization},
volume = {3},
number = {12},
author = {Paolo Liberatore}
}