Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming 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
Video records:
Flash Video 351.3 Mb
Flash Video 2,135.8 Mb
MP4 1,335.8 Mb

Number of views:
This page:2032
Video files:722
Youtube:

V. A. Vassiliev
Photo Gallery



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.
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024