Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
复制标题
DOI：
10.48550/arxiv.2207.05423
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Christian Ikenmeyer;I. Pak;G. Panova
中科院分区：
文献类型：
--
作者：
Christian Ikenmeyer;I. Pak;G. Panova
证明了判定对称群的特征标消失是$\Textsf{C}_=\Textsf{P}$-完全。我们使用这个硬度结果来证明，除非多项式层次折叠到第二层，否则$\extsf{#P}$中不包含字符的绝对值和平方。这排除了字符平方的任何(无符号)组合描述的存在。作为证明的一个副产品，我们得出结论：判定特征标的正性在多对一约简下是$\extsf{PP}$-完全的，因此在图灵约简下是$\extsf{Ph}$-难的。
We prove that deciding the vanishing of the character of the symmetric group is $\textsf{C}_= \textsf{P}$-complete. We use this hardness result to prove that the absolute value and also the square of the character are not contained in $\textsf{#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 $\textsf{PP}$-complete under many-one reductions, and hence $\textsf{PH}$-hard under Turing reductions.