welcome: please sign in
location: OfficialProblemSuite

Official Problem Suite

Problem List - Domains included in BOTH Model & Solve and System Track


Nr

Name

Author(s)

Type

Complexity

Domain

Problem Description

Sample Instances

Checker

ASP-Core-2 encoding

N01

Permutation Pattern Matching

Martin Lackner, Andreas Pfandler

Search

NP

Combinatorial

view

get

get

Permutation Pattern Matching

N02

Valves Location Problem

Andrea Peano

Optimization

Beyond NP

Combinatorial

view

get

get

Valves Location Problem

N04

Connected Maximum-density Still Life

Christian Drescher

Optimization

Beyond NP

AI

view

get

get

Connected Maximum-density Still Life

N05

Graceful Graphs

Christian Drescher

Search

NP

Graph

view

get

get

Graceful Graphs

N06

Bottle Filling Problem

Wolfgang Faber

Search

NP

Combinatorial

view

get

get

Bottle Filling Problem

N07

Nomystery

Giovambattista Ianni, Carlos Linares López*, Hootan Nakhost*

Search

NP

Planning

view

get

get

Nomystery

N08

Sokoban

Giovambattista Ianni, Wolfgang Faber*, Carlos Linares López*

Search

NP

Planning

view

get

get

Sokoban

N09

Ricochet Robots

Julius Höfler, Martin Gebser, Philipp Obermeier, Roland Kaminski, Torsten Schaub

Search

NP

Puzzle

view

get

get

Ricochet Robot

O10

Crossing Minimization

Carmine Dodaro, Graeme Gange*, Peter Stuckey*

Optimization

Beyond NP

Graph

view

get

get

Crossing Minimization

N11*

Reachability

Carmine Dodaro, Giorgio Terracina*

Query

P

Graph

view

get

N.A.

Reachability

N12*

Strategic Companies

Mario Alviano, Marco Maratea*, Francesco Ricca*

Query

Beyond NP

AI

view

get

N.A.

Strategic Companies

O13

Solitaire

Marcello Balduccini, Yuliya Lierler*

Search

NP

Puzzle

view

get

get

Solitaire

O14

Weighted-Sequence Problem

Marcello Balduccini, Yuliya Lierlier, Shaden Smith

Search

NP

Database

view

get

get

Weighted-Sequence Problem

O15

Stable Marriage

Mario Alviano, Carmine Dodaro, Francesco Ricca

Search

P

Graph

view

get

get

Stable Marriage

O16

Incremental Scheduling

Marcello Balduccini, Yuliya Lierler*

Search

NP

Scheduling

view

get

get

Incremental Scheduling

Problem List - Domains included in the System Track ONLY


Nr

Name

Author(s)

Type

Complexity

Domain

Problem Description

Sample Instances

Checker

ASP-Core-2 encoding

N17

Qualitative Spatial Reasoning

Jason Jingshi Li

Search

NP

Formal logic

view

get

get

Qualitative Spatial Reasoning

N18

Chemical Classification

Despoina Magka

Search

P

Natural Sciences

view

get

N.A.

Chemical Classification (60+ MB)

N19

Abstract Dialectical Frameworks Well-founded Model

Stefan Ellmauthaler, Johannes Wallner

Optimization

Beyond NP

Formal logic

view

get

get

Abstract Dialectical Frameworks Well-founded Model

N20

Visit-all

Giovambattista Ianni,Nir Lipovetzky*, Carlos Linares López*

Search

NP

Planning

view

get

get

Visit-all

N21

Complex Optimization of Answer Sets

Martin Gebser, Roland Kaminski, Torsten Schaub

Search

Beyond NP

Synthetic

view

get

get

Complex Optimization of Answer Sets

N22*

Knight Tour with Holes

Francesco Calimeri, Neng-Fa Zhou*

Search

NP

Puzzle

view

get

get

Knight Tour with Holes

O23

Maximal Clique Problem

Guenther Charwat, Martin Kronegger, Johan Wittocx*

Optimization

Beyond NP

Graph

view

get

get

Maximal Clique Problem

O24

Labyrinth

Carmine Dodaro, Giovambattista Ianni, Martin Gebser*

Search

NP

Puzzle

view

get

get

Labyrinth

O25

Minimal Diagnosis

Marcello Balduccini, Martin Gebser*

Search

Beyond NP

Diagnosis

view

get

get

Minimal Diagnosis

O26

Hanoi Tower

Gayathri Namasivayam, Miroslaw Truszczynski, Shaden Smith, Alex Westlund

Search

NP

AI

view

get

get

Hanoi Tower

O27

Graph Colouring

Johannes Wallner, Marcello Balduccini*, Yuliya Lierler*

Search

NP

Graph

view

get

get

Graph Colouring

Legenda

Columns in the table below are to be read as following:

in non-deterministic polynomial time in the size of input. Beyond-NP: any other problem.

Instance set

Alternative Encodings

What do checkers expect as their input? How do I check my solution compliance ?

Changelog

ASP Competition 2013: OfficialProblemSuite (last edited 2013-08-07 16:04:33 by GiovambattistaIanni)