4 ms·
Turing completeness refers to a language, while NP-completeness refers to an optimization problem. So for it to be turing complete you first need to define a l
by elcomet 5y ago
Turing completeness refers to a language, while NP-completeness refers to an optimization problem.
So for it to be turing complete you first need to define a language based on tetris.
For NP-completeness, it might just be solving the game.
- klyrs 5y agoSorry to nitpick your nitpicking, but NP-completeness refers to decision problems (does there exist a solution with parameter k); optimization problems are often NP-Hard (find the minimum parameter k for which the decision problem has a solution).
- elcomet 5y agoYou're right, sorry about the lack of precision