Monday, February 17, 2014, 13:30
Prague Logic Seminar, Institute of Mathematics, Žitná 25, blue lecture hall, rear building
Speaker: Pavel Pudlák (Institute of Mathematics AS CR)
Title: A presentation of Martin’s proof of Borel determinacy
Countably infinite games are, in general, not determined – there are games in which neither player has a winning strategy. A classical result of Martin shows that every game whose payoff set is Borel is determined. Recently Gowers proposed to use finite versions of the concepts involved in Martin’s proof to solve the P vs. NP problem. Although it is not clear if this approach is likely to make a progress in the P vs. NP problem, it is worthwhile to recall Martin’s proof.