On the power of unambiguity in log-space

Aduri Pavan, Raghunath Tewari, N. V. VinodchandranComput. Complex 2012 · OpenReview

TL;DR

This paper makes significant progress on the long-standing NL vs. UL problem, which asks if nondeterministic log-space computations can be made unambiguous. The authors show that min-uniqueness is both necessary and sufficient for NL=UL, and introduce new complexity classes and results that shed light on this fundamental question.

What Problem Does This Paper Address?

The central question this paper tackles is whether nondeterministic log-space computations (NL) can be simulated by unambiguous log-space computations (UL). This is a fundamental problem in computational complexity theory, as it relates to the power of nondeterminism. While it's known that nondeterministic computations can be made unambiguous in a non-uniform setting (NL/poly = UL/poly), the uniform setting remains an open question. Previous work has shown evidence suggesting NL=UL, particularly through results on graph reachability problems for restricted graph classes (planar, bounded genus) which are shown to be in UL. This paper aims to further explore this relationship by investigating key concepts like "min-uniqueness" and introducing new complexity classes to better understand the boundaries of these computational models.

Methods

The paper employs a combination of established techniques and novel definitions. A core method involves leveraging the concept of "min-uniqueness" in directed graphs. A graph is min-unique with respect to a starting vertex if the shortest path from that vertex to any other vertex is unique. The authors show that this property is crucial for making computations unambiguous. They also introduce new complexity classes, such as UOptL[log n], which is an unambiguous version of the OptL[log n] class. This allows them to establish equivalences between NL=UL and equalities between these new classes. For graph-specific results, they use reductions and constructions, particularly for the 3-page graph reachability problem, to demonstrate its NL-completeness.

Datasets

Not discussed in the paper. The paper deals with theoretical complexity classes and abstract computational models, not empirical datasets.

Key Insights and Ideas

  • Min-uniqueness is the linchpin: The paper establishes that the property of "min-uniqueness" in directed graphs is not just a useful tool, but a necessary and sufficient condition for proving NL = UL. This provides a concrete target for future research.
  • New unambiguous classes illuminate the problem: The introduction of UOptL[log n] and its relation to OptL[log n] offers a new lens through which to view the NL vs. UL problem. The collapse of the hierarchy over UOptL[log n] is a significant finding that implies a collapse in the UL hierarchy as well.
  • 3-page graphs are NL-complete: Showing that reachability in 3-page embedded graphs is NL-complete is a notable result. It contrasts with 2-page graphs (which are in UL) and suggests that the boundary between NL and UL might be closely tied to topological properties of graphs.
  • Bridging the gap for ReachFewL: The paper improves the known upper bound for ReachFewL, showing it's in UL ∩ coUL. This is a step towards understanding the complexity of machines with a limited number of accepting paths.

Key Results

  • Min-uniqueness is necessary and sufficient for NL = UL: This is a major theoretical result, providing a clear condition for resolving the NL vs. UL problem.
  • ReachFewL ⊆ UL ∩ coUL: This improves the previously known upper bound for this class.
  • SHORTESTPATHLENGTH is complete for OptL[log n]: This is the first known completeness result for this class.
  • NL = UL if and only if OptL[log n] = UOptL[log n]: This establishes a direct link between the NL vs. UL problem and the equality of these two function classes.
  • 3PAGEREACH is complete for NL: This result highlights the computational power of graphs embedded on 3 pages.
  • LogFew < UOptL[log n] ⊆ FLSPL[log n]: These are new containment results for unambiguous and "few" complexity classes.

Limitations and Future Work

The paper acknowledges that while they've made progress, the NL vs. UL problem itself remains open. They also note that they were unable to show that FewL reduces to UOptL. Future work is implicitly suggested by the open questions and new results:

  • Resolving NL = UL: The paper provides a clear path forward by identifying min-uniqueness as the key.
  • Investigating FewL and UOptL: Further exploration of the relationship between FewL and UOptL would be valuable.
  • Extending graph results: The contrast between 2-page and 3-page graph reachability suggests that exploring graph properties related to page embeddings could yield further insights into the NL/UL separation.
  • Understanding the UL hierarchy: The collapse of the hierarchy over UOptL[log n] is a significant finding that warrants further investigation into the structure of unambiguous complexity classes.

Summary updated

Abstract

We report progress on the NL versus UL problem. We show that counting the number of s-t paths in graphs where the number of s-v paths for any v is bounded by a polynomial can be done in FUL: the unambiguous log-space function class. Several new upper bounds follow from this including $${{{ReachFewL} \subseteq {UL}}}$$ and $${{{LFew} \subseteq {UL}^{FewL}}}$$ We investigate the complexity of min-uniqueness—a central notion in studying the NL versus UL problem. In this regard we revisit the class OptL[log n] and introduce UOptL[log n], an unambiguous version of OptL[log n]. We investigate the relation between UOptL[log n] and other existing complexity classes. We consider the unambiguous hierarchies over UL and UOptL[log n]. We show that the hierarchy over UOptL[log n] collapses. This implies that $${{{ULH} \subseteq {L}^{{promiseUL}}}}$$ thus collapsing the UL hierarchy. 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 log-space equivalent to the reachability problem in planar graphs and hence is in UL.
BibTeX
@inproceedings{pavan2012power,
  author = {Aduri Pavan and Raghunath Tewari and N. V. Vinodchandran},
  title = {{On the power of unambiguity in log-space}},
  booktitle = {Comput. Complex},
  year = {2012},
  url = {https://openreview.net/forum?id=uuQAI_Sj4PS},
}
Figure