welcome: please sign in
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 herein adopt witness as a neutral term for denoting a solution for the problem instance at hand. Depending on the declarative formalism of choice, this can correspond to (part of) a logical model, to a satisfying assignment etc.

We distinguish between two main type of 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:

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. 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.

ASP Competition 2011: BenchmarkProblems (last edited 2010-11-22 12:41:42 by GiovambattistaIanni)