Abstrakt. Vi visar att problemet med att avgöra om Kroneckerkoefficienterna är positiva är NP-hårda. Tidigare var detta problem förmodas vara i P, precis som för Littlewood-Richardson koefficienter. Vårt resultat fastställer på ett formellt sätt att Kroneckerkoefficienter är svårare än Littlewood-Richardson koefficienter, om inte P = NP. Vi visar också att det finns en #P -formula för en viss underklass av Kronecker koefficienter vars positivitet är NP-hård att bestämma. Detta är ett bevis på att det, trots positivitetsproblemets hårdhet, mycket väl kan finnas en positiv kombinationsformel för Kroneckerkoefficienterna. Att hitta en sådan formel är ett stort öppet problem inom representationsteori och algebraisk kombinatorik. Slutligen anser vi att förekomsten av partition trippels (λ, μ, π) sådan att Kronecker koefficienten k λ μ,π = 0 men Kronecker koefficienten k lλ lμ,lπ > 0 för vissa heltal l > 1. Sådana "hål" är av stort intresse när de bevittnar misslyckandet med mättnadsegendomen för Kroneckerkoefficienterna, som fortfarande är dåligt förstådd. Med hjälp av insikt från beräkningskomplex teori, vi förvandlar vår hårdhet bevis till ett positivt resultat: Vi visar att det inte bara finns många sådana tripletter, men de kan också hittas effektivt. Specifikt visar vi att det för alla 0 < ≤ 1 finns 0 < a < 1 sådana att det för alla m finns 2 m partitionstripplar (λ, μ, μ) i Kronecker-konen så att a) Kronecker-koefficienten k λ μ,μ är noll, b) höjden på μ är m, c) höjden på λ är ≤ m, och d). Beviset för det sista resultatet visar hur effektiv GCT:s explicita bevisstrategi är.
I REF visades att beslut om positivitet för Kroneckerkoefficienter i allmänhet är NP-hårda, men detta bevis misslyckas för rektangulära format.
On vanishing of Kronecker coefficients
{'venue': 'computational complexity', 'journal': 'computational complexity', 'mag_field_of_study': ['Mathematics', 'Computer Science']}