Automatic Polytime Reductions of NP Problems into a Fragment of STRIPS

Abstract

We present a software tool that is able to automatically translate an NP problem into a STRIPS problem such that the former problem has a solution iff the latter has one, a solution for the latter can be transformed into a solution for the former, and all this can be done efficiently. Moreover, the tool is built such that it only produces problems that belong to a fragment of STRIPS that is solvable in non-deterministic polynomial time, a fact that guarantees that the whole approach is not an overkill. This tool has interesting applications. For example, with the advancement of planning technology, it can be used as an off-the-shelf method to solve general NP problems with the help of planners and to automatically generate benchmark problems of known complexity in a systematic and controlled manner. Another interesting contribution is related to the area of Knowledge Engineering in which one of the goals is to devise automatic methods for using the available planning technology to solve real-life problems.