A DOWNWARD COLLAPSE WITHIN THE POLYNOMIAL HIERARCHY

Authors
HEMASPAANDRA E HEMASPAANDRA LA HEMPEL H
Citation
E. Hemaspaandra et al., A DOWNWARD COLLAPSE WITHIN THE POLYNOMIAL HIERARCHY, SIAM journal on computing (Print), 28(2), 1999, pp. 383-393
Citations number
29
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing (Print) → ACNP
ISSN journal
00975397
Volume
28
Issue
2
Year of publication
1999
Pages
383 - 393
Database
ISI
SICI code
0097-5397(1999)28:2<383:ADCWTP>2.0.ZU;2-J
Abstract
Downward collapse (also known as upward separation) refers to cases wh ere the equality of two larger classes implies the equality of two sma ller classes. We provide an unqualified downward collapse result compl etely within the polynomial hierarchy. In particular, we prove that, f or k >2, if P-Sigma kp[1] = P Sigma(kp[2]) then Sigma(k)(p) = Pi(k)(p) = PH. We extend this to obtain a more general downward collapse resul t.