An oracle builder's toolkit

DOI10.1016/S0890-5401(03)00018-XzbMATH Open1025.68041OpenAlexW1981741030MaRDI QIDQ1398366FDOQ1398366

Stuart A. Kurtz, S. Fenner, Lance Fortnow, Lide Li

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

complexity classesforcinggenericityrelativizationgeneric oracles

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Quantum Complexity Theory
• Strengths and Weaknesses of Quantum Computing
• Some applications of the notions of forcing and generic sets
• THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Almost everywhere high nonuniform complexity
• 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
• 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
• Complexity of Presburger arithmetic with fixed quantifier dimension
• An oracle builder's toolkit
• Two queries
• Forcing and reducibilities
• Graph isomorphism is low for PP
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• Generic separations
• PP-lowness and a simple definition of AWPP

Cited In (23)

• Complexity classes of equivalence problems revisited
• Partially definable forcing and bounded arithmetic
• Complexity limitations on quantum computation
• An oracle builder's toolkit
• The robustness of LWPP and WPP, with an application to graph reconstruction
• Title not available (Why is that?)
• 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 \(\mathrm{QMA(2)}\)
• Graph Isomorphism is in SPP

   Recommendations

• RELATIVIZED GENERIC CLASSES P AND NP 👍 👎
• Generic separations 👍 👎
• COMPUTABLE DOWD-TYPE GENERIC ORACLES 👍 👎
• A general method to construct oracles realizing given relationships between complexity classes 👍 👎
• The generic oracle hypothesis is false 👍 👎

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)