The VP_s versus VNP separation conjecture

At least 10 years old · documented by

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.

VPs≠VNP.\textup{\textsf{VP$_s$}} \neq \textup{\textsf{VNP}}.

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

References

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.