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
complexityNP-completenessuniversal computationPSPACE-completenessefficient algorithmsrobot swarmsprogrammable matterlogic gatesarray permutationsnano-particlesparallel motion planninguniform inputs
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)
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
