
| 2   |
|-----|
| 3   |
| 4   |
| 5   |
| 6   |
| 7   |
| 8   |
| 9   |
| 10  |
| 11  |
| 12  |
| 13  |
| 14  |

| class of default theories   |  complexity when clauses in W are       |           |           |           |
|-----------------------------|-----------------------------------------|-----------|-----------|-----------|
| Horn                        | 2-literal                               | 1-literal |           |           |
| c-NP-hard                   |                                         |           |           |           |
| 1                           | disjunction-free                        | c-NP-hard | c-NP-hard |           |
| 2                           | unary                                   | c-NP-hard | c-NP-hard | c-NP-hard |
| 3                           | disjunction-free ordered                | c-NP-hard | c-NP-hard | c-NP-hard |
| c-NP-hard                   |                                         |           |           |           |
| 4                           | ordered unary                           | c-NP-hard | c-NP-hard |           |
| 5                           | disjunction-free normal                 | c-NP-hard | c-NP-hard | c-NP-hard |
| 6                           | Horn                                    | c-NP-hard | c-NP-hard | c-NP-hard |
| 7                           | normal unary                            | c-NP-hard | c-NP-hard | c-NP-hard |
| 8                           | prerequisite-free                       | c-NP-hard | c-NP-hard | c-NP-hard |
| prerequisite-free ordered   | c-NP-hard                               |           |           |           |
| 9                           | c-NP-hard                               | c-NP-hard |           |           |
| 10                          | prerequisite-free unary                 | c-NP-hard | c-NP-hard | c-NP-hard |
| 11                          | prerequisite-free ordered unary         | c-NP-hard | c-NP-hard | c-NP-hard |
| 12                          | prerequisite-free normal                | c-NP-hard | c-NP-hard | c-NP-hard |
| 13                          | prerequisite-free normal unary          | c-NP-hard | c-NP-hard | PTIME     |
| 14                          | prerequisite-free positive normal unary | c-NP-hard | c-NP-hard | PTIME     |

Table 2: Complexity of the consequence relations = B and _ BH
Table 3: References to theorems on the complexity of = B and = BH
When looking at Table 2 it is slightly surprising that the favorable computational properties in the totally ordered case are in no way reflected in the complexity of reasoning with arbitrary priorities. With arbitrary priorities, for almost all classes of default theories in the Kautz-Selman-Stillman hierarchy the complexity is the same as the complexity of Reiter's default logic and the lexicographic prioritized default logic that is discussed in Section 5.

| class of default theories               | reference   |           |       |
|-----------------------------------------|-------------|-----------|-------|
| Horn                                    | 2-literal   | 1-literal |       |
| K & S                                   | K&S         | K & S     |       |
| d isjunction-free                       |             |           |       |
| unary                                   | K & S       | K&S       | K & S |
| disjunction-free ordered                | K & S       | K&S       | K & S |
| ordered unary                           | K & S       | K&S       | K & S |
| disjunction-free normal                 | K & S       | K&S       | K&S   |
| Horn                                    | K & S       | K&S       | K&S   |
| normal unary                            | 14          | 14        | T4.15 |
| prerequisite-free                       | 14          | 14        | 12    |
| prerequisite-free ordered               | 14          | 14        | 12    |
| prerequisite-free unary                 | 14          | 14        | 11    |
| prerequisite-free ordered unary         | 14          | 14        | T4.14 |
| prerequisite-free normal                | 14          | 14        | T4.13 |
| prerequisite-free normal unary          | 14          | 14        | T4.11 |
| prerequisite-free positive normal unary | T412        | T4.12     | 13    |
