期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We report progress on the \NL\ vs \UL\ problem.
\begin{itemize}
\item[-] We show unconditionally that the complexity class \ReachFewL\UL. This improves on the earlier known upper bound \ReachFewL\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[logn] and show that {\sc ShortestPathLength} - computing the length of the shortest path in a DAG, is complete for \OptL[logn].
\item We introduce \UOptL[logn], an unambiguous version of \OptL[logn], and show that (a) \NL=\UL if and only if \OptL[logn]=\UOptL[logn], (b) \LogFew\UOptL[logn]\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}
