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

CREATORJ. Andres Montoya
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.08555

Browse the full library · About the Tower of Babel