  In two papers, B\"urgisser and Ikenmeyer (STOC 2011, STOC 2013) used an
adaption of the geometric complexity theory (GCT) approach by Mulmuley and
Sohoni (Siam J Comput 2001, 2008) to prove lower bounds on the border rank of
the matrix multiplication tensor. A key ingredient was information about
certain Kronecker coefficients. While tensors are an interesting test bed for
GCT ideas, the far-away goal is the separation of algebraic complexity classes.
The role of the Kronecker coefficients in that setting is taken by the
so-called plethysm coefficients: These are the multiplicities in the coordinate
rings of spaces of polynomials. Even though several hardness results for
Kronecker coefficients are known, there are almost no results about the
complexity of computing the plethysm coefficients or even deciding their
positivity.
  In this paper we show that deciding positivity of plethysm coefficients is
NP-hard, and that computing plethysm coefficients is #P-hard. In fact, both
problems remain hard even if the inner parameter of the plethysm coefficient is
fixed. In this way we obtain an inner versus outer contrast: If the outer
parameter of the plethysm coefficient is fixed, then the plethysm coefficient
can be computed in polynomial time.
  Moreover, we derive new lower and upper bounds and in special cases even
combinatorial descriptions for plethysm coefficients, which we consider to be
of independent interest. Our technique uses discrete tomography in a more
refined way than the recent work on Kronecker coefficients by Ikenmeyer,
Mulmuley, and Walter (Comput Compl 2017). This makes our work the first to
apply techniques from discrete tomography to the study of plethysm
coefficients. Quite surprisingly, that interpretation also leads to new
equalities between certain plethysm coefficients and Kronecker coefficients.
