Seminars & Colloquia Calendar

Abstract: Consider a two-player game (played by Alice and Bob) in which Alice asks a sequence \(\bar{a}\) and Bob responds with a sequence \(\bar{b}\) with no knowledge of Alice's future requests. A problem P is solvable by an on-line algorithm if Bob has a winning strategy in this game, where Bob wins the game if (\(\bar{a}, \bar{b}\)) constitutes a solution to P. For example, if we take P to be a graph coloring problem, Alice plays by adding a new vertex and edges connecting it to previous vertices; Bob chooses a color for that vertex. The graph is on-line colorable if Bob has a winning strategy in this game. Given a problem P, the corresponding sequential problem SeqP asserts the existence of an infinite sequence of solutions to P. We will show that the reverse-mathematical strength of SeqP is directly related to the on-line solvability of P, and we will exactly characterize which sequential problems are solvable in the axiom systems RCA\(_0\), WKL\(_0\), and ACA\(_0\).

This is joint work with Francois Dorais.