More on BPP and the polynomial-time hierarchy
type: Item
instance of: scholarly article
title: More on BPP and the polynomial-time hierarchy
zbMATH Open document ID: 0875.68425
DOI: 10.1016/0020-0190(96)00016-6
author: Ran Canetti
published in: Information Processing Letters
publication date: 1997-02-27T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 984450
zbMATH Keywords: Theory of computation
zbMATH Keywords: Computational complexity
zbMATH Keywords: Randomness
zbMATH Keywords: Interactive proofs
MaRDI profile type: Publication
full work available at URL: 0020-0190(96)00016-6
OpenAlex ID: W2079192595
cites work: Q4004078
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: BPP and the polynomial hierarchy
cites work: Symmetric alternation captures BPP
cites work: The polynomial-time hierarchy
cites work: Complete sets and the polynomial-time hierarchy
Wikidata QID: Q127179055
Recommended article: Relating the bounded arithmetic and polynomial time hierarchies
Recommended article: On collapsing the polynomial-time hierarchy
Recommended article: PP is as Hard as the Polynomial-Time Hierarchy
Recommended article: A time-space hierarchy between polynomial time and polynomial space
Recommended article: A second step toward the strong polynomial-time hierarchy
Recommended article: Proper hierarchies in polylogarithmic time and absence of complete problems
Recommended article: Q3337458
Recommended article: Parameterized complexity in the polynomial hierarchy. Extending parameterized complexity theory to higher levels of the hierarchy
Recommended article: The polynomial and linear time hierarchies in V0
Recommended article: On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
description: scientific article; zbMATH DE number 984450