---
title: "Reasoning about Action in Polynomial Time"
authors:
  - "Thomas Drakengren"
  - "Marcus Bjäreland"
doi: ""
url: "https://ijcai.org/proceedings/1997/208"
pdf: "https://ijcai.org/proceedings/1997/0208.pdf"
venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence"
year: 1997
pages: "1447-1452"
track: "Temporal Reasoning"
keywords:
---

# Reasoning about Action in Polynomial Time

Thomas Drakengren, Marcus Bjäreland

*Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, pages 1447-1452.

## Abstract

Although many formalisms for reasoning about action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this paper are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for reasoning about action, and NP-completeness results for the unrestricted problems. Many interesting reasoning problems can be modelled, involving nondeterminism, concurrency and memory of actions. The reasoning process is proved to be sound and complete.