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

integral domainarithmetical sentencesfraction fieldalgebraic integer ringsHilbert domainquantifier free arithmetical formulatime complexities of decision problems on diophantine equations

Mathematics Subject Classification ID

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

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

• 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?)
• 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 Polynomials over Algebraic Number Fields
• Factoring Polynomials Over Algebraic Number Fields
• Factoring Polynomials Over Large Finite Fields
• Factoring Polynomials over Algebraic Number Fields
• Factoring multivariate integral polynomials
• Factoring multivariate polynomials over 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
• 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 Distribution of Galois Groups and Hilbert's Irreducibility Theorem
• 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 polynomial-time hierarchy

Cited in

(10)

• Algorithms for sentences over integral domains
• Computational complexity of sentences over fields
• Computational complexities of diophantine equations with parameters
• Computational complexity of arithmetical sentences
• Skolem functions of arithmetical sentences.
• Decidable Sentences Over Polynomial Rings
• Complexity of Sentences over Number Rings
• Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
• The bounds of Skolem functions and their applications
• Complexity of Scott sentences

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)