Enumeration classes defined by circuits

DOI10.1145/3746454MaRDI QIDQ6872354zbMATH OpenFDO

Authors Nadia Creignou, Arnaud Durand, Heribert Vollmer

Publication date 20 January 2026

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3746454

zbMATH Keywords

Boolean circuitcomputational complexityenumeration problem

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A complexity theory for hard enumeration problems
• A glimpse on constant delay enumeration (invited talk)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Complexity classifications of Boolean constraint satisfaction problems
• Enumeration classes defined by circuits
• Enumeration complexity
• First-order definability on finite structures
• First-order queries on structures of bounded degree are computable with constant delay
• scientific article; zbMATH DE number 1265079 (Why is no real title available?)
• scientific article; zbMATH DE number 953683 (Why is no real title available?)
• scientific article; zbMATH DE number 1453080 (Why is no real title available?)
• Incremental delay enumeration: space and time
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• On generating all maximal independent sets
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The Complexity of Enumeration and Reliability Problems

This page was built for publication: Enumeration classes defined by circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6872354)