Polynomial circuits for a VNP-hard family imply VP = VNP
ProvedResultantVNP.hardness_circuit_collapsealgebraic-complexitycircuitsresultants
Let be a family of polynomials over and let . Suppose the family is VNP-hard under p-projections, and suppose has polynomial-size arithmetic circuits. Then
The conclusion does not require polynomial degree or polynomially many variables for itself: each projected target family already belongs to VNP, and therefore has those bounds. This is the complexity-class closure step in the tensor determinant circuit lower-bound argument.
Preamble
import Mathlib import Definitions.Def_ResultantVNP_IsVNPHardPProj import Definitions.Def_ResultantVNP_HasPolySizeCircuits
Formal statement
theorem ResultantVNP.hardness_circuit_collapse {τ : ℕ → Type} (G : ∀ m, MvPolynomial (τ m) ℂ) (lo : ℕ)
(hlo : 1 ≤ lo) (hhard : ResultantVNP.IsVNPHardPProj G lo)
(hcirc : ResultantVNP.HasPolySizeCircuits G) : ResultantVNP.VP = ResultantVNP.VNP := by sorrySource
Auxiliary closure claim for Bhargav–Curticapean–Jindal–Shukla, Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 submission #1103, proof of Theorem 1.4, p.17, and definitions of VP, VNP and p-projections, Section 3.1, p.14. https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1103.pdf