On closure properties of GapP

DOI10.1007/BF01206638zbMath0812.68074OpenAlexW2073989348MaRDI QIDQ1337146

Seinosuke Toda, Thomas Thierauf, Osamu Watanabe

Publication date: 14 May 1995

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01206638

zbMATH Keywords

complexity classesbit cancellationbit insertion

Mathematics Subject Classification ID

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

Related Items (1)

Recursion theoretic characterizations of complexity classes of counting functions

Cites Work

• On the construction of parallel computers from various basis of Boolean functions
• The complexity of combinatorial problems with succinct input representation
• Some observations on the connection between counting and recursion
• On the closure of certain function classes under integer division by polynomially-bounded functions
• Graph isomorphism is low for PP
• The polynomial-time hierarchy
• PP is closed under intersection
• The power of the middle bit of a \(\#\)P function
• PP is closed under truth-table reductions
• A complexity theory for feasible closure properties
• PP is as Hard as the Polynomial-Time Hierarchy
• The Complexity of Enumeration and Reliability Problems
• Computational Complexity of Probabilistic Turing Machines
• Complexity classes defined by counting quantifiers
• Counting classes: Thresholds, parity, mods, and fewness

This page was built for publication: On closure properties of GapP