Abstract
We investigate the computational complexity of testing dominance and consistency in CP-nets. Up until now, the complexity of dominance has been determined only for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. We show here that both dominance and consistency testing for general CP-nets are PSPACE-complete. The reductions used in the proofs are from STRIPS planning, and thus establish strong connections between both areas.
| Original language | English |
|---|---|
| Pages (from-to) | 144-149 |
| Number of pages | 6 |
| Journal | IJCAI International Joint Conference on Artificial Intelligence |
| State | Published - 2005 |
| Event | 19th International Joint Conference on Artificial Intelligence, IJCAI 2005 - Edinburgh, United Kingdom Duration: Jul 30 2005 → Aug 5 2005 |
ASJC Scopus subject areas
- Artificial Intelligence