Abstract
We show that the dominance problem for CP-nets is P-hard, and that the dominance problem for the more general ase of cyclic CP-nets is PSPACE omplete.
| Original language | English |
|---|---|
| Journal | Dagstuhl Seminar Proceedings |
| Volume | 4421 |
| State | Published - 2005 |
| Event | Algebraic Methods in Computational Complexity 2004 - Wadern, Germany Duration: Oct 10 2004 → Oct 15 2004 |
Bibliographical note
Publisher Copyright:© 2005 Dagstuhl Seminar Proceedings. All rights reserved.
Funding
The author a knowledges the input from the logi and AI seminar at the University of Kentu ky and pro ofreading by Chris Lusena and Andy Klapp er. Thanks are due to Andy Klapp er for the observation ab out self lo ops and improving ips. This work partially supp orted by NSF grants CCR-0100040 and ITR-0325063. The main result and others app ear, with signi antly di erent pro ofs, in [6℄.
| Funders | Funder number |
|---|---|
| National Science Foundation (NSF) | CCR-0100040, ITR-0325063 |
Keywords
- CP-nets
- PSPACE completeness
- Qualitative preferences
- complexity
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Control and Systems Engineering
Fingerprint
Dive into the research topics of 'Preferences and Domination'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver