Let T be any strict total order on that extends P . The sizes of the default theory
²  and they can to and the strict total order T are linearly proportional to the size of l be constructed in polynomial time.

First we show that for each extension of that contains   there is    ¹ such that l 1 satisfies ∀  2 (
i i ( 1) = 1 iff  !

1
(the function i selects the th element of an  -tuple.) Let    be an extension of and 1 2 .

Because defaults in are normal, is consistent. Hence appl(
) because the only default where   occurs in the conclusion is 1 l 2 that is, l
² is a logical consequence of the conclusions of generating defaults of 2 for Because does not occur in l l l l By Lemma 5.11    ¹ , defined as  ¡(   ¹) = 1 if  ¦
and A 2 (
l 2 ).

Then we show that for each   1 that satisfies V  2 p l
² ), there is an extension and 1) = 1 iff 1 such that
. Assume that    1 satisfies of A 2 (
l 2 ). Let   =
1 ) = 1 1 ≤
1) = 0 1 <
. Because the extension It is straightforward to verify that is an extension of is consistent, appl( l 2 :
). Because 1 is the P-least default in   , all T-preferred L extensions apply l 2 The counterpart of the T-preferred the extension is the lexicographically maximal and vice versa. This is by the construction of T, where the defaults : +
are ordered as :
satisfying ∀   ²(
1 2 ) iff    belongs to the T-preferred L extension of
□
Notice that Lemma 5.12 cannot be reconstructed in the prioritized default logics by Brewka and by Baader and Hollunder because the construction is based on a highest priority default that becomes applicable only after a number of lower priority defaults have been applied, and in these cases those logics do not work like the lexicographic prioritized default logic. While testing = for strict total orders T is higher in the polynomial hierarchy than cautious reasoning in unprioritized default logic, testing = β and = β H is one level lower.

The area of the corresponding to the corresponding of the corresponding
, strict total orders T on , and formulae
, the problem of testing ∆ = f   is ∆ f -hard.

Proof: All problems in A 3 are polynomial time many-one reducible to Maximum 2-
QUANTIFIED FORMULA, which by Lemma 5.12 is polynomial time many-one reducible to our problem.

□
Testing = for strict total orders T is in ∆ 2 .  The proof of this fact is based on computing the unique preferred extensions step by step, at each step determining whether there is an extension in which one of the defaults is applied in addition to those defaults which we have aready committed to. Lemma 5.14 For the procedure in Figure 6, the call exists(      ) returns true if and ol and the content of such that appl(    ) for all
. The procedure runs in nondeterministic polynomial time given an NP oracle for CN.

Proof: First the procedure guesses a set of conclusions     that possibly are the conclusions of ting the generating defaults of the possible extension Cn (
).  The call to extension(