> What is the computational complexity of Tetris with ARM instructions?
If it is Turing complete it is undecideable. If the user only builds programs that halt, is Teris with ARM instructions of the complexity class NEXPTIME-complete (which is harder than NP-Complete)?
If it is Turing complete it is undecideable. If the user only builds programs that halt, is Teris with ARM instructions of the complexity class NEXPTIME-complete (which is harder than NP-Complete)?
NEXPTIME: https://en.wikipedia.org/wiki/NEXPTIME
Complexity Zoo:N: https://complexityzoo.net/Complexity_Zoo:N