The central open question of algebraic complexity is whether VP is unequal to VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic circuits. For symmetric algebraic circuits, this has been confirmed by Dawar and Wilsenach (2020) who showed exponential lower bounds on the size of symmetric circuits for the permanent. In this work, we set out to develop a more general symmetric algebraic complexity theory. Our main result is that a family of symmetric polynomials admits small symmetric circuits if and only if they can be written as a linear combination of homomorphism counting polynomials of graphs of bounded treewidth. We also establish a relationship between the symmetric complexity of subgraph counting polynomials and the vertex cover number of the pattern graph. As a concrete example, we examine the symmetric complexity of immanant families (a generalisation of the determinant and permanent) and show that a known conditional dichotomy due to Curticapean (2021) holds unconditionally in the symmetric setting.

翻译：代数复杂度的核心开放问题是VP是否不等于VNP，即永久函数能否由多项式规模的代数电路族表示。对于对称代数电路，Dawar和Wilsenach（2020）已证实了这一点，他们证明了永久函数在对称电路上具有指数级规模下界。在本工作中，我们致力于发展更一般的对称代数复杂度理论。我们的主要结果表明：一族对称多项式具有小规模对称电路，当且仅当它们可以表示为有界树宽图的同态计数多项式的线性组合。我们还建立了子图计数多项式的对称复杂度与模式图的顶点覆盖数之间的关系。作为具体示例，我们研究了不变式族（行列式与永久函数的推广）的对称复杂度，并证明了Curticapean（2021）提出的条件二分法在对称设定下无条件成立。