The Resolution Width Problem is EXPTIME-Complete.

Alexander Hertel Alasdair Urquhart

Published in: Electron. Colloquium Comput. Complex. (2006)

Keyphrases

exptime complete
description logics
data complexity
expressive power
expressive description logics
pspace complete
transitive closure
special case
np complete
query answering
query language
data model
satisfiability problem
expert systems
reasoning tasks
knowledge base
artificial intelligence