An oracle builder's toolkit

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

zbMATH Keywords

forcinggenericityrelativizationcomplexity classesgeneric oracles

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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