A note on enumerative counting

DOI10.1016/0020-0190(91)90103-OzbMATH Open0733.68030OpenAlexW1982547542MaRDI QIDQ809598FDOQ809598

Lane A. Hemaspaandra, Jin-Yi Cai

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

• Enumerative counting is hard
• On the power of enumerative counting
• On Approximation Algorithms for # P
• scientific article
• scientific article; zbMATH DE number 1057883

zbMATH Keywords

relations among complexity classes

Mathematics Subject Classification ID

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
• Reductions to sets of low information content
• 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\)
• 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)