William Hoza Proves NL = UL in Strikingly Simple Log-Space Construction
fortnow · x · 2026-11-21
William Hoza's new ECCC paper (TR26-323) proves NL = UL: every nondeterministic log-space Turing machine can be simulated by an unambiguous one.
- An explicit weight-assignment generator uses O(log(wn)) seed space to assign polynomially bounded integer weights to edges of any layered digraph.
- Some seed makes the weight function min-isolating: the minimum-weight s→t path is unique for every reachable pair.
- Combined with Reinhardt–Allender (SICOMP 2000), NL = UL follows; the construction and analysis are remarkably simple.
More from Research
- Why the Riemann Hypothesis is hard: zeta on the 4/5-line gets arbitrarily close to zero — AlexKontorovich · 2026-11-21
- Stanford Study: Deactivating AI for Two Weeks Reduces Loneliness and Boosts Social Interaction — stanfordnlp · 2026-11-21
- DOCKET Benchmark: Only 18-30% of LLM Policy Comments Align With Real Human Feedback — stanfordnlp · 2026-11-21
- Stanford AI100 releases 2026 report on the scaling era and mainstream generative AI — stanfordnlp · 2026-11-21
- New Multi-Agent Coordination Bench finds frontier agents coordinate poorly; only Opus gains — AlexGDimakis · 2026-11-21
- Riemann Hypothesis Result's Dramatically Written Intro Draws Attention — lishali88 · 2026-11-21