UNDER CONSTRUCTION
List of Selected Benchmark Problems
# |
Problem |
Author(s) |
Model & Solve track |
System track |
Language (sub)class |
Type |
Complexity |
|| || || || (yes/no) || (yes/no) || (ASP-Core/ASP-RfC/Open) || (Search/Optimization/Query) || (P/NP/Beyond NP) || (Preliminary) Problem description || Accepted and available on the Competition Platform ||
1 |
Crossing minimization in layered graphs |
Stuckey |
YES |
NO |
Open |
Optimization |
??? |
2 |
Reachability |
Terracina |
YES |
YES |
ASP-Core |
Search |
P |
3 |
Strategic Companies |
Alviano |
YES |
YES |
ASP-Core |
Search |
Beyond NP |
4 |
Company Controls |
Alviano |
YES |
YES |
ASP-RfC??? |
Optimization |
P |
5 |
Company Controls Optimize |
Alviano |
YES |
NO |
Open |
Optimization |
??? |
6 |
Grammar-Based Information Extraction |
Manna |
YES |
YES |
ASP-Core |
Search |
P |
7 |
Generalized Slitherlink |
Faber |
YES |
YES??? |
ASP-RfC??? |
Search |
NP |
8 |
Fastfood Optimality Check |
Faber |
YES |
YES??? |
ASP-RfC??? |
Search |
NP |
9 |
Fastfood Optimization |
Faber |
YES |
NO |
Open |
Optimization |
??? |
10 |
Sokoban Decision |
Faber |
YES |
YES |
ASP-Core |
Search |
NP |
11 |
Sokoban Optimization |
Faber |
YES |
NO |
Open |
Optimization |
??? |
12 |
Knight Tour |
Neng-Fa Zhou |
YES |
YES |
ASP-Core |
Search |
NP |
13 |
Disjunctive Scheduling |
Neng-Fa Zhou |
YES |
YES |
ASP-Core |
Search |
NP |
14 |
Packing Problem |
Neng-Fa Zhou |
YES |
YES |
ASP-Core |
Search |
NP |
16 |
Maximal Clique |
Wittocx |
YES |
NO |
ASP-Core/ASP-RfC |
Optimization |
??? |
17 |
Labyrinth |
Gebser |
YES |
YES |
ASP-Core |
Search |
NP |
18 |
Minimal Diagnosis |
Gebser |
YES |
YES |
ASP-Core |
|
Beyond NP |
19 |
Multi Context System Querying |
Schueller |
YES |
YES |
ASP-Core |
Search |
NP |
20 |
Numberlink |
Neng-Fa Zhou, Tamura |
YES |
??? |
ASP-Core |
|
??? |
21a |
Reverse Folding |
Formisano, Dovier, Pontelli |
YES |
YES |
ASP-Core |
|
|
21b |
Gas Diffusion |
Formisano, Dovier, Pontelli |
YES |
YES??? |
Open |
|
|
21c |
Tangram |
Formisano, Dovier, Pontelli |
YES |
YES??? |
Open |
|
|
22 |
Hanoi Tower |
Truszczynski |
YES |
YES |
ASP-Core |
Search |
NP |
23 |
Magic Square Sets |
You |
YES |
YES??? |
ASP-RfC |
Search |
NP??? |
25 |
Graph Colouring |
Lierler, Balduccini |
YES |
YES |
ASP-Core |
Search |
NP |
26 |
Solitaire |
Lierler, Balduccini |
YES |
YES??? |
ASP-Core |
Search |
NP |
27 |
Partner Units |
Friedrich |
YES |
YES |
ASP-RFC??? |
Search |
NP |
27b |
Partner Units - Polynomial |
Friedrich |
|
YES |
ASP-Core |
Search |
P |
28 |
Weight-Assignment Tree |
Lierler |
YES |
NO |
ASP-Core |
Search |
NP |
30 |
Hydraulic Leaking |
Calimeri |
NO |
YES |
ASP-Core |
Search |
P |
31 |
Hydraulic Planning |
Calimeri |
NO |
YES |
ASP-Core |
Search |
P |
32 |
Stable Marriage Problem |
Ricca |
|
|
ASP-Core |
|
P |