Expressive Reasoning about Action in Nondeterministic Polynomial Time
Thomas Drakengren, Marcus Bjäreland · 1999
The rapid development of efficient heuristics for deciding satisfiability for propositional logic motivates thorough investigations of the usability of NP-complete problems in general. In this paper we introduce a logic of action and change which is expressive in the sense that it can represent most propositional benchmark examples in the literature, and some new examples involving parallel composition of actions, and actions that may or may not be executed. We prove that satisfiability of a scenario in this logic is NP-complete, and that it subsumes an NP-complete logic (which in turn includes a nontrivial polynomial-time fragment) previously introduced by Drakengren and Bjareland. 1 Introduction The rapid development of efficient heuristics for deciding satisfiability for propositional logic (GSAT and similar heuristics [ Selman et al., 1992 ] ) motivates thorough investigations of the usability of NP-complete problems in general. In this paper we introduce a logic of...