Timeline for Can one make high-level proofs about chess positions?
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 1, 2016 at 1:37 | comment | added | usul | It may be worth explicitly completing this line of thought: We generally expect NP $\subsetneq$ EXPTIME, meaning that EXPTIME-complete decision problems such as generalized chess do not have short proofs (concretely, e.g., for generic positions that are a win for white, we do not expect a proof of this that is smaller than exponential in the size of the game). | |
| Jan 31, 2016 at 21:28 | history | answered | Timothy Chow | CC BY-SA 3.0 |