4 ms·
I always find it interesting when people say things like "chess is a PSPACE problem", because in order to define it as such, you have to consider the board size
by klodolph 11y ago
I always find it interesting when people say things like "chess is a PSPACE problem", because in order to define it as such, you have to consider the board size to be variable, even though it's always 8x8.
- dsjoerg 11y agowell you've found the right guy to ask about that because the author is a professor of Computational Complexity Theory.
- tromp 11y agoBut you can safely say "Ladders are PSPACE-complete" about the game of Go which is played on many different sizes, some far larger than the standard 19x19 (e.g. KGS supports 38x38 boards).
- w0bb13 11y agoThe number of serious games above 19x19 is basically nil, so the difference is a bit misleading (although it's definitely more common in go).