Collapsing degrees via strong computation

摘要

Although Berman and others have provided powerful techniques to collapse nondeterministic degrees at and above nondeterministic linear space, and Immerman and Szelepcsényi have provided techniques that collapse even sublinear nondeterministic space classes, it has remained an open question whether any collapses could be proven for sublinear nondeterministic space degrees. This paper provides the first such collapses. For nondeterministic space classes I above NL, we show that all ⩽m1−l-complete sets for I collapse to a single degree (i.e., all ⩽m1−L-complete sets for I areequivalent), and that all ⩽m1−NL-complete sets for I are NL-isomorphic (and thus P-isomorphic). Our techniques also improve previous results for PSPACE.