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
Autores principales: Jeronimo, G., Sabia, J.
Formato: JOUR
Materias:
Algebraic complexity
Algorithms
Polynomial-definable sets
Acceso en línea: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 todo:paper_00218693_v227_n2_p633_Jeronimo
record_format dspace
spelling todo:paper_00218693_v227_n2_p633_Jeronimo2023-10-03T14:21:17Z On the number of sets definable by polynomials Jeronimo, G. Sabia, J. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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
Jeronimo, G.
Sabia, J.
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.
format JOUR
author Jeronimo, G.
Sabia, J.
author_facet Jeronimo, G.
Sabia, J.
author_sort Jeronimo, G.
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
url http://hdl.handle.net/20.500.12110/paper_00218693_v227_n2_p633_Jeronimo
work_keys_str_mv AT jeronimog onthenumberofsetsdefinablebypolynomials
AT sabiaj onthenumberofsetsdefinablebypolynomials
_version_ 1807322922414505984

Ejemplares similares