The structural complexity column - The collapsing hierarchies. (English) Zbl 0661.68047

The paper discusses several recent results concerning “collapsing hierarchies”. In virtually all these proofs a certain census counting technique is used. In particular, the following results are reviewed: the collapse of the strong exponential hierarchy, i.e., \(NP^{NE}=P^{NE}\). Furthermore, by the same technique, it can be shown that polynomially many queries to SAT can be replaced by logarithmically many sequential queries. Immerman’s recent breakthrough result showing that NSPACE(s(n)) is closed under complementation, is also put in this context since its proof uses a very similar counting technique. Another surprising result along these lines is the fact that the polynomial time hierarchy collapses to level \(\Delta^ p_ 3\) if the Boolean hierarchy (over NP) is finite.
Reviewer: U.Schöning


68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D15 Complexity of computation (including implicit computational complexity)