Entropy of pebble automata and space complexity
arXiv:2605.0855554.4
AI Analysis
For theoretical computer scientists, this provides a definitive separation between fundamental complexity classes, settling long-standing open questions.
The paper proves that NL is different from logCFL, which implies L ≠ Ptime and NL ≠ Ptime, resolving a major open problem in complexity theory.
Let L denote the class Logpsace and NL the class NLogspace. We use logCFL to denote the closure under logspace reductions of the set of context-free languages. We prove that NL is different from logCFL. This result implies L different from Ptime and the stronger separation NL different from Ptime.