Sentences over integral domains and their computational complexities

DOI10.1006/INCO.1998.2771MaRDI QIDQ1286369zbMATH OpenOpenAlexFDO

Authors K. Appert

Publication date 3 July 2000

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

Full work available at URL https://doi.org/10.1006/inco.1998.2771

zbMATH Keywords

algebraic integer ringsarithmetical sentencesfraction fieldHilbert domainintegral domainquantifier free arithmetical formulatime complexities of decision problems on diophantine equations

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Model-theoretic algebra (03C60) Complexity of computation (including implicit computational complexity) (03D15) Hilbertian fields; Hilbert's irreducibility theorem (12E25) Decidability and field theory (12L05) Model theory of fields (12L12) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of Sentences over Number Rings
• Computational complexity of sentences over fields
• Algorithms for sentences over integral domains
• Computational complexities of diophantine equations with parameters
• Computational complexity of arithmetical sentences

Cites work

• ACHIEVEMENTS AND PROBLEMS IN DIOPHANTINE APPROXIMATION THEORY
• Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time
• Algorithms for sentences over integral domains
• Axiomatic characterization of fields by the product formula for valuations
• Classification of Quantifier Prefixes Over Diophantine Equations
• Complexity of Sentences over Number Rings
• Complexity of Subcases of Presburger Arithmetic
• Computational complexities of diophantine equations with parameters
• Computational complexity of arithmetical sentences
• Definability in number fields
• Der Hilbertsche Irreduzibilitätssatz.
• Dominoes and the complexity of subclasses of logical theories
• Effective Hilbert irreducibility
• Factoring multivariate integral polynomials
• Factoring Multivariate Polynomials over Algebraic Number Fields
• Factoring multivariate polynomials over finite fields
• Factoring Polynomials over Algebraic Number Fields
• Factoring Polynomials Over Algebraic Number Fields
• Factoring Polynomials Over Large Finite Fields
• Factoring polynomials with rational coefficients
• Factoring sparse multivariate polynomials
• Factorization of polynomials over a finite field and the solution of systems of algebraic equations
• Fast parallel absolute irreducibility testing
• scientific article; zbMATH DE number 4014840 (Why is no real title available?)
• scientific article; zbMATH DE number 3115157 (Why is no real title available?)
• scientific article; zbMATH DE number 3838204 (Why is no real title available?)
• scientific article; zbMATH DE number 3857212 (Why is no real title available?)
• scientific article; zbMATH DE number 3987272 (Why is no real title available?)
• scientific article; zbMATH DE number 3723860 (Why is no real title available?)
• scientific article; zbMATH DE number 3727583 (Why is no real title available?)
• scientific article; zbMATH DE number 3765914 (Why is no real title available?)
• scientific article; zbMATH DE number 66619 (Why is no real title available?)
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3230405 (Why is no real title available?)
• scientific article; zbMATH DE number 3304111 (Why is no real title available?)
• Irreducibility of multivariate polynomials
• Model theory.
• NP-complete decision problems for binary quadratics
• Polynomial time algorithms for sentences over number fields
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Presburger arithmetic with bounded quantifier alternation
• Prüfer domains and rings of integer-valued polynomials
• Solvability by radicals is in polynomial time
• Solving diophantine problems over all residue class fields of a number field and all finite fields
• Surjective polynomial maps, and a remark on the Jacobian problem
• The bounds of Skolem functions and their applications
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• The complexity of theorem-proving procedures
• The Distribution of Galois Groups and Hilbert's Irreducibility Theorem
• The polynomial-time hierarchy

Cited in

(11)

• Polynomial time algorithms for sentences over number fields
• Skolem functions of arithmetical sentences.
• Computational complexity of arithmetical sentences
• The bounds of Skolem functions and their applications
• Complexity of Sentences over Number Rings
• 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
• Computational complexity of sentences over fields

This page was built for publication: Sentences over integral domains and their computational complexities

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