Solving planning domains with polytree causal graphs is NP-complete
classification
💻 cs.AI
cs.CC
keywords
causaldomainsplanningpolytreegraphsnp-completesolvingalgorithm
read the original abstract
We 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.