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
In: Discrete applied mathematics, Vol. 268, 15.09.2019, p. 191-209.
Research output: Contribution to journal › Article › Research › peer review
}
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 -