summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx')
-rw-r--r--Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx3880
1 files changed, 3880 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx
new file mode 100644
index 00000000000..0d443181c8b
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx
@@ -0,0 +1,3880 @@
+#LyX 1.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 221
+\textclass beamer
+\begin_preamble
+\beamertemplateshadingbackground{red!5}{structure!5}
+
+\usepackage{beamerthemeshadow}
+\usepackage{pgfnodes,pgfarrows,pgfheaps}
+
+\beamertemplatetransparentcovereddynamicmedium
+
+
+\pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
+\logo{\pgfuseimage{icsi-logo}}
+
+
+
+
+\newcommand{\Class}[1]{\operatorname{\mathchoice
+ {\text{\small #1}}
+ {\text{\small #1}}
+ {\text{#1}}
+ {\text{#1}}}}
+
+\newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
+
+\newcommand{\tape}[3]{%
+ \color{structure!30!averagebackgroundcolor}
+ \pgfmoveto{\pgfxy(-0.5,0)}
+ \pgflineto{\pgfxy(-0.6,0.1)}
+ \pgflineto{\pgfxy(-0.4,0.2)}
+ \pgflineto{\pgfxy(-0.6,0.3)}
+ \pgflineto{\pgfxy(-0.4,0.4)}
+ \pgflineto{\pgfxy(-0.5,0.5)}
+ \pgflineto{\pgfxy(4,0.5)}
+ \pgflineto{\pgfxy(4.1,0.4)}
+ \pgflineto{\pgfxy(3.9,0.3)}
+ \pgflineto{\pgfxy(4.1,0.2)}
+ \pgflineto{\pgfxy(3.9,0.1)}
+ \pgflineto{\pgfxy(4,0)}
+ \pgfclosepath
+ \pgffill
+
+ \color{structure}
+ \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
+ \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
+
+ \color{black}
+ \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
+}
+
+\newcommand{\shorttape}[3]{%
+ \color{structure!30!averagebackgroundcolor}
+ \pgfmoveto{\pgfxy(-0.5,0)}
+ \pgflineto{\pgfxy(-0.6,0.1)}
+ \pgflineto{\pgfxy(-0.4,0.2)}
+ \pgflineto{\pgfxy(-0.6,0.3)}
+ \pgflineto{\pgfxy(-0.4,0.4)}
+ \pgflineto{\pgfxy(-0.5,0.5)}
+ \pgflineto{\pgfxy(1,0.5)}
+ \pgflineto{\pgfxy(1.1,0.4)}
+ \pgflineto{\pgfxy(0.9,0.3)}
+ \pgflineto{\pgfxy(1.1,0.2)}
+ \pgflineto{\pgfxy(0.9,0.1)}
+ \pgflineto{\pgfxy(1,0)}
+ \pgfclosepath
+ \pgffill
+
+ \color{structure}
+ \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
+ \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
+
+ \color{black}
+ \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
+}
+
+\pgfdeclareverticalshading{heap1}{\the\paperwidth}%
+ {color(0pt)=(black); color(1cm)=(structure!65!white)}
+\pgfdeclareverticalshading{heap2}{\the\paperwidth}%
+ {color(0pt)=(black); color(1cm)=(structure!55!white)}
+\pgfdeclareverticalshading{heap3}{\the\paperwidth}%
+ {color(0pt)=(black); color(1cm)=(structure!45!white)}
+\pgfdeclareverticalshading{heap4}{\the\paperwidth}%
+ {color(0pt)=(black); color(1cm)=(structure!35!white)}
+\pgfdeclareverticalshading{heap5}{\the\paperwidth}%
+ {color(0pt)=(black); color(1cm)=(structure!25!white)}
+\pgfdeclareverticalshading{heap6}{\the\paperwidth}%
+ {color(0pt)=(black); color(1cm)=(red!35!white)}
+
+\newcommand{\heap}[5]{%
+ \begin{pgfscope}
+ \color{#4}
+ \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
+ \pgfclip
+ \begin{pgfmagnify}{1}{#1}
+ \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
+ \end{pgfmagnify}
+ \end{pgfscope}
+ %\pgffill
+
+ \color{#4}
+ \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
+ \pgfstroke
+
+ \color{white}
+ \pgfheaplabel{\pgfxy(0,#1)}{#3}%
+}
+
+
+\newcommand{\langat}[2]{%
+ \color{black!30!beamerexample}
+ \pgfsetlinewidth{0.6pt}
+ \pgfsetendarrow{\pgfarrowdot}
+ \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
+ \color{beamerexample}
+ \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
+}
+
+\newcommand{\langatother}[2]{%
+ \color{black!30!beamerexample}
+ \pgfsetlinewidth{0.6pt}
+ \pgfsetendarrow{\pgfarrowdot}
+ \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
+ \color{beamerexample}
+ \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
+}
+
+
+\pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
+
+
+\pgfdeclareradialshading{graphnode}
+ {\pgfpoint{-3pt}{3.6pt}}%
+ {color(0cm)=(beamerexample!15);
+ color(2.63pt)=(beamerexample!75);
+ color(5.26pt)=(beamerexample!70!black);
+ color(7.6pt)=(beamerexample!50!black);
+ color(8pt)=(beamerexample!10!averagebackgroundcolor)}
+
+\newcommand{\graphnode}[2]{
+ \pgfnodecircle{#1}[virtual]{#2}{8pt}
+ \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
+}
+\end_preamble
+\options notes=show
+\language english
+\inputencoding auto
+\fontscheme times
+\graphics default
+\paperfontsize default
+\spacing single
+\papersize Default
+\paperpackage a4
+\use_geometry 0
+\use_amsmath 1
+\use_natbib 0
+\use_numerical_citations 0
+\paperorientation portrait
+\secnumdepth 2
+\tocdepth 2
+\paragraph_separation indent
+\defskip medskip
+\quotes_language english
+\quotes_times 2
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+
+\layout Title
+
+The Complexity of
+\newline
+Finding Paths in Tournaments
+\layout Author
+
+Till Tantau
+\layout Institute
+
+International Computer Schience Institute
+\newline
+Berkeley, California
+\begin_inset OptArg
+collapsed true
+
+\layout Standard
+
+ICSI
+\end_inset
+
+
+\layout Date
+
+January 30th, 2004
+\layout BeginFrame
+
+Outline
+\layout Standard
+
+
+\begin_inset LatexCommand \tableofcontents{}
+
+\end_inset
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+[pausesections]
+\end_inset
+
+
+\layout EndFrame
+
+\layout Standard
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+% Show the table of contents at the beginning
+\layout Standard
+% of every subsection.
+\layout Standard
+
+\backslash
+AtBeginSubsection[]{
+\layout Standard
+
+\backslash
+frame<handout:0>{
+\layout Standard
+
+\backslash
+frametitle{Outline}
+\layout Standard
+
+\backslash
+tableofcontents[current,currentsubsection]
+\layout Standard
+ }
+\layout Standard
+}
+\end_inset
+
+
+\layout Section
+
+Introduction
+\layout Subsection
+
+What are Tournaments?
+\layout BeginFrame
+
+Tournaments Consist of Jousts Between Knights
+\layout Columns
+
+\begin_deeper
+\layout Column
+
+5.75cm
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
+\layout Standard
+
+\backslash
+pgfnodebox{A}[virtual]{
+\backslash
+pgfxy(2,1)}{
+\backslash
+pgfuseimage{knight1}}{2pt}{2pt}
+\layout Standard
+
+\backslash
+pgfnodebox{B}[virtual]{
+\backslash
+pgfxy(6,1)}{
+\backslash
+pgfuseimage{knight2}}{2pt}{2pt}
+\layout Standard
+
+\backslash
+pgfnodebox{C}[virtual]{
+\backslash
+pgfxy(4,-1)}{
+\backslash
+pgfuseimage{knight3}}{2pt}{2pt}
+\layout Standard
+
+\backslash
+pgfnodebox{D}[virtual]{
+\backslash
+pgfxy(4,3)}{
+\backslash
+pgfuseimage{knight4}}{2pt}{2pt}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+only<3->{
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}}
+\layout Standard
+
+\backslash
+only<2->{
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A}{B}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A}{C}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D}{A}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C}{B}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B}{D}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C}{D}}
+\layout Standard
+
+\backslash
+end{pgfpicture}
+\end_inset
+
+
+\layout Column
+
+6cm
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{What is a Tournament?}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<1->
+\end_inset
+
+A group of knights.
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<2->
+\end_inset
+
+Every pair has a joust.
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<3->
+\end_inset
+
+In every joust one knight wins.
+\end_deeper
+\end_deeper
+\layout BeginFrame
+
+Tournaments are Complete Directed Graphs
+\layout Columns
+
+\begin_deeper
+\layout Column
+
+5cm
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\layout Standard
+
+\backslash
+graphnode{A}{
+\backslash
+pgfxy(2.5,1)}
+\layout Standard
+
+\backslash
+graphnode{B}{
+\backslash
+pgfxy(5.5,1)}
+\layout Standard
+
+\backslash
+graphnode{C}{
+\backslash
+pgfxy(4,-0.5)}
+\layout Standard
+
+\backslash
+graphnode{D}{
+\backslash
+pgfxy(4,2.5)}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{white}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{A}}{
+\backslash
+pgfbox[center,center]{$v_2$}}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{B}}{
+\backslash
+pgfbox[center,center]{$v_3$}}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{C}}{
+\backslash
+pgfbox[center,center]{$v_4$}}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D}}{
+\backslash
+pgfbox[center,center]{$v_1$}}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\layout Standard
+
+\backslash
+pgfnodesetsepstart{2pt}
+\layout Standard
+
+\backslash
+pgfnodesetsepend{4pt}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A}{B}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A}{C}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D}{A}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C}{B}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B}{D}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D}{C}
+\layout Standard
+
+\backslash
+end{pgfpicture}
+\end_inset
+
+
+\layout Column
+
+6cm
+\layout Definition
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<2->
+\end_inset
+
+A
+\color red
+tournament
+\color default
+ is a
+\begin_deeper
+\layout Enumerate
+
+directed graphs,
+\layout Enumerate
+
+with exactly one edge between
+\newline
+any two different vertices.
+\end_deeper
+\end_deeper
+\layout BeginFrame
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+[<+>]
+\end_inset
+
+Tournaments Arise Naturally in Different Situations
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Applicatins in Ordering Theory}
+\end_inset
+
+
+\begin_deeper
+\layout Standard
+
+Elements in a set need to be sorted.
+
+\newline
+The comparison relation may be cyclic, however.
+\end_deeper
+\layout Separator
+
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Applications in Sociology}
+\end_inset
+
+
+\begin_deeper
+\layout Standard
+
+Several candidates apply for a position.
+\newline
+Reviewers decide for any two candidates whom they prefer.
+
+\end_deeper
+\layout Separator
+
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Applications in Structural Complexity Theory}
+\end_inset
+
+
+\begin_deeper
+\layout Standard
+
+A language
+\begin_inset Formula $L$
+\end_inset
+
+ is given and a selector function
+\begin_inset Formula $f$
+\end_inset
+
+.
+\newline
+It chooses from any two words the one more likely to be in
+\begin_inset Formula $f$
+\end_inset
+
+.
+\end_deeper
+\layout Subsection
+
+What Does ``Finding Paths'' Mean?
+\layout BeginFrame
+
+``Finding Paths'' is Ambiguous
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{
+\backslash
+strut Input for
+\backslash
+ignorespaces
+\backslash
+def
+\backslash
+par{}% because LyX inserts superfluous paragraphs
+\layout Standard
+
+\backslash
+only<1>{Path Finding Problems}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+only<2-3>{$
+\backslash
+Lang{reach}$}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+only<4-5>{the Construction Problem}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+only<6-7>{the Optimization Problem}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+only<8-9>{$
+\backslash
+Lang{distance}$}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+only<10->{the Approximation Problem}}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+A
+\color red
+graph
+\color default
+
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+, a
+\color red
+source
+\color default
+
+\begin_inset Formula $s\in V$
+\end_inset
+
+ and a
+\color red
+target
+\color default
+
+\begin_inset Formula $t\in V$
+\end_inset
+
+.
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<only@-9| visible@8->
+\end_inset
+
+A
+\color red
+maximum distance
+\color default
+\SpecialChar ~
+
+\begin_inset Formula $d$
+\end_inset
+
+.
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+phantom{p}
+\end_inset
+
+
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<only@10->
+\end_inset
+
+An
+\color red
+approximation ratio
+\color default
+
+\begin_inset Formula $r>1$
+\end_inset
+
+.
+\end_deeper
+\layout Standard
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+nointerlineskip
+\end_inset
+
+
+\layout Overprint
+
+\begin_deeper
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+onslide<1,3,5,7,9,11-12>
+\end_inset
+
+
+\layout Columns
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+[t,onlytextwidth]
+\end_inset
+
+
+\begin_deeper
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+alt<1-2>{
+\backslash
+column{
+\backslash
+textwidth}}{
+\backslash
+column{5cm}}
+\end_inset
+
+
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Example Input}
+\end_inset
+
+
+\begin_deeper
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\layout Standard
+
+\backslash
+graphnode{A}{
+\backslash
+pgfxy(3,1)}
+\layout Standard
+
+\backslash
+graphnode{B}{
+\backslash
+pgfxy(5,1)}
+\layout Standard
+
+\backslash
+graphnode{C}{
+\backslash
+pgfxy(4,0)}
+\layout Standard
+
+\backslash
+graphnode{D}{
+\backslash
+pgfxy(4,2)}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{white}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{B}}{
+\backslash
+pgfbox[center,center]{$t$}}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D}}{
+\backslash
+pgfbox[center,center]{$s$}}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\layout Standard
+
+\backslash
+pgfnodesetsepstart{2pt}
+\layout Standard
+
+\backslash
+pgfnodesetsepend{4pt}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A}{B}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A}{C}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D}{A}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C}{B}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B}{D}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D}{C}
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<9> {
+\backslash
+pgfputat{
+\backslash
+pgfxy(5.3,1)}{
+\backslash
+pgfbox[left,center]{, $d=2$}}}
+\layout Standard
+
+\backslash
+only<11>{
+\backslash
+pgfputat{
+\backslash
+pgfxy(5.3,1)}{
+\backslash
+pgfbox[left,center]{, $r=1.5$}}}
+\layout Standard
+
+\backslash
+only<12>{
+\backslash
+pgfputat{
+\backslash
+pgfxy(5.3,1)}{
+\backslash
+pgfbox[left,center]{, $r=1.25$}}}
+\layout Standard
+
+\backslash
+end{pgfpicture}
+\end_inset
+
+
+\end_deeper
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+only<3->{
+\backslash
+column{5cm}}
+\end_inset
+
+
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<only@3->{Example Output}
+\end_inset
+
+
+\begin_deeper
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
+\layout Standard
+
+\backslash
+only<5-8,10->{
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\layout Standard
+
+\backslash
+graphnode{A}{
+\backslash
+pgfxy(3,1)}
+\layout Standard
+
+\backslash
+graphnode{B}{
+\backslash
+pgfxy(5,1)}
+\layout Standard
+
+\backslash
+graphnode{C}{
+\backslash
+pgfxy(4,0)}
+\layout Standard
+
+\backslash
+graphnode{D}{
+\backslash
+pgfxy(4,2)}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{white}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{B}}{
+\backslash
+pgfbox[center,center]{$t$}}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D}}{
+\backslash
+pgfbox[center,center]{$s$}}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\layout Standard
+
+\backslash
+pgfnodesetsepstart{2pt}
+\layout Standard
+
+\backslash
+pgfnodesetsepend{4pt}
+\layout Standard
+
+\layout Standard
+
+\backslash
+alert<7,12>{
+\backslash
+pgfnodeconnline{A}{B}}
+\layout Standard
+
+\backslash
+alert<5,11>{
+\backslash
+pgfnodeconnline{A}{C}}
+\layout Standard
+
+\backslash
+alert<5,7,11-12>{
+\backslash
+pgfnodeconnline{D}{A}}
+\layout Standard
+
+\backslash
+alert<5,11>{
+\backslash
+pgfnodeconnline{C}{B}}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B}{D}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D}{C}
+\layout Standard
+ }
+\layout Standard
+
+\backslash
+only<3,9>{
+\backslash
+pgfputat{
+\backslash
+pgfxy(2.75,1)}{
+\backslash
+pgfbox[left,center]{
+\backslash
+alert{``Yes''}}}}
+\layout Standard
+
+\backslash
+end{pgfpicture}
+\end_inset
+
+
+\end_deeper
+\end_deeper
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+onslide<2,4,6,8,10>
+\end_inset
+
+
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Variants of Path Finding Problems}
+\end_inset
+
+
+\begin_deeper
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+usedescriptionitemofwidthas{Approximation Problem:}
+\end_inset
+
+
+\layout Description
+
+Reachability\SpecialChar ~
+Problem:
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<2->
+\end_inset
+
+Is there a path from
+\begin_inset Formula $s$
+\end_inset
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset
+
+?
+\layout Description
+
+Construction\SpecialChar ~
+Problem:
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<4->
+\end_inset
+
+Construct a path from
+\begin_inset Formula $s$
+\end_inset
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset
+
+?
+\layout Description
+
+Optimization\SpecialChar ~
+Problem:
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<6->
+\end_inset
+
+Construct a shortest path from
+\begin_inset Formula $s$
+\end_inset
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset
+
+.
+\layout Description
+
+Distance\SpecialChar ~
+Problem:
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<8->
+\end_inset
+
+Is the distance of
+\begin_inset Formula $s$
+\end_inset
+
+ and\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset
+
+ at most\SpecialChar ~
+
+\begin_inset Formula $d$
+\end_inset
+
+?
+\layout Description
+
+Approximation\SpecialChar ~
+Problem:
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<10->
+\end_inset
+
+Construct a path from
+\begin_inset Formula $s$
+\end_inset
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset
+
+ of length
+\newline
+approximately their distance.
+\end_deeper
+\end_deeper
+\layout Section
+
+Review
+\layout Subsection
+
+Standard Complexity Classes
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+pgfdeclaremask{computer-mask}{beamer-g4-mask}
+\backslash
+pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer-g4}
+\end_inset
+
+
+\layout BeginFrame
+
+The Classes L and NL are Defined via
+\newline
+Logspace Turing Machines
+\layout Standard
+
+
+\begin_inset ERT
+status Open
+
+\layout Standard
+
+\backslash
+begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(0,4)}{
+\backslash
+tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
+\layout Standard
+
+\backslash
+uncover<2->{
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(0,0.5)}{
+\backslash
+tape{}{output tape (write only)}{10690836937182}}}
+\layout Standard
+
+\backslash
+uncover<3->{
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(7,2)}{
+\backslash
+shorttape{work tape (read/write), $O(
+\backslash
+log n)$ symbols}{}{42}}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(1.75,2.5)}{
+\backslash
+pgfbox[center,center]{
+\backslash
+pgfuseimage{computer}}}
+\layout Standard
+ }
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{structure}
+\layout Standard
+
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\layout Standard
+
+\backslash
+pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
+\layout Standard
+
+\backslash
+uncover<2->{
+\backslash
+pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
+\layout Standard
+
+\backslash
+uncover<3->{
+\backslash
+pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
+\layout Standard
+
+\backslash
+end{pgfpicture}
+\end_inset
+
+
+\layout BeginFrame
+
+Logspace Turing Machines Are Quite Powerful
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Deterministic logspace machines can compute}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+addition, multiplication, and even division
+\layout Itemize
+
+reductions used in completeness proofs,
+\layout Itemize
+
+reachability in forests.
+\end_deeper
+\layout Pause
+
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Non-deterministic logspace machines can compute}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+reachability in graphs,
+\layout Itemize
+
+non-reachability in graphs,
+\layout Itemize
+
+satisfiability with two literals per clause.
+\end_deeper
+\layout BeginFrame
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<1>[label=hierarchy]
+\end_inset
+
+The Complexity Class Hierarchy
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.8pt}
+\layout Standard
+
+\backslash
+heap{5.5}{3.5}{$
+\backslash
+Class P$}{black}{1}
+\layout Standard
+
+\backslash
+pgfsetdash{{2pt}}{0pt}
+\layout Standard
+
+\backslash
+only<2->{
+\backslash
+heap{4.5}{3}{$
+\backslash
+Class{NC}^2$}{black!50!structure}{2}}
+\layout Standard
+
+\backslash
+heap{3.5}{2.5}{$
+\backslash
+Class{NL}$}{black!50!structure}{3}
+\layout Standard
+
+\backslash
+heap{2.5}{2}{$
+\backslash
+Class{L}$}{black!50!structure}{4}
+\layout Standard
+
+\backslash
+only<2->{
+\backslash
+heap{1.75}{1.5}{$
+\backslash
+vphantom{A}
+\backslash
+smash{
+\backslash
+Class{NC}^1}$}{black!50!structure}{5}}
+\layout Standard
+
+\backslash
+pgfsetdash{}{0pt}
+\layout Standard
+
+\backslash
+only<2->{
+\backslash
+heap{1.1}{1}{$
+\backslash
+vphantom{A}
+\backslash
+smash{
+\backslash
+Class{AC}^0}$}{black}{6}}
+\layout Standard
+
+\layout Standard
+
+\backslash
+pgfsetlinewidth{1.0pt}
+\layout Standard
+
+\backslash
+color{black}
+\layout Standard
+
+\backslash
+pgfxyline(-5,0)(5,0)
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<1-2>{
+\backslash
+langat{3.375}{$
+\backslash
+Lang{reach}$}}
+\layout Standard
+
+\backslash
+only<1-2>{
+\backslash
+langat{2.375}{$
+\backslash
+Lang{reach}_{
+\backslash
+operatorname{forest}}$}}
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<2>{
+\backslash
+langat{0.975}{$
+\backslash
+Lang{addition}$}}
+\layout Standard
+
+\backslash
+only<2>{
+\backslash
+langatother{1.6}{
+\backslash
+vbox{
+\backslash
+hbox{$
+\backslash
+Lang{division}$,}
+\backslash
+hbox{$
+\backslash
+Lang{parity}$}}}}
+\layout Standard
+
+\backslash
+only<3-5>{
+\backslash
+langat{3.375}{
+\backslash
+vbox{
+\backslash
+hbox{$
+\backslash
+Lang{distance}$,}
+\backslash
+hbox{$
+\backslash
+Lang{reach}$}}}}
+\layout Standard
+
+\backslash
+only<4->{
+\backslash
+langatother{2.375}{
+\backslash
+vbox{
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+hbox{$
+\backslash
+Lang{distance}_{
+\backslash
+operatorname{forest}}$,}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+hbox{$
+\backslash
+Lang{reach}_{
+\backslash
+operatorname{forest}}$,}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+hbox{$
+\backslash
+Lang{distance}_{
+\backslash
+operatorname{path}}$,}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+hbox{$
+\backslash
+Lang{reach}_{
+\backslash
+operatorname{path}}$}}}}
+\layout Standard
+
+\backslash
+only<5->{
+\backslash
+langat{0.975}{$
+\backslash
+Lang{reach}_{
+\backslash
+operatorname{tourn}}$}}
+\layout Standard
+
+\backslash
+only<6->{
+\backslash
+langat{3.375}{
+\backslash
+vbox{
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+hbox{$
+\backslash
+Lang{distance}_{
+\backslash
+operatorname{tourn}}$,}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+hbox{$
+\backslash
+Lang{distance}$,}
+\backslash
+ignorespaces
+\layout Standard
+
+\backslash
+hbox{$
+\backslash
+Lang{reach}$}}}}
+\layout Standard
+
+\backslash
+only<7->{
+\backslash
+pgfsetdash{{1pt}}{0pt}
+\backslash
+langat{2.375}{``$
+\backslash
+Lang{approx}_{
+\backslash
+operatorname{tourn}}$''}}
+\layout Standard
+
+\backslash
+end{pgfpicture}
+\end_inset
+
+
+\layout BeginFrame
+
+The Circuit Complexity Classes AC
+\begin_inset Formula $^{0}$
+\end_inset
+
+, NC
+\begin_inset Formula $^{1}$
+\end_inset
+
+, and NC
+\begin_inset Formula $^{2}$
+\end_inset
+
+
+\newline
+Limit the Circuit Depth
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+setlength
+\backslash
+leftmargini{1em}
+\layout Standard
+
+\backslash
+nointerlineskip
+\end_inset
+
+
+\layout Columns
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+[t]
+\end_inset
+
+
+\begin_deeper
+\layout Column
+
+3.6cm
+\layout Block
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+{
+\end_inset
+
+Circuit Class
+\begin_inset Formula $\Class{AC}^{0}$
+\end_inset
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+
+\begin_inset Formula $O(1)$
+\end_inset
+
+ depth
+\layout Itemize
+
+unbounded fan-in
+\end_deeper
+\layout Examples
+
+\begin_deeper
+\layout Itemize
+
+
+\begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
+\end_inset
+
+.
+\layout Itemize
+
+
+\begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
+\end_inset
+
+.
+\end_deeper
+\layout Pause
+
+\layout Column
+
+3.6cm
+\layout Block
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+{
+\end_inset
+
+Circuit Class
+\begin_inset Formula $\Class{NC}^{1}$
+\end_inset
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ depth
+\layout Itemize
+
+bounded fan-in
+\end_deeper
+\layout Examples
+
+\begin_deeper
+\layout Itemize
+
+
+\begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\layout Itemize
+
+
+\begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\layout Itemize
+
+
+\begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\end_deeper
+\layout Pause
+
+\layout Column
+
+3.6cm
+\layout Block
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+{
+\end_inset
+
+Circuit Class
+\begin_inset Formula $\Class{NC}^{2}$
+\end_inset
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+
+\begin_inset Formula $O(\log^{2}n)$
+\end_inset
+
+ depth
+\layout Itemize
+
+bounded fan-in
+\end_deeper
+\layout Examples
+
+\begin_deeper
+\layout Itemize
+
+
+\begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
+\end_inset
+
+.
+\end_deeper
+\end_deeper
+\layout AgainFrame
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<2>
+\end_inset
+
+hierarchy
+\layout Subsection
+
+Standard Complexity Results on Finding Paths
+\layout BeginFrame
+
+All Variants of Finding Paths in Directed Graphs
+\newline
+Are Equally Difficult
+\layout Fact
+
+
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+ and
+\begin_inset Formula $\Lang{distance}$
+\end_inset
+
+ are
+\begin_inset Formula $\Class{NL}$
+\end_inset
+
+-complete.
+
+\layout Pause
+
+\layout Corollary
+
+For directed graphs, we can solve
+\begin_deeper
+\layout Itemize
+
+the reachability problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\layout Itemize
+
+the construction problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\layout Itemize
+
+the optimization problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\layout Itemize
+
+the approximation problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_deeper
+\layout AgainFrame
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<3>
+\end_inset
+
+hierarchy
+\layout BeginFrame
+
+FindingPaths in Forests and Directed Paths is Easy,
+\newline
+But Not Trivial
+\layout Fact
+
+
+\begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
+\end_inset
+
+ and
+\begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
+\end_inset
+
+ are
+\begin_inset Formula $\Class{L}$
+\end_inset
+
+-complete.
+\layout Separator
+
+\layout Fact
+
+
+\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
+\end_inset
+
+ and
+\begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
+\end_inset
+
+ are
+\begin_inset Formula $\Class{L}$
+\end_inset
+
+-complete.
+\layout AgainFrame
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<4>
+\end_inset
+
+hierarchy
+\layout Section
+
+Finding Paths in Tournaments
+\layout Subsection
+
+Complexity of: Does a Path Exist?
+\layout BeginFrame
+
+Definition of the Tournament Reachability Problem
+\layout Definition
+
+Let
+\color red
+
+\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
+\end_inset
+
+
+\color default
+ contain all triples
+\begin_inset Formula $(T,s,t)$
+\end_inset
+
+ such that
+\begin_deeper
+\layout Enumerate
+
+
+\begin_inset Formula $T=(V,E)$
+\end_inset
+
+ is a tournament and
+\layout Enumerate
+
+there exists a path from\SpecialChar ~
+
+\begin_inset Formula $s$
+\end_inset
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset
+
+.
+\end_deeper
+\layout BeginFrame
+
+The Tournament Reachability Problem is Very Easy
+\layout Theorem
+
+
+\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
+\end_inset
+
+.
+\layout Pause
+
+\layout AlertBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Implications}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+The problem is
+\begin_inset Quotes eld
+\end_inset
+
+easier
+\begin_inset Quotes erd
+\end_inset
+
+ than
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+ and even
+\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
+\end_inset
+
+.
+\layout Itemize
+
+
+\begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
+\end_inset
+
+.
+\end_deeper
+\layout AgainFrame
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<5>
+\end_inset
+
+hierarchy
+\layout Subsection
+
+Complexity of: Construct a Shortest Path
+\layout BeginFrame
+
+Finding a Shortest Path Is as Difficult as
+\newline
+the Distance Problem
+\layout Definition
+
+Let
+\color red
+
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+
+\color default
+contain all tuples
+\begin_inset Formula $(T,s,t,d)$
+\end_inset
+
+ such that
+\begin_deeper
+\layout Enumerate
+
+
+\begin_inset Formula $T=(V,E)$
+\end_inset
+
+ is a tournament in which
+\layout Enumerate
+
+the distance of
+\begin_inset Formula $s$
+\end_inset
+
+ and\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset
+
+ is at most\SpecialChar ~
+
+\begin_inset Formula $d$
+\end_inset
+
+.
+\end_deeper
+\layout BeginFrame
+
+The Tournament Distance Problem is Hard
+\layout Theorem
+
+
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+ is
+\begin_inset Formula $\Class{NL}$
+\end_inset
+
+-complete.
+\layout Standard
+
+
+\hfill
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+hyperlink{hierarchy<6>}{
+\backslash
+beamerskipbutton{Skip Proof}}
+\end_inset
+
+
+\layout Pause
+
+\layout Corollary
+
+Shortest path in tournaments can be constructed
+\newline
+in logarithmic space, iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\layout Pause
+
+\layout Corollary
+
+
+\begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+.
+\layout BeginFrame
+
+Proof That
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+ is NL-complete
+\layout Standard
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+nointerlineskip
+\end_inset
+
+
+\layout Columns
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+[t,onlytextwidth]
+\end_inset
+
+
+\begin_deeper
+\layout Column
+
+5.7cm
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+setlength
+\backslash
+leftmargini{1.5em}
+\end_inset
+
+
+\layout Block
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+{
+\end_inset
+
+Reduce
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+ to
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+}
+\end_inset
+
+
+\begin_deeper
+\layout Enumerate
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<alert@1>
+\end_inset
+
+Is input
+\begin_inset Formula $(G,s,t)$
+\end_inset
+
+ in
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+?
+\layout Enumerate
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<2-| alert@2-8>
+\end_inset
+
+Map
+\begin_inset Formula $G$
+\end_inset
+
+ to
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\layout Enumerate
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<9-| alert@9>
+\end_inset
+
+Query:
+\newline
+
+\begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+?
+\end_deeper
+\layout Separator
+
+\layout Block
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+{
+\end_inset
+
+Correctness
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+}
+\end_inset
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<10->
+\end_inset
+
+
+\begin_deeper
+\layout Enumerate
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<10-| alert@10-11>
+\end_inset
+
+A path in\SpecialChar ~
+
+\begin_inset Formula $G$
+\end_inset
+
+ induces
+\newline
+a length-3 path in\SpecialChar ~
+
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\layout Enumerate
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<12-| alert@12-13>
+\end_inset
+
+A length-3 path in\SpecialChar ~
+
+\begin_inset Formula $G'$
+\end_inset
+
+ induces
+\newline
+a path in\SpecialChar ~
+
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_deeper
+\layout Column
+
+4.5cm
+\layout Example
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\layout Standard
+
+\backslash
+graphnode{A}{
+\backslash
+pgfxy(1,3.3)}
+\layout Standard
+
+\backslash
+graphnode{B}{
+\backslash
+pgfxy(2,3.3)}
+\layout Standard
+
+\backslash
+graphnode{C}{
+\backslash
+pgfxy(3,3.3)}
+\layout Standard
+
+\backslash
+graphnode{D}{
+\backslash
+pgfxy(4,3.3)}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{white}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{A}}{
+\backslash
+pgfbox[center,center]{$s$}}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D}}{
+\backslash
+pgfbox[center,center]{$t$}}
+\layout Standard
+
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\layout Standard
+
+\backslash
+pgfnodesetsepstart{2pt}
+\layout Standard
+
+\backslash
+pgfnodesetsepend{2pt}
+\layout Standard
+
+\backslash
+alert<3>{
+\backslash
+pgfnodeconnline{B}{A}}
+\layout Standard
+
+\backslash
+alert<4>{
+\backslash
+pgfnodeconnline{B}{C}}
+\layout Standard
+
+\backslash
+alert<5,10-11,13>{
+\backslash
+pgfnodeconnline{C}{D}}
+\layout Standard
+
+\backslash
+alert<6,10-11,13>{
+\backslash
+pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
+\layout Standard
+
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(0,3.3)}{
+\backslash
+pgfbox[left,center]{$G
+\backslash
+colon$}}
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<2->{
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(0,2.25)}{
+\backslash
+pgfbox[left,center]{$G'
+\backslash
+colon$}}
+\layout Standard
+
+\backslash
+graphnode{A1}{
+\backslash
+pgfxy(1,2.25)}
+\layout Standard
+
+\backslash
+graphnode{B1}{
+\backslash
+pgfxy(2,2.25)}
+\layout Standard
+
+\backslash
+graphnode{C1}{
+\backslash
+pgfxy(3,2.25)}
+\layout Standard
+
+\backslash
+graphnode{D1}{
+\backslash
+pgfxy(4,2.25)}
+\layout Standard
+
+\layout Standard
+
+\backslash
+graphnode{A2}{
+\backslash
+pgfxy(1,1.25)}
+\layout Standard
+
+\backslash
+graphnode{B2}{
+\backslash
+pgfxy(2,1.25)}
+\layout Standard
+
+\backslash
+graphnode{C2}{
+\backslash
+pgfxy(3,1.25)}
+\layout Standard
+
+\backslash
+graphnode{D2}{
+\backslash
+pgfxy(4,1.25)}
+\layout Standard
+
+\backslash
+graphnode{A3}{
+\backslash
+pgfxy(1,0.25)}
+\layout Standard
+
+\backslash
+graphnode{B3}{
+\backslash
+pgfxy(2,0.25)}
+\layout Standard
+
+\backslash
+graphnode{C3}{
+\backslash
+pgfxy(3,0.25)}
+\layout Standard
+
+\backslash
+graphnode{D3}{
+\backslash
+pgfxy(4,0.25)}
+\layout Standard
+
+\backslash
+graphnode{A4}{
+\backslash
+pgfxy(1,-.75)}
+\layout Standard
+
+\backslash
+graphnode{B4}{
+\backslash
+pgfxy(2,-.75)}
+\layout Standard
+
+\backslash
+graphnode{C4}{
+\backslash
+pgfxy(3,-.75)}
+\layout Standard
+
+\backslash
+graphnode{D4}{
+\backslash
+pgfxy(4,-.75)}
+\layout Standard
+ {
+\backslash
+color{white}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{A1}}{
+\backslash
+pgfbox[center,center]{$s'$}}
+\layout Standard
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D4}}{
+\backslash
+pgfbox[center,center]{$t'$}}
+\layout Standard
+ }}
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<8->{
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.4pt}
+\layout Standard
+
+\backslash
+color{beamerexample!25!averagebackgroundcolor}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A2}{C1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A2}{D1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B2}{A1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B2}{C1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B2}{D1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C2}{D1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D2}{A1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D2}{B1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A3}{C2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A3}{D2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B3}{A2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B3}{C2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B3}{D2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C3}{D2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D3}{A2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D3}{B2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A4}{C3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A4}{D3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B4}{A3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B4}{C3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B4}{D3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C4}{D3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D4}{A3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D4}{B3}
+\layout Standard
+
+\layout Standard
+
+\backslash
+pgfsetstartarrow{
+\backslash
+pgfarrowto}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A1}{B1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B1}{C1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C1}{D1}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A2}{B2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B2}{C2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C2}{D2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A3}{B3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B3}{C3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C3}{D3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A4}{B4}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B4}{C4}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C4}{D4}
+\layout Standard
+
+\layout Standard
+
+\backslash
+pgfclearstartarrow
+\layout Standard
+
+\backslash
+pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
+\layout Standard
+
+\backslash
+pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
+\layout Standard
+
+\backslash
+color{beamerexample}
+\layout Standard
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\layout Standard
+ }
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<3->{
+\layout Standard
+
+\backslash
+color<3>{red}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B1}{A2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B2}{A3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B3}{A4}
+\layout Standard
+ }
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<4->{
+\layout Standard
+
+\backslash
+color<4>{red}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B1}{C2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B2}{C3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B3}{C4}
+\layout Standard
+ }
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<5->{
+\layout Standard
+
+\backslash
+color<5>{red}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C1}{D2}
+\layout Standard
+
+\backslash
+alert<11>{
+\backslash
+pgfnodeconnline{C2}{D3}}
+\layout Standard
+
+\backslash
+alert<12-13>{
+\backslash
+pgfnodeconnline{C3}{D4}}
+\layout Standard
+ }
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<6->{
+\layout Standard
+
+\backslash
+color<6>{red}
+\layout Standard
+
+\backslash
+alert<11>{
+\backslash
+pgfnodeconnline{A1}{C2}}
+\layout Standard
+
+\backslash
+alert<12-13>{
+\backslash
+pgfnodeconnline{A2}{C3}}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A3}{C4}
+\layout Standard
+ }
+\layout Standard
+
+\layout Standard
+
+\backslash
+only<7->{
+\layout Standard
+
+\backslash
+color<7>{red}
+\layout Standard
+
+\backslash
+alert<12-13>{
+\backslash
+pgfnodeconnline{A1}{A2}}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A2}{A3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{A3}{A4}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B1}{B2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B2}{B3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{B3}{B4}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C1}{C2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C2}{C3}
+\layout Standard
+
+\backslash
+pgfnodeconnline{C3}{C4}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D1}{D2}
+\layout Standard
+
+\backslash
+pgfnodeconnline{D2}{D3}
+\layout Standard
+
+\backslash
+alert<11>{
+\backslash
+pgfnodeconnline{D3}{D4}}
+\layout Standard
+ }
+\layout Standard
+
+\backslash
+end{pgfpicture}
+\end_inset
+
+
+\end_deeper
+\layout AgainFrame
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<6>
+\end_inset
+
+hierarchy
+\layout Subsection
+
+Complexity of: Approximating the Shortest Path
+\layout BeginFrame
+
+Approximators Compute Paths that Are Nearly As Short As a Shortest Path
+\layout Definition
+
+An
+\color red
+approximation scheme for
+\begin_inset Formula $\Lang{tournament-shortest-path}$
+\end_inset
+
+
+\color default
+ gets as input
+\begin_deeper
+\layout Enumerate
+
+a tuple
+\begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
+\end_inset
+
+ and
+\layout Enumerate
+
+a number
+\begin_inset Formula $r>1$
+\end_inset
+
+.
+\layout Standard
+
+It outputs
+\layout Itemize
+
+a path from
+\begin_inset Formula $s$
+\end_inset
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset
+
+ of length at most
+\begin_inset Formula $r\operatorname{d_{T}}(s,t)$
+\end_inset
+
+.
+\end_deeper
+\layout BeginFrame
+
+There Exists a Logspace Approximation Scheme for
+\newline
+the Tournament Shortest Path Problem
+\layout Theorem
+
+There exists an approximation scheme for
+\begin_inset Formula $\Lang{tournament-shortest-path}$
+\end_inset
+
+ that for
+\begin_inset Formula $1<r<2$
+\end_inset
+
+ needs space
+\begin_inset Formula \[
+O\left(\log|V|\log\frac{1}{r-1}\right).\]
+
+\end_inset
+
+
+\layout Pause
+
+\layout Corollary
+
+In tournaments, paths can be constructed in logarithmic space.
+\layout Standard
+
+
+\hfill
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+hyperlink{optimality}{
+\backslash
+beamergotobutton{More Details}}
+\end_inset
+
+
+\layout AgainFrame
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<7>
+\end_inset
+
+hierarchy
+\layout Section*
+
+Summary
+\layout Subsection*
+
+Summary
+\layout BeginFrame
+
+Summary
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Summary}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+Tournament
+\color red
+reachability
+\color default
+ is in
+\color red
+
+\begin_inset Formula $\Class{AC}^{0}$
+\end_inset
+
+
+\color default
+.
+
+\layout Itemize
+
+There exists a
+\color red
+logspace approximation scheme
+\color default
+ for
+\color red
+approximating
+\color default
+ shortest paths in tournaments.
+\layout Itemize
+
+Finding
+\color red
+shortest paths
+\color default
+ in tournaments is
+\color red
+
+\begin_inset Formula $\Class{NL}$
+\end_inset
+
+-complete
+\color default
+.
+\end_deeper
+\layout Separator
+
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Outlook}
+\end_inset
+
+
+\begin_deeper
+\layout Itemize
+
+The same results apply to graphs with
+\newline
+bounded independence number.
+\hfill
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+hyperlink{independence}{
+\backslash
+beamergotobutton{More Details}}
+\end_inset
+
+
+\layout Itemize
+
+The complexity of finding paths in undirected graphs
+\newline
+is partly open.
+\hfill
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+hyperlink{undirected}{
+\backslash
+beamergotobutton{More Details}}
+\end_inset
+
+
+\end_deeper
+\layout Subsection*
+
+For Further Reading
+\layout BeginFrame
+
+For Further Reading
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+beamertemplatebookbibitems
+\end_inset
+
+
+\layout Bibliography
+\bibitem {Moon1968}
+
+\SpecialChar ~
+John Moon.
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+newblock
+\end_inset
+
+
+\emph on
+Topics on Tournaments.
+
+\emph default
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+newblock
+\end_inset
+
+ Holt, Rinehart, and Winston, 1968.
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+beamertemplatearticlebibitems
+\end_inset
+
+
+\layout Bibliography
+\bibitem {NickelsenT2002}
+
+\SpecialChar ~
+Arfst Nickelsen and Till Tantau.
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+newblock
+\end_inset
+
+ On reachability in graphs with bounded independence number.
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+newblock
+\end_inset
+
+ In
+\emph on
+Proc.
+ of COCOON 2002
+\emph default
+, Springer-Verlag, 2002.
+\layout Bibliography
+\bibitem {Tantau2004b}
+
+\SpecialChar ~
+Till Tantau
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+newblock
+\end_inset
+
+ A logspace approximation scheme for the shortest path problem for graphs
+ with bounded independence number.
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+newblock
+\end_inset
+
+ In
+\emph on
+Proc.
+ of STACS 2004
+\emph default
+, Springer-Verlag, 2004.
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+newblock
+\end_inset
+
+ In press.
+\layout EndFrame
+
+\layout Standard
+\start_of_appendix
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+AtBeginSubsection[]{}
+\end_inset
+
+
+\layout Section
+
+Appendix
+\layout Subsection
+
+Graphs With Bounded Independence Number
+\layout BeginFrame
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+[label=independence]
+\end_inset
+
+Definition of Independence Number of a Graph
+\layout Definition
+
+The
+\color red
+independence number
+\color default
+
+\begin_inset Formula $\alpha(G)$
+\end_inset
+
+ of a directed graph
+\newline
+is the maximum number of vertices we can pick,
+\newline
+such that there is no edge between them.
+\layout Example
+
+Tournaments have independence number 1.
+
+\layout BeginFrame
+
+The Results for Tournaments also Apply to
+\newline
+Graphs With Bounded Independence Number
+\layout Theorem
+
+For each\SpecialChar ~
+
+\begin_inset Formula $k$
+\end_inset
+
+,
+\color red
+reachability
+\color default
+ in graphs with independence number
+\newline
+at most\SpecialChar ~
+
+\begin_inset Formula $k$
+\end_inset
+
+ is in
+\begin_inset Formula $\Class{AC}^{0}$
+\end_inset
+
+.
+\layout Separator
+
+\layout Theorem
+
+For each\SpecialChar ~
+
+\begin_inset Formula $k$
+\end_inset
+
+, there exists a
+\color red
+logspace approximation scheme
+\color default
+ for approximating the shortest path in graphs with independence number
+ at most\SpecialChar ~
+
+\begin_inset Formula $k$
+\end_inset
+
+
+\layout Separator
+
+\layout Theorem
+
+For each\SpecialChar ~
+
+\begin_inset Formula $k$
+\end_inset
+
+, finding the
+\color red
+shortest path
+\color default
+ in graphs with independence number at most\SpecialChar ~
+
+\begin_inset Formula $k$
+\end_inset
+
+ is
+\color red
+
+\begin_inset Formula $\Class{NL}$
+\end_inset
+
+-complete
+\color default
+.
+\layout Subsection
+
+Finding Paths in Undirected Graphs
+\layout BeginFrame
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<1-2>[label=undirected]
+\end_inset
+
+The Complexity of Finding Paths in Undirected Graphs
+\newline
+Is Party Unknown.
+\layout Fact
+
+
+\begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
+\end_inset
+
+ is
+\begin_inset Formula $\Class{SL}$
+\end_inset
+
+-complete.
+\layout Corollary
+
+For undirected graphs, we can solve
+\begin_deeper
+\layout Itemize
+
+the reachability problem in logspace iff
+\begin_inset Formula $\Class L=\Class{SL}$
+\end_inset
+
+,
+\layout Itemize
+
+the construction problem in logspace iff
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+alt<1>{?}{
+\backslash
+alert{$
+\backslash
+Class L =
+\backslash
+Class{SL}$}}
+\end_inset
+
+,
+\layout Itemize
+
+the optimization problem in logspace iff
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash
+alt<1>{?}{
+\backslash
+alert{$
+\backslash
+Class L =
+\backslash
+Class{NL}$}}
+\end_inset
+
+,
+\layout Itemize
+
+the approximation problem in logspace iff ?.
+
+\end_deeper
+\layout Subsection
+
+The Approximation Scheme is Optimal
+\layout BeginFrame
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+[label=optimality]
+\end_inset
+
+The Approximation Scheme is Optimal
+\layout Theorem
+
+Suppose there exists an approximation scheme for
+\begin_inset Formula $\Lang{tournament-shortest-path}$
+\end_inset
+
+ that needs space
+\begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
+\end_inset
+
+.
+ Then
+\begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
+\end_inset
+
+.
+\layout Proof
+
+\begin_deeper
+\layout Enumerate
+
+Suppose the approximation scheme exists.
+\newline
+We show
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
+\end_inset
+
+.
+
+\layout Enumerate
+
+Let
+\begin_inset Formula $(T,s,t)$
+\end_inset
+
+ be an input.
+ Let
+\begin_inset Formula $n$
+\end_inset
+
+ be the number of vertices.
+\layout Enumerate
+
+Run the approximation scheme for
+\begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
+\end_inset
+
+.
+\newline
+This needs space
+\begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
+\end_inset
+
+.
+\layout Enumerate
+
+The resulting path has optimal length.
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash
+qedhere
+\end_inset
+
+
+\end_deeper
+\layout EndFrame
+
+\the_end