Branching Programs with Extended Memory: New Insights
Publisher Information
- Conf: CIAC 2025 (to appear)
Abstract
One of the central themes of Algebraic Complexity Theory is to understand the relative computation power of algebraic complexity classes \mathsf{VP} and \mathsf{VNP}. \mathsf{VP} is a class of polynomial families which can be computed efficiently by algebraic circuits. \mathsf{VNP} is a class of polynomials which can be efficiently expressed through polynomial families in \mathsf{VP}, but we do not know if they can be computed efficiently. It is a long standing open problem in this area to show that \mathsf{VP} is a strict subset of \mathsf{VNP}. At this juncture, it is fair to believe that newer characterization of these complexity classes could help us understand these models better (and possibly help us is resolving this question in restricted settings like non-commutativity at the very least).
Recently, Mengel [MFCS, 2013] showed that Algebraic Branching Programs (ABPs) (it is well known that algebraic branching programs (ABPs) characterize the class \mathsf{VBP} (or equivalently \mathsf{VP}_{\mathrm{skew}})) can be extended with memory and the computational models thus obtained can be used to characterize \mathsf{VP} and \mathsf{VNP}. In particular, Mengel showed that ABPs with a single stack characterize \mathsf{VP}, and branching programs with random-access memory characterize \mathsf{VNP}.
In this work we show that algebraic branching programs with just 2 stacks efficiently simulates the polynomial families in \mathsf{VNP}, and two stack branching programs are \mathsf{VNP}-complete.
Further, we observe that k-stack branching programs (for all polynomially bounded k) are no more powerful than 2-stack branching programs (upto a polynomial blowup in size).
This strengthens the work of Mengel in the following way – \mathsf{VBP} vs. \mathsf{VP} vs. \mathsf{VNP} are characterized by algebraic branching programs with 0, 1, and 2 stacks, respectively, or no-memory, a stack as memory, and a queue as memory respectively, which hold even in the non-commutative setting.
We also refine Mengel’s characterization of \mathsf{VP} through stack-height characterization.