Разборов, Александр Александрович

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Александр Александрович Разборов
Александр Разборов.jpg
Дата рождения 16 февраля 1963(1963-02-16) (59 лет)
Место рождения
Страна  Россия
 США
Научная сфера математик
Место работы Математический институт им. В. А. Стеклова РАН, Чикагский университет
Альма-матер МГУ (мехмат)
Научный руководитель С. И. Адян
Награды и премии Премия Неванлинны (1990)
Премия Гёделя (2007)
Сайт people.cs.uchicago.edu/~…

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

Биография[править | править код]

Выпускник московской физико-математической школы № 2 (1980). Окончил механико-математический факультет МГУ (1987). Кандидат физико-математических наук (1987). Доктор физико-математических наук (1991). С 1991 по 2008 год работал в Математическом институте им. В. А. Стеклова РАН. В 2001—2006 году — постоянный член Института перспективных исследований Принстонского университета[3].

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

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

Научные результаты[править | править код]

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

Награды и премии[править | править код]

Библиография[править | править код]

  • Разборов, А. А. Lower bounds for the monotone complexity of some Boolean functions (англ.) // Доклады Академии наук : journal. — 1985. — Vol. 31. — P. 354—357.
  • Разборов, А. А. Нижние оценки монотонной сложности логического перманента // Математические заметки Академии Наук СССР : журнал. — 1985. — Июнь (т. 37, № 6). — С. 485—493. — doi:10.1007/BF01157687.
  • Разборов, Александр Александрович. О системах уравнений в свободной группе. — Московский государственный университет, 1987. (Кандидатская диссертация. 32.56MB)
  • Разборов, А. А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами // Математические заметки Академии Наук СССР : журнал. — 1987. — Апрель (т. 41, № 4). — С. 333—338. — doi:10.1007/BF01137685.
  • Razborov, Alexander A. (1989). “On the method of approximations” (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:10.1145/73007.73023. Используется устаревший параметр |month= (справка); Неизвестный параметр |Month= (предлагается |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:10.1007/BF01240265.
  • Razborov, Alexander A.; Rudich, Stephen (May 1994). “Natural proofs” (PostScript). Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. Montreal, Quebec, Canada. pp. 204—213. DOI:10.1145/195058.195134. Используется устаревший параметр |month= (справка)
  • Razborov, Alexander A. Lower Bounds for the Polynomial Calculus (неопр.) // Computational Complexity. — 1998. — December (т. 7, № 4). — С. 291—324. — doi:10.1007/s000370050013.
  • Razborov, Alexander A. Propositional proof complexity (англ.) // Journal of the ACM : journal. — 2003. — January (vol. 50, no. 1). — P. 80—82. — doi:10.1145/602382.602406. (Survey paper for JACM’s 50th anniversary)
  • Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.

См. также[править | править код]

Примечания[править | править код]

  1. Разборов А.А. - Общая информация. Дата обращения: 3 января 2013. Архивировано 24 августа 2017 года.
  2. List of people with Erdős number 2. Дата обращения: 14 ноября 2011. Архивировано 19 апреля 2019 года.
  3. Computer Science and Discrete Mathematics (CSDM). Дата обращения: 22 марта 2021. Архивировано 23 марта 2021 года.
  4. Curriculum Vitae. Дата обращения: 22 марта 2021. Архивировано 31 октября 2021 года.
  5. Department of Computer Science. Дата обращения: 12 ноября 2013. Архивировано 25 августа 2013 года.
  6. International Mathematical Union: Rolf Nevanlinna Prize Winners (недоступная ссылка). Дата обращения: 14 ноября 2011. Архивировано 18 октября 2007 года.
  7. 2007 Godel Prize (недоступная ссылка). Дата обращения: 12 апреля 2018. Архивировано 3 марта 2016 года.
  8. Gödel Prize — 2007. Дата обращения: 12 апреля 2018. Архивировано 12 апреля 2018 года.

Ссылки[править | править код]