Relativized polynomial hierarchies extending two levels. (English) Zbl 0543.03028

Relativized polynomial hierarchies are studied in the paper. The existence of relativized polynomial hierarchies extending exactly two levels is shown. In these hierarchies two polynomially bounded quantifiers yield more than a single one, but three or more polynomially bounded quantifiers do not yield more than two ones. More precisely, the author constructs oracles X, Y such that \(NP(X)\subsetneqq \Delta_ 2^{P,X}=\Sigma_ 2^{P,X}\) and \(\Delta_ 2^{P,Y}\subsetneqq \Sigma_ 2^{P,Y}=\Pi_ 2^{P,Y}.\) The meaning of the symbols is the following. For an arbitrary set Z, P(Z) and NP(Z) denote the class of languages accepted deterministically or nondeterministically (respectively) with the oracle Z. \(\Delta_ 2^{P,Z}\) is defined as P(NP(Z)), \(\Sigma_ 2^{P,Z}\) as NP(NP(Z)), and \(\Pi_ 2^{P,Z}\) as the class of complements of sets in \(\Sigma_ 2^{P,Z}\).
Reviewer: M.Chytil


03D15 Complexity of computation (including implicit computational complexity)
03D55 Hierarchies of computability and definability
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] T. Baker, J. Gill, R. Solovay, Relativizations of theP = NP? Question,SIAM J. Computing, 4, 4, Dec. 1975, pp. 431–442. · Zbl 0323.68033
[2] T. Baker, A. Selman, A Second Step toward the Polynomial Hierarchy,17th Ann. IEEE Symp. on Foundations of Comp. Sci., 1976, pp. 71–75, also published inTheoretical Comp. Sci. 8, 1979, pp. 177–187.
[3] H. Heller, Relativized Polynomial Hierarchies Extending Two Levels, Dissertation, Technische Universität München, 1981. · Zbl 0516.03021
[4] R. Ladner, N. Lynch, A. Selman, Comparison of Polynomial-Time Reducibilities,Proc. 6th Ann Symp. on the Theory of Computing, Seattle, Washington, 1974, pp. 110–121, also published inTheoretical Comp. Sci. 1, 1975, pp. 103–123. · Zbl 0381.68041
[5] T. Long, On Some Polynomial Time Reducibilities, Dissertation, Purdue University, 1978.
[6] K. Mehlhorn, On the Size of Sets of Computable Functions,Proc. 14th IEEE Symp. on Switching and Automata Theory, Iowa City, Iowa, 1973, pp. 190–196.
[7] A. R. Meyer, L. J. Stockmeyer, The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space,Proc. 13th IEEE Symposium on Switching and Automata Theory, 1972, pp. 125–129.
[8] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967. · Zbl 0183.01401
[9] L. J. Stockmeyer, A. R. Meyer, Word Problems Requiring Exponential Time,5th Annual ACM Symposium on the Theory of Computing, Austin, Texas, 1973, pp. 1–9. · Zbl 0359.68050
[10] C. Wrathall, Complete Sets and the Polynomial Hierarchy,Theoretical Computer Science 3, 1977, pp. 23–33. · Zbl 0366.02031 · doi:10.1016/0304-3975(76)90062-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.