ausblenden:
Schlagwörter:
Computer Science, Computational Complexity, cs.CC,Mathematics, Representation Theory, math.RT,
Zusammenfassung:
It is shown that:
(1) The problem of deciding positivity of Kronecker coefficients is NP-hard.
(2) There exists a positive ($\# P$)-formula for a subclass of Kronecker
coefficients whose positivity is NP-hard to decide.
(3) For any $0 < \epsilon \le 1$, there exists $0<a<1$ such that, for all
$m$, there exist $\Omega(2^{m^a})$ partition triples $(\lambda,\mu,\mu)$ in the
Kronecker cone such that: (a) the Kronecker coefficient $k^\lambda_{\mu,\mu}$
is zero, (b) the height of $\mu$ is $m$, (c) the height of $\lambda$ is $\le
m^\epsilon$, and (d) $|\lambda|= |\mu| \le m^3$.
The last result takes a step towards proving the existence of
occurrence-based representation-theoretic obstructions in the context of the
GCT approach to the permanent vs. determinant problem. Its proof also
illustrates the effectiveness of the explicit proof strategy of GCT.
