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.

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 :

The set of models of this formula is , and the models of are exactly the minimal models of the formula defined as follows.

By the definition of circumscription [41] it holds that is equivalent to . Note that is shorter than . 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.