Karp Plays a Game

Saturday, Oct. 17, 2015 9:30 am9:55 am

Add to Calendar


In an old paper we proved a relationship between circuit size for SAT and the structure of the polynomial hierarchy. There is a section of that paper that almost no one ever reads. I plan on recalling that result and showing that it is actually relevant to a current problem about playing perfect chess.