Is it harder to find a root of a polynomial or to factor it?

Russell Miller


Given a field F, it is natural to ask two questions about polynomials p in F[X]. First, does p factor within F[X]? And second, does p have a root in F? We will use computability theory to compare the difficulty of these two questions for computable fields F, i.e. fields in which the set of elements of F is effectively enumerable and the field operations are given by Turing-computable functions. It has been known since the work of Frohlich and Shepherdson in 1956 that for any single computable field F, these two problems are Turing-equivalent, but recent work by the speaker, subsequently strengthened by his student Rebecca Steiner, has used finer reducibilities to establish that in general one question is strictly more difficult than the other. To find out which is which, come to the talk!

Thursday 16th February 2012, 14:00
Robert Recorde Room
Department of Computer Science