More complexity results about reasoning over (m)CP-nets

Abstract

Aggregating preferences over combinatorial domains has several applications in artificial intelligence. Due to the exponential nature of combinatorial preferences, compact representations are needed, and (m)CP-nets are among the most studied formalisms. Unlike CP-nets, which received an extensive complexity analysis, mCP-nets, as mentioned several times in the literature, lacked such a thorough characterization. An initial complexity analysis for mCP-nets was carried out only recently. In this paper, we further investigate the complexity of mCP-nets. In particular, we prove the Σ P 3 -completeness of checking the existence of max optimal outcomes, which was left as an open problem. We furthermore prove that various tasks known to be feasible in polynomial time are actually P-complete. This shows that these problems are inherently sequential, and hence they cannot benefit from highly parallel computation. The P-completeness results here proven are among the very first of this kind in the computational social choice literature.