Ko, Ker-I Relativized polynomial time hierarchies having exactly k levels. (English) Zbl 0679.68088 SIAM J. Comput. 18, No. 2, 392-408 (1989). Summary: It is proved that for every integer \(k\geq 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. Cited in 1 ReviewCited in 23 Documents MSC: 68Q25 Analysis of algorithms and problem complexity Keywords:relativization; oracle; polynomial time hierarchy × Cite Format Result Cite Review PDF Full Text: DOI