Pavel Pudlák: A presentation of Martin’s proof of Borel determinacy

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

Abstract:

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.