News for hackers. Stuff that matters.
Re:Tetris Is Hard, Even to Approximate by hopler on Friday March 29, 2019 @10:48PM (#19527340)
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

Re:Tetris Is Hard, Even to Approximate by bjourne on Saturday March 30, 2019 @01:57PM (#19530770)
That 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.