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 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 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:

- 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--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.
- 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].