requirements in 1972.

He and Stephen Cook independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook-Levin theorem, was a basis for one of the seven Millennium Prize Problems declared by the Clay Mathematics Institute