Positivity of the symmetric group characters is as hard as the polynomial time hierarchy

DOI10.1137/1.9781611977554.CH136arXiv2207.05423OpenAlexW4316652344MaRDI QIDQ6404697FDOQ6404697

Igor Pak, Christian Ikenmeyer, Greta Panova

Publication date: 12 July 2022

Abstract: 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 $$, 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.

Full work available at URL: https://doi.org/10.1137/1.9781611977554.ch136

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited In (1)

• Computational complexity of counting coincidences

This page was built for publication: Positivity of the symmetric group characters is as hard as the polynomial time hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404697)