\documentclass[12pt]{article}

\sloppy

\usepackage[usenames]{color}
\usepackage{epsfig}
\usepackage[numbers]{natbib}
\usepackage{latexsym}

\setlength{\topmargin}{-1.0cm}
\setlength{\textheight}{16.0cm}
\setlength{\oddsidemargin}{2.5cm}
\setlength{\evensidemargin}{0.0cm}
\setlength{\textwidth}{20.0cm}
\setlength{\parskip}{5pt plus 2pt minus 1pt}

\renewcommand{\topfraction}{1}
\renewcommand{\textfraction}{0}
\renewcommand{\floatpagefraction}{0.99}

\definecolor{darkgreen}{rgb}{0,0.8,.18}
\definecolor{darkred}{rgb}{0.8,0,0}
\definecolor{teal}{rgb}{0.05,0.32,0.41}

% red bullets (for itemize env.):
\def\bu{\color{red}$\bullet\:$}
\newcommand{\bsection}[1]{\begin{center}{\bfseries \textcolor{Apricot}{#1}}\end{center}}
\newcommand{\rem}[1]{\marginpar{{\normalsize \textcolor{cyan}{\b #1}}}}
%\newcommand{\explain}[1]{\textcolor{cyan}{\underline{\textcolor{white}{#1}}}\rem{}}
\newcommand{\explain}[1]{#1}
\newcommand{\pto}{\marginpar{\mbox{\huge \hspace*{1em}$\rhd$}}}
\newcommand{\vfills}{\vspace*{\fill}}
\newcommand{\descr}[1]{\textcolor{Apricot}{#1}}

\newtheorem{prop}{Proposition}
\newtheorem{theo}{Theorem}
\newtheorem{lem}[theo]{Lemma}
\newtheorem{corol}[theo]{Corollary}
\newtheorem{defn}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{example}{Example}
\newtheorem{obs}{Observation}
\newtheorem{fact}{Fact}
\newtheorem{conj}{Conjecture}
\newtheorem{open}{Open Problem}

\newcommand{\sproofsketch}[1]{\subsection{Proof sketch of Theorem~\ref{#1}.}}
\newcommand{\sproof}[1]{\subsection{Proof of Theorem~\ref{#1}.}}
\def\proof{\relax{\noindent\bfseries\upshape Proof.\ }}
\def\halmos{\hspace*{1em}{\rule[-0.5mm]{1.5mm}{3mm}}}
\def\halmoseol{\hspace*{\fill}\halmos}

\newcommand{\And}{\wedge}
\newcommand{\Or}{\vee}
\newcommand{\de}{\stackrel{\raisebox{.6ex}{\textup{{\Large def}}}}{=}}

\newcommand{\N}{{{\sf l} \kern -.10em {\sf N} }}

\newcommand{\p}{\mbox{\bfseries\upshape P}}
\newcommand{\ip}{\mbox{\bfseries\upshape IP}}
\newcommand{\np}{\mbox{\bfseries\upshape NP}}
\newcommand{\npc}{\mbox{\bfseries\upshape NP}-complete}
\newcommand{\pspace}{\mbox{\bfseries\upshape PSPACE}}
\newcommand{\pspacec}{\pspace{}-complete}
\newcommand{\exptime}{\mbox{\bfseries\upshape EXPTIME}}
\newcommand{\exptimec}{\mbox{\bfseries\upshape EXPTIME}-complete}
\newcommand{\expspace}{\mbox{\bfseries\upshape EXPSPACE}}
\newcommand{\logspace}{\mbox{\bfseries\upshape LOGSPACE}}
\newcommand{\conpnpc}{\mbox{\bfseries\upshape coNP$^{\mbox{\sfseries\upshape NP}}$}-complete}
\newcommand{\piptc}{$\mathbf{\Pi}^\mathsf{P}_2$-complete}

\newcommand{\setcomma}{\,,\,}
\newcommand{\union}{\:\cup\:}
\renewcommand{\b}{{\Large$\Box$}~}

% paper-specific commands: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\ramsey}{\mbox{\textsf{Ramsey}}}
\newcommand{\gramsey}{\mbox{$G_{\mbox{\sffamily {\Large Avoid-Ramsey}}}$}}
\newcommand{\lramsey}{\mbox{$L_{\mbox{\sffamily {\Large Avoid-Ramsey}}}$}}
\newcommand{\gmisereramsey}{\mbox{$G_{\mbox{\sffamily {\Large Avoid'-Ramsey}}}$}}
\newcommand{\lmisereramsey}{\mbox{$L_{\mbox{\sffamily {\Large Avoid'-Ramsey}}}$}}
\newcommand{\gmultiramsey}{\mbox{$G_{\mbox{\sffamily {\Large Avoid-Ramsey}}^n}$}}
\newcommand{\lmultiramsey}{\mbox{$L_{\mbox{\sffamily {\Large Avoid-Ramsey}}^n}$}}
\newcommand{\gachieveramsey}{\mbox{$G_{\mbox{\sffamily {\Large Achieve-Ramsey}}}$}}
\newcommand{\lachieveramsey}{\mbox{$L_{\mbox{\sffamily {\Large Achieve-Ramsey}}}$}}
\newcommand{\gachieveramseynt}{\mbox{$G_{\mbox{\sffamily {\Large Achieve'-Ramsey}}}$}}
\newcommand{\lachieveramseybt}{\mbox{$L_{\mbox{\sffamily {\Large Achieve'-Ramsey}}}$}}
\newcommand{\gweakachieveramsey}{\mbox{$G_{\mbox{\sffamily {\Large Achieve''-Ramsey}}}$}}
\newcommand{\lweakachieveramsey}{\mbox{$L_{\mbox{\sffamily {\Large Achieve''-Ramsey}}}$}}
\newcommand{\gasymmetricramsey}{\mbox{$G_{\mbox{\sffamily {\Large Asymmetric-Ramsey}}}$}}
\newcommand{\lasymmetricramsey}{\mbox{$L_{\mbox{\sffamily {\Large Asymmetric-Ramsey}}}$}}
\newcommand{\gseekramsey}{\mbox{$G_{\mbox{\sffamily {\Large Seek-Ramsey}}}$}}
\newcommand{\lseekramsey}{\mbox{$L_{\mbox{\sffamily {\Large Seek-Ramsey}}}$}}
\newcommand{\gseekntramsey}{\mbox{$G_{\mbox{\sffamily {\Large Seek'-Ramsey}}}$}}
\newcommand{\lseekntramsey}{\mbox{$L_{\mbox{\sffamily {\Large Seek'-Ramsey}}}$}}
\newcommand{\gramseyplus}{\mbox{$G_{\mbox{\sffamily {\Large Avoid-Ramsey}}^+}$}}
\newcommand{\lramseyplus}{\mbox{$L_{\mbox{\sffamily {\Large Avoid-Ramsey}}^+}$}}
\newcommand{\gpos}{\mbox{$G_{\mbox{\sffamily {\Large Achieve-POS-CNF}}}$}}
\newcommand{\lposcnf}{\mbox{$L_{\mbox{\sffamily {\Large Pos}}}(\mbox{\sffamily POS CNF})$}}
\newcommand{\gposdnf}{\mbox{$G_{\mbox{\sffamily {\Large Achieve-POS-DNF}}}$}}
\newcommand{\lposdnf}{\mbox{$L_{\mbox{\sffamily {\Large POS DNF}}}$}}
\newcommand{\tri}[3]{\triangle(#1\setcomma #2\setcomma #3)}
\newcommand{\trifi}[3]{\{#1\setcomma #2\},\{#1\setcomma #3\},\{#2\setcomma #3\}}
\newcommand{\trif}[3]{\left\{\rule[-1ex]{0cm}{2ex}\trifi{#1}{#2}{#3}\right\}}
\newcommand{\vrii}[3]{\{#1\setcomma #2\},\{#1\setcomma #3\}}
\newcommand{\vri}[3]{\left\{\rule[-1ex]{0cm}{2ex}\vrii{#1}{#2}{#3}\right\}}
\newcommand{\arrowing}{{\sc Arrowing}}
\newcommand{\cdc}{{\sc Competitive Distributed Computing}}
\newcommand{\Simp}{Sim$^{\mbox{+}}$}
\newcommand{\Simf}{Sim$_{\mbox{4}}$}
\newcommand{\Sima}{Sim$_{\mbox{a}}$}
\newcommand{\Simn}{Sim$_n$}
\newcommand{\Simnp}{Sim$_n^{\mbox{+}}$}

\begin{document}

\pagestyle{myheadings}
\markboth{}{\color{SkyBlue}\sffamily\slshape The complexity of graph Ramsey achievement and avoidance games \hspace*{12pt}(Wolfgang Slany) \hspace*{12pt}
\hrulefill \hspace*{20pt}}
\renewcommand{\thepage}{\color{SkyBlue}\sffamily \arabic{page}}

\sffamily
\huge
\pagecolor{teal}
\color{white}
\thispagestyle{empty}

\begin{center}
{\Huge \bfseries \color{Apricot} The complexity of graph Ramsey\\ achievement and avoidance games}
\vfill
\bigskip
Wolfgang Slany
\vfill
{\Large Institut f\"{u}r Informationssysteme, Technische Universit\"{a}t Wien, Austria\\[-1.2ex]
mailto:\,wsi@dbai.tuwien.ac.at, http://www.dbai.tuwien.ac.at/staff/slany/}
\end{center}
\vfill
\bigskip
\begin{center}Abstract\end{center}
\bigskip
\noindent Given two graphs $\,G$ and $A$, two players, Red and Green,
alternate in coloring the edges of $G$ in their respective color. Aim
is to avoid (achieve) to build a monochromatic subgraph isomorphic to
$A$. How difficult are these games?
\vfill
% []\noindent \mbox{\Large {Literature: \color{SpringGreen} http://www.dbai.tuwien.ac.at/ftp/papers/slany/dbai-tr-99-25.$\{$ps$|$ps.gz$\}$}}
\vfills

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mbox{}\\[-2em]
\bsection{Overview}
\vfill
\begin{itemize}
\item[\bu] In medias res: Let's play \ldots
\item[\bu] Complexity of the graph Ramsey games
\item[\bu] Ultra-strongly solving Sim and \Simp
\item[\bu] About the unlikeliness of solving \Simf\ etc.
\item[\bu] The ``difficulty'' of combinatorial games revisited
\item[\bu] Some conjectures
\item[\bu] Further remarks
\end{itemize}
\vfills

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mbox{}\\[-5ex]
\bsection{Sim: \textcolor{white}{\mdseries $G=K_{\Large \ramsey(3,3)}=K_6,\ A=K_3$\/ ~on~ \gramsey}}
\mbox{}\\[-5ex]
\begin{center}
\epsfig{file=chexi.eps,width=\textwidth}
\end{center}

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\enlargethispage*{3cm}
\noindent Considering that a hands-on session with an interactive system often
is worth more than a thousand images:\\
\begin{picture}(0,0)(0,0)
\put(0,0){\epsfig{file=css1.eps,angle=270,width=\textwidth}}
\end{picture}
\vspace{.85\textheight}
\mbox{}\pto

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\enlargethispage{2cm}
\noindent ... with random permutations between moves:
\vspace{-2ex}
\begin{center}
\epsfig{file=css.eps,angle=270,width=.8\textwidth}
\end{center}
This Java applet plays Sim and a variant, \explain{\Simp}. In case you
win, you will be allowed to leave your name in our hall-of-fame!

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vfills
\noindent Sim and \Simp\ can never end in a tie:
\vfill
\bsection{\hspace*{3em}\ramsey(3,3)=6}
\begin{center}
\epsfig{file=cr33e6.eps,width=.9\textwidth}
\end{center}
\vfill
\begin{flushright}
(visual proof by courtesy of Ranan Banerji)
\end{flushright}
\vfills

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mbox{}\\
\noindent A winning strategy for the \gachieveramsey\ game \Sima:
\vfill
\begin{center}
\epsfig{file=csima.eps,width=\textwidth}
\end{center}
\vfill
\mbox{}

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mbox{}\\
\noindent No simple winning strategies are known for Sim and \Simp.
\bsection{$\mathbf{\Rightarrow}$ \ Natural question: How ``difficult'' is a game?}
\noindent Translation to complexity theory:

{\slshape How does the function bounding the computational resources
that are needed in the worst case to determine a winning strategy for
the first player grow in relation to the size of the game
description?}  
\vfill
\noindent Typical results: \explain{Generalizations} of well-known games such as
Chess, Checkers, and Go to boards of size $n\times n$ have been
classified as \explain{polynomial space} and \explain{exponential
time}
\explain{complete} \explain{\cite{Fraenkel81,Fraenkel78,Lichtenstein80}}.
\vfill
Note: \ \ \ $\p\subseteq\np\subseteq\pspace\subseteq\exptime$
\vfills

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vfills
\noindent How to generalize Sim to game boards of arbitrary size?
\vfill
\bsection{$\mathbf{\Rightarrow}$ \ Graph Ramsey theory}
\vfill
\begin{defn}\label{def:arrowing} \ \ {$G\rightarrow A$:}\\
\hspace*{\parindent}We say that a graph $G$\/ {\em arrows} a graph $A$
if every edge-coloring of $G$ with colors red and green contains a
monochromatic subgraph isomorphic to $A$. $G$ is called a\/ {\em
Ramsey graph} of $A$.
\end{defn}
\vfill
\begin{theo} \ \textup{\explain{\cite{Deuber75,Erdos75,Roedl73}}} \
Every graph has Ramsey graphs. 
\end{theo}
\vfill
\begin{theo} \ \textup{\explain{\cite{Schaefer99}}}\\
\hspace*{\parindent}Deciding \ {$G\rightarrow A$} \ for given $G$ and $A$ is\/ \piptc.
\end{theo}
\vfills

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vfills
\noindent Generalizing Sim to graph Ramsey theory leads to:
\vfill
\begin{defn}\label{def:gramsey} \ \ \descr{\gramsey$(G,A,E^r,E^g)$}:\\
\hspace*{\parindent}Given two graphs $G=(V,E)$ and $A$ and two non-intersecting sets $E^r
\cup E^g \subseteq E$ that contain edges initially colored in red and
green, respectively. Two players, Red and Green, take turns in
selecting at each move one so-far uncolored edge from $E$ and color it
in red for player Red respectively in green for player Green. However,
both players are forbidden to choose an edge such that $A$ becomes
isomorphic to a subgraph of the red or the green part of $G$. It is
Red's turn. The first player who cannot move loses.
\end{defn}
\bigskip\bigskip
Similar definitions of \gramseyplus\ and \gachieveramsey.  
\vfills 

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vfills
\bsection{Main complexity results} 
\vfill
\begin{theo}\label{theo:gramsey} \quad \gramsey\ is\/ \pspacec.
\end{theo}
\vfill
\begin{theo}\label{theo:gramseyplus} \quad \gramseyplus\ is\/ \pspacec.
\end{theo}
\vfill

And, surprisingly,
\vfill 
\begin{theo}\label{theo:gachieveramsey} \quad  \gachieveramsey\
is\/ \pspacec.
\end{theo}
\bigskip
\bigskip
Significance: These games thus are as difficult as other
well-known difficult games such as Go, and at least as difficult as
any \npc\ problem.
\vfills 

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bsection{Proof sketch of Theorem~\ref{theo:gramsey}}
\begin{itemize}
\item[\bu] Membership in \pspace: easy.
\item[\bu] Hardness: via a \logspace\ reduction from the \pspacec\ game 
\gpos\ \cite{Schaefer78}:
\end{itemize}

\begin{defn}\label{def:gpos} \ \gpos$(F)$: We are given a positive CNF formula
$F$. A move consists of choosing some variable of $F$ which has not
yet been chosen. Player I starts the game. The game ends after all
variables of $F$ have been chosen. Player I wins iff $F$ is\/ {\tt true}
when all variables chosen by player I are set to\/ {\tt true} and all
variables chosen by player II are set to\/ {\tt false}. 
\end{defn}

Example: On input $F=(x_1\Or x_4)\And (x_2\Or x_3)\And
(x_2\Or x_4)$\linebreak[0] player I has a winning strategy. 

$F$ is reduced to the following \gramsey\ game \ldots\pto

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vspace*{0ex}
\begin{flushright}{\Large $\mathbf{F=(x_1\Or x_4)\,\And \hspace*{4.5em}}$\\
$\mathbf{(x_2\Or x_3)\And (x_2\Or x_4)}$}\end{flushright}
\vspace{-8ex}
\begin{center}
\epsfig{file=creduct.eps,width=\textwidth}
\end{center}

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vfills
\bsection{Proof sketch of Theorem~\ref{theo:gramseyplus}}
\vfill
\begin{itemize}
\item[\bu] A careful analysis of the proof of Theorem~\ref{theo:gramsey} reveals
that we can reuse the reduction of that proof to show the
\pspacec{}ness of \gramseyplus.
\item[\bu] Indeed, all arguments go through even
when both players are allowed to color more than one edge per
move. 
\item[\bu] The difficulty here lies in the rather involved analysis of the
cases when the opponent plays non-optimally.
\end{itemize}
\vfills

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bsection{Proof sketch of Theorem~\ref{theo:gachieveramsey}}
\begin{itemize}
\item[\bu] Membership in \pspace: easy.
\item[\bu] Hardness: via a \logspace\ reduction from the \pspacec\ game 
\gposdnf\ \cite{Schaefer78}:
\end{itemize}

\begin{defn}\label{def:gposdnf} \ \gposdnf$(F)$: We are given a positive DNF formula
$F$. A move consists of choosing some variable of $F$ which has not
yet been chosen. Player I starts the game. The game ends after all
variables of $F$ have been chosen. Player I wins iff $F$ is\/ {\tt true}
when all variables chosen by player I are set to\/ {\tt true} and all
variables chosen by player II are set to\/ {\tt false}. 
\end{defn}

Example: On input $F=(x_1\And x_2)\Or (x_3\And x_4\And x_5)\Or
(x_3\And x_5\And x_6)\Or (x_3\And x_4\And x_7)$ player II has a
winning strategy. The corresponding \gachieveramsey\ game is
\ldots\pto

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\enlargethispage{2cm}
\vspace*{0ex}
\begin{flushright}{\Large $\mathbf{F=(x_1\And x_2)\Or
(x_3\And x_4\And x_5)\,\Or\hspace*{1.4em}}$\\
$\mathbf{(x_3\And x_5\And x_6)\Or (x_3\And x_4\And x_7)}$}\end{flushright}
\vspace{-8ex}
\epsfig{file=careductd.eps,width=\textwidth}

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{defn}[\cite{Allis94,Schaeffer96a}]\label{def:solved} \ A combinatorial
game is \ldots
\begin{description}
\item[\bu] \descr{ultra-weakly solved} if the game-theoretic value for the initial
position has been determined,
\item[\bu] \descr{weakly solved} if it is ultra-weakly solved and a strategy
exists for achieving the game-theoretic value from the opening
position, assuming reasonable computing resources,
\item[\bu] \descr{strongly solved} if for all possible positions, a strategy is
known for determining the game-theoretic value for both players,
assuming reasonable computing resources, and
\item[\bu] \descr{ultra-strongly solved} if for all positions in a strongly solved
game, a strategy is known that improves the chances of achieving more
than the game-theoretic value against a fallible opponent.
\end{description}
\end{defn}

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent Theoretical size of Sim's game tree: $\mathsf{15! \approx 1.3\times 10^{12}}$.\\
In case of \Simp: $\mathsf{15! \times 2^{15-1} \approx 2.1\times 10^{16}}$.
\vfill
\noindent Practical size of their directed acyclic game graphs:
\begin{itemize}
\item[\bu] Sim: 2,309 non-isomorphic positions
\item[\bu] \Simp: 13,158 non-isomorphic positions
\end{itemize}
\vfill
\noindent $\mathbf{\Rightarrow}$ \ Strong solutions of Sim and \Simp\
are easily feasible.
\vfill
To \descr{ultra-strongly\/} solve Sim, we additionally need
a strategy for non-winning positions.  In our applet, we:
\begin{itemize}
\item[\bu] maximize static chance of opponent to make a mistake
\item[\bu] improve this strategy by learning the value of moves
through playing over the Internet
\end{itemize}
\bsection{$\mathbf{\Rightarrow}$ \ Sim and \Simp\ are ultra-strongly solved.}
\vfills

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mbox{}\\[-2em]
\begin{defn}\label{def:simn} \ \Simn:\\
\hspace*{\parindent}$G=K_{\Large \ramsey(n,n)},\ 
A=K_n$\/ ~played on~ \gramsey.
\end{defn}
\vfill
\noindent Problem: Despite much effort, only \ramsey(4,4)$\,=\,$18 is
known so far (conjecture \cite{McKay98} \ramsey(5,5)$\,=\hspace{-1.45ex}?\:\:$43 \ldots{}).
\vfill
\noindent Let us consider the game \descr{\Simf} played on a game
board $G$ having ${18\choose2}=153$ edges, the graph $A$ to avoid
being a tetrahedron. Unfortunately, we found that the number of
non-isomorphic game positions in \Simf\ is around
\descr{$\mathsf{10^{54}}$}.
\vfill
\noindent $\mathbf{\Rightarrow}$ \ There is
not much hope to even weakly solve any game \Simn\ and
even less so any game \Simnp\ with $n\geq 4$.
\vfills 

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bsection{The difficulty of games: another view}

\noindent Problem: \pspacec{}ness is a very coarse instrument to
measure the difficulty of combinatorial games: no statement about
particular instances are possible.

\bsection{$\mathbf{\Rightarrow}$ \ time-bounded Kolmogorov complexity of combinatorial game instances:}

\begin{defn}~~
The time bounded Kolmogorov complexity $K^t_G$ of a game instance $x$
(for example, $x=\gramsey(G,A,E^r_0,E^g_0)$) is defined~by
\[K^t_G(x)\:\de\:\min_p\:\sup_{y\,\epsilon\, s(x)}\:\inf_{s(x)}\;\{l(p)+ t(p,y)\},\] 
where $p$ is a program of length $l(p)$ that runs on input $y$ (e.g.,
$y=(E^r_i,E^g_i)$) in $t(p,y)$ steps on a universal Turing machine
$U$. $U$ has the three halting states\/ {\rm win}, \pto {\rm loss}, and\/
{\rm draw} such that the halting state of $U(p,y)=x(y)$ is the answer
of the decision problem for the first player in situation $y$ of game
$x$. The (not unique) sets $s(x)$ are recursively defined as follows:
\begin{eqnarray*}
s(x)   & \de & \bigcup_{i=0}^\infty F_i,\\
F_0    & \de & \{y_0\},
\end{eqnarray*}
where $y_0$ denotes the initial situation of $x$ (in the example,
$y_0=(E^r_0,E^g_0)$), and
\vfill
\[
F_{i+1} \:\de\: \bigcup_{y\,\in F_i} N(y)
\]
\vfills\pto
\newpage
\[
N(y) \:\de\: \left\{ \begin{array}{ll}
                 ~\{\} \quad \mbox{if } & G(\{y\})=\{\}\;\Or\\[.4ex]
                                       & G(G(\{y\}))=\{\}\\[3ex]

                 ~\makebox[1em][l]{$Y''\subseteq G(G(\{y\}))$\quad otherwise, where}\\[.4ex] 
                       & \exists\, y'\in G(\{y\})\:|\: x(y')=x(y)\;\And \\[.4ex]
                       & \forall\, y''\,\in G(\{y\}),~ y''\in Y''
                     \end{array}
\right.\]
\vfill
\noindent where
\vfill
\[
\begin{array}{ll}
G(Y) \de \{ y'\:|\:&\hspace*{-.4em}\exists\, y\in Y \mbox{ such that } y' \mbox{ is reachable}\\
                   &\hspace*{-.4em}\mbox{in one move from } y\}.
\end{array}
\]
\end{defn}
\vfill
\begin{conj}\label{conj:kolmo}
\[K^t_G({\rm Sim}_a)\ll K^t_G({\rm Sim})<K^t_G({\rm Sim}^+)\ll K^t_G({\rm Sim}^4)\]
\end{conj}
\vfills

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{conj}\label{conj:empty} 
\ Graph Ramsey games played on $(G,A,\{\},\{\})$ are \pspacec.
\end{conj}
\begin{conj} \ Graph Ramsey achievement games played on $(K_n,A,E^r,E^g)$
are tractable.
\end{conj}
\begin{conj}\label{conj:classic}
\ Graph Ramsey avoidance games played on $(K_k,K_n,E^r,E^g)\,$ where
$\:k\geq\ramsey(n,n)\:$ are \pspacec.
\end{conj}
\begin{conj} \ The graph Ramsey avoidance games played on 
$(K_{\scriptsize {\ramsey(n,n)}},K_n,\{\},\{\})$ are
2-\expspace-complete.
\end{conj}
\begin{conj} \ The high-score handling between the server and an unknown
remote client can be made tamper-proof for all practical purposes with
respect to client-cheating by an appropriate randomized algebraic
protocol.
\end{conj}

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bsection{Further remarks}
\begin{itemize}
\item[\bu] The proof of the complexity of \gramseyplus\ is, to our best
knowledge, the first \pspacec{}ness proof for a problem where the
number of decisions that can be taken at each alternation is not
predetermined. 
\item[\bu] Our results can be applied to a number of known abstract
and practical problems (detailed in the paper).
\item[\bu] Sim and \Simp\ are to be integrated in a role-playing 
game $\mathbf{\Rightarrow}$ \ ``cheats'' will be made impossible.
\item[\bu] Please try out our applet that plays Sim and \Simp\ on
\begin{center}{\color{SpringGreen}
http://www.dbai.tuwien.ac.at/proj/ramsey/}\end{center} so that it can
continue to become even better.
\end{itemize}

\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{../authordate1sml} 
%\bibliography{../ramsey}
\input{../cgrg.bbl}

\end{document}
