|
Size: 3161
Comment: table first draft
|
Size: 3207
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 8: | Line 8: |
| || || || || ''(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 || ? || |
|| || || || ''(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 || ??? || |
| Line 12: | Line 12: |
| || 4 || Company Controls || Alviano || YES || YES || ASP-RFC? || Optimization || P || || 5 || Company Controls Optimize || Alviano || YES || NO || Open || Optimization || ? || |
|| 4 || Company Controls || Alviano || YES || YES || ASP-RfC??? || Optimization || P || || 5 || Company Controls Optimize || Alviano || YES || NO || Open || Optimization || ??? || |
| Line 15: | Line 15: |
| || 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 || ? || |
|| 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 || ??? || |
| Line 19: | Line 19: |
| || 11 || Sokoban Optimization || Faber || YES || NO || Open || Optimization || ? || | || 11 || Sokoban Optimization || Faber || YES || NO || Open || Optimization || ??? || |
| Line 23: | Line 23: |
| || 16 || Maximal Clique || Wittocx || YES || NO || ASP-Core/ASP-RfC || Optimization || ? || | || 16 || Maximal Clique || Wittocx || YES || NO || ASP-Core/ASP-RfC || Optimization || ??? || |
| Line 27: | Line 27: |
| || 20 || Numberlink || Neng-Fa Zhou, Tamura || YES || ? || ASP-Core || || ? || | || 20 || Numberlink || Neng-Fa Zhou, Tamura || YES || ??? || ASP-Core || || ??? || |
| Line 32: | Line 32: |
| || 23 || Magic Square Sets || You || YES || YES??? || ASP-RfC || Search || NP? || | || 23 || Magic Square Sets || You || YES || YES??? || ASP-RfC || Search || NP??? || |
| Line 35: | Line 35: |
| || 27 || Partner Units || Friedrich || YES || YES || ASP-RFC? || Search || NP || | || 27 || Partner Units || Friedrich || YES || YES || ASP-RFC??? || Search || NP || |
| Line 38: | Line 38: |
| || 30 || Hydraulic Leaking || Calimeri || || || ASP-Core || || P || || 31 || Hydraulic Planning || Calimeri || || || ASP-Core || || P || |
|| 30 || Hydraulic Leaking || Calimeri || NO || YES || ASP-Core || Search || P || || 31 || Hydraulic Planning || Calimeri || NO || YES || ASP-Core || Search || 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 |
NO |
YES |
ASP-Core |
Search |
P |
31 |
Hydraulic Planning |
Calimeri |
NO |
YES |
ASP-Core |
Search |
P |
32 |
Stable Marriage Problem |
Ricca |
|
|
ASP-Core |
|
P |