|
Size: 3304
Comment:
|
Size: 3313
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 3: | Line 3: |
| = List of Selected Benchmark Problems = | = Preliminary List of Selected Benchmark Problems = |
| Line 7: | Line 7: |
| || # || '''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 || |
|| # || '''Problem''' || '''Author(s)''' || '''Model & Solve track''' || '''System track''' || '''Language (sub)class''' || '''Type''' || '''Complexity''' || ''(Preliminary) Problem description'' || Accepted and available on the Competition Platform || || || || ''(yes/no)'' || ''(yes/no)'' || ''(ASP-Core/ASP-RfC/Open)'' || ''(Search/Optimization/Query)'' || ''(P/NP/Beyond NP)'' || |
UNDER CONSTRUCTION
Preliminary List of Selected Benchmark Problems
|| # || Problem || Author(s) || Model & Solve track || System track || Language (sub)class || Type || Complexity || (Preliminary) Problem description || Accepted and available on the Competition Platform || || || || (yes/no) || (yes/no) || (ASP-Core/ASP-RfC/Open) || (Search/Optimization/Query) || (P/NP/Beyond NP) ||
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 |