-#LyX 1.3 created this file. For more info see http://www.lyx.org/
-\lyxformat 221
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin /systemlyxdir/examples/
\textclass beamer
\begin_preamble
\beamertemplateshadingbackground{red!5}{structure!5}
\newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
+% This gets defined by beamerbasecolor.sty, but only at the beginning of
+% the document
+\colorlet{averagebackgroundcolor}{normal text.bg}
+
\newcommand{\tape}[3]{%
\color{structure!30!averagebackgroundcolor}
\pgfmoveto{\pgfxy(-0.5,0)}
}
\end_preamble
\options notes=show
+\use_default_options false
+\maintain_unincluded_children false
\language english
+\language_package default
\inputencoding auto
-\fontscheme times
+\fontencoding global
+\font_roman "lmodern" "default"
+\font_sans "lmss" "default"
+\font_typewriter "lmtt" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures false
\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
\paperfontsize default
-\spacing single
-\papersize Default
-\paperpackage a4
-\use_geometry 0
-\use_amsmath 1
-\use_natbib 0
-\use_numerical_citations 0
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry true
+\use_package amsmath 2
+\use_package amssymb 2
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\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
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
\secnumdepth 2
\tocdepth 2
\paragraph_separation indent
-\defskip medskip
-\quotes_language english
-\quotes_times 2
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
-\layout Title
+\begin_body
+\begin_layout Title
The Complexity of
-\newline
+\begin_inset Newline newline
+\end_inset
+
Finding Paths in Tournaments
-\layout Author
+\end_layout
+\begin_layout Author
Till Tantau
-\layout Institute
+\end_layout
-International Computer Schience Institute
-\newline
-Berkeley, California
-\begin_inset OptArg
-collapsed true
+\begin_layout Institute
+International Computer Science Institute
+\begin_inset Newline newline
+\end_inset
-\layout Standard
+Berkeley, California
+\begin_inset Argument 1
+status collapsed
+\begin_layout Plain Layout
ICSI
-\end_inset
+\end_layout
+\end_inset
-\layout Date
+\end_layout
+
+\begin_layout Date
January 30th, 2004
-\layout BeginFrame
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+\begin_layout Plain Layout
Outline
-\layout Standard
+\end_layout
+
+\end_inset
+
+\end_layout
-\begin_inset LatexCommand \tableofcontents{}
+\begin_deeper
+\begin_layout Standard
+\begin_inset CommandInset toc
+LatexCommand tableofcontents
-\end_inset
+\end_inset
\begin_inset ERT
-status Collapsed
+status collapsed
-\layout Standard
-[pausesections]
-\end_inset
+\begin_layout Plain Layout
+[pausesections]
+\end_layout
-\layout EndFrame
+\end_inset
-\layout Standard
+\end_layout
+\end_deeper
+\begin_layout Standard
\begin_inset ERT
-status Collapsed
+status open
+
+\begin_layout Plain Layout
-\layout Standard
% Show the table of contents at the beginning
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
% of every subsection.
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+AtBeginSubsection[]{%
+\end_layout
+
+\begin_layout Plain Layout
-\backslash
-AtBeginSubsection[]{
-\layout Standard
-\backslash
+\backslash
frame<handout:0>{
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
frametitle{Outline}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
tableofcontents[current,currentsubsection]
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
}
-\end_inset
+\end_layout
+
+\end_inset
-\layout Section
+\end_layout
+\begin_layout Section
Introduction
-\layout Subsection
+\end_layout
+\begin_layout Subsection
What are Tournaments?
-\layout BeginFrame
+\end_layout
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Tournaments Consist of Jousts Between Knights
-\layout Columns
+\end_layout
-\begin_deeper
-\layout Column
+\end_inset
-5.75cm
-\layout Standard
+\end_layout
+
+\begin_deeper
+\begin_layout Columns
+
+\end_layout
+
+\begin_deeper
+\begin_layout Column
+5.75cm
+\end_layout
+\begin_layout Standard
\begin_inset ERT
-status Inlined
+status collapsed
-\layout Standard
+\begin_layout Plain Layout
-\backslash
+
+\backslash
begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodebox{A}[virtual]{
-\backslash
-pgfxy(2,1)}{
-\backslash
-pgfuseimage{knight1}}{2pt}{2pt}
-\layout Standard
+\backslash
+pgfxy(2,1)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
+pgfuseimage{knight1}}{2pt}{2pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodebox{B}[virtual]{
-\backslash
-pgfxy(6,1)}{
-\backslash
-pgfuseimage{knight2}}{2pt}{2pt}
-\layout Standard
+\backslash
+pgfxy(6,1)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
+pgfuseimage{knight2}}{2pt}{2pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodebox{C}[virtual]{
-\backslash
-pgfxy(4,-1)}{
-\backslash
-pgfuseimage{knight3}}{2pt}{2pt}
-\layout Standard
+\backslash
+pgfxy(4,-1)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
+pgfuseimage{knight3}}{2pt}{2pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodebox{D}[virtual]{
-\backslash
-pgfxy(4,3)}{
-\backslash
-pgfuseimage{knight4}}{2pt}{2pt}
-\layout Standard
+\backslash
+pgfxy(4,3)}{%
+\end_layout
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
+pgfuseimage{knight4}}{2pt}{2pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
color{beamerexample}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
only<3->{
-\backslash
+\backslash
pgfsetendarrow{
-\backslash
+\backslash
pgfarrowto}}
-\layout Standard
-
-\backslash
-only<2->{
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<2->{%
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
pgfsetlinewidth{0.6pt}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
pgfnodeconnline{A}{B}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
pgfnodeconnline{A}{C}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
pgfnodeconnline{D}{A}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
pgfnodeconnline{C}{B}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
pgfnodeconnline{B}{D}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
-pgfnodeconnline{C}{D}}
-\layout Standard
+\backslash
+pgfnodeconnline{C}{D}
+\end_layout
-\backslash
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
end{pgfpicture}
-\end_inset
+\end_layout
+
+\end_inset
-\layout Column
+\end_layout
+\begin_layout Column
6cm
-\layout Block
+\end_layout
+\begin_layout Block
+\begin_inset Argument 2
+status open
-\begin_inset ERT
-status Inlined
+\begin_layout Plain Layout
+What is a Tournament?
+\end_layout
-\layout Standard
-{What is a Tournament?}
-\end_inset
+\end_inset
-\begin_deeper
-\layout Itemize
+\end_layout
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Argument item:2
+status open
-\begin_inset ERT
-status Collapsed
+\begin_layout Plain Layout
-\layout Standard
-<1->
-\end_inset
+1-
+\end_layout
+
+\end_inset
A group of knights.
-\layout Itemize
+\end_layout
+\begin_layout Itemize
+\begin_inset Argument item:2
+status open
-\begin_inset ERT
-status Collapsed
+\begin_layout Plain Layout
-\layout Standard
-<2->
-\end_inset
+2-
+\end_layout
+
+\end_inset
Every pair has a joust.
-\layout Itemize
+\end_layout
+\begin_layout Itemize
+\begin_inset Argument item:2
+status open
-\begin_inset ERT
-status Collapsed
+\begin_layout Plain Layout
-\layout Standard
-<3->
-\end_inset
+3-
+\end_layout
+
+\end_inset
In every joust one knight wins.
-\end_deeper
-\end_deeper
-\layout BeginFrame
+\end_layout
+
+\end_deeper
+\end_deeper
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Tournaments are Complete Directed Graphs
-\layout Columns
+\end_layout
-\begin_deeper
-\layout Column
+\end_inset
-5cm
-\layout Standard
+\end_layout
+
+\begin_deeper
+\begin_layout Columns
+
+\end_layout
+\begin_deeper
+\begin_layout Column
+5cm
+\end_layout
+
+\begin_layout Standard
\begin_inset ERT
-status Inlined
+status collapsed
-\layout Standard
+\begin_layout Plain Layout
-\backslash
+
+\backslash
begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
color{beamerexample}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfsetlinewidth{0.6pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{A}{
-\backslash
+\backslash
pgfxy(2.5,1)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{B}{
-\backslash
+\backslash
pgfxy(5.5,1)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{C}{
-\backslash
+\backslash
pgfxy(4,-0.5)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{D}{
-\backslash
+\backslash
pgfxy(4,2.5)}
-\layout Standard
+\end_layout
-\layout Standard
-
-\backslash
+\begin_layout Plain Layout
+
+
+\backslash
color{white}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfputat{
-\backslash
+\backslash
pgfnodecenter{A}}{
-\backslash
+\backslash
pgfbox[center,center]{$v_2$}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfputat{
-\backslash
+\backslash
pgfnodecenter{B}}{
-\backslash
+\backslash
pgfbox[center,center]{$v_3$}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfputat{
-\backslash
+\backslash
pgfnodecenter{C}}{
-\backslash
+\backslash
pgfbox[center,center]{$v_4$}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfputat{
-\backslash
+\backslash
pgfnodecenter{D}}{
-\backslash
+\backslash
pgfbox[center,center]{$v_1$}}
-\layout Standard
+\end_layout
-\layout Standard
-
-\backslash
+\begin_layout Plain Layout
+
+
+\backslash
color{beamerexample}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfsetendarrow{
-\backslash
+\backslash
pgfarrowto}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodesetsepstart{2pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodesetsepend{4pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A}{B}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A}{C}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D}{A}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C}{B}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B}{D}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D}{C}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
-\backslash
+
+\backslash
end{pgfpicture}
-\end_inset
+\end_layout
+
+\end_inset
-\layout Column
+\end_layout
+\begin_layout Column
6cm
-\layout Definition
+\end_layout
+\begin_layout Definition
+\begin_inset Argument 1
+status collapsed
-\begin_inset ERT
-status Collapsed
+\begin_layout Plain Layout
+
+2-
+\end_layout
-\layout Standard
-<2->
-\end_inset
+\end_inset
-A
+A
+\color none
+
\color red
tournament
-\color default
- is a
-\begin_deeper
-\layout Enumerate
+\color none
+
+\color inherit
+is a
+\end_layout
+\begin_deeper
+\begin_layout Enumerate
directed graphs,
-\layout Enumerate
+\end_layout
+\begin_layout Enumerate
with exactly one edge between
-\newline
+\begin_inset Newline newline
+\end_inset
+
any two different vertices.
-\end_deeper
-\end_deeper
-\layout BeginFrame
+\end_layout
+\end_deeper
+\end_deeper
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+
++
+\end_layout
+
+\end_inset
-\begin_inset ERT
-status Collapsed
-\layout Standard
-[<+>]
-\end_inset
+\begin_inset Argument 4
+status open
+\begin_layout Plain Layout
Tournaments Arise Naturally in Different Situations
-\layout ExampleBlock
+\end_layout
+\end_inset
-\begin_inset ERT
-status Inlined
-\layout Standard
-{Applicatins in Ordering Theory}
-\end_inset
+\end_layout
+
+\begin_deeper
+\begin_layout ExampleBlock
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Applications in Ordering Theory
+\end_layout
+
+\end_inset
-\begin_deeper
-\layout Standard
+\end_layout
+\begin_deeper
+\begin_layout Standard
Elements in a set need to be sorted.
-\newline
+\begin_inset Newline newline
+\end_inset
+
The comparison relation may be cyclic, however.
-\end_deeper
-\layout Separator
+\end_layout
-\layout ExampleBlock
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
-\begin_inset ERT
-status Inlined
+\end_layout
+
+\begin_layout ExampleBlock
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Applications in Sociology
+\end_layout
-\layout Standard
-{Applications in Sociology}
-\end_inset
+\end_inset
-\begin_deeper
-\layout Standard
+\end_layout
+\begin_deeper
+\begin_layout Standard
Several candidates apply for a position.
-\newline
+\begin_inset Newline newline
+\end_inset
+
Reviewers decide for any two candidates whom they prefer.
-\end_deeper
-\layout Separator
+\end_layout
-\layout ExampleBlock
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
-\begin_inset ERT
-status Inlined
+\end_layout
+
+\begin_layout ExampleBlock
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Applications in Structural Complexity Theory
+\end_layout
-\layout Standard
-{Applications in Structural Complexity Theory}
-\end_inset
+\end_inset
-\begin_deeper
-\layout Standard
+\end_layout
+\begin_deeper
+\begin_layout Standard
A language
\begin_inset Formula $L$
-\end_inset
+\end_inset
is given and a selector function
\begin_inset Formula $f$
-\end_inset
+\end_inset
.
-\newline
+\begin_inset Newline newline
+\end_inset
+
It chooses from any two words the one more likely to be in
\begin_inset Formula $f$
-\end_inset
+\end_inset
.
-\end_deeper
-\layout Subsection
+\end_layout
+\end_deeper
+\end_deeper
+\begin_layout Subsection
What Does ``Finding Paths'' Mean?
-\layout BeginFrame
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+\begin_layout Plain Layout
``Finding Paths'' is Ambiguous
-\layout Block
+\end_layout
+\end_inset
-\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
+\end_layout
-\backslash
-only<2-3>{$
-\backslash
-Lang{reach}$}
-\backslash
-ignorespaces
-\layout Standard
+\begin_deeper
+\begin_layout Block
+\begin_inset Argument 2
+status open
-\backslash
-only<4-5>{the Construction Problem}
-\backslash
-ignorespaces
-\layout Standard
+\begin_layout Plain Layout
+Input for
+\begin_inset Flex Only
+status open
-\backslash
-only<6-7>{the Optimization Problem}
-\backslash
-ignorespaces
-\layout Standard
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-\backslash
-only<8-9>{$
-\backslash
-Lang{distance}$}
-\backslash
-ignorespaces
-\layout Standard
+\begin_layout Plain Layout
-\backslash
-only<10->{the Approximation Problem}}
-\end_inset
+1
+\end_layout
+\end_inset
-\begin_deeper
-\layout Itemize
+Path Finding Problems
+\end_layout
-A
-\color red
-graph
-\color default
-
-\begin_inset Formula $G=(V,E)$
-\end_inset
+\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
+\begin_inset Flex Only
+status open
-.
-\layout Itemize
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+2-3
+\end_layout
-\layout Standard
-<only@-9| visible@8->
-\end_inset
+\end_inset
-A
-\color red
-maximum distance
-\color default
-\SpecialChar ~
-\begin_inset Formula $d$
-\end_inset
+\begin_inset Formula $\Lang{reach}$
+\end_inset
-.
-\begin_inset ERT
-status Collapsed
-\layout Standard
+\end_layout
-\backslash
-phantom{p}
-\end_inset
+\end_inset
-\layout Itemize
+\begin_inset Flex Only
+status open
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-\begin_inset ERT
-status Collapsed
+\begin_layout Plain Layout
-\layout Standard
-<only@10->
-\end_inset
+4-5
+\end_layout
-An
-\color red
-approximation ratio
-\color default
-
-\begin_inset Formula $r>1$
-\end_inset
+\end_inset
-.
-\end_deeper
-\layout Standard
+the Construction Problem
+\end_layout
+\end_inset
-\begin_inset ERT
-status Collapsed
-\layout Standard
+\begin_inset Flex Only
+status open
-\backslash
-nointerlineskip
-\end_inset
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
+\begin_layout Plain Layout
-\layout Overprint
+6-7
+\end_layout
-\begin_deeper
-\layout Standard
+\end_inset
+the Optimization Problem
+\end_layout
-\begin_inset ERT
-status Inlined
+\end_inset
-\layout Standard
-\backslash
-onslide<1,3,5,7,9,11-12>
-\end_inset
+\begin_inset Flex Only
+status open
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-\layout Columns
+\begin_layout Plain Layout
+8-9
+\end_layout
-\begin_inset ERT
-status Inlined
+\end_inset
-\layout Standard
-[t,onlytextwidth]
-\end_inset
+\begin_inset Formula $\Lang{distance}$
+\end_inset
-\begin_deeper
-\layout Standard
+\end_layout
-\begin_inset ERT
-status Inlined
+\end_inset
-\layout Standard
-\backslash
-alt<1-2>{
-\backslash
-column{
-\backslash
-textwidth}}{
-\backslash
-column{5cm}}
-\end_inset
+\begin_inset Flex Only
+status open
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-\layout ExampleBlock
+\begin_layout Plain Layout
+10-
+\end_layout
-\begin_inset ERT
-status Inlined
+\end_inset
-\layout Standard
-{Example Input}
-\end_inset
+the Approximation Problem
+\end_layout
+\end_inset
-\begin_deeper
-\layout Standard
+\end_layout
-\begin_inset ERT
-status Inlined
+\end_inset
-\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
+\end_layout
-\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
+\begin_deeper
+\begin_layout Itemize
+A
+\color none
+
+\color red
+graph
+\color none
+
+\color inherit
-\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
+\begin_inset Formula $G=(V,E)$
+\end_inset
-\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
+, a
+\color none
+
+\color red
+source
+\color none
+
+\color inherit
-\backslash
-end{pgfpicture}
-\end_inset
+\begin_inset Formula $s\in V$
+\end_inset
+
+ and a
+\color none
+
+\color red
+target
+\color none
+
+\color inherit
+\begin_inset Formula $t\in V$
+\end_inset
-\end_deeper
-\layout Standard
+.
+\end_layout
+\begin_layout Itemize
+\begin_inset Argument item:2
+status open
-\begin_inset ERT
-status Inlined
+\begin_layout Plain Layout
-\layout Standard
+only@-9| visible@8-
+\end_layout
-\backslash
-only<3->{
-\backslash
-column{5cm}}
-\end_inset
+\end_inset
+
+A
+\color none
+
+\color red
+maximum distance
+\color inherit
+\begin_inset space ~
+\end_inset
-\layout ExampleBlock
+\begin_inset Formula $d$
+\end_inset
+.
\begin_inset ERT
-status Inlined
+status collapsed
-\layout Standard
-<only@3->{Example Output}
-\end_inset
+\begin_layout Plain Layout
-\begin_deeper
-\layout Standard
+\backslash
+phantom{p}
+\end_layout
+\end_inset
-\begin_inset ERT
-status Inlined
-\layout Standard
+\end_layout
-\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
+\begin_layout Itemize
+\begin_inset Argument item:2
+status open
-\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
+\begin_layout Plain Layout
-\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
+only@10-
+\end_layout
-\backslash
-end{pgfpicture}
-\end_inset
+\end_inset
+An
+\color none
+
+\color red
+approximation ratio
+\color none
+
+\color inherit
-\end_deeper
-\end_deeper
-\layout Standard
+\begin_inset Formula $r>1$
+\end_inset
+.
+\end_layout
+\end_deeper
+\begin_layout Standard
\begin_inset ERT
-status Inlined
+status collapsed
-\layout Standard
+\begin_layout Plain Layout
-\backslash
-onslide<2,4,6,8,10>
-\end_inset
+\backslash
+nointerlineskip
+\end_layout
-\layout Block
+\end_inset
-\begin_inset ERT
-status Inlined
+\end_layout
-\layout Standard
-{Variants of Path Finding Problems}
-\end_inset
+\begin_layout Overprint
+\begin_inset Argument item:1
+status open
+\begin_layout Plain Layout
-\begin_deeper
-\layout Standard
+1,3,5,7,9,11-12
+\end_layout
+\end_inset
-\begin_inset ERT
-status Inlined
-\layout Standard
+\end_layout
-\backslash
-usedescriptionitemofwidthas{Approximation Problem:}
-\end_inset
+\begin_deeper
+\begin_layout Columns
+\begin_inset Argument 1
+status open
+\begin_layout Plain Layout
+t,onlytextwidth
+\end_layout
-\layout Description
+\end_inset
-Reachability\SpecialChar ~
-Problem:
-\begin_inset ERT
-status Collapsed
-\layout Standard
-<2->
-\end_inset
+\end_layout
-Is there a path from
-\begin_inset Formula $s$
-\end_inset
+\begin_deeper
+\begin_layout Standard
+\begin_inset Flex Alternative
+status open
- to\SpecialChar ~
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-\begin_inset Formula $t$
-\end_inset
+\begin_layout Plain Layout
-?
-\layout Description
+1-2
+\end_layout
-Construction\SpecialChar ~
-Problem:
-\begin_inset ERT
-status Collapsed
+\end_inset
-\layout Standard
-<4->
-\end_inset
-Construct a path from
-\begin_inset Formula $s$
-\end_inset
+\begin_inset Argument 2
+status open
- to\SpecialChar ~
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
-\begin_inset Formula $t$
-\end_inset
+\begin_layout Plain Layout
-?
-\layout Description
-Optimization\SpecialChar ~
-Problem:
-\begin_inset ERT
-status Collapsed
+\backslash
+column{
+\backslash
+textwidth}
+\end_layout
-\layout Standard
-<6->
-\end_inset
+\end_inset
-Construct a shortest path from
-\begin_inset Formula $s$
-\end_inset
- to\SpecialChar ~
+\end_layout
-\begin_inset Formula $t$
-\end_inset
+\end_inset
-.
-\layout Description
-Distance\SpecialChar ~
-Problem:
\begin_inset ERT
-status Collapsed
+status open
-\layout Standard
-<8->
-\end_inset
+\begin_layout Plain Layout
-Is the distance of
-\begin_inset Formula $s$
-\end_inset
- and\SpecialChar ~
+\backslash
+column{5cm}
+\end_layout
-\begin_inset Formula $t$
-\end_inset
+\end_inset
- at most\SpecialChar ~
-\begin_inset Formula $d$
-\end_inset
+\end_layout
-?
-\layout Description
+\end_inset
-Approximation\SpecialChar ~
-Problem:
-\begin_inset ERT
-status Collapsed
-\layout Standard
-<10->
-\end_inset
+\end_layout
-Construct a path from
-\begin_inset Formula $s$
-\end_inset
+\begin_layout ExampleBlock
+\begin_inset Argument 2
+status collapsed
- to\SpecialChar ~
+\begin_layout Plain Layout
+Example Input
+\end_layout
-\begin_inset Formula $t$
-\end_inset
+\end_inset
- of length
-\newline
-approximately their distance.
-\end_deeper
-\end_deeper
-\layout Section
-Review
-\layout Subsection
+\end_layout
-Standard Complexity Classes
-\layout Standard
+\begin_deeper
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+\begin_layout Plain Layout
-\begin_inset ERT
-status Inlined
-\layout Standard
+\backslash
+begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
+\end_layout
-\backslash
-pgfdeclaremask{computer-mask}{beamer-g4-mask}
-\backslash
-pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer-g4}
-\end_inset
+\begin_layout Plain Layout
+\end_layout
-\layout BeginFrame
+\begin_layout Plain Layout
-The Classes L and NL are Defined via
-\newline
-Logspace Turing Machines
-\layout Standard
+
+\backslash
+color{beamerexample}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Open
+\end_layout
-\layout Standard
+\begin_layout Plain Layout
-\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
+\backslash
pgfsetlinewidth{0.6pt}
-\layout Standard
+\end_layout
-\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
+\begin_layout Plain Layout
-\backslash
-end{pgfpicture}
-\end_inset
+\end_layout
+\begin_layout Plain Layout
-\layout BeginFrame
+
+\backslash
+graphnode{A}{
+\backslash
+pgfxy(3,1)}
+\end_layout
-Logspace Turing Machines Are Quite Powerful
-\layout Block
+\begin_layout Plain Layout
+\end_layout
-\begin_inset ERT
-status Inlined
+\begin_layout Plain Layout
-\layout Standard
-{Deterministic logspace machines can compute}
-\end_inset
+
+\backslash
+graphnode{B}{
+\backslash
+pgfxy(5,1)}
+\end_layout
+\begin_layout Plain Layout
-\begin_deeper
-\layout Itemize
+\end_layout
-addition, multiplication, and even division
-\layout Itemize
+\begin_layout Plain Layout
-reductions used in completeness proofs,
-\layout Itemize
+
+\backslash
+graphnode{C}{
+\backslash
+pgfxy(4,0)}
+\end_layout
-reachability in forests.
-\end_deeper
-\layout Pause
+\begin_layout Plain Layout
-\layout Block
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Inlined
+
+\backslash
+graphnode{D}{
+\backslash
+pgfxy(4,2)}
+\end_layout
-\layout Standard
-{Non-deterministic logspace machines can compute}
-\end_inset
+\begin_layout Plain Layout
+\end_layout
-\begin_deeper
-\layout Itemize
+\begin_layout Plain Layout
-reachability in graphs,
-\layout Itemize
+\end_layout
-non-reachability in graphs,
-\layout Itemize
+\begin_layout Plain Layout
-satisfiability with two literals per clause.
-\end_deeper
-\layout BeginFrame
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Inlined
+
+\backslash
+color{white}
+\end_layout
-\layout Standard
-<1>[label=hierarchy]
-\end_inset
+\begin_layout Plain Layout
-The Complexity Class Hierarchy
-\layout Standard
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Inlined
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{B}}{
+\backslash
+pgfbox[center,center]{$t$}}
+\end_layout
-\layout Standard
+\begin_layout Plain Layout
-\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
+\end_layout
-\layout Standard
-
-\backslash
-pgfsetlinewidth{1.0pt}
-\layout Standard
-
-\backslash
-color{black}
-\layout Standard
-
-\backslash
-pgfxyline(-5,0)(5,0)
-\layout Standard
+\begin_layout Plain Layout
-\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
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D}}{
+\backslash
+pgfbox[center,center]{$s$}}
+\end_layout
-\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
+\begin_layout Plain Layout
-\backslash
-end{pgfpicture}
-\end_inset
+\end_layout
+\begin_layout Plain Layout
-\layout BeginFrame
+\end_layout
-The Circuit Complexity Classes AC
-\begin_inset Formula $^{0}$
-\end_inset
+\begin_layout Plain Layout
-, NC
-\begin_inset Formula $^{1}$
-\end_inset
+\end_layout
-, and NC
-\begin_inset Formula $^{2}$
-\end_inset
+\begin_layout Plain Layout
+
+\backslash
+color{beamerexample}
+\end_layout
-\newline
-Limit the Circuit Depth
-\layout Standard
+\begin_layout Plain Layout
+\end_layout
-\begin_inset ERT
-status Inlined
+\begin_layout Plain Layout
-\layout Standard
+
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\end_layout
-\backslash
-setlength
-\backslash
-leftmargini{1em}
-\layout Standard
+\begin_layout Plain Layout
-\backslash
-nointerlineskip
-\end_inset
+\end_layout
+\begin_layout Plain Layout
-\layout Columns
+
+\backslash
+pgfnodesetsepstart{2pt}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+\end_layout
-\layout Standard
-[t]
-\end_inset
+\begin_layout Plain Layout
+
+\backslash
+pgfnodesetsepend{4pt}
+\end_layout
-\begin_deeper
-\layout Column
+\begin_layout Plain Layout
-3.6cm
-\layout Block
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+
+\backslash
+pgfnodeconnline{A}{B}
+\end_layout
-\layout Standard
-{
-\end_inset
+\begin_layout Plain Layout
-Circuit Class
-\begin_inset Formula $\Class{AC}^{0}$
-\end_inset
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+
+\backslash
+pgfnodeconnline{A}{C}
+\end_layout
-\layout Standard
-}
-\end_inset
+\begin_layout Plain Layout
+\end_layout
-\begin_deeper
-\layout Itemize
+\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{D}{A}
+\end_layout
-\begin_inset Formula $O(1)$
-\end_inset
+\begin_layout Plain Layout
- depth
-\layout Itemize
+\end_layout
-unbounded fan-in
-\end_deeper
-\layout Examples
+\begin_layout Plain Layout
-\begin_deeper
-\layout Itemize
+
+\backslash
+pgfnodeconnline{C}{B}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
-\end_inset
+\end_layout
-.
-\layout Itemize
+\begin_layout Plain Layout
+
+\backslash
+pgfnodeconnline{B}{D}
+\end_layout
-\begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
-\end_inset
+\begin_layout Plain Layout
-.
-\end_deeper
-\layout Pause
+\end_layout
-\layout Column
+\begin_layout Plain Layout
-3.6cm
-\layout Block
+
+\backslash
+pgfnodeconnline{D}{C}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+\end_layout
-\layout Standard
-{
-\end_inset
+\begin_layout Plain Layout
-Circuit Class
-\begin_inset Formula $\Class{NC}^{1}$
-\end_inset
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+\end_layout
-\layout Standard
-}
-\end_inset
+\begin_layout Plain Layout
+
+\backslash
+only<9> {
+\backslash
+pgfputat{
+\backslash
+pgfxy(5.3,1)}{
+\backslash
+pgfbox[left,center]{, $d=2$}}}
+\end_layout
-\begin_deeper
-\layout Itemize
+\begin_layout Plain Layout
+\end_layout
-\begin_inset Formula $O(\log n)$
-\end_inset
+\begin_layout Plain Layout
- depth
-\layout Itemize
+
+\backslash
+only<11>{
+\backslash
+pgfputat{
+\backslash
+pgfxy(5.3,1)}{
+\backslash
+pgfbox[left,center]{, $r=1.5$}}}
+\end_layout
-bounded fan-in
-\end_deeper
-\layout Examples
+\begin_layout Plain Layout
-\begin_deeper
-\layout Itemize
+\end_layout
+\begin_layout Plain Layout
-\begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
-\end_inset
+
+\backslash
+only<12>{
+\backslash
+pgfputat{
+\backslash
+pgfxy(5.3,1)}{
+\backslash
+pgfbox[left,center]{, $r=1.25$}}}
+\end_layout
-.
-\layout Itemize
+\begin_layout Plain Layout
+\end_layout
-\begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
-\end_inset
+\begin_layout Plain Layout
-.
-\layout Itemize
+\backslash
+end{pgfpicture}
+\end_layout
-\begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
-\end_inset
+\end_inset
-.
-\end_deeper
-\layout Pause
-\layout Column
+\end_layout
-3.6cm
-\layout Block
+\end_deeper
+\begin_layout Standard
+\begin_inset Flex Only
+status open
+\begin_layout Plain Layout
+\begin_inset Argument 1
+status open
-\begin_inset ERT
-status Collapsed
+\begin_layout Plain Layout
-\layout Standard
-{
-\end_inset
+3-
+\end_layout
-Circuit Class
-\begin_inset Formula $\Class{NC}^{2}$
-\end_inset
+\end_inset
\begin_inset ERT
-status Collapsed
+status open
-\layout Standard
-}
-\end_inset
+\begin_layout Plain Layout
-\begin_deeper
-\layout Itemize
+\backslash
+column{5cm}
+\end_layout
+\end_inset
-\begin_inset Formula $O(\log^{2}n)$
-\end_inset
- depth
-\layout Itemize
+\end_layout
-bounded fan-in
-\end_deeper
-\layout Examples
+\end_inset
-\begin_deeper
-\layout Itemize
+\end_layout
-\begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
-\end_inset
+\begin_layout ExampleBlock
+\begin_inset Argument 1
+status collapsed
-.
-\end_deeper
-\end_deeper
-\layout AgainFrame
+\begin_layout Plain Layout
+only@3-
+\end_layout
-\begin_inset ERT
-status Collapsed
+\end_inset
-\layout Standard
-<2>
-\end_inset
-hierarchy
-\layout Subsection
+\begin_inset Argument 2
+status collapsed
-Standard Complexity Results on Finding Paths
-\layout BeginFrame
+\begin_layout Plain Layout
+Example Output
+\end_layout
-All Variants of Finding Paths in Directed Graphs
-\newline
-Are Equally Difficult
-\layout Fact
+\end_inset
-\begin_inset Formula $\Lang{reach}$
-\end_inset
+\end_layout
- and
-\begin_inset Formula $\Lang{distance}$
-\end_inset
+\begin_deeper
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
- are
-\begin_inset Formula $\Class{NL}$
-\end_inset
+\begin_layout Plain Layout
--complete.
-
-\layout Pause
-\layout Corollary
+\backslash
+begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
+\end_layout
-For directed graphs, we can solve
-\begin_deeper
-\layout Itemize
+\begin_layout Plain Layout
-the reachability problem in logspace iff
-\begin_inset Formula $\Class{L}=\Class{NL}$
-\end_inset
-.
-\layout Itemize
+\backslash
+only<5-8,10->{%
+\end_layout
-the construction problem in logspace iff
-\begin_inset Formula $\Class{L}=\Class{NL}$
-\end_inset
+\begin_layout Plain Layout
-.
-\layout Itemize
+
+\backslash
+color{beamerexample}
+\end_layout
-the optimization problem in logspace iff
-\begin_inset Formula $\Class{L}=\Class{NL}$
-\end_inset
+\begin_layout Plain Layout
-.
-\layout Itemize
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\end_layout
-the approximation problem in logspace iff
-\begin_inset Formula $\Class{L}=\Class{NL}$
-\end_inset
+\begin_layout Plain Layout
-.
-\end_deeper
-\layout AgainFrame
+
+\backslash
+graphnode{A}{
+\backslash
+pgfxy(3,1)}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+
+\backslash
+graphnode{B}{
+\backslash
+pgfxy(5,1)}
+\end_layout
-\layout Standard
-<3>
-\end_inset
+\begin_layout Plain Layout
-hierarchy
-\layout BeginFrame
+
+\backslash
+graphnode{C}{
+\backslash
+pgfxy(4,0)}
+\end_layout
-FindingPaths in Forests and Directed Paths is Easy,
-\newline
-But Not Trivial
-\layout Fact
+\begin_layout Plain Layout
+
+\backslash
+graphnode{D}{
+\backslash
+pgfxy(4,2)}
+\end_layout
-\begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
-\end_inset
+\begin_layout Plain Layout
- and
-\begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
-\end_inset
+
+\backslash
+color{white}
+\end_layout
- are
-\begin_inset Formula $\Class{L}$
-\end_inset
+\begin_layout Plain Layout
--complete.
-\layout Separator
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{B}}{
+\backslash
+pgfbox[center,center]{$t$}}
+\end_layout
-\layout Fact
+\begin_layout Plain Layout
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D}}{
+\backslash
+pgfbox[center,center]{$s$}}
+\end_layout
-\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
-\end_inset
+\begin_layout Plain Layout
- and
-\begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
-\end_inset
+
+\backslash
+color{beamerexample}
+\end_layout
- are
-\begin_inset Formula $\Class{L}$
-\end_inset
+\begin_layout Plain Layout
--complete.
-\layout AgainFrame
+
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+
+\backslash
+pgfnodesetsepstart{2pt}
+\end_layout
-\layout Standard
-<4>
-\end_inset
+\begin_layout Plain Layout
-hierarchy
-\layout Section
+
+\backslash
+pgfnodesetsepend{4pt}
+\end_layout
-Finding Paths in Tournaments
-\layout Subsection
+\begin_layout Plain Layout
-Complexity of: Does a Path Exist?
-\layout BeginFrame
+
+\backslash
+alert<7,12>{
+\backslash
+pgfnodeconnline{A}{B}}
+\end_layout
-Definition of the Tournament Reachability Problem
-\layout Definition
+\begin_layout Plain Layout
-Let
-\color red
+
+\backslash
+alert<5,11>{
+\backslash
+pgfnodeconnline{A}{C}}
+\end_layout
-\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
-\end_inset
+\begin_layout Plain Layout
+
+\backslash
+alert<5,7,11-12>{
+\backslash
+pgfnodeconnline{D}{A}}
+\end_layout
-\color default
- contain all triples
-\begin_inset Formula $(T,s,t)$
-\end_inset
+\begin_layout Plain Layout
- such that
-\begin_deeper
-\layout Enumerate
+
+\backslash
+alert<5,11>{
+\backslash
+pgfnodeconnline{C}{B}}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset Formula $T=(V,E)$
-\end_inset
+
+\backslash
+pgfnodeconnline{B}{D}
+\end_layout
- is a tournament and
-\layout Enumerate
+\begin_layout Plain Layout
-there exists a path from\SpecialChar ~
+
+\backslash
+pgfnodeconnline{D}{C}
+\end_layout
-\begin_inset Formula $s$
-\end_inset
+\begin_layout Plain Layout
+
+}
+\end_layout
- to\SpecialChar ~
+\begin_layout Plain Layout
-\begin_inset Formula $t$
-\end_inset
-.
-\end_deeper
-\layout BeginFrame
+\backslash
+only<3,9>{
+\backslash
+pgfputat{
+\backslash
+pgfxy(2.75,1)}{
+\backslash
+pgfbox[left,center]{
+\backslash
+alert{``Yes''}}}}
+\end_layout
-The Tournament Reachability Problem is Very Easy
-\layout Theorem
+\begin_layout Plain Layout
-\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
-\end_inset
+\backslash
+end{pgfpicture}
+\end_layout
-.
-\layout Pause
+\end_inset
-\layout AlertBlock
+\end_layout
-\begin_inset ERT
-status Inlined
+\end_deeper
+\end_deeper
+\end_deeper
+\begin_layout Overprint
+\begin_inset Argument item:1
+status open
-\layout Standard
-{Implications}
-\end_inset
+\begin_layout Plain Layout
+2,4,6,8,10
+\end_layout
-\begin_deeper
-\layout Itemize
+\end_inset
-The problem is
-\begin_inset Quotes eld
-\end_inset
-easier
-\begin_inset Quotes erd
-\end_inset
+\end_layout
- than
-\begin_inset Formula $\Lang{reach}$
-\end_inset
+\begin_deeper
+\begin_layout Block
+\begin_inset Argument 2
+status collapsed
- and even
-\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
-\end_inset
+\begin_layout Plain Layout
+Variants of Path Finding Problems
+\end_layout
-.
-\layout Itemize
+\end_inset
-\begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
-\end_inset
+\end_layout
-.
-\end_deeper
-\layout AgainFrame
+\begin_deeper
+\begin_layout Description
+\begin_inset Argument item:1
+status open
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+2-
+\end_layout
-\layout Standard
-<5>
-\end_inset
+\end_inset
-hierarchy
-\layout Subsection
+Reachability
+\begin_inset space ~
+\end_inset
-Complexity of: Construct a Shortest Path
-\layout BeginFrame
+Problem: Is there a path from
+\begin_inset Formula $s$
+\end_inset
-Finding a Shortest Path Is as Difficult as
-\newline
-the Distance Problem
-\layout Definition
+ to
+\begin_inset space ~
+\end_inset
-Let
-\color red
-\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
-\end_inset
+\begin_inset Formula $t$
+\end_inset
-
-\color default
-contain all tuples
-\begin_inset Formula $(T,s,t,d)$
-\end_inset
+?
+\begin_inset Argument 2
+status open
- such that
-\begin_deeper
-\layout Enumerate
+\begin_layout Plain Layout
+Approximation Problem:
+\end_layout
+\end_inset
-\begin_inset Formula $T=(V,E)$
-\end_inset
- is a tournament in which
-\layout Enumerate
+\end_layout
-the distance of
+\begin_layout Description
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+
+4-
+\end_layout
+
+\end_inset
+
+Construction
+\begin_inset space ~
+\end_inset
+
+Problem: Construct a path from
\begin_inset Formula $s$
-\end_inset
+\end_inset
+
+ to
+\begin_inset space ~
+\end_inset
- and\SpecialChar ~
\begin_inset Formula $t$
-\end_inset
+\end_inset
- is at most\SpecialChar ~
+?
+\end_layout
-\begin_inset Formula $d$
-\end_inset
+\begin_layout Description
+\begin_inset Argument item:1
+status open
-.
-\end_deeper
-\layout BeginFrame
+\begin_layout Plain Layout
-The Tournament Distance Problem is Hard
-\layout Theorem
+6-
+\end_layout
+\end_inset
-\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
-\end_inset
+Optimization
+\begin_inset space ~
+\end_inset
- is
-\begin_inset Formula $\Class{NL}$
-\end_inset
+Problem: Construct a shortest path from
+\begin_inset Formula $s$
+\end_inset
--complete.
-\layout Standard
+ to
+\begin_inset space ~
+\end_inset
-\hfill
+\begin_inset Formula $t$
+\end_inset
-\begin_inset ERT
-status Inlined
+.
+\end_layout
-\layout Standard
+\begin_layout Description
+\begin_inset Argument item:1
+status open
-\backslash
-hyperlink{hierarchy<6>}{
-\backslash
-beamerskipbutton{Skip Proof}}
-\end_inset
+\begin_layout Plain Layout
+8-
+\end_layout
-\layout Pause
+\end_inset
-\layout Corollary
+Distance
+\begin_inset space ~
+\end_inset
-Shortest path in tournaments can be constructed
-\newline
-in logarithmic space, iff
-\begin_inset Formula $\Class{L}=\Class{NL}$
-\end_inset
+Problem: Is the distance of
+\begin_inset Formula $s$
+\end_inset
-.
-\layout Pause
+ and
+\begin_inset space ~
+\end_inset
-\layout Corollary
+\begin_inset Formula $t$
+\end_inset
-\begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
-\end_inset
+ at most
+\begin_inset space ~
+\end_inset
-.
-\layout BeginFrame
-Proof That
-\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
-\end_inset
+\begin_inset Formula $d$
+\end_inset
- is NL-complete
-\layout Standard
+?
+\end_layout
+\begin_layout Description
+\begin_inset Argument item:1
+status open
-\begin_inset ERT
-status Collapsed
+\begin_layout Plain Layout
-\layout Standard
+10-
+\end_layout
-\backslash
-nointerlineskip
-\end_inset
+\end_inset
+Approximation
+\begin_inset space ~
+\end_inset
-\layout Columns
+Problem: Construct a path from
+\begin_inset Formula $s$
+\end_inset
+ to
+\begin_inset space ~
+\end_inset
-\begin_inset ERT
-status Inlined
-\layout Standard
-[t,onlytextwidth]
-\end_inset
+\begin_inset Formula $t$
+\end_inset
+ of length
+\begin_inset Newline newline
+\end_inset
-\begin_deeper
-\layout Column
+approximately their distance.
+\end_layout
-5.7cm
-\layout Standard
+\end_deeper
+\end_deeper
+\end_deeper
+\begin_layout Section
+Review
+\end_layout
+\begin_layout Subsection
+Standard Complexity Classes
+\end_layout
+\begin_layout Standard
\begin_inset ERT
-status Inlined
+status collapsed
-\layout Standard
+\begin_layout Plain Layout
-\backslash
-setlength
-\backslash
-leftmargini{1.5em}
-\end_inset
+\backslash
+pgfdeclaremask{computer-mask}{beamer-g4-mask}
+\backslash
+pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
+-g4}
+\end_layout
-\layout Block
+\end_inset
-\begin_inset ERT
-status Collapsed
+\end_layout
-\layout Standard
-{
-\end_inset
+\begin_layout Frame
+\begin_inset Argument 4
+status open
-Reduce
-\begin_inset Formula $\Lang{reach}$
-\end_inset
+\begin_layout Plain Layout
+The Classes L and NL are Defined via
+\begin_inset Newline newline
+\end_inset
- to
-\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
-\end_inset
+Logspace Turing Machines
+\end_layout
+\end_inset
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
\begin_inset ERT
-status Collapsed
+status collapsed
-\layout Standard
-}
-\end_inset
+\begin_layout Plain Layout
-\begin_deeper
-\layout Enumerate
+\backslash
+begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Inlined
-\layout Standard
-<alert@1>
-\end_inset
+\backslash
+pgfputat{
+\backslash
+pgfxy(0,4)}{%
+\end_layout
-Is input
-\begin_inset Formula $(G,s,t)$
-\end_inset
+\begin_layout Plain Layout
- in
-\begin_inset Formula $\Lang{reach}$
-\end_inset
+
+\backslash
+tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
+\end_layout
-?
-\layout Enumerate
+\begin_layout Plain Layout
-\begin_inset ERT
-status Inlined
+\backslash
+uncover<2->{%
+\end_layout
-\layout Standard
-<2-| alert@2-8>
-\end_inset
+\begin_layout Plain Layout
-Map
-\begin_inset Formula $G$
-\end_inset
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(0,0.5)}{%
+\end_layout
- to
-\begin_inset Formula $G'$
-\end_inset
+\begin_layout Plain Layout
-.
-\layout Enumerate
+
+\backslash
+tape{}{output tape (write only)}{10690836937182}}
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Inlined
+}
+\end_layout
-\layout Standard
-<9-| alert@9>
-\end_inset
+\begin_layout Plain Layout
-Query:
-\newline
-\begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
-\end_inset
+\backslash
+uncover<3->{%
+\end_layout
-?
-\end_deeper
-\layout Separator
+\begin_layout Plain Layout
-\layout Block
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(7,2)}{%
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
+
+\backslash
+shorttape{work tape (read/write), $O(
+\backslash
+log n)$ symbols}{}{42}}
+\end_layout
-\layout Standard
-{
-\end_inset
+\begin_layout Plain Layout
-Correctness
-\begin_inset ERT
-status Collapsed
+
+\backslash
+pgfputat{
+\backslash
+pgfxy(1.75,2.5)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfbox[center,center]{
+\backslash
+pgfuseimage{computer}}}
+\end_layout
+
+\begin_layout Plain Layout
-\layout Standard
}
-\end_inset
+\end_layout
+\begin_layout Plain Layout
-\begin_inset ERT
-status Collapsed
-\layout Standard
-<10->
-\end_inset
+\backslash
+pgfsetlinewidth{0.6pt}
+\end_layout
+\begin_layout Plain Layout
-\begin_deeper
-\layout Enumerate
+\backslash
+color{structure}
+\end_layout
-\begin_inset ERT
-status Inlined
+\begin_layout Plain Layout
-\layout Standard
-<10-| alert@10-11>
-\end_inset
-A path in\SpecialChar ~
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\end_layout
-\begin_inset Formula $G$
-\end_inset
+\begin_layout Plain Layout
- induces
-\newline
-a length-3 path in\SpecialChar ~
-\begin_inset Formula $G'$
-\end_inset
+\backslash
+pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
+\end_layout
-.
-\layout Enumerate
+\begin_layout Plain Layout
-\begin_inset ERT
-status Inlined
+\backslash
+uncover<2->{
+\backslash
+pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
+\end_layout
-\layout Standard
-<12-| alert@12-13>
-\end_inset
+\begin_layout Plain Layout
-A length-3 path in\SpecialChar ~
-\begin_inset Formula $G'$
-\end_inset
+\backslash
+uncover<3->{
+\backslash
+pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
+\end_layout
- induces
-\newline
-a path in\SpecialChar ~
+\begin_layout Plain Layout
-\begin_inset Formula $G'$
-\end_inset
-.
-\end_deeper
-\layout Column
+\backslash
+end{pgfpicture}
+\end_layout
-4.5cm
-\layout Example
+\end_inset
-\begin_inset ERT
-status Inlined
+\end_layout
-\layout Standard
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
-\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
+\end_layout
-\layout Standard
-
-\backslash
-color{beamerexample}
-\layout Standard
-
-\backslash
-pgfsetendarrow{
-\backslash
-pgfarrowto}
-\layout Standard
-
-\backslash
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+Logspace Turing Machines Are Quite Powerful
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Block
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Deterministic logspace machines can compute
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+addition, multiplication, and even division
+\end_layout
+
+\begin_layout Itemize
+reductions used in completeness proofs,
+\end_layout
+
+\begin_layout Itemize
+reachability in forests.
+\end_layout
+
+\end_deeper
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Non-deterministic logspace machines can compute
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+reachability in graphs,
+\end_layout
+
+\begin_layout Itemize
+non-reachability in graphs,
+\end_layout
+
+\begin_layout Itemize
+satisfiability with two literals per clause.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 1
+status collapsed
+
+\begin_layout Plain Layout
+
+1
+\end_layout
+
+\end_inset
+
+
+\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
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfsetlinewidth{0.8pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+heap{5.5}{3.5}{$
+\backslash
+Class P$}{black}{1}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfsetdash{{2pt}}{0pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<2->{
+\backslash
+heap{4.5}{3}{$
+\backslash
+Class{NC}^2$}{black!50!structure}{2}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+heap{3.5}{2.5}{$
+\backslash
+Class{NL}$}{black!50!structure}{3}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+heap{2.5}{2}{$
+\backslash
+Class{L}$}{black!50!structure}{4}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<2->{
+\backslash
+heap{1.75}{1.5}{$
+\backslash
+vphantom{A}%
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+smash{
+\backslash
+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
+
+
+\backslash
+only<2->{
+\backslash
+heap{1.1}{1}{$
+\backslash
+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
+
+
+\backslash
+pgfsetlinewidth{1.0pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+color{black}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfxyline(-5,0)(5,0)
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<1-2>{
+\backslash
+langat{3.375}{$
+\backslash
+Lang{reach}$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<1-2>{
+\backslash
+langat{2.375}{$
+\backslash
+Lang{reach}_{
+\backslash
+operatorname{forest}}$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<2>{
+\backslash
+langat{0.975}{$
+\backslash
+Lang{addition}$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<2>{
+\backslash
+langatother{1.6}{
+\backslash
+vbox{
+\backslash
+hbox{$
+\backslash
+Lang{division}$,}
+\backslash
+hbox{$
+\backslash
+Lang{parity}$}}}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<3-5>{
+\backslash
+langat{3.375}{
+\backslash
+vbox{
+\backslash
+hbox{$
+\backslash
+Lang{distance}$,}
+\backslash
+hbox{$
+\backslash
+Lang{reach}$}}}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<4->{
+\backslash
+langatother{2.375}{
+\backslash
+vbox{
+\backslash
+ignorespaces
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+hbox{$
+\backslash
+Lang{distance}_{
+\backslash
+operatorname{forest}}$,}
+\backslash
+ignorespaces
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+hbox{$
+\backslash
+Lang{reach}_{
+\backslash
+operatorname{forest}}$,}
+\backslash
+ignorespaces
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+hbox{$
+\backslash
+Lang{distance}_{
+\backslash
+operatorname{path}}$,}
+\backslash
+ignorespaces
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+hbox{$
+\backslash
+Lang{reach}_{
+\backslash
+operatorname{path}}$}}}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<5->{
+\backslash
+langat{0.975}{$
+\backslash
+Lang{reach}_{
+\backslash
+operatorname{tourn}}$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<6->{
+\backslash
+langat{3.375}{
+\backslash
+vbox{
+\backslash
+ignorespaces
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+hbox{$
+\backslash
+Lang{distance}_{
+\backslash
+operatorname{tourn}}$,}
+\backslash
+ignorespaces
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+hbox{$
+\backslash
+Lang{distance}$,}
+\backslash
+ignorespaces
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+hbox{$
+\backslash
+Lang{reach}$}}}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<7->{
+\backslash
+pgfsetdash{{1pt}}{0pt}%
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+langat{2.375}{``$
+\backslash
+Lang{approx}_{
+\backslash
+operatorname{tourn}}$''}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{pgfpicture}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\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
+
+, NC
+\begin_inset Formula $^{1}$
+\end_inset
+
+, and NC
+\begin_inset Formula $^{2}$
+\end_inset
+
+
+\begin_inset Newline newline
+\end_inset
+
+Limit the Circuit Depth
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+setlength
+\backslash
+leftmargini{1em}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+nointerlineskip
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Columns
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+t
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Column
+3.6cm
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Circuit Class
+\begin_inset Formula $\Class{AC}^{0}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $O(1)$
+\end_inset
+
+ depth
+\end_layout
+
+\begin_layout Itemize
+unbounded fan-in
+\end_layout
+
+\end_deeper
+\begin_layout Examples
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Column
+3.6cm
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Circuit Class
+\begin_inset Formula $\Class{NC}^{1}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ depth
+\end_layout
+
+\begin_layout Itemize
+bounded fan-in
+\end_layout
+
+\end_deeper
+\begin_layout Examples
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Column
+3.6cm
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Circuit Class
+\begin_inset Formula $\Class{NC}^{2}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $O(\log^{2}n)$
+\end_inset
+
+ depth
+\end_layout
+
+\begin_layout Itemize
+bounded fan-in
+\end_layout
+
+\end_deeper
+\begin_layout Examples
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status collapsed
+
+\begin_layout Plain Layout
+
+2
+\end_layout
+
+\end_inset
+
+hierarchy
+\end_layout
+
+\begin_layout Subsection
+Standard Complexity Results on Finding Paths
+\end_layout
+
+\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
+
+
+\end_layout
+
+\begin_deeper
+\begin_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.
+
+\end_layout
+
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Corollary
+For directed graphs, we can solve
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+the reachability problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+the construction problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+the optimization problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+the approximation problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status collapsed
+
+\begin_layout Plain Layout
+
+3
+\end_layout
+
+\end_inset
+
+hierarchy
+\end_layout
+
+\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
+
+
+\end_layout
+
+\begin_deeper
+\begin_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.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_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.
+\end_layout
+
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status collapsed
+
+\begin_layout Plain Layout
+
+4
+\end_layout
+
+\end_inset
+
+hierarchy
+\end_layout
+
+\begin_layout Section
+Finding Paths in Tournaments
+\end_layout
+
+\begin_layout Subsection
+Complexity of: Does a Path Exist?
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+Definition of the Tournament Reachability Problem
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Definition
+Let
+\color none
+
+\color red
+
+\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
+\end_inset
+
+
+\color none
+
+\color inherit
+contain all triples
+\begin_inset Formula $(T,s,t)$
+\end_inset
+
+ such that
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Formula $T=(V,E)$
+\end_inset
+
+ is a tournament and
+\end_layout
+
+\begin_layout Enumerate
+there exists a path from
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $s$
+\end_inset
+
+ to
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $t$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\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
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Theorem
+\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout AlertBlock
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Implications
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_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
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+
+5
+\end_layout
+
+\end_inset
+
+hierarchy
+\end_layout
+
+\begin_layout Subsection
+Complexity of: Construct a Shortest Path
+\end_layout
+
+\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
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Definition
+Let
+\color none
+
+\color red
+
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+
+\color none
+
+\color inherit
+contain all tuples
+\begin_inset Formula $(T,s,t,d)$
+\end_inset
+
+ such that
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Formula $T=(V,E)$
+\end_inset
+
+ is a tournament in which
+\end_layout
+
+\begin_layout Enumerate
+the distance of
+\begin_inset Formula $s$
+\end_inset
+
+ and
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $t$
+\end_inset
+
+ is at most
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $d$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\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
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Theorem
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+ is
+\begin_inset Formula $\Class{NL}$
+\end_inset
+
+-complete.
+\end_layout
+
+\begin_layout Standard
+\begin_inset space \hfill{}
+\end_inset
+
+
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+hyperlink{hierarchy<6>}{
+\backslash
+beamerskipbutton{Skip Proof}}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Corollary
+Shortest path in tournaments can be constructed
+\begin_inset Newline newline
+\end_inset
+
+in logarithmic space, iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Corollary
+\begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\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
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+nointerlineskip
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Columns
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+t,onlytextwidth
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Column
+5.7cm
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+setlength
+\backslash
+leftmargini{1.5em}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Reduce
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+ to
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+
+alert@1
+\end_layout
+
+\end_inset
+
+Is input
+\begin_inset Formula $(G,s,t)$
+\end_inset
+
+ in
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+?
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+
+2-| alert@2-8
+\end_layout
+
+\end_inset
+
+Map
+\begin_inset Formula $G$
+\end_inset
+
+ to
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+
+9-| alert@9
+\end_layout
+
+\end_inset
+
+Query:
+\begin_inset Newline newline
+\end_inset
+
+
+\begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+?
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Correctness
+\end_layout
+
+\end_inset
+
+
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+
+10-
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+
+10-| alert@10-11
+\end_layout
+
+\end_inset
+
+A path in
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ induces
+\begin_inset Newline newline
+\end_inset
+
+a length-3 path in
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+
+12-| alert@12-13
+\end_layout
+
+\end_inset
+
+A length-3 path in
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $G'$
+\end_inset
+
+ induces
+\begin_inset Newline newline
+\end_inset
+
+a path in
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Column
+4.5cm
+\end_layout
+
+\begin_layout Example
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+color{beamerexample}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+graphnode{A}{
+\backslash
+pgfxy(1,3.3)}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+graphnode{B}{
+\backslash
+pgfxy(2,3.3)}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+graphnode{C}{
+\backslash
+pgfxy(3,3.3)}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+graphnode{D}{
+\backslash
+pgfxy(4,3.3)}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+color{white}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{A}}{
+\backslash
+pgfbox[center,center]{$s$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D}}{
+\backslash
+pgfbox[center,center]{$t$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+color{beamerexample}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfsetendarrow{
+\backslash
+pgfarrowto}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodesetsepstart{2pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodesetsepend{2pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<3>{
-\backslash
+\backslash
pgfnodeconnline{B}{A}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<4>{
-\backslash
+\backslash
pgfnodeconnline{B}{C}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<5,10-11,13>{
-\backslash
+\backslash
pgfnodeconnline{C}{D}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<6,10-11,13>{
-\backslash
+\backslash
pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
-\layout Standard
-
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfputat{
-\backslash
+\backslash
pgfxy(0,3.3)}{
-\backslash
+\backslash
pgfbox[left,center]{$G
-\backslash
+\backslash
colon$}}
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<2->{%
+\end_layout
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
-only<2->{
-\layout Standard
-
-\backslash
+\backslash
pgfputat{
-\backslash
+\backslash
pgfxy(0,2.25)}{
-\backslash
+\backslash
pgfbox[left,center]{$G'
-\backslash
+\backslash
colon$}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{A1}{
-\backslash
+\backslash
pgfxy(1,2.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{B1}{
-\backslash
+\backslash
pgfxy(2,2.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{C1}{
-\backslash
+\backslash
pgfxy(3,2.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{D1}{
-\backslash
+\backslash
pgfxy(4,2.25)}
-\layout Standard
+\end_layout
-\layout Standard
-
-\backslash
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{A2}{
-\backslash
+\backslash
pgfxy(1,1.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{B2}{
-\backslash
+\backslash
pgfxy(2,1.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{C2}{
-\backslash
+\backslash
pgfxy(3,1.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{D2}{
-\backslash
+\backslash
pgfxy(4,1.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{A3}{
-\backslash
+\backslash
pgfxy(1,0.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{B3}{
-\backslash
+\backslash
pgfxy(2,0.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{C3}{
-\backslash
+\backslash
pgfxy(3,0.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{D3}{
-\backslash
+\backslash
pgfxy(4,0.25)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{A4}{
-\backslash
+\backslash
pgfxy(1,-.75)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{B4}{
-\backslash
+\backslash
pgfxy(2,-.75)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{C4}{
-\backslash
+\backslash
pgfxy(3,-.75)}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
graphnode{D4}{
-\backslash
+\backslash
pgfxy(4,-.75)}
-\layout Standard
- {
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+ {
+\backslash
color{white}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfputat{
-\backslash
+\backslash
pgfnodecenter{A1}}{
-\backslash
+\backslash
pgfbox[center,center]{$s'$}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfputat{
-\backslash
+\backslash
pgfnodecenter{D4}}{
-\backslash
+\backslash
pgfbox[center,center]{$t'$}}
-\layout Standard
- }}
-\layout Standard
-
-\layout Standard
-
-\backslash
-only<8->{
-\layout Standard
-
-\backslash
+\end_layout
+
+\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}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
color{beamerexample!25!averagebackgroundcolor}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A2}{C1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A2}{D1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B2}{A1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B2}{C1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B2}{D1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C2}{D1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D2}{A1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D2}{B1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A3}{C2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A3}{D2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B3}{A2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B3}{C2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B3}{D2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C3}{D2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D3}{A2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D3}{B2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A4}{C3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A4}{D3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B4}{A3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B4}{C3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B4}{D3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C4}{D3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D4}{A3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D4}{B3}
-\layout Standard
+\end_layout
-\layout Standard
-
-\backslash
+\begin_layout Plain Layout
+
+
+\backslash
pgfsetstartarrow{
-\backslash
+\backslash
pgfarrowto}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A1}{B1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B1}{C1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C1}{D1}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A2}{B2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B2}{C2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C2}{D2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A3}{B3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B3}{C3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C3}{D3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A4}{B4}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B4}{C4}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C4}{D4}
-\layout Standard
+\end_layout
-\layout Standard
-
-\backslash
+\begin_layout Plain Layout
+
+
+\backslash
pgfclearstartarrow
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
color{beamerexample}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfsetlinewidth{0.6pt}
-\layout Standard
- }
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<3->{%
+\end_layout
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
-only<3->{
-\layout Standard
-
-\backslash
+\backslash
color<3>{red}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B1}{A2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B2}{A3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B3}{A4}
-\layout Standard
- }
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<4->{%
+\end_layout
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
-only<4->{
-\layout Standard
-
-\backslash
+\backslash
color<4>{red}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B1}{C2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B2}{C3}
-\layout Standard
-
-\backslash
-pgfnodeconnline{B3}{C4}
-\layout Standard
- }
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
-\layout Standard
+\backslash
+pgfnodeconnline{B3}{C4}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<5->{%
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
-only<5->{
-\layout Standard
-
-\backslash
+\backslash
color<5>{red}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C1}{D2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<11>{
-\backslash
+\backslash
pgfnodeconnline{C2}{D3}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<12-13>{
-\backslash
+\backslash
pgfnodeconnline{C3}{D4}}
-\layout Standard
- }
-\layout Standard
-
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<6->{%
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
-only<6->{
-\layout Standard
-
-\backslash
+\backslash
color<6>{red}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<11>{
-\backslash
+\backslash
pgfnodeconnline{A1}{C2}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<12-13>{
-\backslash
+\backslash
pgfnodeconnline{A2}{C3}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A3}{C4}
-\layout Standard
- }
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+only<7->{%
+\end_layout
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
-only<7->{
-\layout Standard
-
-\backslash
+\backslash
color<7>{red}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<12-13>{
-\backslash
+\backslash
pgfnodeconnline{A1}{A2}}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A2}{A3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{A3}{A4}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B1}{B2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B2}{B3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{B3}{B4}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C1}{C2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C2}{C3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{C3}{C4}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D1}{D2}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
pgfnodeconnline{D2}{D3}
-\layout Standard
-
-\backslash
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
alert<11>{
-\backslash
+\backslash
pgfnodeconnline{D3}{D4}}
-\layout Standard
- }
-\layout Standard
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
-\backslash
+\backslash
end{pgfpicture}
-\end_inset
+\end_layout
+\end_inset
-\end_deeper
-\layout AgainFrame
+\end_layout
-\begin_inset ERT
-status Collapsed
+\end_deeper
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
-\layout Standard
-<6>
-\end_inset
+6
+\end_layout
+
+\end_inset
hierarchy
-\layout Subsection
+\end_layout
+\begin_layout Subsection
Complexity of: Approximating the Shortest Path
-\layout BeginFrame
+\end_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
-\layout Definition
+\end_layout
-An
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Definition
+An
+\color none
+
\color red
approximation scheme for
\begin_inset Formula $\Lang{tournament-shortest-path}$
-\end_inset
+\end_inset
-\color default
- gets as input
-\begin_deeper
-\layout Enumerate
+\color none
+
+\color inherit
+gets as input
+\end_layout
+\begin_deeper
+\begin_layout Enumerate
a tuple
\begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
-\end_inset
+\end_inset
and
-\layout Enumerate
+\end_layout
+\begin_layout Enumerate
a number
\begin_inset Formula $r>1$
-\end_inset
+\end_inset
.
-\layout Standard
+\end_layout
+\begin_layout Standard
It outputs
-\layout Itemize
+\end_layout
+\begin_layout Itemize
a path from
\begin_inset Formula $s$
-\end_inset
+\end_inset
+
+ to
+\begin_inset space ~
+\end_inset
- to\SpecialChar ~
\begin_inset Formula $t$
-\end_inset
+\end_inset
of length at most
\begin_inset Formula $r\operatorname{d_{T}}(s,t)$
-\end_inset
+\end_inset
.
-\end_deeper
-\layout BeginFrame
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
There Exists a Logspace Approximation Scheme for
-\newline
+\begin_inset Newline newline
+\end_inset
+
the Tournament Shortest Path Problem
-\layout Theorem
+\end_layout
+
+\end_inset
+
+\end_layout
+
+\begin_deeper
+\begin_layout Theorem
There exists an approximation scheme for
\begin_inset Formula $\Lang{tournament-shortest-path}$
-\end_inset
+\end_inset
that for
\begin_inset Formula $1<r<2$
-\end_inset
+\end_inset
needs space
-\begin_inset Formula \[
-O\left(\log|V|\log\frac{1}{r-1}\right).\]
+\begin_inset Formula
+\[
+O\left(\log|V|\log\frac{1}{r-1}\right).
+\]
-\end_inset
+\end_inset
-\layout Pause
+\end_layout
-\layout Corollary
+\begin_layout Pause
+\end_layout
+
+\begin_layout Corollary
In tournaments, paths can be constructed in logarithmic space.
-\layout Standard
+\end_layout
+\begin_layout Standard
+\begin_inset space \hfill{}
+\end_inset
-\hfill
\begin_inset ERT
-status Inlined
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
hyperlink{optimality}{
-\backslash
+\backslash
beamergotobutton{More Details}}
-\end_inset
+\end_layout
+\end_inset
-\layout AgainFrame
+\end_layout
-\begin_inset ERT
-status Collapsed
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-<7>
-\end_inset
+7
+\end_layout
+
+\end_inset
hierarchy
-\layout Section*
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+If a frame includes a program listing, the frame needs to be marked as
+\begin_inset Quotes eld
+\end_inset
+
+fragile
+\begin_inset Quotes erd
+\end_inset
+
+.
+ \SpecialChar LyX
+ has the FragileFrame layout for this.
+\end_layout
+
+\end_inset
+
+\end_layout
+
+\begin_layout FragileFrame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+Just a frame with a program code listing
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout FragileFrame
+This is some program code:
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset listings
+lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
+inline false
+status open
+
+\begin_layout Plain Layout
+
+def func(param):
+\end_layout
+
+\begin_layout Plain Layout
+
+ 'this is a python function'
+\end_layout
+
+\begin_layout Plain Layout
+
+ pass
+\end_layout
+
+\begin_layout Plain Layout
+
+def func(param):
+\end_layout
+
+\begin_layout Plain Layout
+
+'This is a German word: Tschüs'
+\end_layout
+
+\begin_layout Plain Layout
+
+pass
+\end_layout
+
+\begin_layout Plain Layout
+
+def func(param):
+\end_layout
+
+\begin_layout Plain Layout
+
+'this is a python function'
+\end_layout
+
+\begin_layout Plain Layout
+
+pass
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Section*
Summary
-\layout Subsection*
+\end_layout
+\begin_layout Subsection*
Summary
-\layout BeginFrame
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+\begin_layout Plain Layout
Summary
-\layout Block
+\end_layout
+\end_inset
-\begin_inset ERT
-status Inlined
-\layout Standard
-{Summary}
-\end_inset
+\end_layout
+
+\begin_deeper
+\begin_layout Block
+\begin_inset Argument 2
+status collapsed
+\begin_layout Plain Layout
+Summary
+\end_layout
+
+\end_inset
-\begin_deeper
-\layout Itemize
-Tournament
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+Tournament
+\color none
+
\color red
reachability
-\color default
- is in
-\color red
+\color none
+
+\color inherit
+is in
+\color none
+\color red
+
\begin_inset Formula $\Class{AC}^{0}$
-\end_inset
+\end_inset
-\color default
+\color inherit
.
-\layout Itemize
+\end_layout
-There exists a
+\begin_layout Itemize
+There exists a
+\color none
+
\color red
logspace approximation scheme
-\color default
- for
+\color none
+
+\color inherit
+for
+\color none
+
\color red
approximating
-\color default
- shortest paths in tournaments.
-\layout Itemize
+\color none
+
+\color inherit
+shortest paths in tournaments.
+\end_layout
-Finding
+\begin_layout Itemize
+Finding
+\color none
+
\color red
shortest paths
-\color default
- in tournaments is
-\color red
+\color none
+\color inherit
+in tournaments is
+\color none
+
+\color red
+
\begin_inset Formula $\Class{NL}$
-\end_inset
+\end_inset
-complete
-\color default
+\color inherit
.
-\end_deeper
-\layout Separator
+\end_layout
-\layout Block
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
-\begin_inset ERT
-status Inlined
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Outlook
+\end_layout
-\layout Standard
-{Outlook}
-\end_inset
+\end_inset
-\begin_deeper
-\layout Itemize
+\end_layout
+\begin_deeper
+\begin_layout Itemize
The same results apply to graphs with
-\newline
+\begin_inset Newline newline
+\end_inset
+
bounded independence number.
-\hfill
+\begin_inset space \hfill{}
+\end_inset
+
\begin_inset ERT
-status Inlined
+status collapsed
-\layout Standard
+\begin_layout Plain Layout
-\backslash
+
+\backslash
hyperlink{independence}{
-\backslash
+\backslash
beamergotobutton{More Details}}
-\end_inset
+\end_layout
+
+\end_inset
-\layout Itemize
+\end_layout
+\begin_layout Itemize
The complexity of finding paths in undirected graphs
-\newline
+\begin_inset Newline newline
+\end_inset
+
is partly open.
-\hfill
+\begin_inset space \hfill{}
+\end_inset
+
\begin_inset ERT
-status Inlined
+status collapsed
-\layout Standard
+\begin_layout Plain Layout
-\backslash
+
+\backslash
hyperlink{undirected}{
-\backslash
+\backslash
beamergotobutton{More Details}}
-\end_inset
+\end_layout
+
+\end_inset
-\end_deeper
-\layout Subsection*
+\end_layout
+\end_deeper
+\end_deeper
+\begin_layout Subsection*
For Further Reading
-\layout BeginFrame
+\end_layout
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
For Further Reading
-\layout Standard
+\end_layout
+
+\end_inset
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
\begin_inset ERT
-status Inlined
+status open
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
beamertemplatebookbibitems
-\end_inset
+\end_layout
+\end_inset
-\layout Bibliography
-\bibitem {Moon1968}
-\SpecialChar ~
+\end_layout
+
+\begin_layout Bibliography
+\begin_inset CommandInset bibitem
+LatexCommand bibitem
+key "Moon1968"
+literal "true"
+
+\end_inset
+
+
+\begin_inset space ~
+\end_inset
+
John Moon.
\begin_inset ERT
-status Collapsed
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
newblock
-\end_inset
+\end_layout
+
+\end_inset
-\emph on
+\emph on
Topics on Tournaments.
-\emph default
+\emph default
\begin_inset ERT
-status Collapsed
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
newblock
-\end_inset
+\end_layout
+
+\end_inset
Holt, Rinehart, and Winston, 1968.
\begin_inset ERT
-status Inlined
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
beamertemplatearticlebibitems
-\end_inset
+\end_layout
+
+\end_inset
+
+\end_layout
-\layout Bibliography
-\bibitem {NickelsenT2002}
+\begin_layout Bibliography
+\begin_inset CommandInset bibitem
+LatexCommand bibitem
+key "NickelsenT2002"
+literal "true"
+
+\end_inset
+
+
+\begin_inset space ~
+\end_inset
-\SpecialChar ~
Arfst Nickelsen and Till Tantau.
\begin_inset ERT
-status Collapsed
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
newblock
-\end_inset
+\end_layout
+
+\end_inset
On reachability in graphs with bounded independence number.
\begin_inset ERT
-status Collapsed
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
newblock
-\end_inset
+\end_layout
+
+\end_inset
In
-\emph on
+\emph on
Proc.
of COCOON 2002
-\emph default
+\emph default
, Springer-Verlag, 2002.
-\layout Bibliography
-\bibitem {Tantau2004b}
+\end_layout
+
+\begin_layout Bibliography
+\begin_inset CommandInset bibitem
+LatexCommand bibitem
+key "Tantau2004b"
+literal "true"
+
+\end_inset
+
+
+\begin_inset space ~
+\end_inset
-\SpecialChar ~
Till Tantau
\begin_inset ERT
-status Collapsed
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
newblock
-\end_inset
+\end_layout
+
+\end_inset
A logspace approximation scheme for the shortest path problem for graphs
with bounded independence number.
\begin_inset ERT
-status Collapsed
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
newblock
-\end_inset
+\end_layout
+
+\end_inset
In
-\emph on
+\emph on
Proc.
of STACS 2004
-\emph default
+\emph default
, Springer-Verlag, 2004.
\begin_inset ERT
-status Collapsed
+status collapsed
+
+\begin_layout Plain Layout
-\layout Standard
-\backslash
+\backslash
newblock
-\end_inset
+\end_layout
- In press.
-\layout EndFrame
+\end_inset
-\layout Standard
-\start_of_appendix
+ In press.
+\end_layout
+\end_deeper
+\begin_layout Standard
+\start_of_appendix
\begin_inset ERT
-status Inlined
+status open
+
+\begin_layout Plain Layout
+
-\layout Standard
+\backslash
+AtBeginSubsection[]{}
+\end_layout
-\backslash
-AtBeginSubsection[]{}
-\end_inset
+\end_inset
-\layout Section
+\end_layout
+\begin_layout Section
Appendix
-\layout Subsection
+\end_layout
+\begin_layout Subsection
Graphs With Bounded Independence Number
-\layout BeginFrame
+\end_layout
+\begin_layout Frame
+\begin_inset Argument 3
+status collapsed
-\begin_inset ERT
-status Inlined
+\begin_layout Plain Layout
+label=independence
+\end_layout
+
+\end_inset
-\layout Standard
-[label=independence]
-\end_inset
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Definition of Independence Number of a Graph
-\layout Definition
+\end_layout
+
+\end_inset
-The
+
+\end_layout
+
+\begin_deeper
+\begin_layout Definition
+The
+\color none
+
\color red
independence number
-\color default
+\color none
+\color inherit
+
\begin_inset Formula $\alpha(G)$
-\end_inset
+\end_inset
of a directed graph
-\newline
+\begin_inset Newline newline
+\end_inset
+
is the maximum number of vertices we can pick,
-\newline
+\begin_inset Newline newline
+\end_inset
+
such that there is no edge between them.
-\layout Example
+\end_layout
+\begin_layout Example
Tournaments have independence number 1.
-\layout BeginFrame
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Results for Tournaments also Apply to
-\newline
+\begin_inset Newline newline
+\end_inset
+
Graphs With Bounded Independence Number
-\layout Theorem
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Theorem
+For each
+\begin_inset space ~
+\end_inset
-For each\SpecialChar ~
\begin_inset Formula $k$
-\end_inset
+\end_inset
-,
+,
+\color none
+
\color red
reachability
-\color default
- in graphs with independence number
-\newline
-at most\SpecialChar ~
+\color none
+
+\color inherit
+in graphs with independence number
+\begin_inset Newline newline
+\end_inset
+
+at most
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
-\end_inset
+\end_inset
is in
\begin_inset Formula $\Class{AC}^{0}$
-\end_inset
+\end_inset
.
-\layout Separator
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
-\layout Theorem
+\begin_layout Theorem
+For each
+\begin_inset space ~
+\end_inset
-For each\SpecialChar ~
\begin_inset Formula $k$
-\end_inset
+\end_inset
-, there exists a
+, there exists a
+\color none
+
\color red
logspace approximation scheme
-\color default
- for approximating the shortest path in graphs with independence number
- at most\SpecialChar ~
+\color none
+
+\color inherit
+for approximating the shortest path in graphs with independence number at
+ most
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
-\end_inset
+\end_inset
+
+\end_layout
-\layout Separator
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
-\layout Theorem
-For each\SpecialChar ~
+\end_layout
+
+\begin_layout Theorem
+For each
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
-\end_inset
+\end_inset
-, finding the
+, finding the
+\color none
+
\color red
shortest path
-\color default
- in graphs with independence number at most\SpecialChar ~
+\color none
+
+\color inherit
+in graphs with independence number at most
+\begin_inset space ~
+\end_inset
+
\begin_inset Formula $k$
-\end_inset
+\end_inset
- is
+ is
+\color none
+
\color red
\begin_inset Formula $\Class{NL}$
-\end_inset
+\end_inset
-complete
-\color default
+\color inherit
.
-\layout Subsection
+\end_layout
+\end_deeper
+\begin_layout Subsection
Finding Paths in Undirected Graphs
-\layout BeginFrame
+\end_layout
+\begin_layout Frame
+\begin_inset Argument 1
+status collapsed
-\begin_inset ERT
-status Inlined
+\begin_layout Plain Layout
-\layout Standard
-<1-2>[label=undirected]
-\end_inset
+1-2
+\end_layout
+\end_inset
+
+
+\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
-\newline
+\begin_inset Newline newline
+\end_inset
+
Is Party Unknown.
-\layout Fact
+\end_layout
+\end_inset
+
+\end_layout
+
+\begin_deeper
+\begin_layout Fact
\begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
-\end_inset
+\end_inset
is
\begin_inset Formula $\Class{SL}$
-\end_inset
+\end_inset
-complete.
-\layout Corollary
+\end_layout
+\begin_layout Corollary
For undirected graphs, we can solve
-\begin_deeper
-\layout Itemize
+\end_layout
+\begin_deeper
+\begin_layout Itemize
the reachability problem in logspace iff
\begin_inset Formula $\Class L=\Class{SL}$
-\end_inset
+\end_inset
,
-\layout Itemize
+\end_layout
+\begin_layout Itemize
the construction problem in logspace iff
-\begin_inset ERT
-status Inlined
+\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
-\layout Standard
-\backslash
-alt<1>{?}{
-\backslash
-alert{$
-\backslash
-Class L =
-\backslash
-Class{SL}$}}
-\end_inset
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
,
-\layout Itemize
+\end_layout
+\begin_layout Itemize
the optimization problem in logspace iff
-\begin_inset ERT
-status Inlined
+\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
-\layout Standard
+\begin_layout Plain Layout
+\begin_inset Formula $\Class L=\Class{NL}$
+\end_inset
-\backslash
-alt<1>{?}{
-\backslash
-alert{$
-\backslash
-Class L =
-\backslash
-Class{NL}$}}
-\end_inset
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
,
-\layout Itemize
+\end_layout
+\begin_layout Itemize
the approximation problem in logspace iff ?.
-\end_deeper
-\layout Subsection
+\end_layout
+\end_deeper
+\end_deeper
+\begin_layout Subsection
The Approximation Scheme is Optimal
-\layout BeginFrame
+\end_layout
+\begin_layout Frame
+\begin_inset Argument 3
+status collapsed
+
+\begin_layout Plain Layout
+label=optimality
+\end_layout
+
+\end_inset
-\begin_inset ERT
-status Inlined
-\layout Standard
-[label=optimality]
-\end_inset
+\begin_inset Argument 4
+status open
+\begin_layout Plain Layout
The Approximation Scheme is Optimal
-\layout Theorem
+\end_layout
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Theorem
Suppose there exists an approximation scheme for
\begin_inset Formula $\Lang{tournament-shortest-path}$
-\end_inset
+\end_inset
that needs space
\begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
-\end_inset
+\end_inset
.
Then
\begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
-\end_inset
+\end_inset
.
-\layout Proof
+\end_layout
+
+\begin_layout Proof
-\begin_deeper
-\layout Enumerate
+\end_layout
+\begin_deeper
+\begin_layout Enumerate
Suppose the approximation scheme exists.
-\newline
+\begin_inset Newline newline
+\end_inset
+
We show
\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
-\end_inset
+\end_inset
.
-\layout Enumerate
+\end_layout
+\begin_layout Enumerate
Let
\begin_inset Formula $(T,s,t)$
-\end_inset
+\end_inset
be an input.
Let
\begin_inset Formula $n$
-\end_inset
+\end_inset
be the number of vertices.
-\layout Enumerate
+\end_layout
+\begin_layout Enumerate
Run the approximation scheme for
\begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
-\end_inset
+\end_inset
.
-\newline
+\begin_inset Newline newline
+\end_inset
+
This needs space
\begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
-\end_inset
+\end_inset
.
-\layout Enumerate
+\end_layout
+\begin_layout Enumerate
The resulting path has optimal length.
\begin_inset ERT
-status Collapsed
+status collapsed
-\layout Standard
+\begin_layout Plain Layout
-\backslash
+
+\backslash
qedhere
-\end_inset
+\end_layout
+
+\end_inset
-\end_deeper
-\layout EndFrame
+\end_layout
-\the_end
+\end_deeper
+\end_deeper
+\end_body
+\end_document
projects / lyx.git / blobdiff