Relativized worlds with an infinite hierarchy
type: Item
instance of: scholarly article
title: Relativized worlds with an infinite hierarchy
zbMATH Open document ID: 1002.68060
DOI: 10.1016/S0020-0190(99)00034-4
published in: Information Processing Letters
publication date: 2002-07-25T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1771657
zbMATH Keywords: book trick
zbMATH Keywords: counting class SPP
zbMATH Keywords: polynomial-time hierarchy
Wikidata QID: Q61688303
author: Lance Fortnow
MaRDI profile type: Publication
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: On collapsing the polynomial-time hierarchy
cites work: The complexity of generating and checking proofs of membership
cites work: The random oracle hypothesis is false
cites work: Gap-definable counting classes
cites work: An oracle builder's toolkit
cites work: Q4289278
cites work: Q4359457
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Threshold Computation and Cryptographic Security
cites work: Relative to a random oracle, NP is not small
cites work: The isomorphism conjecture fails relative to a random oracle
cites work: Algebraic methods for interactive proof systems
cites work: Q4359463
cites work: Hardness vs randomness
cites work: UP and the low and high hierarchies: A relativized separation
cites work: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
cites work: Structural analysis of the complexity of inverse functions
description: scientific article; zbMATH DE number 1771657