Complexity of quantifier elimination in the theory of algebraically closed fields | Zendy

A. L. Chistov | Zendy; D. Yu. Grigor'ev | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Complexity of quantifier elimination in the theory of algebraically closed fields

Author(s) -

A. L. Chistov,

D. Yu. Grigor'ev

Publication year - 2006

Publication title -

mathematical foundations of computer science

Language(s) - English

Resource type - Book series

ISBN - 3-540-13372-0

DOI - 10.1007/bfb0030287

Subject(s) - algebraically closed field , mathematics , quantifier elimination , quantifier (linguistics) , upper and lower bounds , combinatorics , polynomial , discrete mathematics , order (exchange) , computer science , mathematical analysis , finance , artificial intelligence , economics

An algorithm is described producing for each formula of the first order theory of algebraically closed fields an equivalent free of quantifiers one. Denote by N a number of polynomials occuring in the formula, by d an upper bound on the degrees of polynomials, by n a number of variables, by a a number of quantifier alternations (in the prefix form). Then the algorithm works within the polynomial in the formula's size and in (Nd)n(2a+2) time. Up to now a bound (Nd)no(n) was known ([5], [7], [15]).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research