zlacker

>>Bluest+(OP)
For those who don't know the author:

https://en.wikipedia.org/wiki/Erik_Demaine

>>Tactic+L7
I know him from proving NP-hardness of the game Sokoban:

https://erikdemaine.org/papers/PushingBlocks_CGTA/

And I clicked this submission because of his name, after all the time.

I didn't fully go through or understand the proof, but it was a refreshing addition to the classic problems I had to understand for college at the time.

Didn't need it, just fed my curiosity.

And when I clicked this link, my curiosity was fed again.

Seems like it's worth having heard of him, even as a non-scientist, because his subjects are just so interesting. Reminds me of Scott Aaronson in that regard.

>>moritz+fd1
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/

>>areyou+2i1
Yes, correct, and mentioned in the abstract. Sorry, I was imprecise and wrong.

Thanks for the links!