An oracle builder's toolkit
From MaRDI portal
Publication:1398366
DOI10.1016/S0890-5401(03)00018-XzbMATH Open1025.68041OpenAlexW1981741030MaRDI QIDQ1398366FDOQ1398366
Authors: Stuart A. Kurtz, Lide Li, S. Fenner, Lance 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
Recommendations
Cites Work
- The complexity of computing the permanent
- Set theory. An introduction to independence proofs
- A model of set-theory in which every set of reals is Lebesgue measurable
- Title not available (Why is that?)
- Quantum Complexity Theory
- Strengths and Weaknesses of Quantum Computing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some applications of the notions of forcing and generic sets
- THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS
- Title not available (Why is that?)
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Almost everywhere high nonuniform complexity
- Title not available (Why is that?)
- One-way functions and the nonisomorphism of NP-complete sets
- Complexity Measures for Public-Key Cryptosystems
- On the degree of Boolean functions as real polynomials
- Classical recursion theory. The theory of functions and sets of natural numbers
- Graph Isomorphism is in SPP
- Complexity limitations on quantum computation
- On degrees of recursive unsolvability
- Title not available (Why is that?)
- Title not available (Why is that?)
- Gap-definable counting classes
- The upper semi-lattice of degrees of recursive unsolvability
- Definability in the Turing degrees
- Definability in the enumeration degrees
- The isomorphism conjecture fails relative to a random oracle
- The Isomorphism Conjecture Holds Relative to an Oracle
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Title not available (Why is that?)
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Title not available (Why is that?)
- Title not available (Why is that?)
- An oracle builder's toolkit
- Two queries
- Forcing and reducibilities
- Title not available (Why is that?)
- Graph isomorphism is low for PP
- Title not available (Why is that?)
- The isomorphism conjecture holds and one-way functions exist relative to an oracle
- Generic separations
- PP-lowness and a simple definition of AWPP
- Title not available (Why is that?)
Cited In (24)
- Complexity classes of equivalence problems revisited
- Partially definable forcing and bounded arithmetic
- Complexity limitations on quantum computation
- Relativized generic classes P and NP
- An oracle builder's toolkit
- The robustness of LWPP and WPP, with an application to graph reconstruction
- A tight relationship between generic oracles and type-2 complexity theory
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- LWPP and WPP are not uniformly gap-definable
- A general method to construct oracles realizing given relationships between complexity classes
- Error-bounded probabilistic computations between MA and AM
- Relativized worlds with an infinite hierarchy
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- A hierarchy based on output multiplicity
- One complexity theorist's view of quantum computing
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- Strong self-reducibility precludes strong immunity
- The isomorphism conjecture holds and one-way functions exist relative to an oracle
- Complexity measures and decision tree complexity: a survey.
- The generic oracle hypothesis is false
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)
- Graph Isomorphism is in SPP
This page was built for publication: An oracle builder's toolkit
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1398366)
