Departement Mathematik und Statistik

Seminar: Algebra and Logic (HS 2015)

Lecturer

  • Prof. Dr. George Metcalfe

Assistant

  • Denisa Diaconescu

Date and Venue

  • Thursday, 10 - 12 h, A97 (ExWi)
  • Start: September 17, 2015 (short introduction)

Details

  • 3 ECTS credit points
  • Enrollment for oral/written exam by the second last Friday of the lecture period via KSL
  • Prerequisites for exam: TBA
  • This course is intended for students in the following programs:
    • M.Sc. in Mathematics (Gefäss Algebra und Grundlagen)
    • M.Sc. in Statistics (Gefäss Mathematik)

The Topic

In this seminar, we will consider the games people play  (e.g., Chess, Go, Poker, Jass) and the puzzles they solve (e.g., sliding blocks) from the perspective of computational complexity. We investigate the underlying mathematical reasons why certain games and puzzles are challenging, and find also that games and puzzles serve as powerful alternative models of computation. The relationships between games, puzzles, and computation are studied in the framework of constraint logic. We will see that a constraint logic both represents the computationally hardest case from a family of games or puzzles (one or two player, perfect or imperfect information, etc.), and determines a corresponding complexity class (P, NP, PSPACE, EXPTIME, etc.).

The seminar will be based mostly on material from the book:

Games, Puzzles, and Computation.
Robert A. Hearn and Erik D. Demaine.
A K Peters/CRC Press, first edition, 2009.