RUS  ENG
Full version
SEMINARS

Steklov Mathematical Institute Seminar
March 15, 2012 16:00, Moscow, Steklov Mathematical Institute of RAS, Conference Hall (8 Gubkina)


Topological complexity of approximate calculation of roots of polynomials

V. A. Vassiliev


http://youtu.be/wk44RCfnjMk

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.


© Steklov Math. Inst. of RAS, 2024