Computational complexity of motion planning of a robot through simple gadgets
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 2002586
- Lower Bounds for Geometrical and Physical Problems
- The parameterized complexity of motion planning for snake-like robots
- Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
Cites work
- \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
- Classic Nintendo games are (computationally) hard
- Games, puzzles, and computation
- How to draw a planar graph on a grid
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Push-pull block puzzles are hard
- Pushing blocks is hard.
- Relationships between nondeterministic and deterministic tape complexities
- Super Mario Bros. is harder/easier than we thought
- The complexity of satisfiability problems
Cited in
(18)- PSPACE-completeness of reversible deterministic systems
- Traversability, reconfiguration, and reachability in the gadget framework
- Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
- Motion planning with pulley, rope, and baskets
- Motion planning with pulley, rope, and baskets
- scientific article; zbMATH DE number 2002586 (Why is no real title available?)
- The parameterized complexity of motion planning for snake-like robots
- Recursed Is Not Recursive: A Jarring Result
- Traversability, reconfiguration, and reachability in the gadget framework
- The Legend of Zelda: the complexity of mechanics
- On the complexity of motion planning problem of a forklift
- Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
- Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets
- Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
- You can't solve these Super Mario Bros. levels: undecidable Mario games
- PSPACE-completeness of reversible deterministic systems
- Reachability in restricted chemical reaction networks
- Agent motion planning as block asynchronous cellular automata: pushing, pulling, suplexing, and more
This page was built for publication: Computational complexity of motion planning of a robot through simple gadgets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3305736)
