Particle computation: complexity, algorithms, and logic

DOI10.1007/s11047-017-9666-6zbMath1530.68111arXiv1712.01197OpenAlexW2963435534MaRDI QIDQ6150976

Erik D. Demaine, Rose Morris-Wright, Aaron Becker, Jarrett Lonsford, Sándor P. Fekete

Publication date: 9 February 2024

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.01197

zbMATH Keywords

complexityNP-completenessuniversal computationPSPACE-completenessefficient algorithmsrobot swarmsprogrammable matterlogic gatesarray permutationsnano-particlesparallel motion planninguniform inputs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Other nonclassical models of computation (68Q09) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (4)

Coordinating Swarms of Objects at Extreme Dimensions ⋮ Fast reconfiguration of robot swarms with uniform control signals ⋮ CADbots: algorithmic aspects of manipulating programmable matter with finite automata ⋮ Particle-based assembly using precise global control

Cites Work

• Orienting polygonal parts without sensors
• The complexity of finding minimum-length generator sequences
• Conservative logic
• Motion planning in the presence of movable obstacles
• Reconfiguring massive particle swarms with limited, global control
• SOKOBAN and other motion planning problems
• Assembling molecules in ATOMIX is hard
• Parts feeding on a conveyor with a one joint robot
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• Deterministic boundary recognition and topology extraction for large sensor networks
• Limitations of Self-assembly at Temperature One
• Algorithmic Aspects of Wireless Sensor Networks
• Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly
• Intrinsic universality in tile self-assembly requires cooperation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Particle computation: complexity, algorithms, and logic