Computational complexity of sentences over fields

DOI10.1016/J.IC.2008.04.001zbMath1154.68434OpenAlexW2088407853MaRDI QIDQ937294

B. E. Eshmatov

Publication date: 14 August 2008

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

Full work available at URL: https://doi.org/10.1016/j.ic.2008.04.001

zbMATH Keywords

fieldscomputational complexityarithmetical sentences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Factoring integers with elliptic curves
• Factoring polynomials with rational coefficients
• Polynomial time algorithms for sentences over number fields
• Solving diophantine problems over all residue class fields of a number field and all finite fields
• Sentences over integral domains and their computational complexities
• Computational complexity of arithmetical sentences
• The elementary theory of finite fields
• Diophantine problems over local fields. III: Decidable fields
• Metamathematical Considerations On The Relative Irreducibility Of Polynomials
• The Undecidability of Algebraic Rings and Fields
• Generalized riemann hypothesis and factoring polynomials over finite fields
• Factoring Polynomials over Algebraic Number Fields
• Effective Hilbert irreducibility
• Provability and Decidability of Arithmetical Universal-Existential Sentences
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Factoring Multivariate Polynomials over Algebraic Number Fields
• Computational complexities of diophantine equations with parameters
• On definable subsets of p-adic fields
• Decidable fragments of field theories
• Diophantine Problems Over Local Fields I
• THE UNDECIDABILITY OF PURE TRANSCENDENTAL EXTENSIONS OF REAL FIELDS
• Definability and decision problems in arithmetic
• Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy

This page was built for publication: Computational complexity of sentences over fields