We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Complexity of Polynomial System Solving

Formal Metadata

Title
Complexity of Polynomial System Solving
Title of Series
Number of Parts
20
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
Analysis of condition number for random matrices originated in the works of von Neumann and Turing on complexity of linear system solving. For the case of non-linear algebraic equations (i.e. polynomials), there are two decoupling facts: feasibility of a system of equations over the complex numbers is NP-Hard, and a generic system of polynomials always has the same number of roots (i.e. Bezout number or BKK bound). These facts led to the search for algorithms that solves a generic polynomial system fast, and a notion of condition number arose naturally. The analysis of condition number for random polynomial systems thus became the central ingredient for understanding complexity of polynomial system solving. We present a rather quick survey on condition number analysis over complex numbers (i.e., a survey on the solution of Smale's 17th problem), then pass to the field of real numbers. We hope to finish by presenting our results on condition number analysis of random real polynomial systems. This is joint work with J. Maurice Rojas and Grigoris Paouris.