Valiant's VP versus VNP conjecture
Let denote the permutation group on elements, let be linear coordinates on , and define the permanent by
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
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.