## Games, Computation and Complexity

报告人：Peter van Emde Boas 荷兰阿姆斯特丹大学 教授

主办：清华大学人文学院 哲学系

课程简介：

The study of games invokes ideas from many different areas if scientific research: Philosophy, Mathematics, Computer Science, Logic, Psychology and Economics. In this short course the use of arguments, specifically from Mathematics, Logic and Computer Science will be illustrated, focussing on four by now rather classic topics in Computation and Complexity theory (classic because these topics all have a history of more than 20 years).

Course 1: Problems about games and mathematical solutions

地点：清华大学新斋 335 教室

时间：5 月 22 日 9:30-12:00 AM

A first question to ask when facing some (new) game is to determine whether the game as presented will terminate at all. The next question is to determine whether it can be predicted which player can win the game starting at some particular configuration, in particular starting at the start configuration of the game. Termination proofs for games are of quite different degrees of sophistication; frequently termination is trivial or enforced by the rules of the game. In other cases the proof may share the same degree of mathematical depth as encountered with termination proofs for programs. No wonder – these two problems are in essence equal. The problem of determining the winner in some given position rarely can be solved my a direct mathematical argument. Lacking such mathematical insight the generic solution method is known by the name Backward Induction. How this method should be used and to what degree it is applicable and yields the desired result depends on the structure of the game. We discuss the variations, generalizations and limitations of Backward Induction.

Course 2: PSPACE and its relation to games

地点：清华大学新斋 335 教室

时间：5 月 22 日 2:00-4:30 PM

In Complexity theory there is a folklore belief expressed by the slogan “Games capture the complexity class PSPACE” . In order to understand the content of this belief we first have to understand how (families) of games can be used to determine a language as is performed by the machine models used in Automata and Computation Theory. Next we explain how a single mathematical description of elements in PSPACE leads to four types of characterizations: in terms of Space bounded sequential computations, time bounded parallel computations,

alternation based descriptions in logic and machine models and finally games. This description goes back to the analysis underneath Savitch’ theorem (1970) stating that PSPACE = NPSPACE.

Course 3: Interactive protocols

地点：清华大学新斋 301 教室

时间：5 月 23 日 9:30-12:00 AM

Interactive protocols represent a mode of computation which introduces an almost complete set of game based ingredients into computation theory: multiple agents, choices, randomness and partially hidden information. Using these protocols one can achieve tasks formerly believed to be impossible, like convincing someone of the truth of some statement without providing a shred of evidence. Eventually, as shown by Shamir (1990), it yields yet another characterization of PSPACE.

Course 4: The evasiveness problem for graph properties

地点：清华大学新斋 324 教室

时间：5 月 23 日 2:00-4:30 PM

One of the earliest appearances of games in Theoretical Computer Science is the game played by an algorithm attempting to solve a problem against an adversary feeding the worst possible input to this algorithm (this type of argument is known by the name of the adversary argument). Evasive properties are properties for which in the worst case the complete structure of the object under consideration must be known in order to decide the property. Around 1973-74 several authors together converged on the conjecture that, for the special case of Graph properties in the edge-probe model all nontrivial monotone graph properties are evasive. In this form the conjecture is still open. However, the weaker conjecture that for these properties at least a constant fraction of all edges must be probed has been proved. We describe the theory (an application of algebraic methods in combinatorics) leading to this result by Rivest and Vuillemin (1974) which establishes the undesirable consequences of using adjacency matrices for representing graphs in a computer.

参考文献:

Combinatorial two person games

1. Elwyn R. Berlekamp, John H. Conway & Richard K. Guy, Winning Ways (Vol 1 and Vol. 2), Academic Press, 1982.

2. John H. Conway, On Numbers and Games, Academic Press 1976.

Computation Theory.

1. John E. Hopcroft & Jeffrey D. Ullman, Intorduction to Automata Theory, Languages and Computation, Addison Wesley, 1979.

2. David Harel, Algorithmics; the Spirit of Computing, (second Edition), Addison Wesley 1992.

3. A.K. Chandra, D. Kozen & L.J. Stockmeyer, Alternation, J.Assoc. Comput. Mach. 28 (1981) 114–133.

4. Christos H. Papadimitriou, Computational Complexity, Addison Wesley 1995. Chapter 19 covers many of the computation theory subjects dealt with in this course!

Tiling Game and its use in Reduction Theory

1. Bogdan S. Chlebus, Domino-Tiling Games, J. Comput. Syst. Sci. 32 (1986), 374–392.

2. Martin. P.W. Savelsberg & Peter van Emde Boas, BOUNDED TILING, an alternative to SATISFIABILITY?, in G.Wechsung ed., proc. 2nd Frege Memorial Conference, Schwerin, Sep 1984, Akademie Verlag, Mathematische Forschung vol. 20, 1984, pp. 401–407. preprint: rep. CWI-OS-R8405.

3. Peter van Emde Boas, The Convenience of Tilings, in: Andrea Sorbi, ed., Complexity, Logic and Recursion Theory, lecture notes in pure and applied mathematics vol 187, 1997, pp. 331–363.

Games hard for PSPACE

1. T.J. Schäfer, Complexity of some two-person perfect-information games, J.Comput. Syst. Science, 16 (1978) 185–225.

2. D. Lichtenstein & M. Sipser, GO is polynomial-space hard, J. Assoc. Comput. Mach, 27 (1980) 393–401.

3. S. Even & R.E. Tarjan, A combinatorial game which is complete for polynomial space, J. Assoc. Comput. Mach, 23 (1976) 710–719.

4. S. Reisch, HEX ist PSPACE-volständig, Acta Informatica 15 (1981) 167–191.

5. A.S. Fraenkel, M.R. Garey, D.S. Johnson, T. Schäfer & Y. Yesha, The complexity of checkers on an N X N board – preliminary report, Proc IEEE FOCS 19 (1978) pp. 55–64.

6. A.S. Fraenkel & D. Lichtenstein, Computing a perfect strategy for n x n chess requires time exponential in n, J. Combin. Theory series A 31 (1981) 119–213.

7. Erik D. Demaine, Playing Games with Algorithms: Algorithmic Combinatorial Game Theory , MFCS 2001, Springel LNCS 2136, pp. 18-32 .

Much more information is available from his impressive website: http://erikdemaine.org/games/

Interactive protocols

1. Carsten Lund, Lance Fortnow & Howard Karloff, Algebraic Methods for Interactive Proof Systems, J. ACM. 39 (1992) 859-868.

2. Adi Shamir, IP = PSPACE, J.ACM. 93 (1992) 869-877.

The Evasiveness problem

1. M.R. Best, P. van Emde Boas and H.W. Lenstra, jr., A Sharpened version of the Aandera-Rosenberg Conjecture, rep. MC-ZW-30-74, October 1974.

2. Ronald L. Rivest & Jean Vuillemin, On recognizing Graph properties from Adjacency Matrices, Theor. Comp. Sci. 3 (1976) 371-384.

3. L. Lovasz, Lecture notes on Evasive Graph properties, notes taken by Neal Young around fall 1990 at Princeton University. See http://staff.science.uva.nl/~peter/teaching/LovaszEvasiveness.pdf