Abstract

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.

Video Recording