logoalt Hacker News

quibono • today at 8:58 AM • 1 reply • view on HN

FWIW there's a proof of Sokoban being NP-complete in a Cambridge University student publication called Eureka [0], edition 54.

So, quite a lot more complex than one might think.

[0] https://archim.org.uk/publications/


Replies

mjdv • today at 9:16 AM

In fact it's even PSPACE-complete, which is (probably) much, much harder!

➕ show 1 reply