A note on enumerative counting
DOI10.1016/0020-0190(91)90103-OzbMATH Open0733.68030OpenAlexW1982547542MaRDI QIDQ809598FDOQ809598
Authors: Jin-Yi Cai, Lane A. Hemaspaandra 
Publication date: 1991
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(91)90103-o
Recommendations
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- The complexity of computing the permanent
- Title not available (Why is that?)
- On Approximation Algorithms for # P
- The Complexity of Enumeration and Reliability Problems
- Computational Complexity of Probabilistic Turing Machines
- Bounded queries to SAT and the Boolean hierarchy
- Title not available (Why is that?)
- Enumerative counting is hard
- Addendum to: Non-deterministic exponential time has two-prower interactive protocols
- Title not available (Why is that?)
- Structural complexity theory: Recent surprises
Cited In (18)
- Optimal series-parallel trade-offs for reducing a function to its own graph
- The enumerability of P collapses P to NC
- Enumerative counting is hard
- Tally NP sets and easy census functions.
- Some connections between bounded query classes and non-uniform complexity.
- Toward a Theory of Enumerations
- Reconstructing Algebraic Functions from Mixed Data
- A new way of counting \(n^ m\)
- Reductions to sets of low information content (extended abstract)
- The communication complexity of enumeration, elimination, and selection
- Counting CTL
- The Power of Self-Reducibility: Selectivity, Information, and Approximation
- On the hardness of computing the permanent of random matrices
- Enumerations of the Kolmogorov function
- On the power of enumerative counting
- On Approximation Algorithms for # P
- An Introduction to Enumeration
- The Enumeration Methods of Redfield
This page was built for publication: A note on enumerative counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q809598)
