The VP_s versus VNP separation conjecture

Let \textup{\textsf{VP_s}} denote the class of polynomial-size algebraic circuits with bounded degree, and let VNP\textup{\textsf{VNP}} denote Valiant's class of efficiently definable polynomial families. VP_s versus VNP conjecture.

VPsVNP.\textup{\textsf{VP$_s$}} \neq \textup{\textsf{VNP}}.

This is a major conjecture in algebraic complexity theory, related to the classical PNP\textup{\textsf{P}} \neq \textup{\textsf{NP}} conjecture. Its equivalent formulation in terms of determinantal complexity appears immediately afterward in the source.

Sources & referencesView supporting material

Primary source

Christian Ikenmeyer and Greta Panova, “Rectangular Kronecker coefficients and plethysms in geometric complexity theory”, arXiv:1512.03798 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.