Assembling molecules in ATOMIX is hard

DOI10.1016/J.TCS.2002.11.002zbMath1070.68069OpenAlexW2010582226WikidataQ56619903 ScholiaQ56619903MaRDI QIDQ1885003

Stefan Schwoon, Markus Holzer

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2002.11.002

zbMATH Keywords

PSPACE-completenessFinite automataBlock sliding puzzleIntersection emptiness

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Enumerative combinatorics (05A99) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Related Items (5)

\textsc{Pull} and \textsc{PushPull} are PSPACE-complete ⋮ Generalized Pete's Pike is PSPACE-complete ⋮ Particle computation: complexity, algorithms, and logic ⋮ On the complexity of jelly-no-puzzle ⋮ Quell

Uses Software

• Grail

Cites Work

• Unnamed Item
• Unnamed Item
• The \((n^ 2-1)\)-puzzle and related relocation problems
• Hierarchies of complete problems
• SOKOBAN and other motion planning problems
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants

This page was built for publication: Assembling molecules in ATOMIX is hard