based on restricting the possible queries in other ways, i.e., considering only queries in Horn form (Kautz, Kearns, & Selman, 1995).

Reasoning with characteristic models (Kautz, Kearns, & Selman, 1993) is based on using only a subset of models of the original formula. As for forgetting, this may increase the size of the representation of a knowledge base exponentially. Khardon and Roth (1996)
have shown that aracteristic models can be used for efficient reasoning on some sets of restricted queries.

| Problem                |
|------------------------|
| Synt. Var-independence |
| Var-independence       |
| Dependent variables    |
| FullVar-independence   |
| Var-simplified         |
| Var-equivalence        |

## 7. Concluding Remarks

We have investigated several ways of answering the key question of determining what a propositional knowledge base tells about the (in)dependencies between variables and formulas. For each of the notions studied, we have related it to other previously known notions and we have studied it from a computational point of view, giving both complexity results and characterization results to be used for practical computation. In the light of our results, it appears that the various forms of logical independence are closely connected. Especially, several of them had been proposed by different authors without being explicitely related. Boutilier's influenceability and Lakemeyer's relevance of a formula to a subject matter are identical to FV-independence (Propositions 25 and 26). We also discussed much related work, and suggest some extensions to more general framework than mere propositional

| Problem                |
|------------------------|
| Synt. Lit-independence |
| Lit-independence       |
| Dependent literals     |
| FullLit-independence   |
| Lit-simplified         |
| Lit-equivalence        |

logic.

The following table gives a synthetic view of many notions addressed in this paper and the corresponding complexity results.

Problems on literals and their complexity.

| Definition                 | Complexity     |
|----------------------------|----------------|
| Lt(E)                      |                |
| 99                         | coNP-complete  |
| {{ } } }}                  | BH 2 -complete |
| coNP-complete              |                |
| L ⊆ DepLit(Σ)              |                |
| ∀Ι , {|} ✈ Σ # Ι # Lit(Σ)  | NP-complete    |
| ForgetLit(E, Lit(E) \ L) ≡ |                |
| ForgetLit(Φ, Lit(Φ) \ L)   | n 2 -complete  |

Problems on variables and their complexity.

| Notation      |
|---------------|
| L A L         |
| Dep Lit ( Σ ) |
| L = L  Φ      |

| Notation                    | Definition                 | Complexity   |               |
|-----------------------------|----------------------------|--------------|---------------|
| Var(Σ)  V = ∅               |                            |              |               |
| V A + I                     | ∃Φ , Φ ≡ Σ, Var(Φ) ∩ Σ = ∅ | cNP-complete |               |
| {v | v → £}                 |                            |              |               |
| DepVar(Σ)                   | B-complete                 |              |               |
| V ⊆ DepVar(Σ)               | cNP-complete               |              |               |
| ∀v . {v} H ‡ ‡ ¥ v Ø Var(Σ) | NP-complete                |              |               |
| ForgetVar(Σ, Var(Σ) \ V) ≡  |                            |              |               |
| L = V  Φ                    | ForgetVar(Φ,Var(Φ)\        | V            | n 2 -complete |
