The computational complexity of dominance and consistency in CP-nets

Files in this item

Icon
Name: PSPACEIJCAIfinal- ...
Size: 90.25Kb
Format: PDF
Description: Accepted version
View/Open

The computational complexity of dominance and consistency in CP-nets

Goldsmith, Judy; Lang, Jérôme; Truszczynski, Miroslaw; Wilson, Nic
Date: 2005-07
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
Related: https://www.ijcai.org/Proceedings/2005
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.

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.

Show full item record

This item appears in the following Collection(s)

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement