In this paper we analyze the complexity of the language A, proposed in [Gelfond and Lifschitz, 1993] to formalize properties of actions. We prove that the general language is NP complete, thus intractable, and show some tractable (polynomial) subclasses of it. We also show how states that are unreachable affect the semantics of the language.
The language A has been proposed in 1993 by Gelfond and Lifschitz to formalize properties of actions. A is an high-level language, and its syntax and semantics are similar to those of logic programming languages (with negation). For example, stating that a fact P holds after a sequence of actions A1,...,Am is denoted by P after A1;...;Am.
The main contribution of this paper is the analysis of the computational properties of A. Namely, we prove that deciding the consistency of a set of statements in A is NP complete. We also prove that entailment (deciding what is implied by a set of statements) is coNP complete. These two results are strictly related.
The practical implications of these results are not necessarily negative. While it is strongly believed that NP complete problems cannot, in general, be solved efficiently, they are easier than other problems in higher classes of the polynomial hierarchy. Many heuristics for solving NP problems (e.g. the problem of satisfiability of a propositional formula) have been developed. We explicitly reformulate the problem of consistency in A as the problem of satisfiability of a propositional formula. This is done by translating the set of statements of A into a set of clauses whose Clark's completion is satisfiable if and only if the original set of statements in A is consistent. Since Clark's completion of a set of clauses can be expressed as a propositional formula, this is indeed a translation of consistency in A into propositional satisfiability. Heuristics for SAT can thus be applied to the resulting propositional formula.
We analyze the computational properties of A when the language is restricted. The main result obtained is that an exponential number of initial states is a necessary condition to obtain the NP hardness. The number of actions and the number of effect of actions seemed at a first look to cause intractability. Indeed they do not, since restricting these numbers to be small does not lead to tractability. The two most significant tractable sublanguages of A are the one in which the initial state is fully known, and the one in which cause-effect rules have only one positive precondition and one positive effect.
The last problem analyzed in this paper is the effect of states that are not reachable from the initial state. In the original semantics of A, unreachable states can affect the consistency of a set of statements, while intuitively they should not. We propose an alternative semantics that does not suffer from this drawback.