Simple characterizations of \(P(\# P)\) and complete problems
type: Item
instance of: scholarly article
title: Simple characterizations of \(P(\# P)\) and complete problems
zbMATH Open document ID: 0942.68571
DOI: 10.1016/S0022-0000(05)80082-0
published in: Journal of Computer and System Sciences
publication date: 2000-08-14T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 639122
MaRDI profile type: Publication
cites work: Q3971277
cites work: The polynomial-time hierarchy and sparse oracles
cites work: Q4039803
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Q4198056
cites work: Lower Bounds for Selection in X + Y and Other Multisets
cites work: Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
cites work: The complexity of optimization problems
cites work: On counting and approximation
cites work: A complexity theory for feasible closure properties
cites work: Q4739657
cites work: On the complexity of unique solutions
cites work: The polynomial-time hierarchy
cites work: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: The complexity of combinatorial problems with succinct input representation
cites work: Some observations on the connection between counting and recursion
cites work: Complete sets and the polynomial-time hierarchy
full work available at URL: s0022-0000(05)80082-0
OpenAlex ID: W1982124236
author: Seinosuke Toda
description: scientific article; zbMATH DE number 639122