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
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
0.7725276947021484
0 references
0.7396426796913147
0 references
0.7332637310028076
0 references
0.7223740816116333
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