✦ 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
DOI: 10.1137/0220025

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

On collapsing the polynomial-time hierar

On collapsing the polynomial-time hierarchy

✍ Ronald V. Book 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 210 KB

Graph Nonisomorphism Has Subexponential

Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

✍ Klivans, Adam R.; van Melkebeek, Dieter 📂 Article 📅 2002 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 275 KB

Does the Polynomial Hierarchy Collapse i

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

✍ Harry Buhrman; Lance Fortnow; Michal Koucký; John D. Rogers; Nikolay Vereshchagi 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 373 KB

A Downward Collapse within the Polynomia

A Downward Collapse within the Polynomial Hierarchy

✍ 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