The Hardness of Polynomial Equation Solving

D. Castro; M. Giusti; J. HeintzG. MateraL. M. Pardo

首页> 外文期刊>Foundations of computational mathematics >The Hardness of Polynomial Equation Solving

【24h】

The Hardness of Polynomial Equation Solving

机译：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 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.

著录项

来源
《Foundations of computational mathematics》 |2003年第4期|347-420|共74页
作者
D. Castro; M. Giusti; J. HeintzG. MateraL. M. Pardo;
展开▼
作者单位

Departamento de Ciencias de la Computacion, E.U. Politecnica, Universidad de Alcala, 28871 Alcala de Henares, Spain;

Laboratoire GAGE, Ecole Polytechnique, F-91128 Palaiseau Cedex, France;

Departamento de Matematicas, Estadistica y Computacion, Facultad de Ciencias, Universidad de Cantabria, E-39071 Santander, SpainInstituto de Desarrollo Humano, Universidad Nacional de General Sarmiento, Campus Universitario, Jose M. Gutierrez 1150 (1613) Los Polvorines, Pcia. de Buenos Aires, Argentina;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类应用数学;
关键词

The Hardness of Polynomial Equation Solving

摘要

著录项

相关主题

期刊订阅