Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory

Question

I was reading the GCT IV paper (http://arxiv.org/pdf/cs/0703110v4.pdf) and while the representation theory is clear enough (by which I do not mean to say 'easy'!) the relation to complexity theory as stated in the introduction confuses me.

I quote:

The flip suggests that separating the classes P and NP will require solving difficult positivity problems in algebraic geometry and representation theory. A central positivity problem arising here is the following fundamental problem in the representation theory of the symmetric group.

Let $S_r$ denote the symmetric group on $r$ letters and let $M_\nu$ denote the $S_r$-irreducible corresponding to the partition $\nu$. Given three partitions λ, µ, ν of r, the Kronecker coefficient $g_{\lambda \mu \nu}$ is defined to be the multiplicity of $M_\nu$ in the tensor product $M_\lambda \otimes M_\mu$. (...)

Problem 1.1 (Kronecker problem). Find a positive combinatorial formula for the Kronecker coefficients $g_{\lambda \mu \nu}$.

There are two precise related problems in complexity theory that arise in the flip: (1) find a (positive) #P formula for Kronecker coefficients, and harder, (2) find a polynomial time algorithm to determine whether a Kronecker coefficient is zero.

My questions are:

A) When they say polynomial time in question (2), what is the input size here? I found it easy to find a $O(d^3)$ algorithm where $d$ is the product of the dimensions of the vector spaces $M_\lambda, M_\mu, M_\nu$, so apparently they are thinking of something smaller than that. But what? The number $r$? How do we know that the dimensions are not polynomial in $r$? (It seems to me they are polynomial in $r$ but with an exponent that depends on the number of elements in the partition, so maybe that doesn't count as truly polynomial?)

B) How can question (2) be harder than question (1) when, obviously, any solution to question (1) gives you a solution to question (2). (At least I find it hard to imagine a world where an algorithm to compute a number doesn't give you an algortithm to tell if that number is zero.) The $P$ in $\#P$ also means 'polynomial time', right?

It looks like I am missing something really obvious here but what?

Answer 1

A) The input here is the triple of partitions $(\lambda, \mu, \nu)$, represented as sequences of numbers in binary. The dimension of the irreducible representation $M_{\lambda}$ can actually be exponential in $r$, take for example the hook partition $n + 1, 1, 1, \dots, 1 \vdash 2n + 1$. Using the hook formula for the dimension we get $\frac {(2n)!}{(n !)^2}$.

B) The $P$ in $\# P$ means polynomial time, but the $\#$ in $\#P$ means "count computation paths of a nondeterministic machine". An example of $\#P$ problem is $\#SAT$ (count the number of satisfying assignments for a given formula), and the corresponding decision problem is $SAT$, which is probably not in $P$.