-#LyX 1.4.3 created this file. For more info see http://www.lyx.org/
-\lyxformat 245
+#LyX 1.6.5svn created this file. For more info see http://www.lyx.org/
+\lyxformat 345
\begin_document
\begin_header
\textclass beamer
}
\end_preamble
\options notes=show
+\use_default_options false
\language english
\inputencoding auto
-\fontscheme times
+\font_roman times
+\font_sans default
+\font_typewriter default
+\font_default_family default
+\font_sc false
+\font_osf false
+\font_sf_scale 100
+\font_tt_scale 100
+
\graphics default
\paperfontsize default
\spacing single
+\use_hyperref false
\papersize default
\use_geometry false
\use_amsmath 2
+\use_esint 0
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\papersides 1
\paperpagestyle default
\tracking_changes false
-\output_changes true
+\output_changes false
+\author ""
+\author ""
\end_header
\begin_body
\begin_layout Title
The Complexity of
-\newline
+\begin_inset Newline newline
+\end_inset
+
Finding Paths in Tournaments
\end_layout
\begin_layout Institute
International Computer Schience Institute
-\newline
+\begin_inset Newline newline
+\end_inset
+
Berkeley, California
\begin_inset OptArg
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
ICSI
\end_layout
\end_layout
\begin_layout Standard
-\begin_inset LatexCommand \tableofcontents{}
+\begin_inset CommandInset toc
+LatexCommand tableofcontents
\end_inset
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
[pausesections]
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
% Show the table of contents at the beginning
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
% of every subsection.
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
AtBeginSubsection[]{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
frame<handout:0>{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
frametitle{Outline}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
tableofcontents[current,currentsubsection]
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfuseimage{knight1}}{2pt}{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfuseimage{knight2}}{2pt}{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfuseimage{knight3}}{2pt}{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfuseimage{knight4}}{2pt}{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfarrowto}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<2->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A}{B}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A}{C}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D}{A}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C}{B}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B}{D}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C}{D}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Block
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{What is a Tournament?}
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<1->
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<2->
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<3->
\end_layout
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(2.5,1)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(5.5,1)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,-0.5)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,2.5)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{white}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$v_2$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$v_3$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$v_4$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$v_1$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfarrowto}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodesetsepstart{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodesetsepend{4pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A}{B}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A}{C}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D}{A}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C}{B}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B}{D}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D}{C}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<2->
\end_layout
\end_inset
-A
+A
+\color none
+
\color red
tournament
+\color none
+
\color inherit
- is a
+is a
\end_layout
\begin_deeper
\begin_layout Enumerate
with exactly one edge between
-\newline
+\begin_inset Newline newline
+\end_inset
+
any two different vertices.
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
[<+>]
\end_layout
\begin_layout ExampleBlock
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Applicatins in Ordering Theory}
\end_layout
\begin_layout Standard
Elements in a set need to be sorted.
-\newline
+\begin_inset Newline newline
+\end_inset
+
The comparison relation may be cyclic, however.
\end_layout
\begin_layout ExampleBlock
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Applications in Sociology}
\end_layout
\begin_deeper
\begin_layout Standard
Several candidates apply for a position.
-\newline
-Reviewers decide for any two candidates
- whom they prefer.
+\begin_inset Newline newline
+\end_inset
+
+Reviewers decide for any two candidates whom they prefer.
\end_layout
\begin_layout ExampleBlock
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Applications in Structural Complexity Theory}
\end_layout
\end_inset
.
-\newline
+\begin_inset Newline newline
+\end_inset
+
It chooses from any two words the one more likely to be in
\begin_inset Formula $f$
\end_inset
\begin_layout Block
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{
\backslash
par{}% because LyX inserts superfluous paragraphs
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_deeper
\begin_layout Itemize
-A
+A
+\color none
+
\color red
graph
-\color inherit
+\color none
+\color inherit
+
\begin_inset Formula $G=(V,E)$
\end_inset
-, a
+, a
+\color none
+
\color red
source
-\color inherit
+\color none
+\color inherit
+
\begin_inset Formula $s\in V$
\end_inset
- and a
+ and a
+\color none
+
\color red
target
-\color inherit
+\color none
+\color inherit
+
\begin_inset Formula $t\in V$
\end_inset
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<only@-9| visible@8->
\end_layout
\end_inset
-A
+A
+\color none
+
\color red
maximum distance
\color inherit
-\InsetSpace ~
+
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $d$
\end_inset
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<only@10->
\end_layout
\end_inset
-An
+An
+\color none
+
\color red
approximation ratio
-\color inherit
+\color none
+\color inherit
+
\begin_inset Formula $r>1$
\end_inset
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_deeper
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Columns
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
[t,onlytextwidth]
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout ExampleBlock
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Example Input}
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(3,1)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(5,1)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,0)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,2)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{white}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$t$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$s$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfarrowto}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodesetsepstart{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodesetsepend{4pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A}{B}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A}{C}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D}{A}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C}{B}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B}{D}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D}{C}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[left,center]{, $d=2$}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[left,center]{, $r=1.5$}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[left,center]{, $r=1.25$}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\end_deeper
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout ExampleBlock
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<only@3->{Example Output}
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<5-8,10->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(3,1)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(5,1)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,0)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,2)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{white}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$t$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$s$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfarrowto}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodesetsepstart{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodesetsepend{4pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A}{B}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A}{C}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D}{A}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C}{B}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B}{D}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D}{C}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
alert{``Yes''}}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\end_deeper
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Block
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Variants of Path Finding Problems}
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\end_layout
\begin_layout Description
-Reachability\InsetSpace ~
+Reachability
+\begin_inset space ~
+\end_inset
+
Problem:
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<2->
\end_layout
\begin_inset Formula $s$
\end_inset
- to\InsetSpace ~
+ to
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $t$
\end_inset
\end_layout
\begin_layout Description
-Construction\InsetSpace ~
+Construction
+\begin_inset space ~
+\end_inset
+
Problem:
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<4->
\end_layout
\begin_inset Formula $s$
\end_inset
- to\InsetSpace ~
+ to
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $t$
\end_inset
\end_layout
\begin_layout Description
-Optimization\InsetSpace ~
+Optimization
+\begin_inset space ~
+\end_inset
+
Problem:
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<6->
\end_layout
\begin_inset Formula $s$
\end_inset
- to\InsetSpace ~
+ to
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $t$
\end_inset
\end_layout
\begin_layout Description
-Distance\InsetSpace ~
+Distance
+\begin_inset space ~
+\end_inset
+
Problem:
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<8->
\end_layout
\begin_inset Formula $s$
\end_inset
- and\InsetSpace ~
+ and
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $t$
\end_inset
- at most\InsetSpace ~
+ at most
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $d$
\end_inset
\end_layout
\begin_layout Description
-Approximation\InsetSpace ~
+Approximation
+\begin_inset space ~
+\end_inset
+
Problem:
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<10->
\end_layout
\begin_inset Formula $s$
\end_inset
- to\InsetSpace ~
+ to
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $t$
\end_inset
of length
-\newline
+\begin_inset Newline newline
+\end_inset
+
approximately their distance.
\end_layout
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout BeginFrame
The Classes L and NL are Defined via
-\newline
+\begin_inset Newline newline
+\end_inset
+
Logspace Turing Machines
\end_layout
\begin_inset ERT
status open
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
uncover<2->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
tape{}{output tape (write only)}{10690836937182}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
uncover<3->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
log n)$ symbols}{}{42}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfuseimage{computer}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{structure}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfarrowto}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Block
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Deterministic logspace machines can compute}
\end_layout
\begin_layout Block
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Non-deterministic logspace machines can compute}
\end_layout
\end_deeper
\begin_layout BeginFrame
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<1>[label=hierarchy]
\end_layout
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.8pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Class P$}{black}{1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetdash{{2pt}}{0pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Class{NC}^2$}{black!50!structure}{2}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Class{NL}$}{black!50!structure}{3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Class{L}$}{black!50!structure}{4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Class{NC}^1}$}{black!50!structure}{5}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetdash{}{0pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Class{AC}^0}$}{black}{6}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{1.0pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{black}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxyline(-5,0)(5,0)
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Lang{reach}$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
operatorname{forest}}$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Lang{addition}$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Lang{parity}$}}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Lang{reach}$}}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
operatorname{path}}$}}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
operatorname{tourn}}$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
ignorespaces
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Lang{reach}$}}}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
operatorname{tourn}}$''}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\end_inset
-\newline
+\begin_inset Newline newline
+\end_inset
+
Limit the Circuit Depth
\end_layout
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
leftmargini{1em}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
[t]
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<2>
\end_layout
\begin_layout BeginFrame
All Variants of Finding Paths in Directed Graphs
-\newline
+\begin_inset Newline newline
+\end_inset
+
Are Equally Difficult
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<3>
\end_layout
\begin_layout BeginFrame
FindingPaths in Forests and Directed Paths is Easy,
-\newline
+\begin_inset Newline newline
+\end_inset
+
But Not Trivial
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<4>
\end_layout
\end_layout
\begin_layout Definition
-Let
+Let
+\color none
+
\color red
\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
\end_inset
+\color none
+
\color inherit
- contain all triples
+contain all triples
\begin_inset Formula $(T,s,t)$
\end_inset
\end_layout
\begin_layout Enumerate
-there exists a path from\InsetSpace ~
+there exists a path from
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $s$
\end_inset
- to\InsetSpace ~
+ to
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $t$
\end_inset
\begin_layout AlertBlock
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Implications}
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<5>
\end_layout
\begin_layout BeginFrame
Finding a Shortest Path Is as Difficult as
-\newline
+\begin_inset Newline newline
+\end_inset
+
the Distance Problem
\end_layout
\begin_layout Definition
-Let
+Let
+\color none
+
\color red
\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
\end_inset
+
+\color none
\color inherit
contain all tuples
\begin_inset Formula $s$
\end_inset
- and\InsetSpace ~
+ and
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $t$
\end_inset
- is at most\InsetSpace ~
+ is at most
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $d$
\end_inset
\end_layout
\begin_layout Standard
+\begin_inset space \hfill{}
+\end_inset
-\hfill
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Corollary
Shortest path in tournaments can be constructed
-\newline
-in logarithmic space, iff
-
+\begin_inset Newline newline
+\end_inset
+
+in logarithmic space, iff
\begin_inset Formula $\Class{L}=\Class{NL}$
\end_inset
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Columns
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
[t,onlytextwidth]
\end_layout
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
\begin_deeper
\begin_layout Enumerate
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<alert@1>
\end_layout
\begin_layout Enumerate
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<2-| alert@2-8>
\end_layout
\begin_layout Enumerate
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<9-| alert@9>
\end_layout
\end_inset
Query:
-\newline
+\begin_inset Newline newline
+\end_inset
+
\begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
\end_inset
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<10->
\end_layout
\begin_deeper
\begin_layout Enumerate
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<10-| alert@10-11>
\end_layout
\end_inset
-A path in\InsetSpace ~
+A path in
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $G$
\end_inset
induces
-\newline
-a length-3 path in\InsetSpace ~
+\begin_inset Newline newline
+\end_inset
+
+a length-3 path in
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $G'$
\end_inset
\begin_layout Enumerate
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<12-| alert@12-13>
\end_layout
\end_inset
-A length-3 path in\InsetSpace ~
+A length-3 path in
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $G'$
\end_inset
induces
-\newline
-a path in\InsetSpace ~
+\begin_inset Newline newline
+\end_inset
+
+a path in
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $G'$
\end_inset
\begin_layout Example
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(1,3.3)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(2,3.3)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(3,3.3)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,3.3)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{white}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$s$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$t$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfarrowto}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodesetsepstart{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodesetsepend{2pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B}{A}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B}{C}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C}{D}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
colon$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<2->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
colon$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(1,2.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(2,2.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(3,2.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,2.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(1,1.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(2,1.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(3,1.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,1.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(1,0.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(2,0.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(3,0.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,0.25)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(1,-.75)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(2,-.75)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(3,-.75)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfxy(4,-.75)}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
{
\backslash
color{white}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$s'$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfbox[center,center]{$t'$}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<8->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.4pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample!25!averagebackgroundcolor}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A2}{C1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A2}{D1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B2}{A1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B2}{C1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B2}{D1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C2}{D1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D2}{A1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D2}{B1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A3}{C2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A3}{D2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B3}{A2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B3}{C2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B3}{D2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C3}{D2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D3}{A2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D3}{B2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A4}{C3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A4}{D3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B4}{A3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B4}{C3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B4}{D3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C4}{D3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D4}{A3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D4}{B3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfarrowto}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A1}{B1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B1}{C1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C1}{D1}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A2}{B2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B2}{C2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C2}{D2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A3}{B3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B3}{C3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C3}{D3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A4}{B4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B4}{C4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C4}{D4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfclearstartarrow
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color{beamerexample}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<3->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color<3>{red}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B1}{A2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B2}{A3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B3}{A4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<4->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color<4>{red}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B1}{C2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B2}{C3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B3}{C4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<5->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color<5>{red}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C1}{D2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C2}{D3}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C3}{D4}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<6->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color<6>{red}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A1}{C2}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A2}{C3}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A3}{C4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
only<7->{
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
color<7>{red}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A1}{A2}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A2}{A3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{A3}{A4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B1}{B2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B2}{B3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{B3}{B4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C1}{C2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C2}{C3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{C3}{C4}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D1}{D2}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D2}{D3}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
pgfnodeconnline{D3}{D4}}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
}
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\end_layout
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<6>
\end_layout
\end_layout
\begin_layout Definition
-An
+An
+\color none
+
\color red
approximation scheme for
\begin_inset Formula $\Lang{tournament-shortest-path}$
\end_inset
+\color none
+
\color inherit
- gets as input
+gets as input
\end_layout
\begin_deeper
\begin_inset Formula $s$
\end_inset
- to\InsetSpace ~
+ to
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $t$
\end_inset
\end_deeper
\begin_layout BeginFrame
There Exists a Logspace Approximation Scheme for
-\newline
-the Tournament Shortest
- Path Problem
+\begin_inset Newline newline
+\end_inset
+
+the Tournament Shortest Path Problem
\end_layout
\begin_layout Theorem
\end_layout
\begin_layout Standard
+\begin_inset space \hfill{}
+\end_inset
-\hfill
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<7>
\end_layout
hierarchy
\end_layout
+\begin_layout EndFrame
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+If a frame includes a program listing, the frame needs to be marked as
+\begin_inset Quotes eld
+\end_inset
+
+fragile
+\begin_inset Quotes erd
+\end_inset
+
+.
+ This is not yet supported by LyX, so the frame is created using TeX code.
+ Note that the
+\backslash
+begin{frame}[fragile] needs to be preceeded by an
+\emph on
+EndFrame
+\emph default
+ environment.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{frame}[fragile]
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+frametitle{
+\end_layout
+
+\end_inset
+
+Just a frame with a program code listing
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+This is some program code:
+\end_layout
+
+\begin_layout Standard
+\begin_inset listings
+lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
+inline false
+status open
+
+\begin_layout Plain Layout
+
+def func(param):
+\end_layout
+
+\begin_layout Plain Layout
+
+ 'this is a python function'
+\end_layout
+
+\begin_layout Plain Layout
+
+ pass
+\end_layout
+
+\begin_layout Plain Layout
+
+def func(param):
+\end_layout
+
+\begin_layout Plain Layout
+
+'This is a German word: Tschüs'
+\end_layout
+
+\begin_layout Plain Layout
+
+pass
+\end_layout
+
+\begin_layout Plain Layout
+
+def func(param):
+\end_layout
+
+\begin_layout Plain Layout
+
+'this is a python function'
+\end_layout
+
+\begin_layout Plain Layout
+
+pass
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{frame}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
\begin_layout Section*
Summary
\end_layout
\begin_layout Block
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Summary}
\end_layout
\begin_deeper
\begin_layout Itemize
-Tournament
+Tournament
+\color none
+
\color red
reachability
+\color none
+
\color inherit
- is in
-\color red
+is in
+\color none
+\color red
+
\begin_inset Formula $\Class{AC}^{0}$
\end_inset
\end_layout
\begin_layout Itemize
-There exists a
+There exists a
+\color none
+
\color red
logspace approximation scheme
+\color none
+
\color inherit
- for
+for
+\color none
+
\color red
approximating
+\color none
+
\color inherit
- shortest paths in tournaments.
+shortest paths in tournaments.
\end_layout
\begin_layout Itemize
-Finding
+Finding
+\color none
+
\color red
shortest paths
+\color none
+
\color inherit
- in tournaments is
-\color red
+in tournaments is
+\color none
+\color red
+
\begin_inset Formula $\Class{NL}$
\end_inset
\begin_layout Block
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
{Outlook}
\end_layout
\begin_deeper
\begin_layout Itemize
The same results apply to graphs with
-\newline
+\begin_inset Newline newline
+\end_inset
+
bounded independence number.
-\hfill
+\begin_inset space \hfill{}
+\end_inset
+
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Itemize
The complexity of finding paths in undirected graphs
-\newline
+\begin_inset Newline newline
+\end_inset
+
is partly open.
-\hfill
+\begin_inset space \hfill{}
+\end_inset
+
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Standard
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\end_layout
\begin_layout Bibliography
+\begin_inset CommandInset bibitem
+LatexCommand bibitem
+key "Moon1968"
+
+\end_inset
+
+
+\begin_inset space ~
+\end_inset
-\bibitem {Moon1968}
-\InsetSpace ~
John Moon.
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
Holt, Rinehart, and Winston, 1968.
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\end_layout
\begin_layout Bibliography
+\begin_inset CommandInset bibitem
+LatexCommand bibitem
+key "NickelsenT2002"
+
+\end_inset
+
+
+\begin_inset space ~
+\end_inset
-\bibitem {NickelsenT2002}
-\InsetSpace ~
Arfst Nickelsen and Till Tantau.
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\end_layout
\begin_layout Bibliography
+\begin_inset CommandInset bibitem
+LatexCommand bibitem
+key "Tantau2004b"
+
+\end_inset
+
+
+\begin_inset space ~
+\end_inset
-\bibitem {Tantau2004b}
-\InsetSpace ~
Till Tantau
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Standard
\start_of_appendix
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout BeginFrame
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
[label=independence]
\end_layout
\end_layout
\begin_layout Definition
-The
+The
+\color none
+
\color red
independence number
-\color inherit
+\color none
+\color inherit
+
\begin_inset Formula $\alpha(G)$
\end_inset
of a directed graph
-\newline
+\begin_inset Newline newline
+\end_inset
+
is the maximum number of vertices we can pick,
-\newline
-such that
- there is no edge between them.
+\begin_inset Newline newline
+\end_inset
+
+such that there is no edge between them.
\end_layout
\begin_layout Example
\begin_layout BeginFrame
The Results for Tournaments also Apply to
-\newline
-Graphs With Bounded Independence
- Number
+\begin_inset Newline newline
+\end_inset
+
+Graphs With Bounded Independence Number
\end_layout
\begin_layout Theorem
-For each\InsetSpace ~
+For each
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
\end_inset
-,
+,
+\color none
+
\color red
reachability
+\color none
+
\color inherit
- in graphs with independence number
-\newline
-at most\InsetSpace ~
+in graphs with independence number
+\begin_inset Newline newline
+\end_inset
+
+at most
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
\end_inset
\end_layout
\begin_layout Theorem
-For each\InsetSpace ~
+For each
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
\end_inset
-, there exists a
+, there exists a
+\color none
+
\color red
logspace approximation scheme
+\color none
+
\color inherit
- for approximating the shortest path in graphs with independence number
- at most\InsetSpace ~
+for approximating the shortest path in graphs with independence number at
+ most
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
\end_inset
\end_layout
\begin_layout Theorem
-For each\InsetSpace ~
+For each
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
\end_inset
-, finding the
+, finding the
+\color none
+
\color red
shortest path
+\color none
+
\color inherit
- in graphs with independence number at most\InsetSpace ~
+in graphs with independence number at most
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
\end_inset
- is
+ is
+\color none
+
\color red
\begin_inset Formula $\Class{NL}$
\begin_layout BeginFrame
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
<1-2>[label=undirected]
\end_layout
\end_inset
The Complexity of Finding Paths in Undirected Graphs
-\newline
+\begin_inset Newline newline
+\end_inset
+
Is Party Unknown.
\end_layout
\begin_layout Itemize
the construction problem in logspace iff
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout Itemize
the optimization problem in logspace iff
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash
\begin_layout BeginFrame
\begin_inset ERT
-status inlined
+status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
[label=optimality]
\end_layout
\begin_deeper
\begin_layout Enumerate
Suppose the approximation scheme exists.
-\newline
+\begin_inset Newline newline
+\end_inset
+
We show
\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
\end_inset
\end_inset
.
-\newline
+\begin_inset Newline newline
+\end_inset
+
This needs space
\begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
\end_inset
\begin_inset ERT
status collapsed
-\begin_layout Standard
+\begin_layout Plain Layout
\backslash