The hardness of polynomial equation solving
Elimination theory was at the origin of algebraic geometry in the nineteenth century and now deals with the algorithmic solving of multivariate polynomial equation systems over the complex numbers or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intr...
Guardado en:
| Autor principal: | |
|---|---|
| Publicado: |
2003
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v3_n4_p347_Castro http://hdl.handle.net/20.500.12110/paper_16153375_v3_n4_p347_Castro |
| Aporte de: |
| id |
paper:paper_16153375_v3_n4_p347_Castro |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_16153375_v3_n4_p347_Castro2023-06-08T16:25:23Z The hardness of polynomial equation solving Matera, Guillermo Complexity Continuous data structure Elimination theory Holomorphic and continuous encoding Polynomial equation solving Arithmetic circuits Bezout number Elimination theory Geometric objects Algebra Algorithms Computational complexity Data structures Digital arithmetic Encoding (symbols) Geometry Graph theory Problem solving Topology Polynomials Elimination theory was at the origin of algebraic geometry in the nineteenth century and now deals with the algorithmic solving of multivariate polynomial equation systems over the complex numbers or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intrinsic sequential time complexity of universal elimination procedures for arbitrary continuous data structures encoding input and output objects of elimination theory (i.e., polynomial equation systems) and admitting the representation of certain limit objects. Our main result is the following: let there be given such a data structure and together with this data structure a universal elimination algorithm, say P, solving arbitrary parametric polynomial equation systems. Suppose that the algorithm P avoids "unnecessary" branchings and that P admits the efficient computation of certain natural limit objects (as, e.g., the Zariski closure of a given constructible algebraic set or the parametric greatest common divisor of two given algebraic families of univariate polynomials). Then P cannot be a polynomial time algorithm. The paper contains different variants of this result and discusses their practical implications. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2003 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v3_n4_p347_Castro http://hdl.handle.net/20.500.12110/paper_16153375_v3_n4_p347_Castro |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Complexity Continuous data structure Elimination theory Holomorphic and continuous encoding Polynomial equation solving Arithmetic circuits Bezout number Elimination theory Geometric objects Algebra Algorithms Computational complexity Data structures Digital arithmetic Encoding (symbols) Geometry Graph theory Problem solving Topology Polynomials |
| spellingShingle |
Complexity Continuous data structure Elimination theory Holomorphic and continuous encoding Polynomial equation solving Arithmetic circuits Bezout number Elimination theory Geometric objects Algebra Algorithms Computational complexity Data structures Digital arithmetic Encoding (symbols) Geometry Graph theory Problem solving Topology Polynomials Matera, Guillermo The hardness of polynomial equation solving |
| topic_facet |
Complexity Continuous data structure Elimination theory Holomorphic and continuous encoding Polynomial equation solving Arithmetic circuits Bezout number Elimination theory Geometric objects Algebra Algorithms Computational complexity Data structures Digital arithmetic Encoding (symbols) Geometry Graph theory Problem solving Topology Polynomials |
| description |
Elimination theory was at the origin of algebraic geometry in the nineteenth century and now deals with the algorithmic solving of multivariate polynomial equation systems over the complex numbers or, more generally, over an arbitrary algebraically closed field. In this paper we investigate the intrinsic sequential time complexity of universal elimination procedures for arbitrary continuous data structures encoding input and output objects of elimination theory (i.e., polynomial equation systems) and admitting the representation of certain limit objects. Our main result is the following: let there be given such a data structure and together with this data structure a universal elimination algorithm, say P, solving arbitrary parametric polynomial equation systems. Suppose that the algorithm P avoids "unnecessary" branchings and that P admits the efficient computation of certain natural limit objects (as, e.g., the Zariski closure of a given constructible algebraic set or the parametric greatest common divisor of two given algebraic families of univariate polynomials). Then P cannot be a polynomial time algorithm. The paper contains different variants of this result and discusses their practical implications. |
| author |
Matera, Guillermo |
| author_facet |
Matera, Guillermo |
| author_sort |
Matera, Guillermo |
| title |
The hardness of polynomial equation solving |
| title_short |
The hardness of polynomial equation solving |
| title_full |
The hardness of polynomial equation solving |
| title_fullStr |
The hardness of polynomial equation solving |
| title_full_unstemmed |
The hardness of polynomial equation solving |
| title_sort |
hardness of polynomial equation solving |
| publishDate |
2003 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v3_n4_p347_Castro http://hdl.handle.net/20.500.12110/paper_16153375_v3_n4_p347_Castro |
| work_keys_str_mv |
AT materaguillermo thehardnessofpolynomialequationsolving AT materaguillermo hardnessofpolynomialequationsolving |
| _version_ |
1768542474563747840 |