BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Most computer scientists and discrete mathematicians are famil
 iar with computational complexity due to the famous P = NP conjecture. Some
  researchers have a more thorough understanding of the classes P\, NP\, and
  PSPACE since problems in logic\, graph theory\, and combinatorial optimiza
 tion are often classified by their relationship to one of these classes. Mo
 re recently\, these concepts have found a wider audience through their appl
 ication to puzzles and games. For example\, it is known that the number puz
 zle Sudoku is NP-complete\, whereas the box pushing game Sokoban is PSPACE-
 complete. In this talk we establish the computational complexity of several
  puzzles and games. We prove that two new paper and pencil puzzles are NP-c
 omplete. These puzzles are called Pencils and Sto-Stone\, and were created 
 by the Japanese publisher Nikoli that popularized Sudoku. We then prove tha
 t several puzzles that have been implemented as video games are PSPACE-comp
 lete. These games include a row shifting puzzle called MazezaM\, a turnstil
 e puzzle for the Nintendo Game Boy called Kwirk\, and a puzzle called Switc
 hes that was invented by undergraduate student Jonathan Gabor while he was 
 attending high school. Our reductions use conventional approaches such as B
 oolean Satisfiability\, as well as some less conventional tools including G
 ray Codes\, and the new Constraint Logic model pioneered by Hearn and Demai
 ne in their influential textbook "Games\, Puzzles\, and Computation". The t
 alk aims to be accessible to a wide audience\, and hopes to encourage resea
 rchers to seek similar results for problems (or puzzles!) that are close to
  them. Most of the new results consist of joint work with undergraduate stu
 dents at Bard College at Simon's Rock. 
DTSTAMP:20181105T173500
DTSTART:20180709T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin Institut für Mathematik Straße des 1
 7. Juni 136 10623 Berlin room MA 041 (ground floor)
SEQUENCE:0
SUMMARY:Aaron Williams (Bard College at Simon&#x27\;s Rock\, USA): Fun and 
 Games: The Computational Complexity of Puzzles and Video Games
UID:89793045@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20180709-C-Wil
 liams.html
END:VEVENT
END:VCALENDAR