Quantum and classical complexity classes: Separations, collapses, and closure properties
From MaRDI portal
(Redirected from Publication:2486397)
Recommendations
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3984573 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2163013 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- A complexity theory for feasible closure properties
- A note on separating the relativized polynomial time hierarchy by immune sets
- A uniform approach to define complexity classes
- An oracle builder's toolkit
- Approximate formulas for some functions of prime numbers
- Complexity classes and sparse oracles
- Complexity classes defined by counting quantifiers
- Complexity limitations on quantum computation
- Computational Complexity of Probabilistic Turing Machines
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Counting classes: Thresholds, parity, mods, and fewness
- Gap-definable counting classes
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- On the construction of parallel computers from various basis of Boolean functions
- On the power of deterministic reductions to C=P
- On the power of parity polynomial time
- P-Printable Sets
- PP is as Hard as the Polynomial-Time Hierarchy
- PP-lowness and a simple definition of AWPP
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Probabilistic quantifiers and games
- Quantum Complexity Theory
- Quantum Computability
- Relations among MOD-classes
- Relative complexity of checking and evaluating
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativized counting classes: Relations among thresholds, parity, and mods
- Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
- Relativized worlds with an infinite hierarchy
- STRONG SEPARATIONS FOR THE BOOLEAN HIERARCHY OVER RP
- Strengths and Weaknesses of Quantum Computing
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- The Boolean Hierarchy I: Structural Properties
- The complexity of combinatorial problems with succinct input representation
- The complexity theory companion
- Turing machines with few accepting computations and low sets for PP
- \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
Cited in
(7)- scientific article; zbMATH DE number 1583884 (Why is no real title available?)
- 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)
