๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

โœ Scribed by Kadin, Jim


Book ID
118178090
Publisher
Society for Industrial and Applied Mathematics
Year
1991
Tongue
English
Weight
99 KB
Volume
20
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.


๐Ÿ“œ SIMILAR VOLUMES


The PL Hierarchy Collapses
โœ Ogihara, Mitsunori ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Society for Industrial and Applied Mathematics ๐ŸŒ English โš– 220 KB
A Downward Collapse within the Polynomia
โœ Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Society for Industrial and Applied Mathematics ๐ŸŒ English โš– 336 KB
The Analytic Polynomial-Time Hierarchy
โœ Herbert Baier; Klaus W. Wagner ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 863 KB

Motivated by results on interactive proof systems we investigate an 3-V-hierarchy over P using word quantifiers as well as two types of set quantifiers. This hierarchy, which extends the (arithmetic) polynomial-time hierarchy, is called the analytic polynomial-time hierarchy. It is shown that every