Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-323 | 20th November 2026 15:21

NL = UL

RSS-Feed




TR26-323
Authors: William Hoza
Publication: 20th November 2026 15:29
Downloads: 458
Keywords: 


Abstract:

We present an explicit weight assignment generator that uses a seed of length $O(\log(wn))$ to assign a polynomially-bounded integer weight to each vertex of any simple width-$w$ length-$n$ layered digraph. For each such digraph, there is at least one seed such that the weight function is min-isolating, i.e., the minimum-weight path from $s$ to $t$ is unique for every $s, t$ such that $t$ is reachable from $s$. The generator is computable using $O(\log(wn))$ bits of space. Thanks to work by Reinhardt and Allender (SICOMP 2000), it immediately follows that NL = UL, i.e., every nondeterministic log-space Turing machine can be simulated by an unambiguous log-space Turing machine. The construction and analysis of the min-isolating weight function are remarkably simple.



ISSN 1433-8092 | Imprint