A Downward Collapse within the Polynomial Hierarchy

Simple item page
dc.creatorHemaspaandra, Edith
dc.creatorHemaspaandra, Lane A.
dc.creatorHempel, Harald
dc.date1999-10-01
dc.date.accessioned2026-07-07T03:24:23Z
dc.date.available2026-07-07T03:24:23Z
dc.descriptionDownward 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.
dc.description14 pages
dc.identifierhttps://arxiv.org/abs/cs/9910007
dc.identifierhttp://arxiv.org/abs/cs/9910007
dc.identifierSIAM Journal on Computing, 28, 383-393, 1999
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/33306
dc.subjectComputational Complexity
dc.subjectF.1.3
dc.titleA Downward Collapse within the Polynomial Hierarchy
dc.typetext

Files

Collections

arXiv