Timeline for Complexity of games with graph classes
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2021 at 20:42 | vote | accept | Ben Tom | ||
| Oct 15, 2021 at 18:41 | answer | added | domotorp | timeline score: 1 | |
| Oct 15, 2021 at 18:40 | comment | added | Ben Tom | I think we should accept that the Turing machine has an oracle for both sets. You are absolutely right, I have not indicated the correct reduction from $GG$ to $\varnothing - \varnothing- NG$ :(. I assume that it exists and I will think about how to build it. | |
| Oct 15, 2021 at 15:31 | comment | added | domotorp | Are $A$ and $B$ just a finite collection of graphs? If not, how are they presented? I don't see how to reduce Generalized Geography to your game, as you allow players to pick sets of vertices rather than a single vertex. | |
| Aug 11, 2021 at 14:30 | history | asked | Ben Tom | CC BY-SA 4.0 |