Article ID Journal Published Year Pages File Type
4661992 Annals of Pure and Applied Logic 2012 13 Pages PDF
Abstract

For a computable field F, the splitting set SF of F is the set of polynomials in F[X] which factor over F, and the root set RF of F is the set of polynomials in F[X] which have a root in F.Results of Fröhlich and Shepherdson (1956) in [3], imply that for a computable field F, the splitting set SF and the root set RF are Turing-equivalent. More recently, in Miller (2010) [5], Miller showed that for algebraic fields, if we use a finer measure, the root set actually has slightly higher complexity: for algebraic fields F, it is always the case that SF≤1RF, but there are algebraic fields F where we have RF≰1SF.Here we compare the splitting set and the root set of a computable algebraic field under a different reduction: the bounded Turing (bT) reduction. We construct a computable algebraic field for which RF≰bTSF.We also define a Rabin embedding g of a field into its algebraic closure, and for a computable algebraic field F, we compare the relative complexities of RF, SF, and g(F) under m-reducibility and under bT-reducibility.

Related Topics
Physical Sciences and Engineering Mathematics Logic