Counting in logarithmic space

Abstract

We study the class $\#\mathsf{L}$ of functions counting accepting paths of non-deterministic log-space Turing machines and construct methods to prove containment in $\#\mathsf{L}$. We prove that a large number of classical combinatorial and number theoretic functions belong to this class: classical functions from enumerative combinatorics (multinomial coefficients, Catalan numbers, linear extensions of trees, Stirling numbers, etc), algebraic combinatorics (number of standard Young tableaux, etc), discrete geometry, number theoretic functions, representation theoretic multiplicities in a large class of cases. We show that $\mathrm{GL}_2$-plethysm coefficients of bounded length outer partition can be counted by log$^2$-space polytime verifiers. We pose numerous questions and conjectures on $\#\mathsf{L}$ containment and its generalizations, that suggest venues for conditionally disproving $\#\mathsf{P}$-completeness. While studying which combinatorial functions are in $\#\mathsf{P}$ provides a formal way of (dis)proving the existence of combinatorial interpretations, the lower class $\#\mathsf{L}$ serves as an analogue for functions computable in polynomial time.

Disclosure

“RI, during the semester program “Categorification and Computation in Algebraic Combinatorics” in Fall 2025. The authors thank Joshua P. Swanson and Michał Szwej for helpful conversations. ChatGPT 5.6 was used for proofreading. ÁG was funded by a University of Bristol Research Training Support Grant. GP was partially funded by NSF CCF:AF and DMS gr”

PDF page 1

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T18:56:37.112662Z

Structural counts