  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 also show that there exists a #P-formula for a particular subclass of
Kronecker coefficients whose positivity is NP-hard to decide. This is an
evidence that, despite the hardness of the positivity problem, there may well
exist a positive combinatorial formula for the Kronecker coefficients. Finding
such a formula is a major open problem in representation theory and algebraic
combinatorics.
  Finally, we consider the existence of the partition triples $(\lambda, \mu,
\pi)$ such that the Kronecker coefficient $k^\lambda_{\mu, \pi} = 0$ but the
Kronecker coefficient $k^{l \lambda}_{l \mu, l \pi} > 0$ for some integer
$l>1$. Such "holes" are of great interest as they witness the failure of the
saturation property for the Kronecker coefficients, which is still poorly
understood. Using insight from computational complexity theory, we turn our
hardness proof into a positive result: We show that not only do there exist
many such triples, but they can also be found efficiently. Specifically, we
show that, for any $0<\epsilon\leq1$, 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 proof of the last result
illustrates the effectiveness of the explicit proof strategy of GCT.
