Valiant completeness: the permanent is VNP-hard under p-projections
ProvedResultantVNP.permanent_vnp_completealgebraic-complexitycomplexitypermanent
Over the complex numbers, every family in VNP is a p-projection of the generic permanent family. More precisely, for every VNP family (f_n), there is a polynomially bounded function t with t(n) at least 1 such that f_n is obtained from the permanent of a t(n)-by-t(n) matrix by substituting variables and complex constants. VNP here is the Boolean exponential-sum closure of the bounded-degree arithmetic-circuit class VP. This is the classical permanent-completeness result used to pass from the explicit permanent projection in Theorem 3.2 to VNP-hardness.
Preamble
import Mathlib import Definitions.Def_ResultantVNP_IsVNPHardPProj
Formal statement
theorem ResultantVNP.permanent_vnp_complete :
ResultantVNP.IsVNPHardPProj
(fun n => (Matrix.of fun i j : Fin n =>
(MvPolynomial.X (i,j) : MvPolynomial (Fin n × Fin n) ℂ)).permanent) 1 := by sorrySource
The classical Valiant permanent-completeness theorem, as invoked in Section 3.1 and the proof of Theorem 3.2 of Bhargav–Curticapean–Jindal–Shukla, Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 paper #1103.