Making Nondeterminism Unambiguous
From MaRDI portal
Publication:4943859
DOI10.1137/S0097539798339041zbMath0947.68063OpenAlexW2139236203WikidataQ56387896 ScholiaQ56387896MaRDI QIDQ4943859
Klaus Reinhardt, Eric W. Allender
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539798339041
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (39)
NL-printable sets and nondeterministic Kolmogorov complexity ⋮ The complexity of planarity testing ⋮ Unnamed Item ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Is Valiant-Vazirani's isolation probability improvable? ⋮ Depth-first search in directed planar graphs, revisited ⋮ Dual VP classes ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ Unnamed Item ⋮ Positive and negative proofs for circuits and branching programs ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Unnamed Item ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ On arithmetic branching programs ⋮ Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ⋮ Two-way automata making choices only at the endmarkers ⋮ ON THE MINIMAL POLYNOMIAL OF A MATRIX ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ On expressive power of regular realizability problems ⋮ Two-way unary automata versus logarithmic space ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ String shuffle: circuits and graphs ⋮ Green's theorem and isolation in planar graphs ⋮ Unnamed Item ⋮ Planar and grid graph reachability problems ⋮ \textsc{ReachFewL} = \textsc{ReachUL} ⋮ Complexity Theory Basics: NP and NL ⋮ Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Unnamed Item ⋮ Typically-correct derandomization for small time and space ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones ⋮ Unambiguity in Automata Theory ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
This page was built for publication: Making Nondeterminism Unambiguous
