Enumerative counting is hard

DOI10.1016/0890-5401(89)90063-1zbMath0679.68072OpenAlexW2047808405MaRDI QIDQ1822963

Jin-Yi Cai, Hemaspaandra, Lane A.

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90063-1

zbMATH Keywords

enumeratorenumerative countingpolynomial-time machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

On the power of parity polynomial time, On the complexity of ranking, On membership comparable sets, Some connections between bounded query classes and non-uniform complexity., The Power of Self-Reducibility: Selectivity, Information, and Approximation, Frequency computation and bounded queries, Computing functions with parallel queries to NP, Weak cardinality theorems, On the power of enumerative counting, On the power of parity polynomial time, On the reducibility of sets inside NP to sets with low information content, The value of help bits in randomized and average-case complexity, The communication complexity of enumeration, elimination, and selection, The complexity of ODD_n^A, Choosing, agreeing, and eliminating in communication complexity, Enumerations of the Kolmogorov function, 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, A note on enumerative counting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Some observations on the connection between counting and recursion
• Polynomial terse sets
• Random oracles separate PSPACE from the polynomial-time hierarchy
• On counting problems and the polynomial-time hierarchy
• Relative complexity of checking and evaluating
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Terse, superterse, and verbose sets
• Parity, circuits, and the polynomial-time hierarchy
• On Approximation Algorithms for # P
• Complexity Measures for Public-Key Cryptosystems
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Complexity of Enumeration and Reliability Problems
• Computational Complexity of Probabilistic Turing Machines
• The complexity of theorem-proving procedures