← All problems

The VP_s versus VNP separation conjecture

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
  1. 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.