Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants

DOI10.1016/S0304-3975(01)00173-6zbMath0988.68084OpenAlexW2032056620WikidataQ56385393 ScholiaQ56385393MaRDI QIDQ5958338

Gary William Flake, Eric B. Baum

Publication date: 3 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00173-6

zbMATH Keywords

motion planninggamesdual-rail logicPSPACE-completenessreversible logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Game theory (91A99) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (21)

Push-Pull Block Puzzles are Hard ⋮ Trainyard is NP-hard ⋮ Games, Puzzles and Treewidth ⋮ Assembling molecules in ATOMIX is hard ⋮ On the Complexity of Two Dots for Narrow Boards and Few Colors. ⋮ Tracks from hell - When finding a proof may be easier than checking it ⋮ Fixed-parameter algorithms for graph constraint logic ⋮ Phutball is PSPACE-hard ⋮ Generalized Pete's Pike is PSPACE-complete ⋮ Tracks from hell -- when finding a proof may be easier than checking it ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete ⋮ Wooden geometric puzzles: Design and hardness proofs ⋮ Playing Savitch and Cooking Games ⋮ Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch ⋮ Unnamed Item ⋮ The computational complexity of Angry Birds ⋮ PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation ⋮ LaserTank is NP-Complete

Cites Work

• Reversible simulation of space-bounded computations
• The \((n^ 2-1)\)-puzzle and related relocation problems
• Reversible space equals deterministic space
• Reversibility and adiabatic computation: trading time and space for energy
• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• Time/Space Trade-Offs for Reversible Computation
• Logical Reversibility of Computation
• Unnamed Item
• Unnamed Item

This page was built for publication: Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants