The Complexity Of Checking Action Redundancy

In the field of reasoning about actions, it is of practical importance to decide whether an action is redundant, i.e. it is not needed to reach the goal. In this paper, we study the computational complexityof several problems related to the redundancy of actions: checking whether a domain contains a redundant action, what is the minimal number of actions needed to make the goal reachable, checkingwhether the removal of an action does not increase the minimal plan length, and other related problems.