About this episode
Aside from victory questions like "can black force a checkmate on white in 5 moves?" many novel questions can be asked about a game of chess. Some questions are trivial (e.g. "How many pieces does white have?") while more computationally challenging questions can contribute interesting results in computational complexity theory.
In this episode, Josh Brunner, Master's student in Theoretical Computer Science at MIT, joins us to discuss his recent paper Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard.
Works Mentioned
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
by Josh Brunner, Erik D. Demaine, Dylan Hendrickson, and Juilian Wellman
1x1 Rush Hour With Fixed Blocks is PSPACE Complete
by Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff
Get every episode summarized
Each time Data Skeptic publishes, we email you a written briefing from the transcript — the topics, who appeared, and any specific claims, with the ad reads skipped.
Email me new episodesFree for 3 shows. No card needed.
Hosts & guests
No transcript yet
This episode has not been transcribed. Request it and it moves to the front of the queue.
More episodes
