Solving planning domains with polytree causal graphs is NP-complete

Simple item page
dc.creatorGiménez, Omer
dc.date2006-10-16
dc.date.accessioned2026-07-07T07:27:52Z
dc.date.available2026-07-07T07:27:52Z
dc.descriptionWe show that solving planning domains on binary variables with polytree causal graph is \NP-complete. This is in contrast to a polynomial-time algorithm of Domshlak and Brafman that solves these planning domains for polytree causal graphs of bounded indegree.
dc.identifierhttps://arxiv.org/abs/cs/0610095
dc.identifierhttp://arxiv.org/abs/cs/0610095
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/117530
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectI.2.8
dc.titleSolving planning domains with polytree causal graphs is NP-complete
dc.typetext

Files

Collections

arXiv