Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-009 | 13th January 2010 01:56

#### On the Power of Unambiguity in Logspace

TR10-009
Authors: A. Pavan, Raghunath Tewari, N. V. Vinodchandran
Publication: 15th January 2010 18:39
Keywords:

Abstract:

We report progress on the \NL\ vs \UL\ problem.
\begin{itemize}
\item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$.
\item[-] We investigate the complexity of min-uniqueness - a central
notion in studying the \NL\ vs \UL\ problem.
\begin{itemize}
\item We show that min-uniqueness is necessary and sufficient for showing
$\NL\ =\UL$.
\item 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]$.
\item 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$.
\end{itemize}
\item[-] 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.
\end{itemize}

ISSN 1433-8092 | Imprint