In paper 'On vanishing of Kronecker coefficients' here in http://arxiv.org/pdf/1507.02955v1.pdf, it is showed that deciding positivity of kronecker coefficients is in general NP hard. However there is a caveat which states that only positivity of 'rectangular Kronecker coefficients' is needed in GCT. What is the implication to GCT if this also turns to be NP hard?

A related question is what is consequence to GCT if there is no general positive formula akin to one for special case of LR coefficients?


Even if deciding positivity of Kronecker coefficients is NP-hard, or even if there is no general positive formula for them, it is still quite possible for GCT to "work." Even under the preceding assumption, it is still possible that there is a positive formula (and even a polynomial-time decision procedure) for some of the rectangular Kronecker coefficients. If one could find such a formula, and then show that the corresponding irreducible representations appear with nonzero multiplicity in the coordinate ring of the orbit closure of an appropriately-sized permanent, it would still prove the (Strong) Permanent versus Determinant Conjecture.

Update 8/30/15: I should add that, independent of positive combinatorial formulae, I think the geometric approach to complexity, as in GCT, is a very useful way to understand the structure of complexity classes, and using representation theory where it naturally arises (such as here) is always a Good Idea. Landsberg's work in this area is notable in this direction (i.e., using geometric techniques combined with representation theory, even in the absence of positive combinatorial formulae). [end update]

[Now back to positive combinatorial formulae...] Even if more and more Kronecker coefficients end up being NP-hard to decide their vanishing, or if there isn't a positive combinatorial formula for them, (a) it is simply a testament to just how hard these problems are (after all, while GCT gets around the known barriers, it is still aiming at proving some very hard open problems), and/or (b) suggests where to narrow one's focus in order to get GCT to work (e.g., as above).

Also, although NP-hardness is "bad news" in general, it is not necessarily the end of the road. For example, although Hamiltonian Cycle is NP-hard, there are still lots of theorems and theoretical understanding around Hamiltonian cycles. The NP-hardness just leads one (or at least, me) to expect that there won't ever be a "complete theory of Hamiltonian cycles". But one doesn't need such a "complete theory of Kronecker coefficients" to prove a lower bound via GCT - one just needs one family of representations that vanishes on the orbit closure of the determinant but not on the orbit closure of the permanent.

(This answer also applies to the recent paper of Kahle and Michalek which shows that there are families of plethysm multiplicities that are not given by the number of integer points in a natural family of polytopes.)

  • $\begingroup$ What happens if exactly the nature of rectangular Kronecker coefficients which GCT excatly needs to be $P$ turns out to be $NP$ hard? After all this is the $VNP$ vs $VP$ question here (things could infact be circular and ugly). $\endgroup$
    – Mr.
    Aug 3 '15 at 17:22
  • 2
    $\begingroup$ Even if it turns out that for every family of irreps that appears with nonzero multiplicity in the coordinate ring of the orbit closure of the permanent, the corresponding Kronecker decision problem is NP-hard, (a) there could still be a pos. combin. formula, and (b) the third paragraph of my answer still applies. The other thing is: if we knew this fact, we'd likely know so much more about the irreps on the orbit closure of perm than we currently do that we'd probably be able to resolve perm v det anyways.... PS - Email me. $\endgroup$ Aug 3 '15 at 17:30
  • $\begingroup$ what if there is no positive combinatorial formula at all? $\endgroup$
    – Mr.
    Aug 3 '15 at 17:32
  • 2
    $\begingroup$ If there is no positive combinatorial formula for Kronecker (or the multiplicities in the orbit closure of det) for any of the irreps appearing in the orbit closure of perm, that still doesn't rule out GCT. It just means that one will have to prove something about these multiplicities some other way, e.g. geometrically. $\endgroup$ Aug 3 '15 at 17:47
  • 1
    $\begingroup$ The rough idea is that there should be some kind of analogue of the Riemann Hypothesis over finite fields (aka Weil Conjectures), but related to the nonstandard quantum groups (as in GCT IV/VII/VIII). As far as I know, even coming up with the statement of what this analogue should be is still open... $\endgroup$ Aug 3 '15 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.