Downward Collapse from a Weaker Hypothesis

1998/08/24 by Edith Hemaspaandra, Hemaspaandra, Edith, Lane A. Hemaspaandra +4 · 1 citation
Computer Science · Mathematics · #Advanced Topology and Set Theory #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #cs.CC

paper · pdf · doi:10.48550/arxiv.cs/9808002

arxiv created 1998/08/24 · arxiv updated 2009/11/30

Abstract

Hemaspaandra et al. proved that, for m > 0 and 0 < i < k - 1: if Σ_i^p \BoldfaceDelta DIFF_m(Σ_k^p) is closed under complementation, then DIFF_m(Σ_k^p) = coDIFF_m(Σ_k^p). This sharply asymmetric result fails to apply to the case in which the hypothesis is weakened by allowing the Σ_i^p to be replaced by any class in its difference hierarchy. We so extend the result by proving that, for s,m > 0 and 0 < i < k - 1: if DIFF_s(Σ_i^p) \BoldfaceDelta DIFF_m(Σ_k^p) is closed under complementation, then DIFF_m(Σ_k^p) = coDIFF_m(Σ_k^p).

Cited by

• What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses

Related

• A Downward Collapse within the Polynomial Hierarchy
• Using the No-Search Easy-Hard Technique for Downward Collapse
• What's Up with Downward Collapse: Using the Easy-Hard Technique to Link Boolean and Polynomial Hierarchy Collapses
• Strongly almost disjoint families, II
• Derived Models in PFA