summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.lyx
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.lyx')
-rw-r--r--Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.lyx3880
1 files changed, 0 insertions, 3880 deletions
diff --git a/Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.lyx b/Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.lyx
deleted file mode 100644
index 0d443181c8b..00000000000
--- a/Master/texmf-dist/doc/latex/beamer/examples/lyx-based-presentation/beamerexample-lyx.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