4 ms·
For those who don't know the author: https://en.wikipedia.org/wiki/Erik_Demaine https://en.wikipedia.org/wiki/Erik_Demaine
by TacticalCoder 2y ago
For those who don't know the author:
https://en.wikipedia.org/wiki/Erik_Demaine https://en.wikipedia.org/wiki/Erik_Demaine
- breck 2y agoOh wow, quite a portfolio: https://github.com/edemaine https://github.com/edemaine He is also the maintainer of KaTeX, which I depend on. (Thanks Erik!)
- moritzwarhier 2y agoI know him from proving NP-hardness of the game Sokoban: https://erikdemaine.org/papers/PushingBlocks_CGTA/ 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.
- areyousure 2y agoThat 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-883d-3afbee5bce83 https://era.library.ualberta.ca/items/f551dfd8-c8e6-4e78-883... See also https://erikdemaine.org/papers/NCL_TCS/ https://erikdemaine.org/papers/NCL_TCS/
- moritzwarhier 2y agoYes, correct, and mentioned in the abstract. Sorry, I was imprecise and wrong. Thanks for the links!
- pcloadletter_ 2y agoLOL, completed PhD at 20