welcome: please sign in

Revision 1 as of 2010-11-22 12:30:03

Clear message
location: BenchmarkProblems

Problem Classification

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

Problem Type

We distinguish between two main type of problems:

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

A query problem consists in finding all the facts 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:

Problem Language.

Each benchmark problems is classified according to the language fragment exploited in the proposed/available encodings. In particular, we consider the following three classes:

A detailed specification of the language fragments ASP-Core and ASP-RFC is reported in the section File and Language Format.