Entropy of pebble and space complexity
J. Andres Montoya · 2026
Read Entropy of pebble and space complexity by J. Andres Montoya (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08555.txt.
Description
J. Andres Montoya studies the power of pebble automata through the lens of entropy and space complexity. The work compares three classic resource classes: logarithmic space, its nondeterministic version, and the closure of context free languages under thrifty reductions. Montoya presents a claimed proof that the nondeterministic class differs from that closure.
As presented, the separation would also imply that logarithmic space differs from polynomial time, a far stronger outcome. Because such separations touch famous open questions in complexity theory, readers should treat the argument as a claim to be checked by the community, not settled fact. The short paper rewards careful scrutiny of each step in the proof.
Catalog record
| CREATOR | J. Andres Montoya |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.08555