|
Size: 399
Comment:
|
Size: 3161
Comment: table first draft
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = UNDER CONSTRUCTION = | = UNDER CONSTRUCTION = |
| Line 8: | Line 8: |
| || || || || ''(yes/no)'' || ''(yes/no)'' || ''(ASP-Core/ASP-RFC/None)'' || ''(Search/Optimization/Query)'' || ''(P/NP/Beyond NP)'' || || || || || || || || || |
|| || || || ''(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 || || || ASP-Core || || P || || 31 || Hydraulic Planning || Calimeri || || || ASP-Core || || P || || 32 || Stable Marriage Problem || Ricca || || || ASP-Core || || P || |
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) |
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 |
|
|
ASP-Core |
|
P |
31 |
Hydraulic Planning |
Calimeri |
|
|
ASP-Core |
|
P |
32 |
Stable Marriage Problem |
Ricca |
|
|
ASP-Core |
|
P |