-#LyX 2.1 created this file. For more info see http://www.lyx.org/
-\lyxformat 452
+#LyX 2.2 created this file. For more info see http://www.lyx.org/
+\lyxformat 506
\begin_document
\begin_header
+\save_transient_properties true
+\origin /systemlyxdir/examples/
\textclass beamer
\begin_preamble
\beamertemplateshadingbackground{red!5}{structure!5}
\language_package default
\inputencoding auto
\fontencoding global
-\font_roman times
-\font_sans default
-\font_typewriter default
-\font_math auto
+\font_roman "times" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
-\font_sf_scale 100
-\font_tt_scale 100
+\font_sf_scale 100 100
+\font_tt_scale 100 100
\graphics default
\default_output_format default
\output_sync 0
\use_geometry false
\use_package amsmath 2
\use_package amssymb 2
+\use_package cancel 0
\use_package esint 0
\use_package mathdots 1
\use_package mathtools 0
\use_package mhchem 1
+\use_package stackrel 0
+\use_package stmaryrd 0
\use_package undertilde 0
\cite_engine basic
-\cite_engine_type numerical
+\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
January 30th, 2004
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Outline
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents
\end_layout
-\begin_layout EndFrame
-
-\end_layout
-
+\end_deeper
\begin_layout Standard
\begin_inset ERT
-status collapsed
+status open
\begin_layout Plain Layout
What are Tournaments?
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Tournaments Consist of Jousts Between Knights
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Columns
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_deeper
\end_deeper
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Tournaments are Complete Directed Graphs
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Columns
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\color inherit
is a
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_deeper
\end_deeper
-\begin_layout BeginFrame
-\begin_inset ERT
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 2
status collapsed
\begin_layout Plain Layout
-
-[<+>]
++
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Tournaments Arise Naturally in Different Situations
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout ExampleBlock
\begin_inset Argument 2
status collapsed
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
.
\end_layout
+\end_deeper
\end_deeper
\begin_layout Subsection
What Does ``Finding Paths'' Mean?
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
``Finding Paths'' is Ambiguous
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Block
\begin_inset Argument 2
status open
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\begin_layout Overprint
-
-\end_layout
-
-\begin_deeper
-\begin_layout Standard
-\begin_inset ERT
-status collapsed
+\begin_inset Argument item:1
+status open
\begin_layout Plain Layout
+1,3,5,7,9,11-12
+\end_layout
+\end_inset
-\backslash
-onslide<1,3,5,7,9,11-12>
-\end_layout
+\begin_inset Separator parbreak
\end_inset
\end_layout
+\begin_deeper
\begin_layout Columns
\begin_inset Argument 1
status open
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_deeper
\end_deeper
-\begin_layout Standard
-\begin_inset ERT
-status collapsed
+\end_deeper
+\begin_layout Overprint
+\begin_inset Argument item:1
+status open
\begin_layout Plain Layout
+2,4,6,8,10
+\end_layout
+\end_inset
-\backslash
-onslide<2,4,6,8,10>
-\end_layout
+\begin_inset Separator parbreak
\end_inset
\end_layout
+\begin_deeper
\begin_layout Block
\begin_inset Argument 2
status collapsed
\end_inset
-\end_layout
+\begin_inset Separator parbreak
+\end_inset
-\begin_deeper
-\begin_layout Description
-\begin_inset Argument 2
-status open
-\begin_layout Plain Layout
-Approximation Problem:
\end_layout
-\end_inset
-
-
+\begin_deeper
+\begin_layout Description
\begin_inset Argument item:1
status open
\end_inset
?
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Approximation Problem:
+\end_layout
+
+\end_inset
+
+
\end_layout
\begin_layout Description
approximately their distance.
\end_layout
+\end_deeper
\end_deeper
\end_deeper
\begin_layout Section
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Classes L and NL are Defined via
\begin_inset Newline newline
\end_inset
Logspace Turing Machines
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\backslash
pgfputat{
\backslash
-pgfxy(0,4)}{
+pgfxy(0,4)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
+
\backslash
tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
\end_layout
\backslash
pgfputat{
\backslash
-pgfxy(0,0.5)}{
+pgfxy(0,0.5)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
+
\backslash
tape{}{output tape (write only)}{10690836937182}}
\end_layout
\backslash
pgfputat{
\backslash
-pgfxy(7,2)}{
+pgfxy(7,2)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
+
\backslash
shorttape{work tape (read/write), $O(
\backslash
\backslash
pgfputat{
\backslash
-pgfxy(1.75,2.5)}{
+pgfxy(1.75,2.5)}{%
+\end_layout
+
+\begin_layout Plain Layout
+
+
\backslash
pgfbox[center,center]{
\backslash
\end_layout
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Logspace Turing Machines Are Quite Powerful
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Block
\begin_inset Argument 2
status collapsed
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout BeginFrame
-\begin_inset ERT
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
+1
+\end_layout
+
+\end_inset
+
-<1>[label=hierarchy]
+\begin_inset Argument 3
+status collapsed
+
+\begin_layout Plain Layout
+label=hierarchy
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Complexity Class Hierarchy
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\end_layout
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Circuit Complexity Classes AC
\begin_inset Formula $^{0}$
\end_inset
Limit the Circuit Depth
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_deeper
\begin_layout Examples
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_deeper
\begin_layout Examples
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_deeper
\begin_layout Examples
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
.
\end_layout
+\end_deeper
\end_deeper
\end_deeper
\begin_layout AgainFrame
Standard Complexity Results on Finding Paths
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
All Variants of Finding Paths in Directed Graphs
\begin_inset Newline newline
\end_inset
Are Equally Difficult
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Fact
\begin_inset Formula $\Lang{reach}$
\end_inset
\begin_layout Corollary
For directed graphs, we can solve
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
.
\end_layout
+\end_deeper
\end_deeper
\begin_layout AgainFrame
\begin_inset Argument 1
hierarchy
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Finding Paths in Forests and Directed Paths is Easy,
\begin_inset Newline newline
\end_inset
But Not Trivial
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Fact
\begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
\end_inset
-complete.
\end_layout
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
-complete.
\end_layout
+\end_deeper
\begin_layout AgainFrame
\begin_inset Argument 1
status collapsed
Complexity of: Does a Path Exist?
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Definition of the Tournament Reachability Problem
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Definition
Let
\color none
\end_inset
such that
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Tournament Reachability Problem is Very Easy
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
\end_inset
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
.
\end_layout
+\end_deeper
\end_deeper
\begin_layout AgainFrame
\begin_inset Argument 1
-status collapsed
+status open
\begin_layout Plain Layout
5
Complexity of: Construct a Shortest Path
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Finding a Shortest Path Is as Difficult as
\begin_inset Newline newline
\end_inset
the Distance Problem
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Definition
Let
\color none
\end_inset
such that
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Tournament Distance Problem is Hard
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
\end_inset
.
\end_layout
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Proof That
\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
\end_inset
is NL-complete
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
+\end_deeper
\end_deeper
\begin_layout AgainFrame
\begin_inset Argument 1
-status collapsed
+status open
\begin_layout Plain Layout
6
Complexity of: Approximating the Shortest Path
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Approximators Compute Paths that Are Nearly As Short As a Shortest Path
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Definition
An
\color none
\color inherit
gets as input
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
There Exists a Logspace Approximation Scheme for
\begin_inset Newline newline
\end_inset
the Tournament Shortest Path Problem
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
There exists an approximation scheme for
\begin_inset Formula $\Lang{tournament-shortest-path}$
\end_layout
+\end_deeper
\begin_layout AgainFrame
\begin_inset Argument 1
status collapsed
hierarchy
\end_layout
-\begin_layout EndFrame
-
-\end_layout
-
\begin_layout Standard
\begin_inset Note Note
status open
\end_inset
.
- This is not yet supported by LyX, so the frame is created using TeX code.
- Note that the
-\backslash
-begin{frame}[fragile] needs to be preceeded by an
-\emph on
-EndFrame
-\emph default
- environment.
+ \SpecialChar LyX
+ has the FragileFrame layout for this.
\end_layout
\end_inset
\end_layout
-\begin_layout Standard
-\begin_inset ERT
+\begin_layout FragileFrame
+\begin_inset Argument 4
status open
\begin_layout Plain Layout
-
-
-\backslash
-begin{frame}[fragile]
-\end_layout
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status collapsed
-
-\begin_layout Plain Layout
-
-
-\backslash
-frametitle{
+Just a frame with a program code listing
\end_layout
\end_inset
-Just a frame with a program code listing
-\begin_inset ERT
-status collapsed
-\begin_layout Plain Layout
-
-}
\end_layout
+\begin_layout FragileFrame
+This is some program code:
+\begin_inset Separator parbreak
\end_inset
\end_layout
-\begin_layout Standard
-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"
\end_layout
-\begin_layout Standard
-\begin_inset ERT
-status open
+\end_deeper
+\begin_layout Section*
+Summary
+\end_layout
-\begin_layout Plain Layout
+\begin_layout Subsection*
+Summary
+\end_layout
+\begin_layout Frame
+\begin_inset Argument 4
+status open
-\backslash
-end{frame}
+\begin_layout Plain Layout
+Summary
\end_layout
\end_inset
-\end_layout
-
-\begin_layout Section*
-Summary
-\end_layout
+\begin_inset Separator parbreak
+\end_inset
-\begin_layout Subsection*
-Summary
-\end_layout
-\begin_layout BeginFrame
-Summary
\end_layout
+\begin_deeper
\begin_layout Block
\begin_inset Argument 2
status collapsed
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
\end_deeper
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_inset
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
+\end_deeper
\end_deeper
\begin_layout Subsection*
For Further Reading
\end_layout
-\begin_layout BeginFrame
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
For Further Reading
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Standard
\begin_inset ERT
status open
\end_layout
\begin_layout Bibliography
-\labelwidthstring References
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Moon1968"
\end_layout
\begin_layout Bibliography
-\labelwidthstring References
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "NickelsenT2002"
\end_layout
\begin_layout Bibliography
-\labelwidthstring References
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Tantau2004b"
In press.
\end_layout
-\begin_layout EndFrame
-
-\end_layout
-
+\end_deeper
\begin_layout Standard
\start_of_appendix
\begin_inset ERT
Graphs With Bounded Independence Number
\end_layout
-\begin_layout BeginFrame
-\begin_inset ERT
+\begin_layout Frame
+\begin_inset Argument 3
status collapsed
\begin_layout Plain Layout
-
-[label=independence]
+label=independence
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
Definition of Independence Number of a Graph
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Definition
The
\color none
\end_layout
-\begin_layout BeginFrame
+\end_deeper
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Results for Tournaments also Apply to
\begin_inset Newline newline
\end_inset
Graphs With Bounded Independence Number
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
For each
\begin_inset space ~
.
\end_layout
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_layout
-\begin_layout Separator
+\begin_layout Standard
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
.
\end_layout
+\end_deeper
\begin_layout Subsection
Finding Paths in Undirected Graphs
\end_layout
-\begin_layout BeginFrame
-\begin_inset ERT
+\begin_layout Frame
+\begin_inset Argument 1
status collapsed
\begin_layout Plain Layout
+1-2
+\end_layout
+
+\end_inset
-<1-2>[label=undirected]
+
+\begin_inset Argument 3
+status collapsed
+
+\begin_layout Plain Layout
+label=undirected
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Complexity of Finding Paths in Undirected Graphs
\begin_inset Newline newline
\end_inset
Is Party Unknown.
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Fact
\begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
\end_inset
\begin_layout Corollary
For undirected graphs, we can solve
+\begin_inset Separator parbreak
+\end_inset
+
+
\end_layout
\begin_deeper
\end_layout
+\end_deeper
\end_deeper
\begin_layout Subsection
The Approximation Scheme is Optimal
\end_layout
-\begin_layout BeginFrame
-\begin_inset ERT
+\begin_layout Frame
+\begin_inset Argument 3
status collapsed
\begin_layout Plain Layout
-
-[label=optimality]
+label=optimality
\end_layout
\end_inset
+
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
The Approximation Scheme is Optimal
\end_layout
+\end_inset
+
+
+\begin_inset Separator parbreak
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
\begin_layout Theorem
Suppose there exists an approximation scheme for
\begin_inset Formula $\Lang{tournament-shortest-path}$
\end_layout
\begin_layout Proof
+\begin_inset Separator parbreak
+\end_inset
+
\end_layout
\end_layout
\end_deeper
-\begin_layout EndFrame
-
-\end_layout
-
+\end_deeper
\end_body
\end_document