THE LIVING ARCHIVE

From punched cards to autonomous collaborators: the ideas, people, languages and systems that taught machines to follow—and increasingly interpret—human intent.

PAST / PRESENT / NEXT

Collection

Tag: reductions

Stephen Cook, Leonid Levin, and the Discovery of NP-Completeness

Stephen Cook and Leonid Levin independently identified universal hard search problems, creating the foundation of NP-completeness and a new way to compare computational difficulty by reductions.

↗