×

Relativized polynomial time hierarchies having exactly k levels. (English) Zbl 0679.68088

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.

MSC:

68Q25 Analysis of algorithms and problem complexity
Full Text: DOI