-#LyX 1.6.0svn created this file. For more info see http://www.lyx.org/
-\lyxformat 341
+#LyX 2.2 created this file. For more info see http://www.lyx.org/
+\lyxformat 506
\begin_document
\begin_header
+\save_transient_properties true
+\origin /systemlyxdir/examples/
\textclass beamer
\begin_preamble
\beamertemplateshadingbackground{red!5}{structure!5}
}
\end_preamble
\options notes=show
+\use_default_options false
+\maintain_unincluded_children false
\language english
+\language_package default
\inputencoding auto
-\font_roman times
-\font_sans default
-\font_typewriter default
+\fontencoding global
+\font_roman "times" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
\font_default_family default
+\use_non_tex_fonts false
\font_sc false
\font_osf false
-\font_sf_scale 100
-\font_tt_scale 100
-
+\font_sf_scale 100 100
+\font_tt_scale 100 100
\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
-\use_amsmath 2
-\use_esint 0
+\use_package amsmath 2
+\use_package amssymb 2
+\use_package cancel 0
+\use_package esint 0
+\use_package mathdots 1
+\use_package mathtools 0
+\use_package mhchem 1
+\use_package stackrel 0
+\use_package stmaryrd 0
+\use_package undertilde 0
\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
\use_bibtopic false
+\use_indices false
\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
\secnumdepth 2
\tocdepth 2
\paragraph_separation indent
-\defskip medskip
+\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
-\author ""
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
\end_header
\begin_body
\end_layout
\begin_layout Institute
-International Computer Schience Institute
+International Computer Science Institute
\begin_inset Newline newline
\end_inset
Berkeley, California
-\begin_inset OptArg
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
January 30th, 2004
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Outline
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents
\end_layout
-\begin_layout EndFrame
-
-\end_layout
-
+\end_deeper
\begin_layout Standard
\begin_inset ERT
-status collapsed
+status open
\begin_layout Plain Layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
% of every subsection.
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
-AtBeginSubsection[]{
-\end_layout
-
-\begin_layout Plain Layout
-
+AtBeginSubsection[]{%
\end_layout
\begin_layout Plain Layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
frametitle{Outline}
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
tableofcontents[current,currentsubsection]
\end_layout
-\begin_layout Plain Layout
-
-\end_layout
-
\begin_layout Plain Layout
}
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
}
\end_layout
What are Tournaments?
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Tournaments Consist of Jousts Between Knights
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Columns
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodebox{A}[virtual]{
\backslash
-pgfxy(2,1)}{
-\backslash
-pgfuseimage{knight1}}{2pt}{2pt}
+pgfxy(2,1)}{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfuseimage{knight1}}{2pt}{2pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
pgfnodebox{B}[virtual]{
\backslash
-pgfxy(6,1)}{
-\backslash
-pgfuseimage{knight2}}{2pt}{2pt}
+pgfxy(6,1)}{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfuseimage{knight2}}{2pt}{2pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
pgfnodebox{C}[virtual]{
\backslash
-pgfxy(4,-1)}{
-\backslash
-pgfuseimage{knight3}}{2pt}{2pt}
+pgfxy(4,-1)}{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfuseimage{knight3}}{2pt}{2pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
pgfnodebox{D}[virtual]{
\backslash
-pgfxy(4,3)}{
-\backslash
-pgfuseimage{knight4}}{2pt}{2pt}
-\end_layout
-
-\begin_layout Plain Layout
-
+pgfxy(4,3)}{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfuseimage{knight4}}{2pt}{2pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{beamerexample}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<3->{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
-only<2->{
-\end_layout
-
-\begin_layout Plain Layout
-
+only<2->{%
\end_layout
\begin_layout Plain Layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{A}{B}
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{A}{C}
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{D}{A}
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{C}{B}
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{B}{D}
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
-pgfnodeconnline{C}{D}}
+pgfnodeconnline{C}{D}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Block
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 2
+status open
\begin_layout Plain Layout
-
-{What is a Tournament?}
+What is a Tournament?
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\begin_layout Itemize
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<1->
+1-
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<2->
+2-
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<3->
+3-
\end_layout
\end_inset
\end_deeper
\end_deeper
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Tournaments are Complete Directed Graphs
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Columns
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{beamerexample}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
graphnode{A}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
graphnode{B}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
graphnode{C}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
graphnode{D}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{white}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{beamerexample}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetendarrow{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodesetsepstart{2pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodesetsepend{4pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-\begin_layout Plain Layout
-
-
\backslash
pgfnodeconnline{A}{B}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{A}{C}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{D}{A}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{C}{B}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{B}{D}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodeconnline{D}{C}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
end{pgfpicture}
\end_layout
\begin_layout Definition
-\begin_inset ERT
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
-
-<2->
+2-
\end_layout
\end_inset
\color inherit
is a
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_deeper
\end_deeper
-\begin_layout BeginFrame
-\begin_inset ERT
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-[<+>]
++
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Tournaments Arise Naturally in Different Situations
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout ExampleBlock
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Applicatins in Ordering Theory}
+Applications in Ordering Theory
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\begin_layout ExampleBlock
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Applications in Sociology}
+Applications in Sociology
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\begin_layout ExampleBlock
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Applications in Structural Complexity Theory}
+Applications in Structural Complexity Theory
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
.
\end_layout
+\end_deeper
\end_deeper
\begin_layout Subsection
What Does ``Finding Paths'' Mean?
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
``Finding Paths'' is Ambiguous
\end_layout
-\begin_layout Block
-\begin_inset ERT
-status collapsed
+\end_inset
-\begin_layout Plain Layout
-{
-\backslash
-strut Input for
-\backslash
-ignorespaces
-\backslash
-def
-\backslash
-par{}% because LyX inserts superfluous paragraphs
-\end_layout
+\begin_inset Separator parbreak
+\end_inset
-\begin_layout Plain Layout
\end_layout
+\begin_deeper
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
\begin_layout Plain Layout
+Input for
+\begin_inset Flex Only
+status open
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-\backslash
-only<1>{Path Finding Problems}
-\backslash
-ignorespaces
+\begin_layout Plain Layout
+1
\end_layout
-\begin_layout Plain Layout
+\end_inset
+Path Finding Problems
\end_layout
-\begin_layout Plain Layout
+\end_inset
-\backslash
-only<2-3>{$
-\backslash
-Lang{reach}$}
-\backslash
-ignorespaces
-\end_layout
+\begin_inset Flex Only
+status open
\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+\begin_layout Plain Layout
+2-3
\end_layout
-\begin_layout Plain Layout
+\end_inset
+
+
+\begin_inset Formula $\Lang{reach}$
+\end_inset
-\backslash
-only<4-5>{the Construction Problem}
-\backslash
-ignorespaces
\end_layout
+\end_inset
+
+
+\begin_inset Flex Only
+status open
+
\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+4-5
+\end_layout
+\end_inset
+
+the Construction Problem
\end_layout
+\end_inset
+
+
+\begin_inset Flex Only
+status open
+
\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+\begin_layout Plain Layout
+6-7
+\end_layout
-\backslash
-only<6-7>{the Optimization Problem}
-\backslash
-ignorespaces
+\end_inset
+
+the Optimization Problem
\end_layout
+\end_inset
+
+
+\begin_inset Flex Only
+status open
+
\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+\begin_layout Plain Layout
+8-9
\end_layout
-\begin_layout Plain Layout
+\end_inset
+
+
+\begin_inset Formula $\Lang{distance}$
+\end_inset
-\backslash
-only<8-9>{$
-\backslash
-Lang{distance}$}
-\backslash
-ignorespaces
\end_layout
+\end_inset
+
+
+\begin_inset Flex Only
+status open
+
\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+\begin_layout Plain Layout
+10-
\end_layout
-\begin_layout Plain Layout
+\end_inset
+
+the Approximation Problem
+\end_layout
+
+\end_inset
-\backslash
-only<10->{the Approximation Problem}}
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\begin_layout Itemize
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<only@-9| visible@8->
+only@-9| visible@8-
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<only@10->
+only@10-
\end_layout
\end_inset
\end_layout
\begin_layout Overprint
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+1,3,5,7,9,11-12
+\end_layout
+
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\begin_deeper
-\begin_layout Standard
-\begin_inset ERT
-status collapsed
+\begin_layout Columns
+\begin_inset Argument 1
+status open
\begin_layout Plain Layout
+t,onlytextwidth
+\end_layout
+\end_inset
-\backslash
-onslide<1,3,5,7,9,11-12>
-\end_layout
+\begin_inset Separator parbreak
\end_inset
\end_layout
-\begin_layout Columns
-\begin_inset ERT
-status collapsed
+\begin_deeper
+\begin_layout Standard
+\begin_inset Flex Alternative
+status open
\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-[t,onlytextwidth]
+\begin_layout Plain Layout
+1-2
\end_layout
\end_inset
-\end_layout
+\begin_inset Argument 2
+status open
-\begin_deeper
-\begin_layout Standard
+\begin_layout Plain Layout
\begin_inset ERT
-status collapsed
+status open
\begin_layout Plain Layout
-\backslash
-alt<1-2>{
\backslash
column{
\backslash
-textwidth}}{
+textwidth}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
\backslash
-column{5cm}}
+column{5cm}
+\end_layout
+
+\end_inset
+
+
\end_layout
\end_inset
\end_layout
\begin_layout ExampleBlock
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Example Input}
+Example Input
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_deeper
\begin_layout Standard
-\begin_inset ERT
-status collapsed
+\begin_inset Flex Only
+status open
+
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+3-
+\end_layout
+
+\end_inset
+
+
+\begin_inset ERT
+status open
\begin_layout Plain Layout
\backslash
-only<3->{
-\backslash
-column{5cm}}
+column{5cm}
+\end_layout
+
+\end_inset
+
+
\end_layout
\end_inset
\end_layout
\begin_layout ExampleBlock
-\begin_inset ERT
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
+only@3-
+\end_layout
+
+\end_inset
-<only@3->{Example Output}
+
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Example Output
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
-only<5-8,10->{
-\end_layout
-
-\begin_layout Plain Layout
-
+only<5-8,10->{%
\end_layout
\begin_layout Plain Layout
-
+
\backslash
color{beamerexample}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{A}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{B}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{C}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{D}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
color{white}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
color{beamerexample}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfsetendarrow{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfnodesetsepstart{2pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfnodesetsepend{4pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
alert<7,12>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
alert<5,11>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
alert<5,7,11-12>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
alert<5,11>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfnodeconnline{B}{D}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfnodeconnline{D}{C}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
- }
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<3,9>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
end{pgfpicture}
\end_deeper
\end_deeper
-\begin_layout Standard
-\begin_inset ERT
-status collapsed
+\end_deeper
+\begin_layout Overprint
+\begin_inset Argument item:1
+status open
\begin_layout Plain Layout
+2,4,6,8,10
+\end_layout
+\end_inset
-\backslash
-onslide<2,4,6,8,10>
-\end_layout
+\begin_inset Separator parbreak
\end_inset
\end_layout
+\begin_deeper
\begin_layout Block
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Variants of Path Finding Problems}
+Variants of Path Finding Problems
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
-\begin_layout Standard
-\begin_inset ERT
-status collapsed
+\begin_layout Description
+\begin_inset Argument item:1
+status open
\begin_layout Plain Layout
-
-
-\backslash
-usedescriptionitemofwidthas{Approximation Problem:}
+2-
\end_layout
\end_inset
-
-\end_layout
-
-\begin_layout Description
Reachability
\begin_inset space ~
\end_inset
-Problem:
-\begin_inset ERT
-status collapsed
-
-\begin_layout Plain Layout
-
-<2->
-\end_layout
-
-\end_inset
-
-Is there a path from
+Problem: Is there a path from
\begin_inset Formula $s$
\end_inset
\end_inset
?
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Approximation Problem:
\end_layout
-\begin_layout Description
-Construction
-\begin_inset space ~
\end_inset
-Problem:
-\begin_inset ERT
-status collapsed
-\begin_layout Plain Layout
+\end_layout
+
+\begin_layout Description
+\begin_inset Argument item:1
+status open
-<4->
+\begin_layout Plain Layout
+4-
\end_layout
\end_inset
-Construct a path from
+Construction
+\begin_inset space ~
+\end_inset
+
+Problem: Construct a path from
\begin_inset Formula $s$
\end_inset
\end_layout
\begin_layout Description
-Optimization
-\begin_inset space ~
-\end_inset
-
-Problem:
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:1
+status open
\begin_layout Plain Layout
-
-<6->
+6-
\end_layout
\end_inset
-Construct a shortest path from
+Optimization
+\begin_inset space ~
+\end_inset
+
+Problem: Construct a shortest path from
\begin_inset Formula $s$
\end_inset
\end_layout
\begin_layout Description
-Distance
-\begin_inset space ~
-\end_inset
-
-Problem:
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:1
+status open
\begin_layout Plain Layout
-
-<8->
+8-
\end_layout
\end_inset
-Is the distance of
+Distance
+\begin_inset space ~
+\end_inset
+
+Problem: Is the distance of
\begin_inset Formula $s$
\end_inset
\end_layout
\begin_layout Description
-Approximation
-\begin_inset space ~
-\end_inset
-
-Problem:
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:1
+status open
\begin_layout Plain Layout
-
-<10->
+10-
\end_layout
\end_inset
-Construct a path from
+Approximation
+\begin_inset space ~
+\end_inset
+
+Problem: Construct a path from
\begin_inset Formula $s$
\end_inset
approximately their distance.
\end_layout
+\end_deeper
\end_deeper
\end_deeper
\begin_layout Section
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Classes L and NL are Defined via
\begin_inset Newline newline
\end_inset
Logspace Turing Machines
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
-status open
+status collapsed
\begin_layout Plain Layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfputat{
\backslash
-pgfxy(0,4)}{
-\backslash
-tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
-\end_layout
-
-\begin_layout Plain Layout
-
+pgfxy(0,4)}{%
\end_layout
\begin_layout Plain Layout
\backslash
-uncover<2->{
+tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+uncover<2->{%
\end_layout
\begin_layout Plain Layout
-
+
\backslash
pgfputat{
\backslash
-pgfxy(0,0.5)}{
-\backslash
-tape{}{output tape (write only)}{10690836937182}}}
+pgfxy(0,0.5)}{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+tape{}{output tape (write only)}{10690836937182}}
\end_layout
\begin_layout Plain Layout
-
-\backslash
-uncover<3->{
+}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+uncover<3->{%
\end_layout
\begin_layout Plain Layout
-
+
\backslash
pgfputat{
\backslash
-pgfxy(7,2)}{
+pgfxy(7,2)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
+
\backslash
shorttape{work tape (read/write), $O(
\backslash
\begin_layout Plain Layout
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(1.75,2.5)}{%
\end_layout
\begin_layout Plain Layout
-
-\backslash
-pgfputat{
-\backslash
-pgfxy(1.75,2.5)}{
+
\backslash
pgfbox[center,center]{
\backslash
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
- }
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{structure}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetendarrow{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
uncover<2->{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
uncover<3->{
\backslash
\begin_layout Plain Layout
+
+\backslash
+end{pgfpicture}
\end_layout
-\begin_layout Plain Layout
+\end_inset
-\backslash
-end{pgfpicture}
\end_layout
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
\end_inset
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Logspace Turing Machines Are Quite Powerful
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Block
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Deterministic logspace machines can compute}
+Deterministic logspace machines can compute
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\begin_layout Block
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Non-deterministic logspace machines can compute}
+Non-deterministic logspace machines can compute
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout BeginFrame
-\begin_inset ERT
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+
-<1>[label=hierarchy]
+\begin_inset Argument 3
+status collapsed
+
+\begin_layout Plain Layout
+label=hierarchy
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Complexity Class Hierarchy
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetlinewidth{0.8pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
heap{5.5}{3.5}{$
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetdash{{2pt}}{0pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<2->{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
heap{3.5}{2.5}{$
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
heap{2.5}{2}{$
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<2->{
\backslash
heap{1.75}{1.5}{$
\backslash
-vphantom{A}
+vphantom{A}%
+\end_layout
+
+\begin_layout Plain Layout
+
+
\backslash
smash{
\backslash
-Class{NC}^1}$}{black!50!structure}{5}}
+Class{NC}^1}$}{black!50!structure}{5}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
pgfsetdash{}{0pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<2->{
\backslash
heap{1.1}{1}{$
\backslash
-vphantom{A}
-\backslash
-smash{
-\backslash
-Class{AC}^0}$}{black}{6}}
+vphantom{A}%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+smash{
+\backslash
+Class{AC}^0}$}{black}{6}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetlinewidth{1.0pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{black}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfxyline(-5,0)(5,0)
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<1-2>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<1-2>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<2>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<2>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<3-5>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<4->{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
hbox{$
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
hbox{$
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
hbox{$
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
hbox{$
\backslash
Lang{reach}_{
\backslash
-operatorname{path}}$}}}}
+operatorname{path}}$}}}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
only<5->{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
only<6->{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
hbox{$
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
hbox{$
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
hbox{$
\backslash
-Lang{reach}$}}}}
+Lang{reach}$}}}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
only<7->{
\backslash
-pgfsetdash{{1pt}}{0pt}
+pgfsetdash{{1pt}}{0pt}%
+\end_layout
+
+\begin_layout Plain Layout
+
+
\backslash
langat{2.375}{``$
\backslash
Lang{approx}_{
\backslash
-operatorname{tourn}}$''}}
+operatorname{tourn}}$''}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
\end_layout
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Circuit Complexity Classes AC
\begin_inset Formula $^{0}$
\end_inset
Limit the Circuit Depth
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
nointerlineskip
\end_layout
\begin_layout Columns
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 1
+status open
\begin_layout Plain Layout
-
-[t]
+t
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\begin_layout Block
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 2
+status open
\begin_layout Plain Layout
-
-{
-\end_layout
-
-\end_inset
-
Circuit Class
\begin_inset Formula $\Class{AC}^{0}$
\end_inset
-\begin_inset ERT
-status collapsed
+\end_layout
-\begin_layout Plain Layout
+\end_inset
-}
-\end_layout
+\begin_inset Separator parbreak
\end_inset
\end_deeper
\begin_layout Examples
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_layout
\begin_layout Block
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 2
+status open
\begin_layout Plain Layout
-
-{
-\end_layout
-
-\end_inset
-
Circuit Class
\begin_inset Formula $\Class{NC}^{1}$
\end_inset
-\begin_inset ERT
-status collapsed
+\end_layout
-\begin_layout Plain Layout
+\end_inset
-}
-\end_layout
+\begin_inset Separator parbreak
\end_inset
\end_deeper
\begin_layout Examples
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_layout
\begin_layout Block
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 2
+status open
\begin_layout Plain Layout
-
-{
-\end_layout
-
-\end_inset
-
Circuit Class
\begin_inset Formula $\Class{NC}^{2}$
\end_inset
-\begin_inset ERT
-status collapsed
+\end_layout
-\begin_layout Plain Layout
+\end_inset
-}
-\end_layout
+\begin_inset Separator parbreak
\end_inset
\end_deeper
\begin_layout Examples
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
.
\end_layout
+\end_deeper
\end_deeper
\end_deeper
\begin_layout AgainFrame
-\begin_inset ERT
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
-
-<2>
+2
\end_layout
\end_inset
Standard Complexity Results on Finding Paths
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
All Variants of Finding Paths in Directed Graphs
\begin_inset Newline newline
\end_inset
Are Equally Difficult
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Fact
\begin_inset Formula $\Lang{reach}$
\end_inset
\begin_layout Corollary
For directed graphs, we can solve
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
.
\end_layout
+\end_deeper
\end_deeper
\begin_layout AgainFrame
-\begin_inset ERT
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
-
-<3>
+3
\end_layout
\end_inset
hierarchy
\end_layout
-\begin_layout BeginFrame
-FindingPaths in Forests and Directed Paths is Easy,
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+Finding Paths in Forests and Directed Paths is Easy,
\begin_inset Newline newline
\end_inset
But Not Trivial
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Fact
\begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
\end_inset
-complete.
\end_layout
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
-complete.
\end_layout
+\end_deeper
\begin_layout AgainFrame
-\begin_inset ERT
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
-
-<4>
+4
\end_layout
\end_inset
Complexity of: Does a Path Exist?
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Definition of the Tournament Reachability Problem
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Definition
Let
\color none
\end_inset
such that
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Tournament Reachability Problem is Very Easy
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
\end_inset
\end_layout
\begin_layout AlertBlock
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Implications}
+Implications
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
.
\end_layout
+\end_deeper
\end_deeper
\begin_layout AgainFrame
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 1
+status open
\begin_layout Plain Layout
-
-<5>
+5
\end_layout
\end_inset
Complexity of: Construct a Shortest Path
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Finding a Shortest Path Is as Difficult as
\begin_inset Newline newline
\end_inset
the Distance Problem
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Definition
Let
\color none
\end_inset
such that
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout BeginFrame
-The Tournament Distance Problem is Hard
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+The Tournament Distance Problem is Hard
+\end_layout
+
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
\end_inset
.
\end_layout
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Proof That
\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
\end_inset
is NL-complete
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\end_layout
\begin_layout Columns
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 1
+status open
\begin_layout Plain Layout
-
-[t,onlytextwidth]
+t,onlytextwidth
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\begin_layout Block
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 2
+status open
\begin_layout Plain Layout
-
-{
-\end_layout
-
-\end_inset
-
Reduce
\begin_inset Formula $\Lang{reach}$
\end_inset
\end_inset
-\begin_inset ERT
-status collapsed
+\end_layout
-\begin_layout Plain Layout
+\end_inset
-}
-\end_layout
+\begin_inset Separator parbreak
\end_inset
\begin_deeper
\begin_layout Enumerate
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<alert@1>
+alert@1
\end_layout
\end_inset
\end_layout
\begin_layout Enumerate
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<2-| alert@2-8>
+2-| alert@2-8
\end_layout
\end_inset
\end_layout
\begin_layout Enumerate
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<9-| alert@9>
+9-| alert@9
\end_layout
\end_inset
\end_layout
\end_deeper
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\begin_layout Block
-\begin_inset ERT
-status collapsed
+\begin_inset Argument 2
+status open
\begin_layout Plain Layout
-
-{
+Correctness
\end_layout
\end_inset
-Correctness
-\begin_inset ERT
-status collapsed
-\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-}
+\begin_layout Plain Layout
+10-
\end_layout
\end_inset
-\begin_inset ERT
-status collapsed
-
-\begin_layout Plain Layout
-
-<10->
-\end_layout
-
+\begin_inset Separator parbreak
\end_inset
\begin_deeper
\begin_layout Enumerate
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<10-| alert@10-11>
+10-| alert@10-11
\end_layout
\end_inset
\end_layout
\begin_layout Enumerate
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:2
+status open
\begin_layout Plain Layout
-
-<12-| alert@12-13>
+12-| alert@12-13
\end_layout
\end_inset
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{beamerexample}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetlinewidth{0.6pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
graphnode{A}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
graphnode{B}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
graphnode{C}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
graphnode{D}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{white}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
color{beamerexample}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfsetendarrow{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodesetsepstart{2pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfnodesetsepend{2pt}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
alert<3>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
alert<4>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
alert<5,10-11,13>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
alert<6,10-11,13>{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
\backslash
-only<2->{
-\end_layout
-
-\begin_layout Plain Layout
-
+only<2->{%
\end_layout
\begin_layout Plain Layout
-
+
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{A1}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{B1}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{C1}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{D1}{
\backslash
\begin_layout Plain Layout
+
+\backslash
+graphnode{A2}{
+\backslash
+pgfxy(1,1.25)}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+graphnode{B2}{
+\backslash
+pgfxy(2,1.25)}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+graphnode{C2}{
+\backslash
+pgfxy(3,1.25)}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-graphnode{A2}{
-\backslash
-pgfxy(1,1.25)}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-graphnode{B2}{
-\backslash
-pgfxy(2,1.25)}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-graphnode{C2}{
-\backslash
-pgfxy(3,1.25)}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-graphnode{D2}{
+graphnode{D2}{
\backslash
pgfxy(4,1.25)}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{A3}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{B3}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{C3}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{D3}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{A4}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{B4}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{C4}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
graphnode{D4}{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
- {
+ {
\backslash
color{white}
\end_layout
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-
+
\backslash
pgfputat{
\backslash
\begin_layout Plain Layout
+ }
\end_layout
\begin_layout Plain Layout
- }}
+}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+only<8->{%
\end_layout
\begin_layout Plain Layout
-
+
+\backslash
+pgfsetlinewidth{0.4pt}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+color{beamerexample!25!averagebackgroundcolor}
\end_layout
\begin_layout Plain Layout
\backslash
-only<8->{
+pgfnodeconnline{A2}{C1}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{A2}{D1}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfsetlinewidth{0.4pt}
+pgfnodeconnline{B2}{A1}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B2}{C1}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-color{beamerexample!25!averagebackgroundcolor}
+pgfnodeconnline{B2}{D1}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{C2}{D1}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A2}{C1}
+pgfnodeconnline{D2}{A1}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{D2}{B1}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A2}{D1}
+pgfnodeconnline{A3}{C2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{A3}{D2}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B2}{A1}
+pgfnodeconnline{B3}{A2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B3}{C2}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B2}{C1}
+pgfnodeconnline{B3}{D2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{C3}{D2}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B2}{D1}
+pgfnodeconnline{D3}{A2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{D3}{B2}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{C2}{D1}
+pgfnodeconnline{A4}{C3}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{A4}{D3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{D2}{A1}
+pgfnodeconnline{B4}{A3}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B4}{C3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{D2}{B1}
+pgfnodeconnline{B4}{D3}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{C4}{D3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A3}{C2}
+pgfnodeconnline{D4}{A3}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{D4}{B3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A3}{D2}
+pgfsetstartarrow{
+\backslash
+pgfarrowto}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{A1}{B1}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B3}{A2}
+pgfnodeconnline{B1}{C1}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{C1}{D1}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B3}{C2}
+pgfnodeconnline{A2}{B2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B2}{C2}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B3}{D2}
+pgfnodeconnline{C2}{D2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{A3}{B3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{C3}{D2}
+pgfnodeconnline{B3}{C3}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{C3}{D3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{D3}{A2}
+pgfnodeconnline{A4}{B4}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B4}{C4}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{D3}{B2}
+pgfnodeconnline{C4}{D4}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfclearstartarrow
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A4}{C3}
+pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A4}{D3}
+pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B4}{A3}
-\end_layout
-
-\begin_layout Plain Layout
-
+pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B4}{C3}
+pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B4}{D3}
+pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{C4}{D3}
+pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{D4}{A3}
+pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+color{beamerexample}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{D4}{B3}
+pgfsetlinewidth{0.6pt}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+only<3->{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+color<3>{red}
\end_layout
\begin_layout Plain Layout
-
-\backslash
-pgfsetstartarrow{
+
\backslash
-pgfarrowto}
+pgfnodeconnline{B1}{A2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B2}{A3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A1}{B1}
+pgfnodeconnline{B3}{A4}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B1}{C1}
+only<4->{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+color<4>{red}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{C1}{D1}
+pgfnodeconnline{B1}{C2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B2}{C3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A2}{B2}
+pgfnodeconnline{B3}{C4}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B2}{C2}
+only<5->{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+color<5>{red}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{C2}{D2}
+pgfnodeconnline{C1}{D2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+alert<11>{
+\backslash
+pgfnodeconnline{C2}{D3}}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A3}{B3}
+alert<12-13>{
+\backslash
+pgfnodeconnline{C3}{D4}}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{B3}{C3}
+only<6->{%
\end_layout
\begin_layout Plain Layout
+
+\backslash
+color<6>{red}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{C3}{D3}
+alert<11>{
+\backslash
+pgfnodeconnline{A1}{C2}}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+alert<12-13>{
+\backslash
+pgfnodeconnline{A2}{C3}}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{A4}{B4}
+pgfnodeconnline{A3}{C4}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-
-\backslash
-pgfnodeconnline{B4}{C4}
-\end_layout
-
-\begin_layout Plain Layout
+\backslash
+only<7->{%
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconnline{C4}{D4}
+color<7>{red}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+alert<12-13>{
+\backslash
+pgfnodeconnline{A1}{A2}}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{A2}{A3}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{A3}{A4}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfclearstartarrow
+pgfnodeconnline{B1}{B2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B2}{B3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
+pgfnodeconnline{B3}{B4}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{C1}{C2}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
+pgfnodeconnline{C2}{C3}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{C3}{C4}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
+pgfnodeconnline{D1}{D2}
\end_layout
\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{D2}{D3}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
+alert<11>{
+\backslash
+pgfnodeconnline{D3}{D4}}
\end_layout
\begin_layout Plain Layout
+}
\end_layout
\begin_layout Plain Layout
-
+
\backslash
-pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
+end{pgfpicture}
\end_layout
-\begin_layout Plain Layout
+\end_inset
+
\end_layout
-\begin_layout Plain Layout
+\end_deeper
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status open
-
-\backslash
-pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
+\begin_layout Plain Layout
+6
\end_layout
-\begin_layout Plain Layout
+\end_inset
+hierarchy
\end_layout
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
+\begin_layout Subsection
+Complexity of: Approximating the Shortest Path
\end_layout
-\begin_layout Plain Layout
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+\begin_layout Plain Layout
+Approximators Compute Paths that Are Nearly As Short As a Shortest Path
\end_layout
-\begin_layout Plain Layout
+\end_inset
-
-\backslash
-pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
-\end_layout
-\begin_layout Plain Layout
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
-\begin_layout Plain Layout
+\begin_deeper
+\begin_layout Definition
+An
+\color none
+
+\color red
+approximation scheme for
+\begin_inset Formula $\Lang{tournament-shortest-path}$
+\end_inset
-
-\backslash
-pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
-\end_layout
-\begin_layout Plain Layout
+\color none
+
+\color inherit
+gets as input
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
-\begin_layout Plain Layout
+\begin_deeper
+\begin_layout Enumerate
+a tuple
+\begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
+\end_inset
-
-\backslash
-pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
+ and
\end_layout
-\begin_layout Plain Layout
+\begin_layout Enumerate
+a number
+\begin_inset Formula $r>1$
+\end_inset
+.
\end_layout
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-color{beamerexample}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfsetlinewidth{0.6pt}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
- }
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-only<3->{
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-color<3>{red}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{B1}{A2}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{B2}{A3}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{B3}{A4}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
- }
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-only<4->{
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-color<4>{red}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{B1}{C2}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{B2}{C3}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{B3}{C4}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
- }
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-only<5->{
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-color<5>{red}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{C1}{D2}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-alert<11>{
-\backslash
-pgfnodeconnline{C2}{D3}}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-alert<12-13>{
-\backslash
-pgfnodeconnline{C3}{D4}}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
- }
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-only<6->{
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-color<6>{red}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-alert<11>{
-\backslash
-pgfnodeconnline{A1}{C2}}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-alert<12-13>{
-\backslash
-pgfnodeconnline{A2}{C3}}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{A3}{C4}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
- }
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-only<7->{
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-color<7>{red}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-alert<12-13>{
-\backslash
-pgfnodeconnline{A1}{A2}}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{A2}{A3}
-\end_layout
-
-\begin_layout Plain Layout
-
+\begin_layout Standard
+It outputs
\end_layout
-\begin_layout Plain Layout
+\begin_layout Itemize
+a path from
+\begin_inset Formula $s$
+\end_inset
-
-\backslash
-pgfnodeconnline{A3}{A4}
-\end_layout
+ to
+\begin_inset space ~
+\end_inset
-\begin_layout Plain Layout
-\end_layout
+\begin_inset Formula $t$
+\end_inset
-\begin_layout Plain Layout
+ of length at most
+\begin_inset Formula $r\operatorname{d_{T}}(s,t)$
+\end_inset
-
-\backslash
-pgfnodeconnline{B1}{B2}
+.
\end_layout
-\begin_layout Plain Layout
-
-\end_layout
+\end_deeper
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
-\begin_layout Plain Layout
-
-\backslash
-pgfnodeconnline{B2}{B3}
\end_layout
-\begin_layout Plain Layout
-
-\end_layout
+\begin_layout Frame
+\begin_inset Argument 4
+status open
\begin_layout Plain Layout
+There Exists a Logspace Approximation Scheme for
+\begin_inset Newline newline
+\end_inset
-
-\backslash
-pgfnodeconnline{B3}{B4}
+the Tournament Shortest Path Problem
\end_layout
-\begin_layout Plain Layout
-
-\end_layout
+\end_inset
-\begin_layout Plain Layout
-
-\backslash
-pgfnodeconnline{C1}{C2}
-\end_layout
+\begin_inset Separator parbreak
+\end_inset
-\begin_layout Plain Layout
\end_layout
-\begin_layout Plain Layout
+\begin_deeper
+\begin_layout Theorem
+There exists an approximation scheme for
+\begin_inset Formula $\Lang{tournament-shortest-path}$
+\end_inset
-
-\backslash
-pgfnodeconnline{C2}{C3}
-\end_layout
+ that for
+\begin_inset Formula $1<r<2$
+\end_inset
-\begin_layout Plain Layout
+ needs space
+\begin_inset Formula
+\[
+O\left(\log|V|\log\frac{1}{r-1}\right).
+\]
-\end_layout
+\end_inset
-\begin_layout Plain Layout
-
-\backslash
-pgfnodeconnline{C3}{C4}
\end_layout
-\begin_layout Plain Layout
+\begin_layout Pause
\end_layout
-\begin_layout Plain Layout
-
-
-\backslash
-pgfnodeconnline{D1}{D2}
+\begin_layout Corollary
+In tournaments, paths can be constructed in logarithmic space.
\end_layout
-\begin_layout Plain Layout
-
-\end_layout
+\begin_layout Standard
+\begin_inset space \hfill{}
+\end_inset
-\begin_layout Plain Layout
-
-\backslash
-pgfnodeconnline{D2}{D3}
-\end_layout
+\begin_inset ERT
+status collapsed
\begin_layout Plain Layout
-\end_layout
-
-\begin_layout Plain Layout
-
-\backslash
-alert<11>{
\backslash
-pgfnodeconnline{D3}{D4}}
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
- }
-\end_layout
-
-\begin_layout Plain Layout
-
-\end_layout
-
-\begin_layout Plain Layout
-
-
+hyperlink{optimality}{
\backslash
-end{pgfpicture}
+beamergotobutton{More Details}}
\end_layout
\end_inset
\end_deeper
\begin_layout AgainFrame
-\begin_inset ERT
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
-
-<6>
+7
\end_layout
\end_inset
hierarchy
\end_layout
-\begin_layout Subsection
-Complexity of: Approximating the Shortest Path
-\end_layout
-
-\begin_layout BeginFrame
-Approximators Compute Paths that Are Nearly As Short As a Shortest Path
-\end_layout
-
-\begin_layout Definition
-An
-\color none
-
-\color red
-approximation scheme for
-\begin_inset Formula $\Lang{tournament-shortest-path}$
-\end_inset
-
-
-\color none
-
-\color inherit
-gets as input
-\end_layout
+\begin_layout Standard
+\begin_inset Note Note
+status open
-\begin_deeper
-\begin_layout Enumerate
-a tuple
-\begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
+\begin_layout Plain Layout
+If a frame includes a program listing, the frame needs to be marked as
+\begin_inset Quotes eld
\end_inset
- and
-\end_layout
-
-\begin_layout Enumerate
-a number
-\begin_inset Formula $r>1$
+fragile
+\begin_inset Quotes erd
\end_inset
.
+ \SpecialChar LyX
+ has the FragileFrame layout for this.
\end_layout
-\begin_layout Standard
-It outputs
-\end_layout
-
-\begin_layout Itemize
-a path from
-\begin_inset Formula $s$
-\end_inset
-
- to
-\begin_inset space ~
-\end_inset
-
-
-\begin_inset Formula $t$
\end_inset
- of length at most
-\begin_inset Formula $r\operatorname{d_{T}}(s,t)$
-\end_inset
-.
\end_layout
-\end_deeper
-\begin_layout BeginFrame
-There Exists a Logspace Approximation Scheme for
-\begin_inset Newline newline
-\end_inset
+\begin_layout FragileFrame
+\begin_inset Argument 4
+status open
-the Tournament Shortest Path Problem
+\begin_layout Plain Layout
+Just a frame with a program code listing
\end_layout
-\begin_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_layout
+\begin_layout FragileFrame
+This is some program code:
+\begin_inset Separator parbreak
\end_inset
\end_layout
-\begin_layout Pause
+\begin_deeper
+\begin_layout Standard
+\begin_inset listings
+lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
+inline false
+status open
-\end_layout
+\begin_layout Plain Layout
-\begin_layout Corollary
-In tournaments, paths can be constructed in logarithmic space.
+def func(param):
\end_layout
-\begin_layout Standard
-\begin_inset space \hfill{}
-\end_inset
+\begin_layout Plain Layout
+ 'this is a python function'
+\end_layout
-\begin_inset ERT
-status collapsed
+\begin_layout Plain Layout
+
+ pass
+\end_layout
\begin_layout Plain Layout
+def func(param):
+\end_layout
-\backslash
-hyperlink{optimality}{
-\backslash
-beamergotobutton{More Details}}
+\begin_layout Plain Layout
+
+'This is a German word: Tschüs'
\end_layout
-\end_inset
+\begin_layout Plain Layout
+
+pass
+\end_layout
+\begin_layout Plain Layout
+def func(param):
\end_layout
-\begin_layout AgainFrame
-\begin_inset ERT
-status collapsed
+\begin_layout Plain Layout
+
+'this is a python function'
+\end_layout
\begin_layout Plain Layout
-<7>
+pass
\end_layout
\end_inset
-hierarchy
+
\end_layout
+\end_deeper
\begin_layout Section*
Summary
\end_layout
Summary
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Summary
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Block
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Summary}
+Summary
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\begin_layout Block
-\begin_inset ERT
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-{Outlook}
+Outlook
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
+\end_deeper
\end_deeper
\begin_layout Subsection*
For Further Reading
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
For Further Reading
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
-status collapsed
+status open
\begin_layout Plain Layout
In press.
\end_layout
-\begin_layout EndFrame
-
-\end_layout
-
+\end_deeper
\begin_layout Standard
\start_of_appendix
\begin_inset ERT
-status collapsed
+status open
\begin_layout Plain Layout
\backslash
-AtBeginSubsection[]{}
+AtBeginSubsection[]{}
\end_layout
\end_inset
Graphs With Bounded Independence Number
\end_layout
-\begin_layout BeginFrame
-\begin_inset ERT
+\begin_layout Frame
+\begin_inset Argument 3
status collapsed
\begin_layout Plain Layout
-
-[label=independence]
+label=independence
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Definition of Independence Number of a Graph
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Definition
The
\color none
\end_layout
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Results for Tournaments also Apply to
\begin_inset Newline newline
\end_inset
Graphs With Bounded Independence Number
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
For each
\begin_inset space ~
.
\end_layout
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_layout
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
.
\end_layout
+\end_deeper
\begin_layout Subsection
Finding Paths in Undirected Graphs
\end_layout
-\begin_layout BeginFrame
-\begin_inset ERT
+\begin_layout Frame
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
+1-2
+\end_layout
+
+\end_inset
+
-<1-2>[label=undirected]
+\begin_inset Argument 3
+status collapsed
+
+\begin_layout Plain Layout
+label=undirected
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Complexity of Finding Paths in Undirected Graphs
\begin_inset Newline newline
\end_inset
Is Party Unknown.
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Fact
\begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
\end_inset
\begin_layout Corollary
For undirected graphs, we can solve
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\begin_layout Itemize
the construction problem in logspace iff
-\begin_inset ERT
-status collapsed
+\begin_inset Flex Alternative
+status open
\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+
+
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+?
+\end_layout
+
+\end_inset
+
+
+\begin_inset Flex Alert
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\Class L=\Class{SL}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
-\backslash
-alt<1>{?}{
-\backslash
-alert{$
-\backslash
-Class L =
-\backslash
-Class{SL}$}}
\end_layout
\end_inset
\begin_layout Itemize
the optimization problem in logspace iff
-\begin_inset ERT
-status collapsed
+\begin_inset Flex Alternative
+status open
\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+
+
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+?
+\end_layout
+
+\end_inset
+
+
+\begin_inset Flex Alert
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\Class L=\Class{NL}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
-\backslash
-alt<1>{?}{
-\backslash
-alert{$
-\backslash
-Class L =
-\backslash
-Class{NL}$}}
\end_layout
\end_inset
\end_layout
+\end_deeper
\end_deeper
\begin_layout Subsection
The Approximation Scheme is Optimal
\end_layout
-\begin_layout BeginFrame
-\begin_inset ERT
+\begin_layout Frame
+\begin_inset Argument 3
status collapsed
\begin_layout Plain Layout
-
-[label=optimality]
+label=optimality
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Approximation Scheme is Optimal
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
Suppose there exists an approximation scheme for
\begin_inset Formula $\Lang{tournament-shortest-path}$
\end_layout
\begin_layout Proof
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_layout
\end_deeper
-\begin_layout EndFrame
-
-\end_layout
-
+\end_deeper
\end_body
\end_document