【课程名称】Games, Computation and Complexity

【主讲教师】Peter van Emde Boas

【上课时间】2012年5月22-23日9：30—12：00，下午2：00-4：30

【上课地点】22日新斋335教室，23日上午新斋301教室，23日下午新斋324教室

【学 分】1学分（记非学位课学分）

【选课方式】第一次上课时，课堂报名

【授课教师简介】

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).

【课程大纲】

本课程拟通过课堂讲授和课堂讨论相相结合的方法，分4次课，对以下这些问题进行阐释和探讨：

Course 1: Problems about games and mathematical solutions

Course 2: PSPACE and its relation to games

Course 3: Interactive protocols

Course 4: The evasiveness problem for graph properties