Limits of Rush Hour Logic Complexity
| dc.creator | Tromp, John | |
| dc.creator | Cilibrasi, Rudi | |
| dc.date | 2005-02-15 | |
| dc.date.accessioned | 2026-07-07T03:22:32Z | |
| dc.date.available | 2026-07-07T03:22:32Z | |
| dc.description | Rush Hour Logic was introduced in [Flake&Baum99] as a model of computation inspired by the ``Rush Hour'' toy puzzle, in which cars can move horizontally or vertically within a parking lot. The authors show how the model supports polynomial space computation, using certain car configurations as building blocks to construct boolean circuits for a cpu and memory. They consider the use of cars of length 3 crucial to their construction, and conjecture that cars of size 2 only, which we'll call `Size 2 Rush Hour', do not support polynomial space computation. We settle this conjecture by showing that the required building blocks are constructible in Size 2 Rush Hour. Furthermore, we consider Unit Rush Hour, which was hitherto believed to be trivial, show its relation to maze puzzles, and provide empirical support for its hardness. | |
| dc.identifier | https://arxiv.org/abs/cs/0502068 | |
| dc.identifier | http://arxiv.org/abs/cs/0502068 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32635 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3; F.2 | |
| dc.title | Limits of Rush Hour Logic Complexity | |
| dc.type | text |