present paper we show how this new measure can be directly used to characterize the space efficiency of PKR formalisms. We emphasize methodological aspects, expressing in a more general context many of the results presented before.

## 1.2 Goal

The notion of polynomial time complexity has a great importance in KR (as well as many other fields of computer science), as problems that can be solved in polynomial time are to be considered easy, from a computational point of view.

The notion of polynomial many-one reducibility **also has a very intuitive meaning when**
applied to KR: if there exists a polynomial many-one reduction from one formalism to another one, then the time complexity of reasoning in the two **formalisms is comparable.** This allows to say, e.g., that inference in PL is coNP-complete, i.e. it is one of the hardest problems among those in the complexity class coNP.

As a result, we have a formal tool for comparing the difficulty of reasoning in two formalisms. What is missing is a way for saying that one formalism is able to represent the same information in less space. Example 2 **We consider again the lunch scenario of the previous example. We show that** we can reduce the size of the representation using circumscription instead of Propositional Logic. In PL, the knowledge of the previous example was represented by the formula F:
F = (sandwich ∨ salad) ∧ (¬sandwich ∨ ¬salad) ∧ (water ∨ coke) ∧ (¬water ∨ ¬**coke**)
The set of models of this formula is A, and the models of A **are exactly the minimal**
models of the formula Fc **defined as follows.**
Fc = (sandwich ∨ salad) ∧ (water ∨ **coke**)
By the definition of circumscription (McCarthy, 1980) it holds that F **is equivalent to**
CIRC(Fc; {sandwich, salad,water, coke}, ∅, ∅). Note that Fc is shorter than F**. If this result**
can be proved to hold for arbitrary sets of models, we may conclude that circumscription is more space efficient than Propositional Logic in representing knowledge expressed as sets of models.

Our goal is to provide a formal way of talking about the relative ability of PKR formalisms to compactly represent information, where the information is either a set of models or a set of theorems. In particular, we would like to be able to **say that a specific PKR**
formalism provides "one of the most compact ways to represent models/theorems" among the PKR formalisms of a specific class.

## 1.3 Results

We introduce two new compactness measures (model and theorem compactness**) and the** corresponding classes (model-C and thm-C, where C is a complexity class like P, NP, coNP, etc.). Such classes form two hierarchies that are isomorphic to the polynomial-time hierarchy (Stockmeyer, 1976). We show that the relative space efficiency of a PKR formalism is