Selected publications by Stefan Schwoon

Abstract:
We investigate the complexity of solving puzzles in the game Reflexion. It is shown that the difficulty of the puzzles depends critically on the features used in the puzzles; the most basic variant of the game is SL-complete, and hence can be solved in polynomial time, whereas other variants are NP- or even PSPACE-complete.

@inproceedings{HS-fun04,
   address = {Isola d'Elba, Italy},
   author = {Holzer, Markus and Schwoon, Stefan},
   booktitle = {{P}roceedings of the 3rd {I}nternational {C}onference on {F}un with {A}lgorithms ({FUN}'04)},
   editor = {Ferragina, Paolo and Grossi, Roberto},
   month = may,
   pages = {90-105},
   publisher = {Edizioni Plus, Universit{\`a} di Pisa},
   title = {Reflections on {R}eflexion~-- Computational Complexity Considerations on a Puzzle Game},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/hs-fun04.ps},
   year = {2004},
}

About LSV