Is it harder to factor a polynomial or to find a root?
Russell Miller · Transactions of the American Mathematical Society · 2010
For a computable field $F$, the splitting set $S$ is the set of polynomials $p(X)\in F[X]$ which factor over $F$, and the root set $R$ is the set of polynomials with roots in $F$. Work by Frohlich and Shepherdson essentially showed these two sets to be Turing-equivalent, surprising many mathematicians since it is not obvious how to compute $S$ from $R$. We apply other standard reducibilities from computability theory, along with a healthy dose of Galois theory, to compare the complexity of these two sets. We show, in contrast to the Turing equivalence, that for algebraic fields the root set has slightly higher complexity: both are computably enumerable, and computable algebraic fields always have $S\leq _1 R$, but it is possible to make $R ot \leq _m S$. So the root set may be viewed as being more difficult than the splitting set to compute.