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

DOI10.1090/S0002-9947-2010-04918-9zbMath1215.12005OpenAlexW1968830538MaRDI QIDQ3053472

Russell G. Miller

Publication date: 29 October 2010

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0002-9947-2010-04918-9

zbMATH Keywords

factorization of polynomialsroots of polynomialscomputable fields

Mathematics Subject Classification ID

Decidability and field theory (12L05) Polynomials in general fields (irreducibility, etc.) (12E05) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

Computing constraint sets for differential fields ⋮ Computable fields and the bounded Turing reduction ⋮ Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees ⋮ Primitive recursive ordered fields and some applications ⋮ Spectra of Algebraic Fields and Subfields ⋮ Adapting Rabin’s Theorem for Differential Fields ⋮ Categoricity properties for computable algebraic fields ⋮ Computable procedures for fields

Cites Work

• Effective procedures in field theory
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• d-computable categoricity for algebraic fields
• Reducibility and Completeness for Sets of Integers
• Effective content of field theory
• Computable Algebra, General Theory and Theory of Computable Fields
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item