Computer Science – Computational Complexity
Scientific paper
2010-01-12
Computer Science
Computational Complexity
14 pages, 3 figures
Scientific paper
We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \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 {\sc ShortestPathLength} - computing 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 \leq \UOptL[\log n] \leq \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.
Pavan Aduri
Tewari Raghunath
Vinodchandran N. V.
No associations
LandOfFree
On the Power of Unambiguity in Logspace does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Power of Unambiguity in Logspace, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Power of Unambiguity in Logspace will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-524080