scientific article; zbMATH DE number 1018738
The polynomial-time hierarchy was defined by \textit{L. J. Stockmeyer} [Theor. Comput. Sci. 3, 1-22 (1977; Zbl 0353.02024)], and \textit{C. Wrathall} [ibid. 3, 23-33 (1977; Zbl 0366.02031)] showed that there are natural complete problems for each level of the hierarchy. The analogous result for the exponential hierarchy will be proved in this paper. The proof we give is based on a modification of the proof of the theorem given by \textit{H. R. Lewis} [J. Comput. Syst. Sci. 21, 317-353 (1980; Zbl 0471.03034)], that the satisfiability problem for the Bernays-Schönfinkel class of first-order sentences is complete for NEXPTIME. An investigation of the exponential hierarchy can be interesting because of two reasons. First, it is well known [Wrathall, loc. cit.] that if higher deterministic and nondeterministic complexity classes do not collapse, then the corresponding lower classes are also distinct. So, some answers to the questions about the exponential hierarchy can be interesting from the point of view of its applications to the polynomial hierarchy. Second, the exponential-time hierarchy has probably some different properties than the polynomial hierarchy. For example, \textit{C. Wilson} proved [``Relativization reducibilities and the exponential hierarchy, Tech. Rep. 140, Univ. Toronto (1980)] that there is an oracle \(A\) such that \(\text{P}^A \neq \text{NP}^A\) but \(\text{EXPTIME}^A =\text{NEXPTIME}^A\). So, it can be possible that EXPTIME=NEXPTIME, but there exists the hierarchy at higher levels.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4339481)