Valiant's VP versus VNP conjecture

About 14 years old · traced to

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

perm⁡m(yji)=∑σ∈Smyσ(1)1⋯yσ(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.

References

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.

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.