zbMATH — the first resource for mathematics

On relativized exponential and probabilistic complexity classes. (English) Zbl 0628.68047
For an oracle X denote by P(X) (resp. R(X)) the set of (resp. randomly) polynomial-time computable languages relative to X. Besides, hierarchies \(\Sigma_ i^{P,X}\), \(\Pi_ i^{P,X}\), \(\Delta_ i^{P,X}\) (resp. \(\Sigma_ i^{EL,X}\), \(\Pi_ i^{EL,X}\), \(\Delta_ i^{EL,X})\) are considered as usually involving nondeterministic polynomial-time jump (resp. exponential linear time jump). An oracle X is produced for which \(NP(X)=R(X)\) and \(\Delta_ 2^{EL,X}\subseteq \Sigma_ 2^{P,X}\). Apart from that the produced oracle X satisfies the properties \(\Delta_ 2^{P,X}\subsetneqq \Sigma_ 2^{P,X}=PSPACE(X)=EP(X)=NEP(X)=\Delta_ 2^{EP,X}\subsetneqq \Sigma_ 2^{EP,X}\), where EP denotes exponential polynomial time. At last, for this oracle X, and equality \(\Sigma_ 2^{R,X}=\Delta_ 2^{EP,X}\) is valid, what entails several known results on oracle complexity classes.
Reviewer: D.Yu.Grigoryev

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