Discussion and Open Problems

Rytter [Ryt87] (see also [RR92]) showed that any unambiguous context-free language can be recognized in logarithmic time by CREW-PRAM. In contrast, no such CREW algorithm is known for any problem complete for NL, even in the nonuniform setting. The problem is that, although NL is the class of languages reducible to linear context-free languages, and although the class of languages accepted by deterministic AuxPDAs in logarithmic space and polynomial time coincides with the class of languages logspace-reducible to deterministic context-free languages, and LogCFL coincides with AuxPDA( ), it is not known that UAuxPDA( ) or UL is reducible to unambiguous context-free languages. The work of Niedermeier and Rossmanith does an excellent job of explaining the subtleties and difficulties here [NR95]. CREW algorithms are closely associated with a version of unambiguity called strong unambiguity. In terms of Turing-machine based computation, strong unambiguity means that, not only is there at most one path from the start vertex to the accepting configuration, but in fact there is at most one path between any two configurations of the machine.

Strongly unambiguous algorithms have more efficient algorithms than are known for general NL or UL problems. It is shown in [AL96] that problems in Strongly unambiguous logspace have deterministic algorithms using less than space.

The reader is encouraged to note that, in a min-unique graph, the shortest path between any two vertices is unique. This bears a superficial resemblance to the property of strong unambiguity. We see no application of this observation.

It is natural to ask if the randomized aspect of the construction can be eliminated using some sort of derandomization technique to obtain the equality UL = NL.

A corollary of our work is that UL/poly is closed under complement. It remains an open question if UL is closed under complement, although some of the unambiguous logspace classes that can be defined using strong unambiguity are known to be closed under complement [BJLR92].

It is disappointing that the techniques used in this paper do not seem to provide any new information about complexity classes such as NSPACE(n) and NSPACE . It is straightforward to show that NSPACE(s(n)) is contained in USPACE , but this is interesting only for sublinear s(n).

There is a natural class of functions associated with NL, denoted FNL [AJ93]. This can be defined in several equivalent ways, such as

• The class of functions computable by NC circuits with oracle gates for problems in NL.
• The class of functions f such that { the i-th bit of f(x) is b} is in NL.
• The class of functions computable by logspace-bounded machines with oracles for NL.

Another important class of problems related to NL is the class #L, which counts the number of accepting paths of a NL machine. #L characterizes the complexity of computing the determinant [Vin91]. (See also [Tod, Dam, MV97, Val92, AO96].) It was observed in [AJ93] that if NL = UL, then FNL is contained in #L. Thus a corollary of the result in this paper is that FNL/poly #L/poly.

Many questions about #L remain unanswered. Two interesting complexity classes related to #L are PL (probabilistic logspace) and CL (which characterizes the complexity of singular matrices, as well as questions about computing the rank). It is known that some natural hierarchies defined using these complexity classes collapse:

• AC (CL) = CL = NC (CL) = L [AO96, ABO96].
• AC (PL) = PL = NC (PL) = PL [AO96, Ogi96, BF].

In contrast, the corresponding #L hierarchy (equal to the class of problems AC reducible to computing the determinant) AC (#L) = FL is not known to collapse to any fixed level. Does the equality UL/poly = NL/poly provide any help in analyzing this hierarchy in the nonuniform setting?

Acknowledgment: We thank Klaus-Jörn Lange for helpful comments, and for drawing our attention to min-unique graphs, and for arranging for the second author to spend some of his sabbatical time in Tübingen. We also thank V. Vinay and Lance Fortnow for insightful comments.