3 ms·
If you already know that it's Turing complete, isn't it automatically also NP-complete? (I also read the paper: to clarify, they are referring to different pro
by eru 6y ago
If you already know that it's Turing complete, isn't it automatically also NP-complete?
(I also read the paper: to clarify, they are referring to different problems you can build on top of Tetris, and prove some of them NP-complete and some Turing complete.
(They don't mention Turing completeness directly, but they do a reduction to Post's correspondence problem.))
- dudeinjapan 6y agoRight, my comment was the other way around; I don't know whether infinite Tetris is Turing complete.
- eru 6y agoRunning a Turing machine reduces to Post's correspondence problem (which the paper shows reduces to answering some peculiar questions about Tetris).