10 files changed, 0 insertions, 3880 deletions
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-icsi-logo.pdf b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-icsi-logo.pdf
deleted file mode 100644
index cc004993b09..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-icsi-logo.pdf
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight1-mask.png b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight1-mask.png
deleted file mode 100644
index 4c99c270f50..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight1-mask.png
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight1.png b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight1.png
deleted file mode 100644
index 423db8949d2..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight1.png
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight2-mask.png b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight2-mask.png
deleted file mode 100644
index 728587922b6..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight2-mask.png
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight2.png b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight2.png
deleted file mode 100644
index 2d87261889b..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight2.png
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight3-mask.png b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight3-mask.png
deleted file mode 100644
index 5ec7ead51b0..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight3-mask.png
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight3.png b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight3.png
deleted file mode 100644
index 0de2c0a9468..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight3.png
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight4-mask.png b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight4-mask.png
deleted file mode 100644
index e0074c0e9f6..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight4-mask.png
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight4.png b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight4.png
deleted file mode 100644
index 6bc3baa5901..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamer-knight4.png
+++ /dev/null
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx
deleted file mode 100644
index 0d443181c8b..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx
+++ /dev/null
@@ -1,3880 +0,0 @@
-#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