Алекса́ндр Алекса́ндрович Разбо́ров (род. 16 февраля 1963 года, Белово, Кемеровская область) — российский и американский математик, член-корреспондент РАН (с 2000 года), специалист в области теории вычислений. Имеет число Эрдёша, равное 2.
Биография Выпускник московской физико-математической школы № 2 (1980). Окончил механико-математический факультет МГУ (1987). Кандидат физико-математических наук (1987, диссертация «О системах уравнений в свободной группе»). 4 апреля 1991 года защитил докторскую диссертацию «Нижние оценки сложности вычисления булевых функций» (официальные оппоненты А. Е. Андреев, А. А. Карацуба, А. О. Слисенко).
С 1991 по 2008 год работал в Математическом институте им. В. А. Стеклова РАН. В 2001—2006 годах — постоянный член Института перспективных исследований Принстонского университета.
С 2008 года — заслуженный профессор в Университете Чикаго (США).
26 мая 2000 года избран членом-корреспондентом РАН по Отделению математических наук.
Научные результаты В наиболее известной его работе, написанной совместно со Стивеном Рудичем, он ввёл понятие о «естественных доказательствах», классе стратегий, используемых для доказательства фундаментальных нижних границ в определении вычислительной сложности. В частности, Разборов и Рудич показали, что, в предположении, что определённые виды односторонних функций существуют, такие доказательства не могут дать решение проблемы P = NP, поэтому для того, чтобы эту проблему решить, потребуется разработка новых методов доказательств.
Награды и премии Золотая медаль Международной математической олимпиады в Лондоне (1979). Премия Неванлинны (1990) за «новый приближённый метод решения алгоритмических проблем» Премия Гёделя (2007) (совместно со Стивеном Рудичем) за работу о «естественных доказательствах». Заслуженный профессор (2008) факультета компьютерных наук им. Эндрю МакЛейша в Чикагском университете, США.
Библиография
(Кандидатская диссертация. 32.56MB)
(Survey paper for JACM’s 50th anniversary)
См. также Свободная группа Односторонняя функция Правило резолюций
Примечания
Ссылки
Разборов Александр Александрович на сайте Всероссийского математического портала Персональная страница А. А. Разборова Biography sketch in the Toyota Technological Institute at Chicago. Curricula Vitae at the Department of Computer Science, University of Chicago. DBLP: Alexander A. Razborov. The Work of A.A. Razborov — an article by László Lovász in the Proceedings of the International Congress of Mathematicians, Kyoto, Japan, 1990.
Категория:Математики США Категория:Лауреаты премии Гёделя Категория:Члены-корреспонденты РАН Категория:Победители Всесоюзной олимпиады школьников по математике Категория:Сотрудники МИАН Категория:Преподаватели Принстонского университета Категория:Преподаватели Чикагского университета Категория:Выпускники 2-й физико-математической школы Категория:Лауреаты премии Дэвида Роббинса Категория:Лауреаты премии Неванлинны Категория:Члены Европейской академии Категория:Победители Международной математической олимпиады