## [Computational Complexity] Whats your Game Mr. Bond- The sequel!

Expand Messages
• (I will post about CCC 2010 later in the week.) The word Game is used in many different contexts within math and computer science. I list out all that a group
Message 1 of 1 , Jun 14, 2010
(I will post about CCC 2010 later in the week.)

The word Game is used in many different contexts within math and computer science. I list out all that a group of us at last years Dagstuhl thought of:
1. Duplicator-Spoiler Games are used in Descriptive Complexity theory and Logic. They are also called Ehrenfeucht-Fraisse games. (The pointer, a wikipedia entry, as a pointer to EXCELLENT slides on these games.) Example result: wellfoundness for linear orders is not first order definable.
2. Every A &sub {0,1}&omega gives rise to the following game: Alice picks c1 &isin {0,1} Bob picks c2 &isin {0,1} Alice picks c3 &isin {0,1} Bob picks c4 &isin {0,1} etc. If c1c2c3 ... is in A then Alice wins. If not then Bob wins. The Axiom of Determinacy states that, for every A, one of the two players has a winning strategy. This has been proven for Borel sets A. Full AD contradicts Full AC. See here. I have posted on it before here.
3. Banach Games. Let A be a subset of R. All numbers picked are in R. Alice picks x1. Bob picks x2 < x1. Alice picks x3 < x2. Bob picks x4 < x3. etc. If &sum xi &isin A then Alice wins, otherwise Bob Wins. For more on these see here.
4. Banach Mazur Games. (I am not quite sure of this one since I could not find stuff on the web and it looks too much like the games for AD. If this is incorrect please comment.) Similar to the games under AD; however, instead of picking an element of {0,1} the players pick an element of {0,1}+. This has been used to define when a set is meager and has been extended to poly-time settings. Also has been extended to graphs: see here
5. Martingales. Let A &sub {0,1}&omega. x is in A, but the player does not know what it is. The player starts out with one dollar (wow!). When the player sees the first n bits of x he bits on the (n+1)st bit. Can he win? Depends on A. Has been used to define measure 0 and has been adapted to the poly time setting. Jack Lutz has worked a lot on this stuff.
6. Complexity Classes have been defined via games. Usually a prover wins if he can convince a verifier that x &isin A. Many parameters can be changed to get many classes (number of rounds, number of provers, strengh of verifier, strength of prover(s), prob of error allowed). I would include the Unique Game Conjecture in this use of the word game.
7. Pebble Games have been used to get time-space tradeoffs on simple models of computation. More recently they have been used to get lower bounds on resolution theorem provers. For a survey see the first paper on this page. Warning- the survey is 200 pages!
8. Games have been used to prove theories decidable. Originally S2S (Second order theory with two successors, essentially the theory of infinite strings of 0's and 1's) was proven decidable by Michael Rabin. Later Gurevich and Harrington had a simpler proof using games. See this paper. Another exellent article on this, which alas is not on line, is Infinite Games played on Finite Graphs by Robert McNaughton, Annals of Pure and Applied logic, Volume 65, Issue 2, Pages 149-184.
9. Combinatorial Games like NIM have been well studied.
10. Game Theory needs no commentary here.
11. Richman Games are a way to combine Combinatorial Games with Game Theory. See this paper.
12. In adversary arguments in lower bounds we picture an adversary who is playing a game with the algorithm or with any possible algorithms.
13. Communication Complexity Games. Not sure these are really games, but the term is used.
14. Surreal numbers are actually games. See Conways book On Numbers and Games.
15. A lot of computer science and graphics go into video games.
16. There has been some study of strategies on real games like monopoly and chess. I gave one classification of games in this post. Note that GO and Chess are EXPTIME complete.
Note that most of these games are not fun.

--
Posted By GASARCH to Computational Complexity at 6/14/2010 12:51:00 PM
Your message has been successfully submitted and would be delivered to recipients shortly.