Simple characterizations of \(P(\# P)\) and complete problems

DOI10.1016/S0022-0000(05)80082-0zbMath0942.68571OpenAlexW1982124236MaRDI QIDQ1333395

Seinosuke Toda

Publication date: 14 August 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80082-0

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Related Items

Characterising the complexity of tissue P systems with fission rules, Most probable explanations in Bayesian networks: complexity and tractability, The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The complexity of combinatorial problems with succinct input representation
• Some observations on the connection between counting and recursion
• The complexity of optimization problems
• On counting and approximation
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A complexity theory for feasible closure properties
• The polynomial-time hierarchy and sparse oracles
• On the complexity of unique solutions
• The Complexity of Enumeration and Reliability Problems
• Computational Complexity of Probabilistic Turing Machines
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• Lower Bounds for Selection in X + Y and Other Multisets