In his best known work, joint with Steven Rudich, he introduced the notion of natural proofs, a class of strategies used to prove fundamental lower bounds in computational complexity. In particular, Razborov and Rudich showed that, under the assumption that certain kinds of one-way functions exist, such proofs cannot give a resolution of the P = NP problem, so new techniques will be required in order to solve this question.
Razborov, A. A. (April 1987). "Lower bounds on the size of bounded depth circuits over a complete basis with logical addition". Mathematical Notes of the Academy of Sciences of the USSR41 (4): 333–338. doi:10.1007/BF01137685.
Razborov, A. A. (December 1990). "Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits". Mathematical Notes of the Academy of Sciences of the USSR48 (6): 1226–1234. doi:10.1007/BF01240265.