\textsc{ReachFewL} = \textsc{ReachUL}

DOI10.1007/S00037-012-0050-8MaRDI QIDQ744612zbMATH OpenOpenAlexFDO

Authors Brady Garvin, Derrick Stolee, Raghunath Tewari, N. V. Vinodchandran

Publication date 25 September 2014

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-012-0050-8

zbMATH Keywords

graph reachabilitylog-space complexityunambiguous computations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• ReachFewL = ReachUL
• On the power of unambiguity in log-space
• Directed planar reachability is in unambiguous log-space
• On the complexity of L-reachability
• scientific article; zbMATH DE number 3987266

Cites work

• scientific article; zbMATH DE number 1346519 (Why is no real title available?)
• A very hard log-space counting class
• An unambiguous class possessing a complete set
• Computational Complexity
• Directed planar reachability is in unambiguous log-space
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Making Nondeterminism Unambiguous
• NL-printable sets and nondeterministic Kolmogorov complexity
• On the power of unambiguity in log-space
• RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
• Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Structure and importance of logspace-MOD class
• Using inductive counting to simulate nondeterministic computation

Cited in

(4)

• Polynomial min/max-weighted reachability is in unambiguous log-space
• Min/max-poly weighting schemes and the NL versus UL problem
• On the power of unambiguity in log-space
• ReachFewL = ReachUL

This page was built for publication: \textsc{ReachFewL} = \textsc{ReachUL}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744612)