Default theories that always have extensions

摘要

Default logic is an important and influential formalization of commonsense reasoning. Determining whether a given default theory has an extension is the main computational problem pertinent to default logic, the analog of testing for validity and finding deductions in more classical logics. Substantially generalizing a result by Etherington [5] we show that all default theories that have no odd cycles (in some precise sense) have an extension, which can be found efficiently. We also give a proof that it is NP-complete to find extensions even for default theories with no prerequisites and at most two literals per default, a case substantially simpler than the NP-completeness results in the literature.