کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661992 | 1633486 | 2012 | 13 صفحه PDF | دانلود رایگان |

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.
Journal: Annals of Pure and Applied Logic - Volume 163, Issue 6, June 2012, Pages 730-742