Complexity of Sentences over Number Rings

DOI10.1137/0220007MaRDI QIDQ3204439zbMATH OpenOpenAlexFDO

Authors

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220007

zbMATH Keywords

algebraic integer ringarithmetical sentencesdecision problemfactorization of polynomialsNP-completenesspolynomial timesolvability of diophantine equations with parameters

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Diophantine equations (11D99) Algebraic numbers; rings of algebraic integers (11R04) Decidability (number-theoretic aspects) (11U05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Sentences over integral domains and their computational complexities
• Computational complexity of sentences over fields
• Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
• Computational complexity of arithmetical sentences
• scientific article; zbMATH DE number 4114007

Cited in

(10)

• Polynomial time algorithms for sentences over number fields
• Sentences over integral domains and their computational complexities
• Computational complexity of arithmetical sentences
• Diophantine hierarchy
• On the complexity of Diophantine geometry in low dimensions (extended abstract)
• Computational complexities of diophantine equations with parameters
• Decidable Sentences Over Polynomial Rings
• Complexity of Scott sentences
• Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
• Algorithms for sentences over integral domains

This page was built for publication: Complexity of Sentences over Number Rings

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