Abstract
The partition functions count homomorphisms from an input graph G to a fixed graph H. In the setting of algebraic complexity (which generalises exact counting complexity), probing "from the left" turns out to be more useful. We show that enumerating monomials that are in bijection with homomorphisms from a fixed graph G to an input graph H naturally gives rise to polynomial families complete for VP and VNP, the algebraic analogues of P and NP defined by Valiant in 1979. These provide the first example of a family that is defined independent of a circuit model and that is complete for VP.
The cut enumerator polynomial Cut_q (for a natural number q >1), defined by Burgisser in 2000, is known to have "intermediate" status as follows: Over any finite field of size q, it is in VNP, and unless PH collapses, is neither in VP nor VNP-complete. Till recently this was the only known family with these properties. Abstracting this
technique, we show that a host of other similar polynomials based on a generalised version of enumerations of satisfying assignments, vertex covers, cliques, 3 dimensional matchings, and closed walks, all have the same properties. Furthermore, augmenting recent results due to Grochow using extension complexity bounds in polyhedral theory, we show that two of these polynomials are provably not obtainable as monotone affine polynomial-size projections of the permanent.