The computational complexity of dominance and consistency in CP-nets
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 144-148.
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.
@inproceedings{ijcai2005p70,
title = {The computational complexity of dominance and consistency in CP-nets},
author = {Goldsmith, Judy and Lang, Jérôme and Truszczynski, Miroslaw and Wilson, Nic},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {144--148},
year = {2005},
url = {https://ijcai.org/proceedings/2005/70},
}
TY - CPAPER TI - The computational complexity of dominance and consistency in CP-nets AU - Goldsmith, Judy AU - Lang, Jérôme AU - Truszczynski, Miroslaw AU - Wilson, Nic T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 144 EP - 148 UR - https://ijcai.org/proceedings/2005/70 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
