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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)
Bagan, G., Durand, A., Grandjean, E.: On acyclic conjunctive queries and constant delay enumeration. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 208–222. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74915-8_18
Brault-Baron, J.: De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order). Ph.D. thesis, University of Caen Normandy, France (2013). https://tel.archives-ouvertes.fr/tel-01081392
Creignou, N., Hébrard, J.J.: On generating all solutions of generalized satisfiability problems. Informatique Théorique et Applications 31(6), 499–511 (1997)
Creignou, N., Kröll, M., Pichler, R., Skritek, S., Vollmer, H.: On the complexity of hard enumeration problems. CoRR abs/1610.05493 (2016), http://arxiv.org/abs/1610.05493
Creignou, N., Vollmer, H.: Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting. Fundam. Inform. 136(4), 297–316 (2015). http://dx.doi.org/10.3233/FI-2015-1159
Durand, A., Grandjean, E.: First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log. 8(4), 21/1–21/19 (2007). http://doi.acm.org/10.1145/1276920.1276923
Durand, A., Hermann, M., Kolaitis, P.G.: Subtractive reductions and complete problems for counting complexity classes. Theor. Comput. Sci. 340(3), 496–513 (2005)
Durand, A., Schweikardt, N., Segoufin, L.: Enumerating answers to first-order queries over databases of low degree. In: Proceedings of PODS 2014, pp. 121–131. ACM (2014)
Eiter, T., Gottlob, G.: The complexity of logic-based abduction. J. ACM 42(1), 3–42 (1995)
Hemachandra, L.A.: The strong exponential hierarchy collapses. In: Proceedings of STOC 1987, pp. 110–122. ACM (1987)
Hemaspaandra, L.A., Vollmer, H.: The satanic notations: counting classes beyond #P and other definitional adventures. SIGACT News 26(1), 2–13 (1995)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119–123 (1988)
Kimelfeld, B., Kolaitis, P.G.: The complexity of mining maximal frequent subgraphs. ACM Trans. Database Syst. 39(4), 32:1–32:33 (2014). http://doi.acm.org/10.1145/2629550
Lucchesi, C.L., Osborn, S.L.: Candidate keys for relations. J. Comput. Syst. Sci. 17(2), 270–279 (1978)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of STOC 1978, pp. 216–226. ACM Press (1978)
Strozecki, Y.: Enumeration complexity and matroid decomposition. Ph.D. thesis, Universite Paris Diderot - Paris 7, December 2010. http://www.prism.uvsq.fr/~ ystr/these_strozecki
Strozecki, Y.: On enumerating monomials and other combinatorial structures by polynomial interpolation. Theory Comput. Syst. 53(4), 532–568 (2013)
Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865–877 (1991)
Acknowledgments
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.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Creignou, N., Kröll, M., Pichler, R., Skritek, S., Vollmer, H. (2017). On the Complexity of Hard Enumeration Problems. In: Drewes, F., Martín-Vide, C., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2017. Lecture Notes in Computer Science(), vol 10168. Springer, Cham. https://doi.org/10.1007/978-3-319-53733-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-53733-7_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53732-0
Online ISBN: 978-3-319-53733-7
eBook Packages: Computer ScienceComputer Science (R0)