Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917720361009152 |
|---|---|
| author | Ikenmeyer, Christian Pak, Igor Panova, Greta |
| author_facet | Ikenmeyer, Christian Pak, Igor Panova, Greta |
| contents | We prove that deciding the vanishing of the character of the symmetric group is $C_=P$-complete. We use this hardness result to prove that the the square of the character is not contained in $\#P$, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof we conclude that deciding positivity of the character is $PP$-complete under many-one reductions, and hence $PH$-hard under Turing-reductions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_05423 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Positivity of the symmetric group characters is as hard as the polynomial time hierarchy Ikenmeyer, Christian Pak, Igor Panova, Greta Combinatorics Computational Complexity Representation Theory We prove that deciding the vanishing of the character of the symmetric group is $C_=P$-complete. We use this hardness result to prove that the the square of the character is not contained in $\#P$, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof we conclude that deciding positivity of the character is $PP$-complete under many-one reductions, and hence $PH$-hard under Turing-reductions. |
| title | Positivity of the symmetric group characters is as hard as the polynomial time hierarchy |
| topic | Combinatorics Computational Complexity Representation Theory |
| url | https://arxiv.org/abs/2207.05423 |