|
Size: 2843
Comment: Problem Classification added
|
← Revision 4 as of 2012-05-10 16:57:06 ⇥
Size: 2474
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| == 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. |
== Benchmark 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. |
| Line 5: | Line 7: |
| 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. In ASP terminology, a witness corresponds to an ''answer set'' or a subset thereof. |
|
| Line 9: | Line 8: |
| We distinguish between two main type of problems: | 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. |
| Line 11: | Line 12: |
| * ''search problems'', * ''query problems'', and * ''optimization problems''. |
We distinguish between the following types of problems: |
| Line 15: | Line 14: |
| The first type of problem requires to find (if it exists) a "witness" solving the problem instance at hand. | * ''Search problems'', * ''Optimization problems'', and * ''Query problems'' |
| Line 17: | Line 18: |
| 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. | The first type of problem requires to find (if it exists) a "witness" solving the problem instance at hand (e.g. a coloring for a given instance graph). |
| Line 20: | Line 22: |
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. Query problems include decision problems in which an answer can be a boolean value (e.g. deciding satisfiability of a given propositional formula). |
|
| Line 25: | Line 29: |
| * ''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; | * ''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. |
| Line 27: | Line 31: |
| * ''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; | * ''NP problems:'' We classify in this category NP-complete problems and any problem in NP not known to be polynomially solvable. More precisely, we classify as ''NP'' all search problems in which witnesses correspond to polynomially checkable certificates of some NP-complete problem. |
| Line 29: | Line 33: |
| * ''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. |
* ''Beyond NP:'' We classify in this category any other problem not falling in the above. This class often includes, but it is not restricted to nontrivial optimization problems. |
| Line 33: | Line 36: |
| Each benchmark problem is classified according to the language fragment used in the proposed/available encodings. | |
| Line 35: | Line 37: |
A detailed specification of the language fragments will follow. |
For problems accepted in the [[SystemCompetition|System Track]] benchmark problems are classified according to the language fragment used in the proposed/available encodings. A detailed specification of the language fragments is forthcoming. |
Benchmark 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 the following types of problems:
Search problems,
Optimization problems, and
Query problems
The first type of problem requires to find (if it exists) a "witness" solving the problem instance at hand (e.g. a coloring for a given instance graph).
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.
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. Query problems include decision problems in which an answer can be a boolean value (e.g. deciding satisfiability of a given propositional formula).
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.
NP problems: We classify in this category NP-complete problems and any problem in NP not known to be polynomially solvable. More precisely, we classify as NP all search problems in which witnesses correspond to polynomially checkable certificates of some NP-complete problem.
Beyond NP: We classify in this category any other problem not falling in the above. This class often includes, but it is not restricted to nontrivial optimization problems.
Problem Language.
For problems accepted in the System Track benchmark problems are classified according to the language fragment used in the proposed/available encodings. A detailed specification of the language fragments is forthcoming.