Ordered Logic (
$\mathcal{OL}$
) is an elegant, yet powerful extension of logic programming with the object-oriented notions of modules, inheritance and exceptions. The capability to naturally express several forms of nonmonotonic reasoning is a major feature of
$\mathcal{OL}$
and has recently candidated this language as a powerful tool for knowledge representation and reasoning.
After an overview of
$\mathcal{OL}$
, the paper analyzes the expressive power of the language. The expressibility of
$\mathcal{OL}$
under both brave and cautious inference modalities is formally determined by applying Fagin's theorem. The results show that under the cautious inference modality
$\mathcal{OL}$
captures the complexity class co-NP; while under the brave inference modality,
$\mathcal{OL}$
captures the complexity class NP.
