Sentences over integral domains and their computational complexities

DOI10.1006/inco.1998.2771zbMath0940.03015OpenAlexW1999144446MaRDI QIDQ1286369

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) Decidability and field theory (12L05) Model-theoretic algebra (03C60) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Hilbertian fields; Hilbert's irreducibility theorem (12E25) Model theory of fields (12L12)

Related Items (1)

Computational complexity of sentences over fields

Cites Work

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

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