No label defined (Q4339481)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1018738
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1018738

      Statements

      0 references
      15 September 1997
      0 references
      oracle
      0 references
      alternating Turing machine
      0 references
      complete sets
      0 references
      natural complete problems
      0 references
      exponential hierarchy
      0 references
      complexity classes
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references