Raghunath Tewari

  1. On the Power of Unambiguity in Logspace.

    Authors: Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran
    Subjects: Computational Complexity
    Abstract

    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]$.

Syndicate content