  RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  Ближайшие семинары Календарь семинаров Список семинаров Архив по годам Регистрация семинара Поиск RSS Ближайшие семинары

Семинар «Глобус» (записи с 2011 года)
28 ноября 2013 г. 15:40, г. Москва, конференц-зал НМУ (Москва, Большой Власьевский пер., 11)  The power and limitations of probabilistic algorithms in constructive mathematics

L. Bienvenu

Laboratoire J.-V. Poncelet, Independent University of Moscow
 Видеозаписи: Flash Video 474.2 Mb Flash Video 339.6 Mb MP4 339.6 Mb MP4 474.2 Mb

 Количество просмотров: Эта страница: 191 Видеофайлы: 42  Видео не загружается в Ваш браузер: Активируйте JavaScript в Вашем браузере Установите Adobe Flash Player Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080 Сообщите администратору портала о данной ошибке

Аннотация: Many mathematical theorems are of the following form: "For all X, there exists Y such that P(X,Y)", where X and Y are infinite objects, and P is some relation. Think for example of the Bolzano-Weierstrass theorem: for every sequence X of reals in [0,1], there exists a converging subsequence Y of X". Or Ramsey"s theorem for pairs: for every coloring X of pairs of integers, where each pair is either colored blue or red, there exists an infinite set Y of integers such that all pairs inside Y are colored with the same color. How constructive are such theorems?
One way to understand this question is from a computability theory viewpoint:for each such theorem, is there an algorithm which given some X (say, encoded as an infinite sequence of 0"s and 1"s), produces some Y (again, in some encoded form) such that P(X,Y)? The answer is often negative, but some theorems present an interesting phenomenon: namely, there are theorems for which there is no deterministic algorithm to generate a Y, but for which there is a *probabilistic* algorithm to produce a Y with high probability. A very interesting example is the Baire Category Theorem (properly formulated), for which we will give an explicit probabilistic algorithm. I will also discuss the case of Ramsey-type theorems. Some do admit a probabilistic algorithm (like the Rainbow Ramsey theorem), while some others provably don"t (like the Erdös-Moser theorem). Proving that no probabilistic algorithm exists for a particular theorem can be significantly more difficult than proving that there exists no deterministic one. If time permits, I will present the techniques to obtain such negative results.

 ОТПРАВИТЬ:       Обратная связь: math-net2020_05 [at] mi-ras ru Пользовательское соглашение Регистрация Логотипы © Математический институт им. В. А. Стеклова РАН, 2020