How do we know that a problem is impossible to solve? In Until the Sun Engulfs the Earth, some of the world’s leading researchers and rising stars in the field of computational complexity play a memory game, find their way out of a maze, and explore an imagined landscape, as they make sense of the mathematics of proving the hardness of problems.
As part of the Simons Institute's effort to foster public understanding of algorithmic science, we are delighted to share this second film in our documentary web series, Theory Shorts.
Featuring Paul Beame (University of Washington), Faith Ellen (University of Toronto), Jelani Nelson (UC Berkeley), Manuel Sabin (UC Berkeley), and Madhu Sudan (Harvard University).
Directed by Anil Ananthaswamy and Kristin Kane.