Theorem 3 PL is in model-P and it is thm-coNP**-complete.**
We can now formally establish the connection between succinctness of representations and compilability classes. In the following theorems, the complexity classes C, C1, C2 **belong**
to the polynomial hierarchy (Stockmeyer, 1976). In Theorems 5 and 7 we assume that the polynomial hierarchy does not collapse.

We start by showing that the existence of model-preserving reductions from a formalism to another one can be easily obtained if their levels in the model hierarchy satisfy a simple condition.

Theorem 4 Let F1 and F2 be two PKR formalisms. If F1 is in model-C and F2 is modelC-hard, then there exists a poly-size reduction f : F1 7→ F2 **satisfying model preservation.**
Proof. Recall that since F1 is in model-C, model checking in F1 is in k❀**C, and since** F2 is model-C-hard, model checking in F1 **is non-uniformly comp-reducible to model checking in**
F2. That is, (adapting Def. 6) there exist two poly-size binary functions f1 and f2**, and a**
polynomial-time binary function g such that for every pair hKB, Mi **it holds that**
M |=F1 KB if and only if g(f2(KB, |M|), M) |=F2 f1(KB, |M|)
(note that g is the poly-time function appearing in Def. 6, different from gKB **which is the**
poly-size circuit appearing in Def. 8).

Now observe that |M| can be computed from KB by simply counting the letters appearing in KB; let f3 be such a counting function, i.e., |M| = f3(KB). Clearly, f3 **is poly-size.**
Define the reduction f as f(KB) = f1(KB, f3(KB**)). Since poly-size functions are closed**
under composition, f is poly-size. Now we show that f **is a model-preserving reduction. By** Definition 8, we need to prove that there exists a polynomial p **such that for each knowledge**
base KB in F1, there exists a poly-size circuit gKB **such that for every interpretation** M of the variables of KB it holds that M |=F1 KB iff gKB(M) |=F2 f(KB).

We proceed as follows: Given a KB in F1, we compute z = f2(KB, |M|) = f2(KB, f3(KB)).

Since f2 and f3 are poly-size, z has size polynomial with respect to |KB|**. Define the circuit** gKB(M) as the one computing g(z, M) = g(f2(KB, f3(KB)), M). Since g **is a poly-time**
function over both inputs, and z is poly-size in KB, there exists a representation of g(**z, M**)
as a circuit gKB whose size is polynomial wrt KB. From this construction, M |=F1 KB iff gKB(M) |=F2 f(KB**). Hence, the thesis follows.**
The following theorem, instead, gives a simple method to prove that there is no modelpreserving reduction from one formalism to another one.

Theorem 5 Let F1 and F2 **be two PKR formalisms. If the polynomial hierarchy does not**
collapse, F1 is model-C1-hard, F2 is in model-C2, and C2 ⊂ C1**, then there is no poly-size**
reduction f : F1 7→ F2 **satisfying model preservation.**
Proof. We show that if such a reduction exists, then C1/poly ⊆ C2**/poly which implies that**
the polynomial hierarchy collapses at some level (Yap, 1983). Let A **be a complete problem**
for class C1 - e.g., if C1 **is Σ**p 3 then A may be validity of ∃∀∃**-quantified boolean formulae**
(Stockmeyer, 1976). Define the problem ǫA **as follows.**
ǫA = {hx, yi | x = ǫ **(the empty string) and** y ∈ A}