

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

Therefore, it is possible to define the notions of hardness and completeness for k❀**C for**
every complexity class C.

Definition 7 (k❀C-completeness) Let S be a language of pairs and C **a complexity class.**
S is k❀C-hard iff for all problems A ∈ k❀C we have that A ≤nu−comp S**. Moreover,** S is k❀C-complete if S is in k❀C and is k❀**C-hard**.

We now have the right complexity class to completely characterize the problem pli**. In**
fact pli is k❀**coNP-complete (Cadoli et al., 1996b, Theorem 7). Furthermore, the hierarchy**
formed by the compilability classes is proper if and only if the polynomial hierarchy is proper (Cadoli et al., 1996b; Karp & Lipton, 1980; Yap, 1983) **— a fact widely conjectured** to be true.

Informally, we may say that k❀**NP-hard problems are "not compilable to P", as from**
the above considerations we know that if there exists a preprocessing of their fixed part that makes them on-line solvable in polynomial time, then the polynomial hierarchy collapses.

The same holds for k❀coNP-hard problems. In general, a problem which is k❀**C-complete**
for a class C can be regarded as the "toughest" problem in C, even after arbitrary preprocessing of the fixed part. On the other hand, a problem in k❀**C is a problem that, after**
preprocessing of the fixed part, becomes a problem in C (i.e., **it is "compilable to C").**
We close the section by giving another example of use of the compilability classes through the well-known formalism of Circumscription (McCarthy, 1980). Let x **be any propositional** formula. The minimal models of x are the truth assignments satisfying x **having as few** positive values as possible (w.r.t. set containment). The problem we consider is: check whether a given model is a minimal model of a propositional formula. This problem, called Minimal Model checking (mmc**), can be reformulated as the problem of model checking in**
Circumscription, which is known to be co-NP-complete (Cadoli, 1992).