---
title: "Expressive Reasoning about Action in Nondeterministic Polynomial Time"
authors:
  - "Thomas Drakengren"
  - "Marcus Bjäreland"
doi: ""
url: "https://ijcai.org/proceedings/1999/25"
pdf: "https://ijcai.org/proceedings/1999/0025.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "166-170"
track: "Automated Reasoning"
keywords:
---

# Expressive Reasoning about Action in Nondeterministic Polynomial Time

Thomas Drakengren, Marcus Bjäreland

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, pages 166-170.

## Abstract

Th e 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.