论文标题
对称组字符的积极性与多项式时间层次结构一样困难
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
论文作者
论文摘要
我们证明，确定对称组的角色的消失是$ C_ = P $ -COMPLETE。我们使用这种硬度结果证明，除非多项式层次结构倒入第二级，否则字符的平方不包含在$ \＃p $中。这排除了字符正方形的任何（未签名）组合描述的存在。作为我们证明的副产品，我们得出的结论是，在多一减少的情况下，确定角色的积极性是$ pp $ complete，因此在Turing-Reductions下的$ ph $ - hard。
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.
