THE COMPLEXITY OF THE DECISION PROBLEM FOR THE FIRST ORDER THEORY OF ALGEBRAICALLY CLOSED FIELDS

DOI10.1070/IM1987v029n02ABEH000979zbMath0631.03006OpenAlexW1979600155MaRDI QIDQ3767321

Dima Yu. Grigoriev

Publication date: 1987

Published in: Mathematics of the USSR-Izvestiya (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1070/im1987v029n02abeh000979

zbMATH Keywords

polynomial complexityalgorithm for quantifier eliminationfirst order theory of algebraically closed fields

Mathematics Subject Classification ID

Polynomials in real and complex fields: factorization (12D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (3)

On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals ⋮ Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields ⋮ An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs

This page was built for publication: THE COMPLEXITY OF THE DECISION PROBLEM FOR THE FIRST ORDER THEORY OF ALGEBRAICALLY CLOSED FIELDS