On the power of unambiguity in log-space

DOI10.1007/s00037-012-0047-3zbMath1279.68099arXiv1001.2034WikidataQ56689209 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

zbMATH Keywords

hardness; graph reachability; log-space complexity; unambiguous computations; log-space optimization

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, Compressed Decision Problems in Hyperbolic Groups., Space-efficient algorithms for reachability in directed geometric graphs, Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata, \textsc{ReachFewL} = \textsc{ReachUL}

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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