On closure properties of GapP

DOI10.1007/BF01206638MaRDI QIDQ1337146zbMATH OpenOpenAlexFDO

Authors Thomas Thierauf, Osamu Watanabe, Seinosuke Toda

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)

Recommendations

• A complexity theory for feasible closure properties
• Gap-definable counting classes
• On closure properties of \(\#\text{P}\) in the context of \(\text{PF} \circ \#\text{P}\)
• scientific article; zbMATH DE number 58301
• scientific article; zbMATH DE number 512854

Cites work

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

Cited in

(1)

• Recursion theoretic characterizations of complexity classes of counting functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337146)