If we consider the knowledge base x **as given off-line, and the truth assignment** y as given on-line, we obtain the following definition:

## Mmc = {Hx, Yi | Y **Is A Minimal Model Of** X }

This problem can be shown to be k❀**coNP-complete (Cadoli et al., 1996b, Theorem 13).**
Hence, it is very unlikely that it can be in k❀**P; that is, it is very unlikely that there exists**
some off-line processing of the knowledge base, yielding (say) some data structure x
′**, such**
that given y, it can now checked in polynomial time whether y **is a minimal model of** x. This, of course, unless x
′ **has exponential size. This observation applies also when** x
′**is a**
knowledge base in Propositional Logic, and led to the interpretation that Circumscription is more compact, or succint, than PL (Cadoli, Donini, & Schaerf, 1995; Gogic et al., 1995). Our framework allows to generalize these results for all PKR **formalisms, as shown in the**
sequel.

## 4. Reductions Among Kr Formalisms

We now define the forms of reduction between PKR formalisms that we analyze in the following sections. A formula can always be represented as a **string over an alphabet Σ,**
hence from now on we consider translations as functions transforming strings.

Let F1 and F2 be two PKR formalisms. There exists a poly-size reduction **from** F1 to F2, denoted as f : F1 7→ F2, if f **is a poly-size function such that for any given knowledge**
base KB in F1, f(KB) is a knowledge base in F2**. Clearly, reductions should be restricted**
to produce a meaningful output. In particular, we now discuss reductions that preserve the models of the original theory.

The semantic approach by Gogic and collegues (1995) is that the models of the two knowledge bases must be exactly the same. In other words, if a knowledge base KB **of the**
formalism F1 is translated into a knowledge base KB′ of the formalism F2**, then** M |=F1 KB
if and only if M |=F2 KB′**. This approach can be summarized by: a reduction between**
formalisms F1 and F2 is a way to translate knowledge bases of F1 **into knowledge bases of** F2, preserving their sets of models. While this semantics is intuitively grounded, it is very easy to show examples in which two formalisms that we consider equally space-efficient cannot be translated to each other. Let us consider for instance a variant of the propositional calculus in which the syntax is that formulas must be of the form x1 ∧ F, where F **is a regular** formula over the variables x2, . . .**. Clearly, this formalism is able to represent knowledge**
in the same space than the propositional calculus (apart a polynomial factor). However, according to the definition, this formalism cannot be translated to propositional calculus:
there is no knowledge base that is equivalent to KB = ¬x1**. Indeed, the only model of**
KB is ∅**, while any model of any consistent knowledge base of the modified propositional**
calculus contains x1.

We propose a more general approach that can deal also with functions f **that change**
the language of the KB. To this end, we allow for a translation gKB **from models of** KB to models of f(KB**). We stress that, to be as general as possible, the translation may depend** on KB **— i.e., different knowledge bases may have different translations of their models.**
We want this translation easy to compute, since otherwise the computation of gKB **could**
hide the complexity of reasoning in the formalism. However, **observe that to this end, it is**