Defying Upward and Downward Separation
Lane A. Hemaspaandra, Sudhanshu Kumar Jha · Information and Computation · 1995
"Downward separation" results show that when small classes collapse, larger ones also collapse. For example, Stockmeyer proved that if P=NP, then the polynomial hierarchy collapses to P, and this result itself holds in every relativized world. In contrast, we construct a relativized world in which the exponential-time limited nondeterminism hierarchy does not display such behavior: its tower levels collapse yet its upper levels separate. "Upward separation" results typically show that polynomial-time classes differ on sparse or tally sets if and only if their exponential analogs differ. For example, Hartmanis, Immerman, and Sewelson proved that NP-P contains sparse sets if and only if E ≠ NE, and this result itself holds in every relativized world. In contrast, we construct relativized worlds in which probabilistic classes do not display upward separation, e.g., a world A in which BPPA-PA contains sparse sets even though BPEA = EA. We also construct a relativized world B in which NPB has PB-immune sparse sets yet NEB is not EB-immune. On the other hand, we provide a structural sufficient condition for upward separation.