Quantum and classical complexity classes: Separations, collapses, and closure properties
From MaRDI portal
Publication:2486397
DOI10.1016/J.IC.2004.10.009zbMATH Open1161.68481OpenAlexW2073731787MaRDI QIDQ2486397FDOQ2486397
Authors: Holger Spakowski, Mayur Thakur, Rahul Tripathi 
Publication date: 5 August 2005
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1802/518
Recommendations
computational complexityquantum complexity classesgap-definable counting classesreduction closure propertiesrelativization theory
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Computability
- A uniform approach to define complexity classes
- Complexity classes defined by counting quantifiers
- Quantum Complexity Theory
- Strengths and Weaknesses of Quantum Computing
- Title not available (Why is that?)
- Complexity classes and sparse oracles
- Approximate formulas for some functions of prime numbers
- Title not available (Why is that?)
- Computational Complexity of Probabilistic Turing Machines
- The complexity of combinatorial problems with succinct input representation
- Relativized worlds with an infinite hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- The Boolean Hierarchy I: Structural Properties
- Relative complexity of checking and evaluating
- \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
- Complexity limitations on quantum computation
- Counting classes: Thresholds, parity, mods, and fewness
- On the construction of parallel computers from various basis of Boolean functions
- Gap-definable counting classes
- A complexity theory for feasible closure properties
- The complexity theory companion
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- P-Printable Sets
- Probabilistic quantifiers and games
- Relativized counting classes: Relations among thresholds, parity, and mods
- On the power of parity polynomial time
- Relations among MOD-classes
- On the power of deterministic reductions to C=P
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Turing machines with few accepting computations and low sets for PP
- An oracle builder's toolkit
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- A note on separating the relativized polynomial time hierarchy by immune sets
- Title not available (Why is that?)
- STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
- PP-lowness and a simple definition of AWPP
- Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
Cited In (7)
- Title not available (Why is that?)
- The robustness of LWPP and WPP, with an application to graph reconstruction
- The robustness of LWPP and WPP, with an application to graph reconstruction
- The space ``just above BQP
- Complexity classification of two-qubit commuting Hamiltonians
- LWPP and WPP are not uniformly gap-definable
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
This page was built for publication: Quantum and classical complexity classes: Separations, collapses, and closure properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2486397)
