Downward Collapse from a Weaker Hypothesis
<|reference_start|>Downward Collapse from a Weaker Hypothesis: Hemaspaandra et al. proved that, for $m > 0$ and $0 < i < k - 1$: if $\Sigma_i^p \BoldfaceDelta DIFF_m(\Sigma_k^p)$ is closed under complementation, then $DIFF_m(\Sigma_k^p) = coDIFF_m(\Sigma_k^p)$. This sharply asymmetric result fails to apply to the case in which the hypothesis is weakened by allowing the $\Sigma_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(\Sigma_i^p) \BoldfaceDelta DIFF_m(\Sigma_k^p)$ is closed under complementation, then $DIFF_m(\Sigma_k^p) = coDIFF_m(\Sigma_k^p)$.<|reference_end|>
@article{hemaspaandra1998downward,
    title={Downward Collapse from a Weaker Hypothesis},
    author={Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel},
    journal={arXiv preprint arXiv:cs/9808002},
    year={1998},
    number={see UR-CS-TR-98-681},
    archivePrefix={arXiv},
    eprint={cs/9808002},
    primaryClass={cs.CC}
}