Enumerative counting is hard

DOI10.1016/0890-5401(89)90063-1MaRDI QIDQ1822963zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Lane A. Hemaspaandra

Publication date 1989

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

enumerative countingenumeratorpolynomial-time machine

Mathematics Subject Classification ID

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

Recommendations

• On the power of enumerative counting
• A note on enumerative counting
• Complexity of generalized satisfiability counting problems

Cites work

• Complexity Measures for Public-Key Cryptosystems
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Computational Complexity of Probabilistic Turing Machines
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3568040 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• On Approximation Algorithms for # P
• On counting problems and the polynomial-time hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• Polynomial terse sets
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Relative complexity of checking and evaluating
• Some observations on the connection between counting and recursion
• Terse, superterse, and verbose sets
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• The complexity of theorem-proving procedures
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

Cited in

(23)

• On sets polynomially enumerable by iteration
• On the power of enumerative counting
• Some connections between bounded query classes and non-uniform complexity.
• On the reducibility of sets inside NP to sets with low information content
• Tally NP sets and easy census functions.
• Optimal series-parallel trade-offs for reducing a function to its own graph
• On membership comparable sets
• The value of help bits in randomized and average-case complexity
• The enumerability of P collapses P to NC
• The Power of Self-Reducibility: Selectivity, Information, and Approximation
• Hard Enumeration Problems in Geometry and Combinatorics
• The complexity of ODD_n^A
• On the power of parity polynomial time
• Mathematical Foundations of Computer Science 2004
• Enumerations of the Kolmogorov function
• Weak cardinality theorems
• On the power of parity polynomial time
• The communication complexity of enumeration, elimination, and selection
• Frequency computation and bounded queries
• Computing functions with parallel queries to NP
• Choosing, agreeing, and eliminating in communication complexity
• A note on enumerative counting
• On the complexity of ranking

This page was built for publication: Enumerative counting is hard

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