← All problems

Valiant's VP versus VNP conjecture

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

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.

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

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.