NP-SPEC: an executable specification language for solving all problems in NP

In this paper a logic-based specification language, called NP-SPEC, is pres ented. The language is obtained by extending DATALOG through allowing a lim ited use of some second-order predicates of predefined form. NP-SPEC progra ms specify solutions to problems in a very abstract and concise way, and ar e executable. In the present prototype they are compiled to PROLOG code, wh ich is run to construct outputs. Second-order predicates of suitable form a llow to limit the size of search spaces in order to obtain reasonably effic ient construction of problem solutions. NP-SPEC expressive power is precise ly characterized as to express exactly the problems in the class NP. The sp ecification of several combinatorial problems in NP-SPEC is shown, and the efficiency of the generated programs is evaluated. (C) 2001 Elsevier Scienc e Ltd. All rights reserved.