Алекса́ндр Алекса́ндрович Разбо́ров (род. 16 февраля 1963 года , Белово , Кемеровская область ) — российский и американский математик , член-корреспондент РАН (с 2000 года) , специалист в области теории вычислений . Имеет число Эрдёша , равное 2.

Биография

Выпускник московской физико-математической школы № 2 (1980). Окончил механико-математический факультет МГУ (1987). Кандидат физико-математических наук (1987, диссертация «О системах уравнений в свободной группе»). 4 апреля 1991 года защитил докторскую диссертацию «Нижние оценки сложности вычисления булевых функций» (официальные оппоненты А. Е. Андреев , А. А. Карацуба , А. О. Слисенко ) .

С 1991 по 2008 год работал в Математическом институте им. В. А. Стеклова РАН . В 2001—2006 годах — постоянный член Института перспективных исследований Принстонского университета .

С 2008 года — заслуженный профессор в Университете Чикаго (США) .

26 мая 2000 года избран членом-корреспондентом РАН по Отделению математических наук .

Научные результаты

В наиболее известной его работе, написанной совместно со Стивеном Рудичем, он ввёл понятие о «естественных доказательствах» , классе стратегий, используемых для доказательства фундаментальных нижних границ в определении вычислительной сложности . В частности, Разборов и Рудич показали, что, в предположении, что определённые виды односторонних функций существуют, такие доказательства не могут дать решение проблемы P = NP , поэтому для того, чтобы эту проблему решить, потребуется разработка новых методов доказательств.

Награды и премии

• Золотая медаль Международной математической олимпиады в Лондоне (1979).
• Премия Неванлинны (1990) за «новый приближённый метод решения алгоритмических проблем»
• Премия Гёделя (2007) (совместно со Стивеном Рудичем) за работу о «естественных доказательствах».
• Заслуженный профессор (2008) факультета компьютерных наук им. Эндрю МакЛейша в Чикагском университете , США.

Библиография

• Разборов, А. А. (англ.) // Доклады Академии наук : journal. — 1985. — Vol. 31 . — P. 354—357 .
• Разборов, А. А. Нижние оценки монотонной сложности логического перманента (рус.) // Математические заметки Академии Наук СССР : журнал. — 1985. — Июнь ( т. 37 , № 6 ). — С. 485—493 . — doi : .
• Разборов, Александр Александрович. (рус.) . — Московский государственный университет , 1987. (Кандидатская диссертация. 32.56MB)
• Разборов, А. А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами (рус.) // Математические заметки Академии Наук СССР : журнал. — 1987. — Апрель ( т. 41 , № 4 ). — С. 333—338 . — doi : .
• Razborov, Alexander A. (1989). (PDF. 1.41MB ) . Proceedings of the 21st Annual ACM Symposium on the Theory of Computing . Seattle, Washington (U.S. state), United States. pp. 167—176. doi : . {{ cite conference }} : Неизвестный параметр |Month= игнорируется ( справка )
• Razborov, A. A. Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits (англ.) // Mathematical Notes : journal. — 1990. — December ( vol. 48 , no. 6 ). — P. 1226—1234 . — doi : .
• Razborov, Alexander A. (1994). (PostScript) . Proceedings of the 26th Annual ACM Symposium on the Theory of Computing . Montreal, Quebec, Canada. pp. 204—213. doi : . {{ cite conference }} : Неизвестный параметр |coauthors= игнорируется ( |author= предлагается) ( справка ) ; Неизвестный параметр |month= игнорируется ( справка )
• Razborov, Alexander A. (неопр.) // Computational Complexity. — 1998. — December ( т. 7 , № 4 ). — С. 291—324 . — doi : .
• Razborov, Alexander A. (англ.) // Journal of the ACM : journal. — 2003. — January ( vol. 50 , no. 1 ). — P. 80—82 . — doi : . (Survey paper for JACM’s 50th anniversary)
• Разборов А. А. Алгебраическая сложность. — М. : МЦНМО , 2016. — 32 с. — ISBN 978-5-4439-1032-1 .

См. также

• Свободная группа
• Односторонняя функция
• Правило резолюций

Примечания

Ссылки

• на официальном сайте РАН
• на сайте Всероссийского математического портала
• in the Toyota Technological Institute at Chicago.
• at the Department of Computer Science, University of Chicago.
• .
• — an article by László Lovász in the Proceedings of the International Congress of Mathematicians , Kyoto, Japan, 1990.