
| Time Complexity                         | Space Efficiency              |                       |
|-----------------------------------------|-------------------------------|-----------------------|
| Propositional                           | coNP-complete                 | thm-coNP-complete     |
| Logic                                   | (Cook, 1971)                  | (Cadoli et al., 1996) |
| p                                       |                               |                       |
| WIDTIO                                  | Π 2 -complete                 | thm-coNP-complete     |
| (Eiter & Gottlob, 1992) & (Nebel, 1998) | Th. 18                        |                       |
| Skeptical                               | Π p -complete                 | thm-Πp -complete      |
| 2                                       | 2                             |                       |
| Belief Revision                         | (Eiter & Gottlob, 1992)       | Th. 19                |
| Circumscription                         | Π p -complete                 | thm-Πp -complete      |
| 2                                       | 2                             |                       |
| (Eiter & Gottlob, 1993)                 | Th. 11                        |                       |
| GCWA                                    | Π p -complete                 | thm-coNP-complete     |
| 2                                       |                               |                       |
| (Eiter & Gottlob, 1993) & (Nebel, 1998) | Th. 12                        |                       |
| Skeptical                               | Π p -complete                 | thm-Πp -complete      |
| 2                                       | 2                             |                       |
| Default Reasoning                       | (Gottlob, 1992)               | Th. 14                |
| p -complete                             | thm-Σp                        |                       |
| Credulous                               | Σ                             | -complete             |
| 2                                       | 2                             |                       |
| Default Reasoning                       | (Gottlob, 1992)               | Th. 15                |
| Stable Model                            | coNP-complete                 | thm-coNP-complete     |
| Semantics                               | (Marek & Truszczy´nski, 1991) | Th. 8                 |

all elements of W(K, A**). Once this is done, one is left with model checking and inference in**
PL. Hence, WIDTIO has the same space efficiency as PL, which is below circumscription.

Figures 3 and 4 contain the same information of Tables 1 and 2, **but highlight existing reductions. Each figure contains two diagrams, the left one showing the existence of** polynomial-time reductions among formalisms, the right one showing the existence of polysize reductions. An arrow from a formalism to another denotes that the former can be reduced to the latter one. We use a bidirectional arrow to denote arrows in both directions and a dashed box to enclose formalisms that can be reduced one **into another. Note that**
some formalisms are more appropriate in representing sets of models, while others perform better on sets of formulae. An interesting relation exists between skeptical default reasoning and circumscription. While there is no model-preserving poly-size reduction from circumscription to skeptical default reasoning (Gogic et al., 1995), a theorem-preserving poly-size reduction exists, as shown by Theorem 14.

## 7. Related Work And Conclusions

The idea of comparing the compactness of KR formalisms in representing information is not novel in AI. It is well known that first-order circumscription can be represented in secondorder logic (Schlipf, 1987). Kolaitis and Papadimitriou (1990) discuss several computational aspects of circumscription. Among many interesting results they show a reduction from a restricted form of first-order circumscription into first-order logic. The proposed reduction will increase the size of the original formula by an exponential factor. It is left as an open problem to show whether this increase is intrinsic, because **of the different compactness**
properties of the two formalisms, or there exists a more space-efficient reduction. When a