zlacker

[parent] [thread] 1 comments
1. areyou+(OP)[view] [source] 2024-06-20 19:20:47
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/

replies(1): >>moritz+E1
2. moritz+E1[view] [source] 2024-06-20 19:29:25
>>areyou+(OP)
Yes, correct, and mentioned in the abstract. Sorry, I was imprecise and wrong.

Thanks for the links!

[go to top]