Александр Александрович Разборов (родился 16 февраля 1963 года в Белово Кемеровской обл.) — российский и советский учёный-математик, член-корреспондент РАН (с 2000 года), специалист в области теории вычислений. Имеет число Эрдёша, равное 2.
Биография
Выпускник московской физико-математической школы №2 (1980). Окончил механико-математический факультет МГУ (1987). Кандидат физико-математических наук (1987). Доктор физико-математических наук (1991).
Работает в Университете Чикаго (США) и в Математическом институте им. В. А. Стеклова РАН.
26 мая 2000 года избран членом-корреспондентом РАН по Отделению математических наук.
Научные результаты
В наиболее известной его работе, написанной совместно со Стивеном Рудичем, он ввёл понятие о «естественных доказательствах», классе стратегий, используемых для доказательства фундаментальных нижних границ в определении вычислительной сложности. В частности, Разборов и Рудич показали, что, в предположении, что определённые виды односторонних функций существуют, такие доказательства не могут дать решение проблемы P = NP, поэтому для того, чтобы эту проблему решить, потребуется разработка новых методов доказательств.
Награды и премии
- Золотая медаль Международной математической олимпиады в Лондоне (1979).
- Премия Неванлинны (1990) за «новый приближённый метод решения алгоритмических проблем»
- Премия Гёделя (2007) (совместно со Стивеном Рудичем) за работу о «естественных доказательствах».
- Заслуженный профессор (2008) факультета компьютерных наук им. Эндрю МакЛейша в Чикагском университете, США.
Библиография
- Разборов, А. А. (1985). «Lower bounds for the monotone complexity of some Boolean functions» (PDF). Доклады Академии наук 31: 354–357.
- Разборов, А. А. (Июнь 1985). «Нижние оценки монотонной сложности логического перманента» (PDF). Математические заметки Академии Наук СССР 37 (6): 485–493. DOI:10.1007/BF01157687.
- Разборов Александр Александрович. О системах уравнений в свободной группе. — Московский государственный университет, 1987. (Кандидатская диссертация. 32.56MB)
- Разборов, А. А. (Апрель 1987). «Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами» (PDF). Математические заметки Академии Наук СССР 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: 167–176. DOI:10.1145/73007.73023.
- Razborov, A. A. (December 1990). «Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits» (PDF). Mathematical Notes of the Academy of Sciences of the USSR 48 (6): 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: 204–213. DOI:10.1145/195058.195134.
- Razborov, Alexander A. (December 1998). «Lower Bounds for the Polynomial Calculus» (PostScript). Computational Complexity 7 (4): 291–324. DOI:10.1007/s000370050013.
- Razborov, Alexander A. (January 2003). «Propositional proof complexity» (PostScript). Journal of the ACM 50 (1): 80–82. DOI:10.1145/602382.602406. (Survey paper for JACM’s 50th anniversary)
- Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.
