Details
| Original language | English |
|---|---|
| Title of host publication | Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings |
| Publisher | Springer Verlag |
| Pages | 183-195 |
| Number of pages | 13 |
| ISBN (print) | 9783319537320 |
| Publication status | Published - 16 Feb 2017 |
| Event | 11th International Conference on Language and Automata Theory and Applications, LATA 2017 - Umea, Sweden Duration: 6 Mar 2017 → 9 Mar 2017 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 10168 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Abstract
Complexity theory provides a wealth of complexity classes for analyzing 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.
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. Springer Verlag, 2017. p. 183-195 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10168 LNCS).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - On the complexity of hard enumeration problems
AU - Creignou, Nadia
AU - Kröll, Markus
AU - Pichler, Reinhard
AU - Skritek, Sebastian
AU - Vollmer, Heribert
N1 - Funding Information: This work was supported by the Vienna Science and Technology Fund (WWTF) through project ICT12-015, the Austrian Science Fund (FWF): P25207-N23, P25518-N23, I836-N23, W1255-N23 and the French Agence Nationale de la Recherche, AGGREG project reference ANR-14-CE25-0017-01. Publisher Copyright: © Springer International Publishing AG 2017. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2017/2/16
Y1 - 2017/2/16
N2 - Complexity theory provides a wealth of complexity classes for analyzing 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 analyzing 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.
UR - http://www.scopus.com/inward/record.url?scp=85013371930&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-53733-7_13
DO - 10.1007/978-3-319-53733-7_13
M3 - Conference contribution
AN - SCOPUS:85013371930
SN - 9783319537320
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 183
EP - 195
BT - Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings
PB - Springer Verlag
T2 - 11th International Conference on Language and Automata Theory and Applications, LATA 2017
Y2 - 6 March 2017 through 9 March 2017
ER -