The strong exponential hierarchy collapses (Q584250): Difference between revisions

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.