The computational complexity of dominance and consistency in CP-nets
Loading...
Files
Accepted version
Date
2005-07
Authors
Goldsmith, Judy
Lang, Jérôme
Truszczynski, Miroslaw
Wilson, Nic
Journal Title
Journal ISSN
Volume Title
Publisher
International Joint Conferences on Artificial Intelligence (ICJAI)
Published Version
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.
Description
Keywords
CP-nets , PSPACE-complete , Constraints
Citation
Goldsmith, J., Lang, J., Truszczynski, M. and Wilson, N. (2005) 'The computational complexity of dominance and consistency in CP-nets', IJCAI'05: Proceedings of the 19th International Joint Conference on Artificial intelligence, Edinburgh, Scotland, 30 July-05 August, pp. 144–149.
Copyright
© August 1, 2005 International Joint Conferences on Artificial Intelligence. All rights reserved. This publication, or parts thereof, may not be reproduced in any form without permission