Counting in logarithmic space
Computational Complexity
Summary
The authors study a class of functions called #L that count how many ways a special kind of small-memory computer can accept an input. They show many well-known counting functions from math, like Catalan numbers and Stirling numbers, belong to this class. They also explore more complex counts related to algebra and geometry and discuss tools to prove functions fit into #L. Their work suggests new ways to understand the boundaries between easy and hard counting problems in computer science.
Authors
Álvaro Gutiérrez, Christian Ikenmeyer, Greta Panova
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.