The are the format
=c   for literals   and sets of prerequisite-free ordered unary defaults is co-NP-hard.

Proof: Proof is by many-one reduction from propositional satisfiability to testing Let be any set of clauses, and let be the set of propositional variables occurring in
. Let be an injective function that maps each clause to a propositional variable
() such that   /   . Let

![0_image_0.png](0_image_0.png)

The orderedness condition is fulfilled because the relation «
× false ) ( × '
) is irreflexive.

( )
We claim that     is satisfiable if and only if that is, there is a model such that seems . We construct an extension Sof such that false /  . Let

![0_image_1.png](0_image_1.png)

Define   = Cn(
). To verify that is an extension of it suffices to check that for every :
/ 
, and this is
/
'
straightforward. Hence fc false.

Assume that be a model such that for all propositional variables Let We show that     =    .  Because false /
that = ( ) for some F Hence F For all such Hence for every , there is GD( 
:
l 
/   for some 1 and hence by definition     =   . Hence every definition     =
clause in is true in is and is satisfiable.

Ben-Eliyahu and Dechter (1996) show that testing =c for a class of default theories that subsumes all classes in the Kautz and Selman and Stillman hierarchy that have a 2-literal objective part is co-NP-complete. Hence the problems in Theorems 4.12, 4.13 and 4.14 are in co-NP, and consequently co-NP-complete.  The Ben-Eliyahu and Dechter result, however, has no direct implications on the complexity of the prioritized versions of these problems.