On the number of sets definable by polynomials

We show that the known algorithms used to re-write any first order quantifier-free formula over an algebraically closed field into its normal disjunctive form are essentially optimal. This result follows from an estimate of the number of sets definable by equalities and inequalities of fixed polynom...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2000
Materias:
Algebraic complexity
Algorithms
Polynomial-definable sets
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00218693_v227_n2_p633_Jeronimo
http://hdl.handle.net/20.500.12110/paper_00218693_v227_n2_p633_Jeronimo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_00218693_v227_n2_p633_Jeronimo
record_format dspace
spelling paper:paper_00218693_v227_n2_p633_Jeronimo2023-06-08T14:42:19Z On the number of sets definable by polynomials Algebraic complexity Algorithms Polynomial-definable sets We show that the known algorithms used to re-write any first order quantifier-free formula over an algebraically closed field into its normal disjunctive form are essentially optimal. This result follows from an estimate of the number of sets definable by equalities and inequalities of fixed polynomials. Finally we apply our results to obtain similar estimates in the real case. © 2000 Academic Press. 2000 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00218693_v227_n2_p633_Jeronimo http://hdl.handle.net/20.500.12110/paper_00218693_v227_n2_p633_Jeronimo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Algebraic complexity
Algorithms
Polynomial-definable sets
spellingShingle Algebraic complexity
Algorithms
Polynomial-definable sets
On the number of sets definable by polynomials
topic_facet Algebraic complexity
Algorithms
Polynomial-definable sets
description We show that the known algorithms used to re-write any first order quantifier-free formula over an algebraically closed field into its normal disjunctive form are essentially optimal. This result follows from an estimate of the number of sets definable by equalities and inequalities of fixed polynomials. Finally we apply our results to obtain similar estimates in the real case. © 2000 Academic Press.
title On the number of sets definable by polynomials
title_short On the number of sets definable by polynomials
title_full On the number of sets definable by polynomials
title_fullStr On the number of sets definable by polynomials
title_full_unstemmed On the number of sets definable by polynomials
title_sort on the number of sets definable by polynomials
publishDate 2000
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00218693_v227_n2_p633_Jeronimo
http://hdl.handle.net/20.500.12110/paper_00218693_v227_n2_p633_Jeronimo
_version_ 1768544116888567808

Ejemplares similares