ON COMPACT REPRESENTATIONS OF PROPOSITIONAL CIRCUMSCRIPTION

Circumscription is a popular common-sense reasoning technique, used in the fields of Artificial Intelligence, Databases and Logic Programmin g. In this paper we investigate the size of representations (formulae, data structures) equivalent to the circumscription of a propositional formula T, taking into account three different definitions of equival ence. We find necessary and sufficient conditions for the existence of polynomial-size representations (formulae, data structures) equivalen t to the circumscription of T in the three cases. All such conditions imply the collapse of the polynomial hierarchy. In particular, we prov e that - unless the polynomial hierarchy collapses at the second level - the size of the shortest propositional formula T' logically equival ent to the circumscription of T grows faster than any polynomial as th e size of T increases. The significance of this result in the related held of closed-world reasoning is then analyzed.