Timeline for An intuitive explanation of "provably complex combinatorial games"
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 21, 2022 at 14:02 | history | bounty ended | user56834 | ||
| S Jul 21, 2022 at 14:02 | history | notice removed | user56834 | ||
| Jul 21, 2022 at 14:01 | vote | accept | user56834 | ||
| Jul 21, 2022 at 3:55 | answer | added | Maksym | timeline score: 0 | |
| Jul 18, 2022 at 6:57 | answer | added | pcpthm | timeline score: 4 | |
| Jul 17, 2022 at 16:04 | history | edited | user56834 | CC BY-SA 4.0 |
added 253 characters in body
|
| Jul 17, 2022 at 6:47 | comment | added | user56834 | (Note I didn't find it readable enough possibly due to the complexity needed to prove everthing precisely) | |
| Jul 17, 2022 at 5:26 | comment | added | user56834 | @reinierpost, a shorter intuitive explanation of how the reduction works that isnt spread out over multiple lemmas and definitions (and maybe as a result isnt as rigorous, if necessary). | |
| Jul 15, 2022 at 14:48 | comment | added | reinierpost | The original paper by Fraenkel and Lichtenstein seems pretty readable. What would you like to see that isn't provided there? | |
| S Jul 15, 2022 at 8:49 | history | bounty started | user56834 | ||
| S Jul 15, 2022 at 8:49 | history | notice added | user56834 | Draw attention | |
| Jul 12, 2022 at 17:57 | history | edited | user56834 | CC BY-SA 4.0 |
added 545 characters in body
|
| Jul 12, 2022 at 17:10 | history | edited | user56834 | CC BY-SA 4.0 |
added 167 characters in body
|
| Jul 12, 2022 at 5:25 | comment | added | user56834 | @plshelp, yes this does actually make it easier, but it seems like the main difficulty of the problem is still there. | |
| Jul 12, 2022 at 0:35 | comment | added | plshelp | Note that the problem "Does DTM $M$ halt in $k$ steps?" is EXPTIME-complete. Try reducing this to one of your games and you are done, because encoding another EXPTIME problem as the first problem is usually pretty simple. | |
| Jul 11, 2022 at 19:52 | history | asked | user56834 | CC BY-SA 4.0 |