




Publications  Assembling Molecules in Atomix is Hard





Reference:
Markus Holzer and Stefan Schwoon. Assembling molecules in Atomix is hard. Technical Report TUMI0101, Technische Universität München, May 2001.
Abstract:
It is shown that assembling molecules in the Atomix game can be used to simulate finite automata. In particular, an instance of Atomix is constructed that has a solution if and only if the nonemptiness intersection problem for finite automata is solvable. This shows that the game under consideration is PSPACEcomplete, improving a recent result of Hüffner et al. Thus, there are Atomix games which have superpolynomially long optimal solutions. We also give an easy construction of Atomix game levels whose optimal solutions meet the worst case.
Suggested BibTeX entry:
@techreport{HS01,
author = {Markus Holzer and Stefan Schwoon},
institution = {Technische Universit{\"a}t M{\"u}nchen},
month = {May},
number = {TUMI0101},
title = {Assembling Molecules in {A}tomix is Hard},
year = {2001}
}




