#1996

Rush Hour(1996) — 木箱の交通渋滞が、PSPACE完全の証明を受け取った年

1996年に米国で発売された木製スライドパズル「Rush Hour」は、赤い車を渋滞から脱出させるだけの盤から出発し、2002年にPSPACE完全と証明され、四半世紀を経た今も計算複雑性理論の研究対象であり続けている。考案者・芦ヶ原伸之が遺した一台の盤の歴史をたどる。