2-EXPSPACE-completeness conjecture for Ramsey-number avoidance games
2-EXPSPACE-completeness conjecture for Ramsey-number avoidance games
Let be the complete graph on vertices, let be the symmetric binary Ramsey number, and let be the complete graph on that many vertices. Explicit-Ramsey-number avoidance conjecture. The graph Ramsey avoidance games played on are --complete. This conjecture is presented as a consequence of the preceding conjectures: computing explicit Ramsey numbers and manipulating graphs of their size suggests doubly exponential space requirements under succinct input representations.
Sources & referencesView supporting material
Primary source
Wolfgang Slany, “Graph Ramsey games”, arXiv:cs/9911004 (1999).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.