On the power of enumerative counting
type: Item
instance of: scholarly article
title: On the power of enumerative counting
zbMATH Open document ID: 0754.68050
DOI: 10.1016/0020-0190(92)90002-D
author: Sanjeev Saluja
author: K. V. Subrahmanyam
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
review text: We study the functions in \(\#P\), which have polynomial time enumerators. We show that functions in \(\#P\), which have polynomial time enumerators are low for the counting class \(PP\). As a corollary, it follows that functions hard for \(\#P\) under polynomial time reductions do not have enumerators unless the counting hierarchy collapses in \(PP\). We also construct relativisations in which for any polynomial \(p(n)\), there are functions in \(\#P\), which have enumerators with output size \(p(n)+1\), but not enumerators with output size \(p(n)\).
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 94470
zbMATH Keywords: counting classes
zbMATH Keywords: enumerators
MaRDI profile type: Publication
cites work: Q3747725
cites work: Relativized counting classes: Relations among thresholds, parity, and mods
cites work: Enumerative counting is hard
cites work: On the power of parity polynomial time
cites work: A note on enumerative counting
cites work: A low and a high hierarchy within NP
cites work: Relative complexity of checking and evaluating
cites work: The complexity of computing the permanent
cites work: The complexity of combinatorial problems with succinct input representation
full work available at URL: 0020-0190(92)90002-d
OpenAlex ID: W2069237346
Recommended article: On the expressive power of counting
Recommended article: A note on enumerative counting
Recommended article: Q3798240
Recommended article: A complexity theory for hard enumeration problems
Recommended article: Toward a Theory of Enumerations
Recommended article: The complexity of counting problems
Recommended article: On an asymptotic method in enumeration
Recommended article: Q3539937
Recommended article: Q3804682
Recommended article: Про деякi зв’язанi мiж собою перелiковi задачi
description: scientific article; zbMATH DE number 94470