A note on enumerative counting

DOI10.1016/0020-0190(91)90103-OzbMath0733.68030OpenAlexW1982547542MaRDI QIDQ809598

Hemaspaandra, Lane A., 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

zbMATH Keywords

relations among complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the hardness of computing the permanent of random matrices, Some connections between bounded query classes and non-uniform complexity., The Power of Self-Reducibility: Selectivity, Information, and Approximation, On the power of enumerative counting, The communication complexity of enumeration, elimination, and selection, Reductions to sets of low information content, Enumerations of the Kolmogorov function, Reconstructing Algebraic Functions from Mixed Data, The enumerability of P collapses P to NC, Tally NP sets and easy census functions., Optimal series-parallel trade-offs for reducing a function to its own graph

Cites Work

• The complexity of computing the permanent
• Bounded queries to SAT and the Boolean hierarchy
• Addendum to: Non-deterministic exponential time has two-prower interactive protocols
• Enumerative counting is hard
• On Approximation Algorithms for # P
• The Complexity of Enumeration and Reliability Problems
• Computational Complexity of Probabilistic Turing Machines
• Structural complexity theory: Recent surprises
• Unnamed Item
• Unnamed Item
• Unnamed Item