RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
Forthcoming seminars
Seminar calendar
List of seminars
Archive by years
Register a seminar

Search
RSS
Forthcoming seminars





You may need the following programs to see the files








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 351.3 Mb

Number of views:
This page:1635
Video files:631
Youtube Video:

V. A. Vassiliev
Photo Gallery


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке



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.

SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2017