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.