On the power of unambiguity in log-space

We report progress on the NL vs UL problem.- We show unconditionally that the complexity class ReachFewL ⊆ UL. This improves on the earlier known upper bound ReachFewL ⊆ FewL.- We investigate the complexity of min-uniqueness- a central notion in studying the NL vs UL problem. – We show that min-uniqueness is necessary and sufficient for showing NL = UL. – We revisit the class OptL[log n] and show that ShortestPathLength- com-puting the length of the shortest path in a DAG, is complete for OptL[log n]. – We introduce UOptL[log n], an unambiguous version of OptL[log n], and show that (a) NL = UL if and only if OptL[log n] = UOptL[log n], (b) LogFew ≤ UOptL[log n] ≤ SPL.- We show that the reachability problem over graphs embedded on 3 pages is complete for NL. This contrasts with the reachability problem over graphs embedded on 2 pages which is logspace equivalent to the reachability problem in planar graphs and hence is in UL