Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P

DOI10.1016/0304-3975(92)90369-QzbMath0779.68037MaRDI QIDQ1193633

Seinosuke Toda, Osamu Watanabe

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

polynomial-time reducibilityrelative complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (27)

Simple characterizations of \(P(\# P)\) and complete problems ⋮ The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ Complexity of counting the optimal solutions ⋮ Dependence logic with a majority quantifier ⋮ The effect of combination functions on the complexity of relational Bayesian networks ⋮ On the connection between interval size functions and path counting ⋮ On the Complexity of Probabilistic Abstract Argumentation Frameworks ⋮ On measuring inconsistency in definite and indefinite databases with denial constraints ⋮ A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases ⋮ Complexity of Counting the Optimal Solutions ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ The complexity of problems for quantified constraints ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Computational complexity of flat and generic assumption-based argumentation, with and without probabilities ⋮ Open-world probabilistic databases: semantics, algorithms, complexity ⋮ On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane ⋮ On the autoreducibility of functions ⋮ Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions ⋮ On the Complexity of Computing Generators of Closed Sets ⋮ Unnamed Item ⋮ Relating polynomial time to constant depth ⋮ Complexity of fundamental problems in probabilistic abstract argumentation: beyond independence ⋮ On the complexity of inconsistency measurement ⋮ Subtractive reductions and complete problems for counting complexity classes ⋮ SELF-SPECIFYING MACHINES ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• BPP and the polynomial hierarchy
• NP is as easy as detecting unique solutions
• 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
• Some observations on the probabilistic algorithms and NP-hard problems
• On counting problems and the polynomial-time hierarchy
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Probabilistic complexity classes and lowness
• The polynomial-time hierarchy and sparse oracles
• Robustness of probabilistic computational complexity classes under definitional perturbations
• On Approximation Algorithms for # P
• The Complexity of Enumeration and Reliability Problems
• Alternation
• Computational Complexity of Probabilistic Turing Machines
• A decisive characterization of BPP
• On the power of parity polynomial time
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P