Comment Re:Historical value (Score 1) 345
And on the flipside, Chess, Go and Rubik's cube couldn't possibly be as hard as Tetris... they are all finite problems and so can be solved in constant time. Admittedly, a constant time that is enormous, but constant nonetheless. You need an infinite family of problems before you can get an NP-hard problem.
As it turns out, you can define infinite problems based on Go (play it on an n x n board instead of 19 x 19) or for the Rubik's (give an arbitrary configuration for an n x n cube instead of 3 x 3)
but there's no natural way to do this for chess.
As it turns out, you can define infinite problems based on Go (play it on an n x n board instead of 19 x 19) or for the Rubik's (give an arbitrary configuration for an n x n cube instead of 3 x 3)
but there's no natural way to do this for chess.
