ECCC-Report TR10-009https://eccc.weizmann.ac.il/report/2010/009Comments and Revisions published for TR10-009en-usFri, 15 Jan 2010 18:39:52 +0200
Paper TR10-009
| On the Power of Unambiguity in Logspace |
A. Pavan,
Raghunath Tewari,
N. V. Vinodchandran
https://eccc.weizmann.ac.il/report/2010/009We 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}
Fri, 15 Jan 2010 18:39:52 +0200https://eccc.weizmann.ac.il/report/2010/009