On the power of unambiguity in log-space
From MaRDI portal
Publication:1926109
DOI10.1007/s00037-012-0047-3zbMath1279.68099arXiv1001.2034OpenAlexW1772007397WikidataQ56689209 ScholiaQ56689209MaRDI QIDQ1926109
N. V. Vinodchandran, A. Pavan, Raghunath Tewari
Publication date: 27 December 2012
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1001.2034
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
Space-efficient algorithms for reachability in directed geometric graphs ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ Unnamed Item ⋮ \textsc{ReachFewL} = \textsc{ReachUL} ⋮ Compressed Decision Problems in Hyperbolic Groups.
Cites Work
- The strong exponential hierarchy collapses
- Planar and grid graph reachability problems
- The complexity of optimization problems
- Using inductive counting to simulate nondeterministic computation
- A very hard log-space counting class
- Relative complexity of checking and evaluating
- Equivalence of NC\(^ k\) and AC\(^{k-1}\) closures of NP and other classes
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- The complexity of matrix rank and feasible systems of linear equations
- Isolation, matching, and counting uniform and nonuniform upper bounds
- NL-printable sets and nondeterministic Kolmogorov complexity
- Directed Planar Reachability Is in Unambiguous Log-Space
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
- ReachFewL = ReachUL
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- Undirected connectivity in log-space
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Structure and importance of logspace-MOD class
- Relationships among $PL$, $\#L$, and the determinant
- On the power of parity polynomial time
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the power of unambiguity in log-space
