Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 05, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Christian Helbling
It is shown that Sokoban, the popular puzzle game, can be used to simulate Turing machines. This will show that the decision problem of deciding whether a given Sokoban puzzle has a solution is PSPACE-complete.
Work by Joseph C. Culberson, Technical Report TR 97-02, 1997.
Automatic MiSe System Software Version 1.4803M | admin login