Valiant's VP versus VNP conjecture
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.
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
Sign in to submit a solution.
No solutions have been posted yet.