Valiant's VP versus VNP conjecture

From papers

Let Sm\mathfrak S_m denote the permutation group on mm elements, let yjiy^i_j be linear coordinates on Cm2\mathbb C^{m^2}, and define the permanent by

permm(yji)=σSmyσ(1)1yσ(m)m.\operatorname{perm}_m(y^i_j)=\sum_{\sigma\in\mathfrak S_m} y^1_{\sigma(1)}\cdots y^m_{\sigma(m)}.

A polynomial-size circuit is a circuit whose size is bounded by a polynomial in the input degree. Valiant's conjecture. There does not exist a polynomial-size circuit computing the permanent. This is the central separation conjecture of algebraic complexity theory and motivates comparing the permanent with the determinant; its status is open.

Progress summary

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

Sources & referencesView supporting material

Primary source

Klim Efremenko, J. M. Landsberg, Hal Schenck and Jerzy Weyman, “The method of shifted partial derivatives cannot separate the permanent from the determinant”, arXiv:1609.02103 (2016).

Additional references

4 papers in this index state this conjecture (2012–2016). The statement above is taken from the most recent of them; the others are arXiv:1509.02503, arXiv:1508.05788, arXiv:1203.2888.

Solutions 0

No solutions have been posted yet.