abstract: Can we solve polynomial systems in polynomial time? This question received different answers in different contexts. The NP-hardness of deciding the feasibility of a general polynomial system does not preclude efficient algorithms for computing complex zeros of polynomial systems with as many equations as variables, on which the feasibility is granted under genericity hypotheses.
Smale's 17th problem is a clear-cut formulation of the problem in a numerical setting. We report on recent progress that gives a positive answer to a refinement of Smale's question for structured systems. Joint work with Felipe Cucker and Pierre Lairez: https:/arxiv.orgabs2010.10997