hide
Free keywords:
Computer Science, Computational Complexity, cs.CC,
Abstract:
In 1979 Valiant showed that the complexity class VP_e of families with
polynomially bounded formula size is contained in the class VP_s of families
that have algebraic branching programs (ABPs) of polynomially bounded size.
Motivated by the problem of separating these classes we study the topological
closure VP_e-bar, i.e. the class of polynomials that can be approximated
arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a
strikingly simple complete polynomial (in characteristic different from 2)
whose recursive definition is similar to the Fibonacci numbers. Further
understanding this polynomial seems to be a promising route to new formula
lower bounds.
Our methods are rooted in the study of ABPs of small constant width. In 1992
Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3
ABP size. We extend their result (in characteristic different from 2) by
showing that approximate formula size is polynomially equivalent to approximate
width-2 ABP size. This is surprising because in 2011 Allender and Wang gave
explicit polynomials that cannot be computed by width-2 ABPs at all! The
details of our construction lead to the aforementioned characterization of
VP_e-bar.
As a natural continuation of this work we prove that the class VNP can be
described as the class of families that admit a hypercube summation of
polynomially bounded dimension over a product of polynomially many affine
linear forms. This gives the first separations of algebraic complexity classes
from their nondeterministic analogs.
