Collapsing Recursive Oracles for Relativized Polynomial Hierarchies

摘要

Certain recursive oracles can force the polynomial hierarchy to collapse to any fixed level. All collections of such oracles associated with each collapsing level form an infinite hierarchy, called the collapsing recursive oracle polynomial (CROP) hierarchy. This CROP hierarchy is a significant part of the extended low hierarchy (note that the assumption P = NP makes the both hierarchies coincide). We prove that all levels of the CROP hierarchy are distinct by showing "strong" types of separation. First, we prove that each level of the hierarchy contains a set that is immune to its lower level. Second, we show that any two adjacent levels of the CROP hierarchy can be separated by another level of the CROBPP hierarchy—a bounded-error probabilistic analogue of the CROP hierarchy. Our proofs extend the circuit lower-bound techniques of Yao, Hastad, and Ko.