В наиболее известной его работе, написанной совместно со Стивеном Рудичем, он ввёл понятие о «естественных доказательствах», классе стратегий, используемых для доказательства фундаментальных нижних границ в определении вычислительной сложности. В частности, Разборов и Рудич показали, что, в предположении, что определённые виды односторонних функций существуют, такие доказательства не могут дать решение проблемы P = NP, поэтому для того, чтобы эту проблему решить, потребуется разработка новых методов доказательств.
Разборов, А. А. Нижние оценки монотонной сложности логического перманента (рус.) // Математические заметки Академии Наук СССР : журнал. — 1985. — Июнь (т. 37, № 6). — С. 485—493. — doi:10.1007/BF01157687.
Разборов, А. А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами (рус.) // Математические заметки Академии Наук СССР : журнал. — 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. {{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:10.1007/BF01240265.
Razborov, Alexander A. (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. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка); Неизвестный параметр |month= игнорируется (справка)
