Timeline for What is the complexity class most closely associated with what the human mind can accomplish quickly?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 26 at 20:44 | comment | added | Joshua Grochow | I guess what I wrote holds for "worst-case" instances, which kind of makes sense for puzzles like Sudoku or games like chess. But for "real-world" instances sometimes we can go much farther. E.g. although computing Gröbner bases is EXPSPACE-complete, there are plenty of instances that arise "in practice" that can be solved by hand, and, despite being "small", are not so small as to be uninteresting. | |
| Feb 5 at 20:49 | comment | added | Denis | Indeed, this is a fun open problem :) | |
| Feb 5 at 18:09 | comment | added | Joshua Grochow | @Denis: Thanks! I had thought there was some subtlety about the ko rule. Turns out there is, but the subtlety is not what I thought it was. It seems that with "full ko" rule (rather than the easier-to-check Japanese ko rule, where it is EXP-complete), Go is PSPACE-hard, but could be as hard as EXPSPACE-complete! | |
| Feb 5 at 12:40 | comment | added | Denis | chess and go are EXPTIME-complete rather than PSPACE-complete. This is the case typically for games whose duration can be exponential in the size of the board. | |
| Mar 11, 2011 at 20:24 | vote | accept | CommunityBot | ||
| Mar 10, 2011 at 4:39 | history | edited | Joshua Grochow | CC BY-SA 2.5 |
grammar
|
| Mar 10, 2011 at 4:21 | history | answered | Joshua Grochow | CC BY-SA 2.5 |