Complexity of Sentences over Number Rings

DOI10.1137/0220007zbMath0717.03002OpenAlexW2012827373MaRDI QIDQ3204439

No author found.

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 ringfactorization of polynomialsNP-completenesspolynomial timedecision problemarithmetical sentencessolvability of diophantine equations with parameters

Mathematics Subject Classification ID

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

Related Items (3)

Polynomial time algorithms for sentences over number fields ⋮ Decidable Sentences Over Polynomial Rings ⋮ Sentences over integral domains and their computational complexities

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