Polynomial-size Boolean sums of formulas simulate VP
ProvedResultantVNP.vp_formula_sumalgebraic-complexityarithmetic-circuitsvnp
Every family in VP over the complex numbers can be written as a Boolean sum of a polynomial-size arithmetic-formula family. The number of Boolean witness variables and formula gate count are polynomially bounded. The underlying VP definition counts only arithmetic gates, permits arbitrary complex constants, and bounds the actual output degree; intermediate cancellations are allowed.
Preamble
import Definitions.Def_ResultantVNP_FormulaWitness
Formal statement
theorem ResultantVNP.vp_formula_sum : VNPNestedBooleanSum.VPFormulaSumProperty := by sorry
Source
Valiant, Completeness classes in algebra, STOC 1979; see also Hrubeš, Wigderson and Yehudayoff, Relationless completeness and separations, Theorem 11 and Section IV-A, https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/HWY10_rel/HWY10_rel_proc.pdf.