4 ms·
What does "too well” mean? The paper proves that Tetris is NP hard, but that is only because Tetris is infinitely long game. It's still easy for a computer to
by hopler 8y ago
What does "too well” mean?
The paper proves that Tetris is NP hard, but that is only because Tetris is infinitely long game. It's still easy for a computer to play as well as a human and faster
- bjourne 8y agoThat is the "even to approximate" part. It means that Tetris is NP-hard AND no polynomial time algorithm can be shown to be within a constant factor of the optimal solution. Eg no matter how good your Tetris bot is, there may be one that is a thousand times better waiting to be discovered.