Polynomial time algorithms for sentences over number fields

DOI10.1016/0890-5401(92)90037-GMaRDI QIDQ1187032zbMATH OpenOpenAlexFDO

Authors S. Singh

Publication date 28 June 1992

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(92)90037-g

zbMATH Keywords

polynomial time algorithmquantifier free formulasentence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Decidability and field theory (12L05)

Recommendations

• Decidable fragments of field theories
• Decidable Sentences Over Polynomial Rings
• Sentences over integral domains and their computational complexities
• Fields of algebraic numbers computable in polynomial time. I

Cites work

• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3765914 (Why is no real title available?)
• An Inequality About Factors of Polynomials
• Complexity of Sentences over Number Rings
• Computational complexities of diophantine equations with parameters
• Decidable fragments of field theories
• Definability and decision problems in arithmetic
• Factoring Multivariate Polynomials over Algebraic Number Fields
• Factoring Polynomials over Algebraic Number Fields
• Factoring polynomials with rational coefficients
• Provability and Decidability of Arithmetical Universal-Existential Sentences
• Solvability by radicals is in polynomial time
• THE UNDECIDABILITY OF PURE TRANSCENDENTAL EXTENSIONS OF REAL FIELDS
• The Undecidability of Algebraic Rings and Fields

Cited in

(10)

• Polynomial computability of fields of algebraic numbers
• Algorithms for sentences over integral domains
• Computational complexity of sentences over fields
• Fields of algebraic numbers computable in polynomial time. II
• Polynomial-time presentations of algebraic number fields
• Computational complexity of arithmetical sentences
• Skolem functions of arithmetical sentences.
• A decision algorithm for linear sentences on a PFM
• Sentences over integral domains and their computational complexities
• Decidable Sentences Over Polynomial Rings

This page was built for publication: Polynomial time algorithms for sentences over number fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1187032)