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'\;s Rock\, USA): Fun and
Games: The Computational Complexity of Puzzles and Video Games
UID:89793045@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20180709-C-Williams.html
END:VEVENT
END:VCALENDAR