Making games short (extended abstract)
Uriel Feige, Joe Kilian · 1997
We study the complexity of refereed games, in which two computationally unlimited players play against each other, and a polynomial time referee monitors the game and announces the winner.The players may exchange messages with the referee in private, resulting in a game of perfect recall but incomplete information.We show that any EXPTIME statement can be efficiently transformed into a refereed game in which if the statement is true, the first player wins with overwhelming probability y, and if the statement is false, the second player wins with overwhelming probability.We also prove matching PSPACE upper and lower bounds on the complexity of statements that have refereed games that take one round of communication.