A Downward Collapse within the Polynomial Hierarchy

1999/10/01 by Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel · 1 citation
Computer Science · #cs.CC

paper · pdf

published as SIAM Journal on Computing, 28, 383-393, 1999 · 14 pages

arxiv created 1999/10/01 · arxiv updated 2009/11/30

Abstract

Downward collapse (a.k.a. upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the polynomial hierarchy. In particular, we prove that, for k > 2, if \psigkone = \psigktwo then \sigmak = \pik = \ph. We extend this to obtain a more general downward collapse result.

Cited by

• Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators

Related

• What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses
• Translating Equality Downwards
• Using the No-Search Easy-Hard Technique for Downward Collapse
• Downward Collapse from a Weaker Hypothesis
• The Polynomial Hierarchy does not collapse