← Back to context

Comment by areyousure

7 months ago

That paper does not prove that Sokoban is NP-hard. It does, however, cite an earlier paper proving the stronger result that Sokoban is PSPACE-complete:

Culberson, Joseph. "Sokoban is PSPACE-complete." (1997). https://era.library.ualberta.ca/items/f551dfd8-c8e6-4e78-883...

See also https://erikdemaine.org/papers/NCL_TCS/

1 comment

areyousure

Reply