Computational complexity of sentences over fields

DOI10.1016/J.IC.2008.04.001MaRDI QIDQ937294zbMATH OpenOpenAlexFDO

Authors 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

arithmetical sentencescomputational complexityfields

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Sentences over integral domains and their computational complexities
• On complexity of the existential and universal theories of finite fields
• Polynomial time algorithms for sentences over number fields
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• The complexity of linear problems in fields

Cites work

• Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time
• Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
• Computational complexities of diophantine equations with parameters
• Computational complexity of arithmetical sentences
• Decidable fragments of field theories
• Definability and decision problems in arithmetic
• Diophantine Problems Over Local Fields I
• Diophantine problems over local fields. III: Decidable fields
• Effective Hilbert irreducibility
• Factoring integers with elliptic curves
• Factoring Multivariate Polynomials over Algebraic Number Fields
• Factoring multivariate polynomials over finite fields
• Factoring Polynomials over Algebraic Number 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
• Generalized riemann hypothesis and factoring polynomials over finite fields
• scientific article; zbMATH DE number 4014840 (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 4077312 (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 3465382 (Why is no real title available?)
• scientific article; zbMATH DE number 1305293 (Why is no real title available?)
• scientific article; zbMATH DE number 1305294 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 3804835 (Why is no real title available?)
• scientific article; zbMATH DE number 3445421 (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 3243872 (Why is no real title available?)
• scientific article; zbMATH DE number 3304881 (Why is no real title available?)
• scientific article; zbMATH DE number 3053259 (Why is no real title available?)
• Irreducibility of multivariate polynomials
• Metamathematical Considerations On The Relative Irreducibility Of Polynomials
• On definable subsets of p-adic fields
• Polynomial time algorithms for sentences over number fields
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Provability and Decidability of Arithmetical Universal-Existential Sentences
• Sentences over integral domains and their computational complexities
• Solvability by radicals is in polynomial time
• Solving diophantine problems over all residue class fields of a number field and all finite fields
• The elementary theory of finite fields
• The Undecidability of Algebraic Rings and Fields
• THE UNDECIDABILITY OF PURE TRANSCENDENTAL EXTENSIONS OF REAL FIELDS

Cited in

(4)

• Sentences over integral domains and their computational complexities
• Complexity of Sentences over Number Rings
• On complexity of the existential and universal theories of finite fields
• Algorithms for sentences over integral domains

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

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