A tight relationship between generic oracles and type-2 complexity theory
From MaRDI portal
Publication:1369098
DOI10.1006/inco.1997.2646zbMath0881.68051OpenAlexW1983668094MaRDI QIDQ1369098
Russell Impagliazzo, Tomoyuki Yamakami, Stephen A. Cook
Publication date: 7 October 1997
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/41e3dfe7d75f2e5c071cdd63538a6570cf23e12c
Related Items (5)
Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Propositional proofs and reductions between NP search problems ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ The relative complexity of NP search problems ⋮ Degrees of Dowd-type generic oracles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Functional interpretations of feasibly constructive arithmetic
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Robust machines accept easy sets
- Complexity for type-2 relations
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- On some natural complete operators
- Are there interactive protocols for co-NP languages?
- Polynomial and abstract subrecursive classes
- An oracle builder's toolkit
- Feasible computability and resource bounded topology
- Generic separations
- One-way functions and the nonisomorphism of NP-complete sets
- Parity, circuits, and the polynomial-time hierarchy
- Relativized Questions Involving Probabilistic Algorithms
- Structural properties for feasibly computable classes of type two
- Provably total functions of intuitionistic bounded arithmetic
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Algebraic methods for interactive proof systems
- IP = PSPACE
- A new Characterization of Type-2 Feasibility
- THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS
- The complexity of theorem-proving procedures
This page was built for publication: A tight relationship between generic oracles and type-2 complexity theory
