The strong exponential hierarchy collapses (Q584250)
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 4134022
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The strong exponential hierarchy collapses |
scientific article; zbMATH DE number 4134022 |
Statements
The strong exponential hierarchy collapses (English)
0 references
1989
0 references
It is shown that the so-called strong exponential hierarchy collapses. The strong exponential hierarchy is formally obtained by considering the sequence of complexity classes: NE, P(NE), NP(NE), NP(NP(NE)), etc. Here, NP resp. NE mean nondeterministic polynomial (resp. exponential) time. The ``collapse'' happens at the \(\Delta_ 2\) level, i.e. \(P(NE)=NP(NE)=... \). The result is proved by using census counting techniques and by making extensive use of nondeterminism.
0 references
strong exponential hierarchy
0 references
complexity classes
0 references
census counting techniques
0 references
nondeterminism
0 references
0 references
0.7795678973197937
0 references
