Document Open Access Logo

Enumeration Classes Defined by Circuits

Authors Nadia Creignou, Arnaud Durand, Heribert Vollmer

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.38.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Nadia Creignou
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France
Arnaud Durand
  • Université Paris Cité, CNRS, IMJ-PRG, Paris, France
Heribert Vollmer
  • Leibniz Universität Hannover

Cite As Get BibTex

Nadia Creignou, Arnaud Durand, and Heribert Vollmer. Enumeration Classes Defined by Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.38

Abstract

We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Circuit complexity
Keywords
  • Computational complexity
  • enumeration problem
  • Boolean circuit

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Miklós Ajtai. First-order definability on finite structures. Annals of Pure and Applied Logic, 45:211-225, 1989. Google Scholar
  2. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8(3):121-123, 1979. URL: https://doi.org/10.1016/0020-0190(79)90002-4.
  3. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In Computer Science Logic (CSL), pages 208-222, 2007. Google Scholar
  4. David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC¹. J. Comput. Syst. Sci. (JCSS), 41(3):274-306, 1990. Google Scholar
  5. Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News, 7(1):4-33, 2020. URL: https://doi.org/10.1145/3385634.3385636.
  6. Florent Capelli and Yann Strozecki. Incremental delay enumeration: Space and time. Discret. Appl. Math., 268:179-190, 2019. URL: https://doi.org/10.1016/j.dam.2018.06.038.
  7. Peter Clote and Evangelos Kranakis. Boolean Functions and Computation Models. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002. URL: https://doi.org/10.1007/978-3-662-04943-3.
  8. Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity classifications of Boolean constraint satisfaction problems, volume 7 of SIAM monographs on discrete mathematics and applications. SIAM, 2001. Google Scholar
  9. Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer. A complexity theory for hard enumeration problems. Discret. Appl. Math., 268:191-209, 2019. URL: https://doi.org/10.1016/j.dam.2019.02.025.
  10. Arnaud Durand. Fine-grained complexity analysis of queries: From decision to counting and enumeration. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 331-346. ACM, 2020. URL: https://doi.org/10.1145/3375395.3389130.
  11. Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log., 8(4), 2007. URL: https://doi.org/10.1145/1276920.1276923.
  12. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory, 17(1):13-27, 1984. URL: https://doi.org/10.1007/BF01744431.
  13. Ulrich Hertrampf, Clemans Lautemann, Thomas Schwentick, Heribert Vollmer, and Klaus W. Wagner. On the power of polynomial time bit-reductions. In Proceedings 8th Structure in Complexity Theory, pages 200-207. IEEE Computer Society Press, 1993. Google Scholar
  14. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. On generating all maximal independent sets. Inf. Process. Lett., 27(3):119-123, 1988. URL: https://doi.org/10.1016/0020-0190(88)90065-8.
  15. Donald L. Kreher and Douglas Robert Stinson. Combinatorial Algorithms: generation, enumeration, and search. CRC Press, 1999. Google Scholar
  16. Luc Segoufin. A glimpse on constant delay enumeration (invited talk). In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 13-27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.13.
  17. Yann Strozecki. Enumeration complexity. Bull. EATCS, 129, 2019. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/596/605.
  18. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979. URL: https://doi.org/10.1137/0208032.
  19. Heribert Vollmer. A generalized quantifier concept in computational complexity theory. In Jouko A. Väänänen, editor, Generalized Quantifiers and Computation, 9th European Summer School in Logic, Language, and Information, ESSLLI'97 Workshop, Revised Lectures, volume 1754 of Lecture Notes in Computer Science, pages 99-123. Springer, 1999. URL: https://doi.org/10.1007/3-540-46583-9_5.
  20. Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Springer, Heidelberg, 1999. URL: https://doi.org/10.1007/978-3-662-03927-4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact