Boundaries of VP and VNP

DOI10.4230/LIPICS.ICALP.2016.34zbMATH Open1388.68076arXiv1605.02815OpenAlexW2962995120MaRDI QIDQ4598170FDOQ4598170

Authors: Joshua A. Grochow, Youming Qiao, Ketan D. Mulmuley 

Publication date: 19 December 2017

Abstract: One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = $overlineextrmVP$, where VP is the class of families of polynomials that are of polynomial degree and can be computed by arithmetic circuits of polynomial size, and $overlineextrmVP$ is the class of families of polynomials that are of polynomial degree and can be approximated infinitesimally closely by arithmetic circuits of polynomial size. The goal of this article is to study the conjecture in (Mulmuley, FOCS 2012) that $overlineextrmVP$ is not contained in VP. Towards that end, we introduce three degenerations of VP (i.e., sets of points in $overlineextrmVP$), namely the stable degeneration Stable-VP, the Newton degeneration Newton-VP, and the p-definable one-parameter degeneration VP*. We also introduce analogous degenerations of VNP. We show that Stable-VP $subseteq$ Newton-VP $subseteq$ VP* $subseteq$ VNP, and Stable-VNP = Newton-VNP = VNP* = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating $overlineextrmVP$ from VP. Although we do not yet construct explicit candidates for the polynomial families in $overlineextrmVPsetminus$VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in Newton-VP $setminus$ VP based on semi-invariants of quivers would have to be non-generic by showing that, for many finite quivers (including some wild ones), any Newton degeneration of a generic semi-invariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomial-size circuits.

Full work available at URL: https://arxiv.org/abs/1605.02815

Recommendations

• Characterizing Valiant’s Algebraic Complexity Classes
• An overview of mathematical issues arising in the geometric complexity theory approach to \(\mathbf{VP}\neq\mathbf{VNP}\)
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Characterizing Valiant's algebraic complexity classes
• Homomorphism polynomials complete for VP

zbMATH Keywords

arithmetic circuitgeometric complexity theoryborder complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (10)

• On the closures of monotone algebraic classes and variants of the determinant
• A note on VNP-completeness and border complexity
• On the closures of monotone algebraic classes and variants of the determinant
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Comment: The Two Styles of VC Bounds
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• Title not available (Why is that?)
• On proving parameterized size lower bounds for multilinear algebraic models
• Title not available (Why is that?)
• Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)

This page was built for publication: Boundaries of VP and VNP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598170)