The permanent versus determinant conjecture is a major problem in complexity theory that is equivalent to the separation of the complexity classes VP_ ws and VNP. Mulmuley and Sohoni (SIAM J. Comput., 2001) suggested to study a strengthened version of this conjecture over the complex numbers that amounts to separating the orbit closures of the determinant and padded permanent polynomials. In that paper it was also proposed to separate these orbit closures by exhibiting occurrence obstructions, which are irreducible representations of GL_ n^2 (C), which occur in one coordinate ring of the orbit closure, but not in the other. We prove that this approach is impossible. However, we do not rule out the general approach to the permanent versus determinant problem via multiplicity obstructions as proposed by Mulmuley and Sohoni.
A first attempt towards finding occurrence obstructions was by asymptotic considerations (moment polytopes): this was ruled out in @cite_4 , where it was proven that for all @math there exists a stretching factor @math such that @math . In @cite_5 it was shown that deciding positivity of Kronecker coefficients in general is NP-hard, but this proof fails for rectangular formats.
@cite_5 @cite_4
1894723027 2148706005
We show that the problem of deciding positivity of Kronecker coefficients is NP-hard. Previously, this problem was conjectured to be in P, just as for the Littlewood–Richardson coefficients. Our result establishes in a formal way that Kronecker coefficients are more difficult than Littlewood–Richardson coefficients, unless P = NP. We prove that for any partition ( 1;:::; d2) of size ‘d there exists k 1 such that the tensor square of the irreducible representation of the symmetric group Sk‘d with respect to the rectangular partition (k‘;:::;k‘) contains the irreducible representation corresponding to the stretched partition (k 1;:::;k d 2). We also prove a related approximate version of this statement in which the stretching factor k is eectively bounded in terms of d. We further discuss the consequences for geometric complexity theory which provided the motivation for this work.