Алексей Разборов¶

Алексей Разборов — российский математик, специалист в области математической логики, теории сложности вычислений и комбинаторики. Доктор физико-математических наук, профессор, лауреат премий имени Делиня (2018) и имени Лобачевского (2021). Известен прежде всего доказательством экспоненциальных нижних оценок для схемной сложности булевых функций и работами по теории доказательств, которые заложили основы современной области — алгебраической сложности доказательств.

¶Биография

Алексей Александрович Разборов родился в 1963 году в Москве. В 1985 году окончил механико-математический факультет Московского государственного университета имени М. В. Ломоносова. В 1989 году под руководством Сергея Адянца защитил кандидатскую диссертацию по математической логике в Математическом институте имени В. А. Стеклова АН СССР. В 1992 году защитил докторскую диссертацию.

С 1988 по 2000 годы работал в Математическом институте имени В. А. Стеклова, где прошёл путь от стажёра-исследователя до ведущего научного сотрудника. В начале 1990-х годов стажировался в США, в том числе в Принстонском университете и Институте перспективных исследований. С 2000 года работает в США: занимал должности профессора в Чикагском университете и Массачусетском технологическом институте, с 2008 года является профессором Оксфордского университета (Великобритания). Одновременно продолжает поддерживать связи с российскими научными школами, регулярно публикуясь в российских журналах и участвуя в конференциях.

¶Научные достижения

¶Нижние оценки для схемной сложности

Главным результатом Разборова считается доказательство в 1987 году экспоненциальной нижней оценки размера булевых схем с ограниченной глубиной (класс AC⁰) для вычисления функции паритета. Эта работа, опубликованная в 1989 году, решила проблему, открытую в 1980-х годах, и продемонстрировала, что схемы с постоянной глубиной и неограниченным ветвлением не способны вычислять простые на вид функции. Доказательство Разборова использовало метод приближённых полиномов и комбинаторный аппарат, который впоследствии стал стандартным инструментом в теории сложности.

¶Алгебраические методы в теории доказательств

В 1990-е годы Разборов совместно с Александром Храпченко разработал метод алгебраических нижних оценок для систем доказательств. Они доказали экспоненциальные нижние оценки для исчисления секвенций с ограниченной глубиной (система LK с ограничением на глубину формул), что стало одним из первых существенных результатов в области пропозициональных доказательств после знаменитой теоремы Хакена о системе с резолюциями. Эти работы установили связь между сложностью булевых функций и сложностью поиска доказательств, открыв направление алгебраической сложности доказательств.

¶Теорема Разборова — Рудича

В 1994 году совместно с Стивеном Рудичем Разборов доказал, что функция паритета не может быть вычислена схемами с постоянной глубиной даже при использовании дополнительных логических элементов, если схема имеет ограниченный размер. Теорема Разборова — Рудича усилила ранние результаты и стала важной вехой в понимании пределов параллельных вычислений.

¶Работы по комбинаторике и теории графов

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

¶Признание

В 2018 году Разборов стал лауреатом премии имени Поля Делиня, присуждаемой Европейским математическим обществом за выдающиеся достижения в математике. В 2021 году Казанский федеральный университет присудил ему премию имени Н. И. Лобачевского за цикл работ по теории сложности вычислений и теории доказательств. В 2022 году был избран членом Лондонского королевского общества — одной из старейших и наиболее престижных научных академий мира.

¶Основные публикации

• Razborov A. A. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition // Mathematical Notes. — 1987. — Vol. 41, no. 4. — P. 333–338.
• Razborov A. A. Lower bounds for the size of circuits of bounded depth with basis {∧, ⊕} // Mathematical Notes. — 1987. — Vol. 41, no. 4. — P. 333–338.
• Razborov A. A. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition // Mathematical Notes. — 1987. — Vol. 41, no. 4. — P. 333–338.
• Razborov A. A. On the distributional complexity of disjointness // Theoretical Computer Science. — 1992. — Vol. 106, no. 2. — P. 385–390.
• Razborov A. A., Rudich S. Natural proofs // Journal of Computer and System Sciences. — 1997. — Vol. 55, no. 1. — P. 24–35.
• Razborov A. A. Lower bounds for the polynomial calculus // Computational Complexity. — 1998. — Vol. 7, no. 4. — P. 291–324.

¶См. также

• Теория сложности вычислений
• Булевы схемы
• Проблема P versus NP