Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Rush Hour

Expand Messages
  • Lance Fortnow
    John Tromp at CWI has been telling me about some work he is doing on the Rush Hour problem. Rush Hour is a puzzle where you have to remove a car stuck in
    Message 1 of 1 , Mar 4, 2003
    • 0 Attachment
      John Tromp at CWI has been telling me about some work he is doing on the Rush Hour problem. Rush Hour is a puzzle where you have to remove a car stuck in gridlock. A nice description of the problem is presented in a Science News article.

      The general problem is PSPACE complete shown by Eric Baum and Gary Flake when they were at NEC. Tromp tells me that he has shown the problem is still PSPACE-complete when the cars are 2x1. Oddly enough the 1x1 case is the hardest to analyze and its complexity remains wide open.

      Also check out Tromp's Rush Hour mazes.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 3/4/2003 4:37:10 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.