Relativized Polynomial Time Hierarchies Having Exactly K Levels
Ker‐I Ko · SIAM Journal on Computing · 1989
It is proved that for every integer $k \geqq 0$, there is an oracle $A_k $ relative to which the polynomial time hierarchy collapses so that it has exactly k levels. Furthermore, sets $B_k $ and $C_k $ may be constructed so that, relative to $B_k $, the polynomial time hierarchy has exactly k levels and the class PSPACE coincides with the polynomial time hierarchy, and, relative to $C_k $, the polynomial time hierarchy has exactly k levels and the class PSPACE is different from the polynomial time hierarchy.