Enumerative counting is hard
type: Item
instance of: scholarly article
title: Enumerative counting is hard
zbMATH Open document ID: 0679.68072
DOI: 10.1016/0890-5401(89)90063-1
author: Jin-Yi Cai
author: Lane A. Hemaspaandra
published in: Information and Computation
publication date: 1989-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4113996
zbMATH Keywords: enumerative counting
zbMATH Keywords: polynomial-time machine
zbMATH Keywords: enumerator
MaRDI profile type: Publication
full work available at URL: 0890-5401(89)90063-1
OpenAlex ID: W2047808405
cites work: Polynomial terse sets
cites work: Q3747725
cites work: On counting problems and the polynomial-time hierarchy
cites work: Random oracles separate PSPACE from the polynomial-time hierarchy
cites work: Terse, superterse, and verbose sets
cites work: The complexity of theorem-proving procedures
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Q4198056
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Q3862379
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: Q4743737
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: Q4139697
cites work: On Approximation Algorithms for # P
cites work: Relative complexity of checking and evaluating
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Some observations on the connection between counting and recursion
description: scientific article; zbMATH DE number 4113996