Definition 4.4 The consequence relations =B and =BH are defined by ∆ =B   if and only if the formula    is in all P-preferred B  extensions of ∆, and ∆ = BH    if and only if the formula is in all P-preferredBH extensions of A.

Lemma 4.5 Let for all          ,      is a T-preferredB extension of              if and only if    is a T-preferredBH extension of Proof: If    is inconsistent, then the inconsistent extension   is the unique T-preferred B
and T -preferred BH extension of ∆ . So assume    is consistent. ( ⇒ ) Assume that    is a T -preferred B extension of Definition 4.3. Let 0, and hence     = U i> 0 Cn (  {) is a T-preferred BH extension of ∆ . Induction hypothesis :
i = 
i-l = 
hypothesis that and i-1 ≠    simply because   i-1
( ( ) Let     be a T -preferred BH extension of 0 0 are the sets in Definition 4.2. Let   i      0 be the sets in Definition 4.3. We sssshhhooowww Immediate. Inductive case     1: Assume that for no  T  :
and no  T  :      is active in Because  {-1 Hence that for induction hypothesis {
≠ 
{ =  {_1, and further  {_1 for all a contradiction with the assumption = and the fact  !_ 1 ≠     obtained with the induction hypothesis.  Therefore the assumption is false, and    ≠
and 
□

## 4.1 Complexity In The General Case

With no restrictions on the form of defaults, both the Brewka and the Baader and Hollunder prioritized default logics are complete for the second level of the polynomial hierarchy.  This means that there are polynomial time translations between cautious reasoning in Reiter's default logic and the prioritized versions of cautious reasoning in both of these logics.

Theorem 4.6 Testing ∆ = β   for normal default theories ∆ , strict partial orders P and formulae Proof: The Π 2 -hardness is because with an empty priority relation Brewka's logic coincides with Reiter's default logic (Proposition 6 in (Brewka, 1994)), whi is Π 2 -hard even with