Richard Reckhow is a contemporary logician and theoretical computer scientist best known for foundational contributions to proof complexity. With Stephen Cook, he formalized the notion of a propositional proof system and initiated the systematic study of lower bounds on proof length, a field now central to computational complexity theory.
Co-authored the seminal 1979 Cook-Reckhow paper defining propositional proof systems
Introduced the polynomial simulation relation between proof systems
Established foundational connections between proof complexity and the NP vs coNP problem
Contributed to early research on lower bounds for resolution and Frege systems