Nationality USA, Russia | Role Mathematician Name Alexander Razborov | |
 | ||
Institutions University of Chicago, Steklov Mathematical Institute, Toyota Technological Institute at Chicago Awards Nevanlinna Prize, Godel Prize | ||
Education Moscow State University | ||
Alexander razborov on a combinatorial approach to the hirsch conjecture
Aleksandr Aleksandrovich Razborov (Russian: Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist.
Contents
- Alexander razborov on a combinatorial approach to the hirsch conjecture
- Propositional proof complexity fifteen or so years after alexander razborov
- Research
- Awards
- References
Propositional proof complexity fifteen or so years after alexander razborov
Research
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.
Awards
References
Alexander Razborov Wikipedia(Text) CC BY-SA