A tight relationship between generic oracles and type-2 complexity theory
type: Item
instance of: scholarly article
title: A tight relationship between generic oracles and type-2 complexity theory
zbMATH Open document ID: 0881.68051
author: Russell Impagliazzo
author: Tomoyuki Yamakami
author: Stephen Cook
published in: Information and Computation
publication date: 1997-10-07T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1071912
zbMATH Keywords: generic oracle
MaRDI profile type: Publication
OpenAlex ID: W1983668094
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Q4234077
cites work: THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS
cites work: Q4062633
cites work: The complexity of theorem-proving procedures
cites work: Functional interpretations of feasibly constructive arithmetic
cites work: An oracle builder's toolkit
cites work: Are there interactive protocols for co-NP languages?
cites work: Generic separations
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Provably total functions of intuitionistic bounded arithmetic
cites work: One-way functions and the nonisomorphism of NP-complete sets
cites work: Robust machines accept easy sets
cites work: Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
cites work: A new Characterization of Type-2 Feasibility
cites work: On some natural complete operators
cites work: Algebraic methods for interactive proof systems
cites work: Polynomial and abstract subrecursive classes
cites work: Q3720579
cites work: Relativized Questions Involving Probabilistic Algorithms
cites work: IP = PSPACE
cites work: Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
cites work: Complexity for type-2 relations
cites work: Feasible computability and resource bounded topology
cites work: Structural properties for feasibly computable classes of type two
DOI: 10.1006/INCO.1997.2646
Recommended article: A general method to construct oracles realizing given relationships between complexity classes
Recommended article: Complexity of the \(r\)-query tautologies in the presence of a generic oracle
Recommended article: COMPUTABLE DOWD-TYPE GENERIC ORACLES
Recommended article: Generalized computations with oracles
Recommended article: Q3809784
Recommended article: Generic oracles, uniform machines, and codes
Recommended article: Speed-up theorems in type-2 computations using oracle Turing machines
Recommended article: Generalized computations with binary oracles
Recommended article: Degrees of Dowd-type generic oracles
Recommended article: Oracles and query lower bounds in generalised probabilistic theories
description: scientific article; zbMATH DE number 1071912