Abstract:
There is no continuous function of the complex variable $a$, providing a solution of the equation $z^2=a$; there is no continuous function of two real variables $p,q$, providing a real solution of the equation $x^3 + px +q=0$, and there is no continuous function of three real variables $p,q,r$, providing a real solution of the equation from the 13th Hilbert problem, $x^7+px^3+qx^2+rx+1=0$. Therefore any arithmetic algorithms of approximate solution of these equations should include branchings (IF operators). The minimal necessary number of such operators is called the topological complexity of a computational problem.
For the above simplest examples this complexity is equal to 1, but how will it behave for general polynomial equations (or systems of equations) of higher degrees?
I will talk on the estimates of this complexity, based on the notion of the genus of a map (introduced by Albert Solomonovich Schwarz and rediscovered by Steve Smale in the context of the complexity theory), on homology of braid groups and theory of discriminants.