论文标题
从算法区分对称组的不可还原特征
Algorithmically distinguishing irreducible characters of the symmetric group
论文作者
论文摘要
假设$χ_λ$和$χ_μ$是对称组$ s_n $的不同性质。我们给出了一种算法，该算法在$ n $中及时构建$π\ s_n $中的$χ_λ（π）$与$χ_μ（π）$有很大不同。实际上，我们显示了更多。假设$ f =χ_λ$对于某些不可约的字符$ s_n $的$χ_λ$，但我们不知道$λ$，并且我们只有Oracle访问$ f $。我们提供了一种确定$λ$的算法，使用许多查询到$ f $，在$ n $中是多项式。知道$λ$的人可以在$ n $中按时计算每个查询。
Suppose that $χ_λ$ and $χ_μ$ are distinct irreducible characters of the symmetric group $S_n$. We give an algorithm that, in time polynomial in $n$, constructs $π\in S_n$ such that $χ_λ(π)$ is provably different from $χ_μ(π)$. In fact, we show a little more. Suppose $f=χ_λ$ for some irreducible character $χ_λ$ of $S_n$, but we do not know $λ$, and we are given only oracle access to $f$. We give an algorithm that determines $λ$, using a number of queries to $f$ that is polynomial in $n$. Each query can be computed in time polynomial in $n$ by someone who knows $λ$.
