期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2008
卷号：33
页码：403-432
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：We investigate the computational complexity of testing dominance and consistency
in CP-nets. Previously, the complexity of dominance has been determined 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. In our main results, we show here that
both dominance and consistency for general CP-nets are PSPACE-complete. We then
consider the concept of strong dominance, dominance equivalence and dominance
incomparability, and several notions of optimality, and identify the complexity
of the corresponding decision problems. The reductions used in the proofs are
from STRIPS planning, and thus reinforce the earlier established connections
between both areas
