## Details

Original language | English |
---|---|

Pages (from-to) | 191-209 |

Number of pages | 19 |

Journal | Discrete applied mathematics |

Volume | 268 |

Early online date | 6 Mar 2019 |

Publication status | Published - 15 Sept 2019 |

## Abstract

Complexity theory provides a wealth of complexity classes for analysing the complexity of decision and counting problems. Despite the practical relevance of enumeration problems, the tools provided by complexity theory for this important class of problems are very limited. In particular, complexity classes analogous to the polynomial hierarchy and an appropriate notion of problem reduction are missing. In this work, we lay the foundations for a complexity theory of hard enumeration problems by proposing a hierarchy of complexity classes and by investigating notions of reductions for enumeration problems.

## Keywords

- Complexity classes, Computational complexity, Enumeration, Reductions

## ASJC Scopus subject areas

- Mathematics(all)
**Discrete Mathematics and Combinatorics**- Mathematics(all)
**Applied Mathematics**

## Cite this

- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS

**A complexity theory for hard enumeration problems.**/ Creignou, Nadia; Kröll, Markus; Pichler, Reinhard et al.

In: Discrete applied mathematics, Vol. 268, 15.09.2019, p. 191-209.

Research output: Contribution to journal › Article › Research › peer review

*Discrete applied mathematics*, vol. 268, pp. 191-209. https://doi.org/10.1016/j.dam.2019.02.025

*Discrete applied mathematics*,

*268*, 191-209. https://doi.org/10.1016/j.dam.2019.02.025

}

TY - JOUR

T1 - A complexity theory for hard enumeration problems

AU - Creignou, Nadia

AU - Kröll, Markus

AU - Pichler, Reinhard

AU - Skritek, Sebastian

AU - Vollmer, Heribert

N1 - Funding Information: We would like to thank Phokion Kolaitis for his encouragement on this work during his visit to Marseilles and for suggesting to consider database repairs as complete problems for our complexity classes. This work was supported by the Vienna Science and Technology Fund (WWTF) through project ICT12-015 , the Austrian Science Fund (FWF) : P30930-N35 , P25207-N23 , P25518-N23 , I836-N23 , W1255-N23 and the French Agence Nationale de la Recherche , AGGREG project reference ANR-14-CE25-0017.

PY - 2019/9/15

Y1 - 2019/9/15

N2 - Complexity theory provides a wealth of complexity classes for analysing the complexity of decision and counting problems. Despite the practical relevance of enumeration problems, the tools provided by complexity theory for this important class of problems are very limited. In particular, complexity classes analogous to the polynomial hierarchy and an appropriate notion of problem reduction are missing. In this work, we lay the foundations for a complexity theory of hard enumeration problems by proposing a hierarchy of complexity classes and by investigating notions of reductions for enumeration problems.

AB - Complexity theory provides a wealth of complexity classes for analysing the complexity of decision and counting problems. Despite the practical relevance of enumeration problems, the tools provided by complexity theory for this important class of problems are very limited. In particular, complexity classes analogous to the polynomial hierarchy and an appropriate notion of problem reduction are missing. In this work, we lay the foundations for a complexity theory of hard enumeration problems by proposing a hierarchy of complexity classes and by investigating notions of reductions for enumeration problems.

KW - Complexity classes

KW - Computational complexity

KW - Enumeration

KW - Reductions

UR - http://www.scopus.com/inward/record.url?scp=85062391491&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.02.025

DO - 10.1016/j.dam.2019.02.025

M3 - Article

AN - SCOPUS:85062391491

VL - 268

SP - 191

EP - 209

JO - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

ER -