An oracle builder's toolkit
From MaRDI portal
Publication:1398366
DOI10.1016/S0890-5401(03)00018-XzbMath1025.68041OpenAlexW1981741030MaRDI QIDQ1398366
Stuart A. Kurtz, Lide Li, Stephen A. Fenner, Lance J. Fortnow
Publication date: 29 July 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00018-x
Related Items
A general method to construct oracles realizing given relationships between complexity classes, The isomorphism conjecture holds and one-way functions exist relative to an oracle, A tight relationship between generic oracles and type-2 complexity theory, Typical forcings, NP search problems and an extension of a theorem of Riis, NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN, An oracle builder's toolkit, Unnamed Item, Complexity limitations on quantum computation, Strong self-reducibility precludes strong immunity, Partially definable forcing and bounded arithmetic, Quantum and classical complexity classes: Separations, collapses, and closure properties, LWPP and WPP are not uniformly gap-definable, Graph Isomorphism is in SPP, Complexity classes of equivalence problems revisited, The robustness of LWPP and WPP, with an application to graph reconstruction, Error-bounded probabilistic computations between MA and AM, A hierarchy based on output multiplicity, AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly, Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\), Complexity measures and decision tree complexity: a survey., Relativized worlds with an infinite hierarchy, One complexity theorist's view of quantum computing
Cites Work
- The complexity of computing the permanent
- On degrees of recursive unsolvability
- Definability in the Turing degrees
- Set theory. An introduction to independence proofs
- Classical recursion theory. The theory of functions and sets of natural numbers
- Almost everywhere high nonuniform complexity
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- Graph isomorphism is low for PP
- Gap-definable counting classes
- On the degree of Boolean functions as real polynomials
- Complexity of Presburger arithmetic with fixed quantifier dimension
- The isomorphism conjecture holds and one-way functions exist relative to an oracle
- Definability in the enumeration degrees
- An oracle builder's toolkit
- PP-lowness and a simple definition of AWPP
- Generic separations
- Two queries
- Complexity limitations on quantum computation
- Graph Isomorphism is in SPP
- A model of set-theory in which every set of reals is Lebesgue measurable
- One-way functions and the nonisomorphism of NP-complete sets
- The upper semi-lattice of degrees of recursive unsolvability
- Forcing and reducibilities
- Complexity Measures for Public-Key Cryptosystems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- The isomorphism conjecture fails relative to a random oracle
- Quantum Complexity Theory
- Strengths and Weaknesses of Quantum Computing
- The Isomorphism Conjecture Holds Relative to an Oracle
- Some applications of the notions of forcing and generic sets
- THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item