Vi undersöker den beräkningsmässiga komplexiteten i att testa dominans och konsekvens i CP-nät. Tidigare har dominansens komplexitet fastställts för begränsade klasser där beroendekurvan för CP-net är acyklisk. Det finns dock intressepreferenser som definierar cykliska beroendediagram; dessa modelleras med allmänna CP-nät. I våra huvudsakliga resultat visar vi här att både dominans och konsekvens för allmänna CP-nät är PSPACE-komplett. Vi betraktar sedan begreppet stark dominans, dominerande ställning likställdhet och dominerande ställning ojämförlig, och flera begrepp om optimalitet, och identifierar komplexiteten i motsvarande beslutsproblem. De minskningar som används i bevisen är från STRIPs planering och förstärker därmed de tidigare etablerade kopplingarna mellan båda områdena.
Goldsmith m.fl. REF undersökte den beräkningsmässiga komplexiteten i att testa dominans och konsekvens i CP-nät, och visade att både dominans och konsekvens för allmänna CP-nät är PSPACE-fullbordade.
The Computational Complexity of Dominance and Consistency in CP-Nets
{'venue': 'Journal Of Artificial Intelligence Research, Volume 33, pages 403-432, 2008', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}