Problem Classification

Problems, on which systems will compete, are classified according to type, complexity and language. Such categorizations are independent, although strictly related each other.

Problem Type

We herein adopt witness as a neutral term for denoting a solution for the given problem instance. Depending on the declarative formalism of choice, this can correspond to (part of) a logical model, to a satisfying assignment, etc. In ASP terminology, a witness corresponds to an answer set or a subset thereof.

We distinguish between two main type of problems:

• search problems,

• query problems, and

• optimization problems.

The first type of problem requires to find (if it exists) a "witness" solving the problem instance at hand.

A query problem consists in finding all the facts (having a given signature) which hold in all the "witnesses" of the instance for the problem at hand.

An optimization problem is specified as a search problem together with a cost function which assigns an integer cost value to witnesses. We are always searching for witnesses with minimal cost.

Problem Complexity

Problems are also classified according to their computational complexity in:

• Polynomial problems: We classify in this category problems which are solvable in polynomial time in the size of the input data (data complexity). Such problems are usually characterized by the huge size of instance data. Although ASP systems do not aim at competing with more tailored technologies (database etc.) for solving this category of problems, several practical real-world applications fall in this category. Also, it is expected that an ASP solver can deal satisfactorily with basic skills such as answering queries over stratified recursive programs at a reasonable degree of efficiency. It is thus important to assess participants over this category;

• NP problems: We classify in this category NP-complete problems and any problem in NP not known to be polynomially solvable: these problems constitute the "core" category, in which to test the attitude of a solver of efficiently dealing with problems formulated with the "Guess and Check" methodology;

• Beyond NP: We classify in this category any problem not known to be in NP: these are in general very hard problems (often including

optimization problems) and naturally encourage the development of new constructs and new algorithmic techniques: in this category participant systems assess their capabilities as general purpose specification environments.

Problem Language.

Each benchmark problem is classified according to the language fragment used in the proposed/available encodings.

A detailed specification of the language fragments will follow.