1. the isolation lemma of Mulmuley, Vazirani, and Vazirani, and

2. the inductive counting technique of Immerman and Szelepscenyi

combine to give a surprising collapse in complexity theory. Namely, in the context of nonuniform logspace, nondeterministic computation can be made unambiguous. An analogous result holds for the class of problems reducible to context-free languages. Of course, nondeterminism has been the focus of a great deal of research, because it has been an extremely useful tool in characterizing the complexity of many important problems. For example, computing transitive closure is one of many natural problems that are complete for nondeterministic logspace (NL). Unambiguity is also of great importance in computer science -- it often forms the basis for improved algorithms. For instance, unambiguous context-free languages can be parsed in time $n^2$, and they have logarithmic-time CREW algorithms. Neither is known for general context-free languages (and neither is known for transitive closure). The audience is invited to see if a more sophisticated approach building on our main theorem would have algorithmic significance. In terms of complexity classes, the main result can be stated as: NL/poly = UL/poly I think that the stronger statement NL = UL is probably true, too.

Joint work with Klaus Reinhardt, to appear in FOCS '97