Related Work and Conclusions

The idea of comparing the compactness of KR formalisms in representing information is not novel in AI. It is well known that first-order circumscription can be represented in second-order logic [46]. Kolaitis and Papadimitriou [34] discuss several computational aspects of circumscription. Among many interesting results they show a reduction from a restricted form of first-order circumscription into first-order logic. The proposed reduction will increase the size of the original formula by an exponential factor. It is left as an open problem to show whether this increase is intrinsic, because of the different compactness properties of the two formalisms, or there exists a more space-efficient reduction. When a first-order language is used, more results on compactness and existence of reductions are reported by Schlipf [47].

Khardon and Roth [31,32], and Kautz, Kearns and Selman [28] propose model-based representations of a $KB$ in Propositional Logic, and compare it with formula-based representations. Although their results are significant for comparing representations within PL, they refer only to this formalism, hence they are not applicable to our comparison between different PKR formalisms. The same comment applies also to the idea of representing a $KB$ with an efficient basis by Moses and Tennenholz [43], since it refers only to one PKR formalism, namely, PL.

An active area of research studies the connections of the various non-monotonic logics. In particular, there are several papers discussing the existence of translations that are polynomial in time and satisfy other intuitive requirements such as modularity and faithfulness. Janhunen [25], improving on results of Imielinski [24] and Gottlob [23], shows that default logic is the most expressive, among the non-monotonic logics examined, since both circumscription and autoepistemic logic can be modularly and faithfully embedded in default logic, but not the other way around. While these results are of interest and help to fully understand the relation among many knowledge representation formalisms, they are not directly related to ours. In fact, we allow for translations that are more general than polynomial time, while in all of the above papers they only consider translations that use polynomial time and also satisfy additional requirements.

The first result on compactness of representations for a propositional language is presented, to the best of our knowledge, by Kautz and Selman [30]. They show that, unless there is a collapse in the polynomial hierarchy, the size of the smallest representation of the least Horn upper bound of a propositional theory is superpolynomial in the size of the original theory. These results are also presented in a different form in the more comprehensive paper [48]. The technique used in the proof has been then used by us and other researchers to prove several other results on the relative complexity of propositional knowledge representation formalisms [10,11,8,21].

In a recent paper [6] we introduced a new complexity measure, i.e., compilability. In this paper we have shown how this measure is inherently related to the succinctness of PKR formalisms. We analyzed PKR formalisms with respect to two succinctness measures: succinctness in representing sets of models and succinctness in representing sets of theorems.

The main advantage of our framework is the machinery necessary for a formal way of talking about the relative ability of PKR formalisms to compactly represent information. In particular, we were able to formalize the intuition that a specific PKR formalism provides ``one of the most compact ways to represent models/theorems'' among the PKR formalisms of a specific class.

In our opinion, the proposed framework improves over the state of the art in two different aspects:

1. All the proofs presented in the previous papers only compare pairs of PKR formalisms, for example propositional circumscription and Propositional Logic [11]. These results do not allow for a precise classification of the level of compactness of the considered formalisms. Rephrasing and adapting these results in our framework allows us to infer that circumscription is model-coNP-complete and thm-$\Pi^p_{2}$-complete. As a consequence, we also have that it is more space-efficient of the WIDTIO belief revision formalism in representing sets of models or sets of theorems.

2. Using the proposed framework it is now possible to find criteria for adapting existent polynomial reductions showing C-hardness into reductions that show model-C or thm-C-hardness, where C is a class in the polynomial hierarchy [36].