On the power of unambiguity in log-space
From MaRDI portal
Publication:1926109
DOI10.1007/s00037-012-0047-3zbMath1279.68099arXiv1001.2034WikidataQ56689209 ScholiaQ56689209MaRDI QIDQ1926109
A. Pavan, Raghunath Tewari, N. V. Vinodchandran
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
hardness; graph reachability; log-space complexity; unambiguous computations; log-space optimization
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
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
