6 ms·
One surprising example not listed there is "sliding-block puzzles", as proven in this paper: https://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pdf http
by dane-pgp 5y ago
One surprising example not listed there is "sliding-block puzzles", as proven in this paper:
https://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pdf https://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pd...
- stellaathena 5y agoThis paper repeatedly states that it’s PSPACE, but I see no evidence that it’s Turing complete.
- dane-pgp 5y agoSorry, you're right, yes. > Technically, a problem is called PSPACE-complete if it is equal in computational power to a particular mathematical model of computation (called “polynomial-space-bounded Turing machines”).