1 #LyX 2.2 created this file. For more info see http://www.lyx.org/
5 \save_transient_properties true
6 \origin /systemlyxdir/examples/
9 \beamertemplateshadingbackground{red!5}{structure!5}
11 \usepackage{beamerthemeshadow}
12 \usepackage{pgfnodes,pgfarrows,pgfheaps}
14 \beamertemplatetransparentcovereddynamicmedium
17 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
18 \logo{\pgfuseimage{icsi-logo}}
23 \newcommand{\Class}[1]{\operatorname{\mathchoice
29 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
31 % This gets defined by beamerbasecolor.sty, but only at the beginning of
33 \colorlet{averagebackgroundcolor}{normal text.bg}
35 \newcommand{\tape}[3]{%
36 \color{structure!30!averagebackgroundcolor}
37 \pgfmoveto{\pgfxy(-0.5,0)}
38 \pgflineto{\pgfxy(-0.6,0.1)}
39 \pgflineto{\pgfxy(-0.4,0.2)}
40 \pgflineto{\pgfxy(-0.6,0.3)}
41 \pgflineto{\pgfxy(-0.4,0.4)}
42 \pgflineto{\pgfxy(-0.5,0.5)}
43 \pgflineto{\pgfxy(4,0.5)}
44 \pgflineto{\pgfxy(4.1,0.4)}
45 \pgflineto{\pgfxy(3.9,0.3)}
46 \pgflineto{\pgfxy(4.1,0.2)}
47 \pgflineto{\pgfxy(3.9,0.1)}
48 \pgflineto{\pgfxy(4,0)}
53 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
54 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
57 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
60 \newcommand{\shorttape}[3]{%
61 \color{structure!30!averagebackgroundcolor}
62 \pgfmoveto{\pgfxy(-0.5,0)}
63 \pgflineto{\pgfxy(-0.6,0.1)}
64 \pgflineto{\pgfxy(-0.4,0.2)}
65 \pgflineto{\pgfxy(-0.6,0.3)}
66 \pgflineto{\pgfxy(-0.4,0.4)}
67 \pgflineto{\pgfxy(-0.5,0.5)}
68 \pgflineto{\pgfxy(1,0.5)}
69 \pgflineto{\pgfxy(1.1,0.4)}
70 \pgflineto{\pgfxy(0.9,0.3)}
71 \pgflineto{\pgfxy(1.1,0.2)}
72 \pgflineto{\pgfxy(0.9,0.1)}
73 \pgflineto{\pgfxy(1,0)}
78 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
79 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
82 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
85 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
86 {color(0pt)=(black); color(1cm)=(structure!65!white)}
87 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
88 {color(0pt)=(black); color(1cm)=(structure!55!white)}
89 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
90 {color(0pt)=(black); color(1cm)=(structure!45!white)}
91 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
92 {color(0pt)=(black); color(1cm)=(structure!35!white)}
93 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
94 {color(0pt)=(black); color(1cm)=(structure!25!white)}
95 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
96 {color(0pt)=(black); color(1cm)=(red!35!white)}
98 \newcommand{\heap}[5]{%
101 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
103 \begin{pgfmagnify}{1}{#1}
104 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
110 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
114 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
118 \newcommand{\langat}[2]{%
119 \color{black!30!beamerexample}
120 \pgfsetlinewidth{0.6pt}
121 \pgfsetendarrow{\pgfarrowdot}
122 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
123 \color{beamerexample}
124 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
127 \newcommand{\langatother}[2]{%
128 \color{black!30!beamerexample}
129 \pgfsetlinewidth{0.6pt}
130 \pgfsetendarrow{\pgfarrowdot}
131 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
132 \color{beamerexample}
133 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
137 \pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
140 \pgfdeclareradialshading{graphnode}
141 {\pgfpoint{-3pt}{3.6pt}}%
142 {color(0cm)=(beamerexample!15);
143 color(2.63pt)=(beamerexample!75);
144 color(5.26pt)=(beamerexample!70!black);
145 color(7.6pt)=(beamerexample!50!black);
146 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
148 \newcommand{\graphnode}[2]{
149 \pgfnodecircle{#1}[virtual]{#2}{8pt}
150 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
154 \use_default_options false
155 \maintain_unincluded_children false
157 \language_package default
160 \font_roman "times" "default"
161 \font_sans "default" "default"
162 \font_typewriter "default" "default"
163 \font_math "auto" "auto"
164 \font_default_family default
165 \use_non_tex_fonts false
168 \font_sf_scale 100 100
169 \font_tt_scale 100 100
171 \default_output_format default
173 \bibtex_command default
174 \index_command default
175 \paperfontsize default
180 \use_package amsmath 2
181 \use_package amssymb 2
182 \use_package cancel 0
184 \use_package mathdots 1
185 \use_package mathtools 0
186 \use_package mhchem 1
187 \use_package stackrel 0
188 \use_package stmaryrd 0
189 \use_package undertilde 0
191 \cite_engine_type default
195 \paperorientation portrait
205 \paragraph_separation indent
206 \paragraph_indentation default
207 \quotes_language english
210 \paperpagestyle default
211 \tracking_changes false
212 \output_changes false
215 \html_be_strict false
222 \begin_inset Newline newline
225 Finding Paths in Tournaments
232 \begin_layout Institute
233 International Computer Science Institute
234 \begin_inset Newline newline
238 \begin_inset Argument 1
241 \begin_layout Plain Layout
255 \begin_inset Argument 4
258 \begin_layout Plain Layout
265 \begin_inset Separator parbreak
272 \begin_layout Standard
273 \begin_inset CommandInset toc
274 LatexCommand tableofcontents
282 \begin_layout Plain Layout
293 \begin_layout Standard
297 \begin_layout Plain Layout
299 % Show the table of contents at the beginning
302 \begin_layout Plain Layout
304 % of every subsection.
307 \begin_layout Plain Layout
311 AtBeginSubsection[]{%
314 \begin_layout Plain Layout
321 \begin_layout Plain Layout
328 \begin_layout Plain Layout
332 tableofcontents[current,currentsubsection]
335 \begin_layout Plain Layout
340 \begin_layout Plain Layout
350 \begin_layout Section
354 \begin_layout Subsection
355 What are Tournaments?
359 \begin_inset Argument 4
362 \begin_layout Plain Layout
363 Tournaments Consist of Jousts Between Knights
369 \begin_inset Separator parbreak
376 \begin_layout Columns
377 \begin_inset Separator parbreak
388 \begin_layout Standard
392 \begin_layout Plain Layout
396 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
399 \begin_layout Plain Layout
403 pgfnodebox{A}[virtual]{
408 \begin_layout Plain Layout
412 pgfuseimage{knight1}}{2pt}{2pt}
415 \begin_layout Plain Layout
419 pgfnodebox{B}[virtual]{
424 \begin_layout Plain Layout
428 pgfuseimage{knight2}}{2pt}{2pt}
431 \begin_layout Plain Layout
435 pgfnodebox{C}[virtual]{
440 \begin_layout Plain Layout
444 pgfuseimage{knight3}}{2pt}{2pt}
447 \begin_layout Plain Layout
451 pgfnodebox{D}[virtual]{
456 \begin_layout Plain Layout
460 pgfuseimage{knight4}}{2pt}{2pt}
463 \begin_layout Plain Layout
470 \begin_layout Plain Layout
481 \begin_layout Plain Layout
488 \begin_layout Plain Layout
492 pgfsetlinewidth{0.6pt}
495 \begin_layout Plain Layout
499 pgfnodeconnline{A}{B}
502 \begin_layout Plain Layout
506 pgfnodeconnline{A}{C}
509 \begin_layout Plain Layout
513 pgfnodeconnline{D}{A}
516 \begin_layout Plain Layout
520 pgfnodeconnline{C}{B}
523 \begin_layout Plain Layout
527 pgfnodeconnline{B}{D}
530 \begin_layout Plain Layout
534 pgfnodeconnline{C}{D}
537 \begin_layout Plain Layout
542 \begin_layout Plain Layout
559 \begin_inset Argument 2
562 \begin_layout Plain Layout
563 What is a Tournament?
569 \begin_inset Separator parbreak
576 \begin_layout Itemize
577 \begin_inset Argument item:2
580 \begin_layout Plain Layout
589 \begin_layout Itemize
590 \begin_inset Argument item:2
593 \begin_layout Plain Layout
599 Every pair has a joust.
602 \begin_layout Itemize
603 \begin_inset Argument item:2
606 \begin_layout Plain Layout
612 In every joust one knight wins.
618 \begin_layout Standard
619 \begin_inset Separator parbreak
626 \begin_inset Argument 4
629 \begin_layout Plain Layout
630 Tournaments are Complete Directed Graphs
636 \begin_inset Separator parbreak
643 \begin_layout Columns
644 \begin_inset Separator parbreak
655 \begin_layout Standard
659 \begin_layout Plain Layout
663 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
666 \begin_layout Plain Layout
673 \begin_layout Plain Layout
677 pgfsetlinewidth{0.6pt}
680 \begin_layout Plain Layout
689 \begin_layout Plain Layout
698 \begin_layout Plain Layout
707 \begin_layout Plain Layout
716 \begin_layout Plain Layout
723 \begin_layout Plain Layout
731 pgfbox[center,center]{$v_2$}}
734 \begin_layout Plain Layout
742 pgfbox[center,center]{$v_3$}}
745 \begin_layout Plain Layout
753 pgfbox[center,center]{$v_4$}}
756 \begin_layout Plain Layout
764 pgfbox[center,center]{$v_1$}}
767 \begin_layout Plain Layout
774 \begin_layout Plain Layout
783 \begin_layout Plain Layout
787 pgfnodesetsepstart{2pt}
790 \begin_layout Plain Layout
794 pgfnodesetsepend{4pt}
797 \begin_layout Plain Layout
801 pgfnodeconnline{A}{B}
804 \begin_layout Plain Layout
808 pgfnodeconnline{A}{C}
811 \begin_layout Plain Layout
815 pgfnodeconnline{D}{A}
818 \begin_layout Plain Layout
822 pgfnodeconnline{C}{B}
825 \begin_layout Plain Layout
829 pgfnodeconnline{B}{D}
832 \begin_layout Plain Layout
836 pgfnodeconnline{D}{C}
839 \begin_layout Plain Layout
855 \begin_layout Definition
856 \begin_inset Argument 1
859 \begin_layout Plain Layout
874 \begin_inset Separator parbreak
881 \begin_layout Enumerate
885 \begin_layout Enumerate
886 with exactly one edge between
887 \begin_inset Newline newline
890 any two different vertices.
896 \begin_layout Standard
897 \begin_inset Separator parbreak
904 \begin_inset Argument 2
907 \begin_layout Plain Layout
914 \begin_inset Argument 4
917 \begin_layout Plain Layout
918 Tournaments Arise Naturally in Different Situations
924 \begin_inset Separator parbreak
931 \begin_layout ExampleBlock
932 \begin_inset Argument 2
935 \begin_layout Plain Layout
936 Applications in Ordering Theory
942 \begin_inset Separator parbreak
949 \begin_layout Standard
950 Elements in a set need to be sorted.
952 \begin_inset Newline newline
955 The comparison relation may be cyclic, however.
959 \begin_layout Standard
960 \begin_inset Separator parbreak
966 \begin_layout ExampleBlock
967 \begin_inset Argument 2
970 \begin_layout Plain Layout
971 Applications in Sociology
977 \begin_inset Separator parbreak
984 \begin_layout Standard
985 Several candidates apply for a position.
986 \begin_inset Newline newline
989 Reviewers decide for any two candidates whom they prefer.
994 \begin_layout Standard
995 \begin_inset Separator parbreak
1001 \begin_layout ExampleBlock
1002 \begin_inset Argument 2
1005 \begin_layout Plain Layout
1006 Applications in Structural Complexity Theory
1012 \begin_inset Separator parbreak
1019 \begin_layout Standard
1021 \begin_inset Formula $L$
1024 is given and a selector function
1025 \begin_inset Formula $f$
1029 \begin_inset Newline newline
1032 It chooses from any two words the one more likely to be in
1033 \begin_inset Formula $f$
1041 \begin_layout Subsection
1042 What Does ``Finding Paths'' Mean?
1046 \begin_inset Argument 4
1049 \begin_layout Plain Layout
1050 ``Finding Paths'' is Ambiguous
1056 \begin_inset Separator parbreak
1064 \begin_inset Argument 2
1067 \begin_layout Plain Layout
1069 \begin_inset Flex Only
1072 \begin_layout Plain Layout
1073 \begin_inset Argument 1
1076 \begin_layout Plain Layout
1082 Path Finding Problems
1088 \begin_inset Flex Only
1091 \begin_layout Plain Layout
1092 \begin_inset Argument 1
1095 \begin_layout Plain Layout
1102 \begin_inset Formula $\Lang{reach}$
1111 \begin_inset Flex Only
1114 \begin_layout Plain Layout
1115 \begin_inset Argument 1
1118 \begin_layout Plain Layout
1124 the Construction Problem
1130 \begin_inset Flex Only
1133 \begin_layout Plain Layout
1134 \begin_inset Argument 1
1137 \begin_layout Plain Layout
1143 the Optimization Problem
1149 \begin_inset Flex Only
1152 \begin_layout Plain Layout
1153 \begin_inset Argument 1
1156 \begin_layout Plain Layout
1163 \begin_inset Formula $\Lang{distance}$
1172 \begin_inset Flex Only
1175 \begin_layout Plain Layout
1176 \begin_inset Argument 1
1179 \begin_layout Plain Layout
1185 the Approximation Problem
1196 \begin_inset Separator parbreak
1203 \begin_layout Itemize
1213 \begin_inset Formula $G=(V,E)$
1225 \begin_inset Formula $s\in V$
1237 \begin_inset Formula $t\in V$
1243 \begin_layout Itemize
1244 \begin_inset Argument item:2
1247 \begin_layout Plain Layout
1260 \begin_inset space ~
1264 \begin_inset Formula $d$
1271 \begin_layout Plain Layout
1283 \begin_layout Itemize
1284 \begin_inset Argument item:2
1287 \begin_layout Plain Layout
1302 \begin_inset Formula $r>1$
1309 \begin_layout Standard
1313 \begin_layout Plain Layout
1325 \begin_layout Overprint
1326 \begin_inset Argument item:1
1329 \begin_layout Plain Layout
1336 \begin_inset Separator parbreak
1343 \begin_layout Columns
1344 \begin_inset Argument 1
1347 \begin_layout Plain Layout
1354 \begin_inset Separator parbreak
1361 \begin_layout Standard
1362 \begin_inset Flex Alternative
1365 \begin_layout Plain Layout
1366 \begin_inset Argument 1
1369 \begin_layout Plain Layout
1376 \begin_inset Argument 2
1379 \begin_layout Plain Layout
1383 \begin_layout Plain Layout
1403 \begin_layout Plain Layout
1420 \begin_layout ExampleBlock
1421 \begin_inset Argument 2
1424 \begin_layout Plain Layout
1431 \begin_inset Separator parbreak
1438 \begin_layout Standard
1442 \begin_layout Plain Layout
1446 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1449 \begin_layout Plain Layout
1453 \begin_layout Plain Layout
1457 color{beamerexample}
1460 \begin_layout Plain Layout
1464 \begin_layout Plain Layout
1468 pgfsetlinewidth{0.6pt}
1471 \begin_layout Plain Layout
1475 \begin_layout Plain Layout
1484 \begin_layout Plain Layout
1488 \begin_layout Plain Layout
1497 \begin_layout Plain Layout
1501 \begin_layout Plain Layout
1510 \begin_layout Plain Layout
1514 \begin_layout Plain Layout
1523 \begin_layout Plain Layout
1527 \begin_layout Plain Layout
1531 \begin_layout Plain Layout
1535 \begin_layout Plain Layout
1542 \begin_layout Plain Layout
1546 \begin_layout Plain Layout
1554 pgfbox[center,center]{$t$}}
1557 \begin_layout Plain Layout
1561 \begin_layout Plain Layout
1569 pgfbox[center,center]{$s$}}
1572 \begin_layout Plain Layout
1576 \begin_layout Plain Layout
1580 \begin_layout Plain Layout
1584 \begin_layout Plain Layout
1588 color{beamerexample}
1591 \begin_layout Plain Layout
1595 \begin_layout Plain Layout
1604 \begin_layout Plain Layout
1608 \begin_layout Plain Layout
1612 pgfnodesetsepstart{2pt}
1615 \begin_layout Plain Layout
1619 \begin_layout Plain Layout
1623 pgfnodesetsepend{4pt}
1626 \begin_layout Plain Layout
1630 \begin_layout Plain Layout
1634 pgfnodeconnline{A}{B}
1637 \begin_layout Plain Layout
1641 \begin_layout Plain Layout
1645 pgfnodeconnline{A}{C}
1648 \begin_layout Plain Layout
1652 \begin_layout Plain Layout
1656 pgfnodeconnline{D}{A}
1659 \begin_layout Plain Layout
1663 \begin_layout Plain Layout
1667 pgfnodeconnline{C}{B}
1670 \begin_layout Plain Layout
1674 \begin_layout Plain Layout
1678 pgfnodeconnline{B}{D}
1681 \begin_layout Plain Layout
1685 \begin_layout Plain Layout
1689 pgfnodeconnline{D}{C}
1692 \begin_layout Plain Layout
1696 \begin_layout Plain Layout
1700 \begin_layout Plain Layout
1704 \begin_layout Plain Layout
1714 pgfbox[left,center]{, $d=2$}}}
1717 \begin_layout Plain Layout
1721 \begin_layout Plain Layout
1731 pgfbox[left,center]{, $r=1.5$}}}
1734 \begin_layout Plain Layout
1738 \begin_layout Plain Layout
1748 pgfbox[left,center]{, $r=1.25$}}}
1751 \begin_layout Plain Layout
1755 \begin_layout Plain Layout
1768 \begin_layout Standard
1769 \begin_inset Flex Only
1772 \begin_layout Plain Layout
1773 \begin_inset Argument 1
1776 \begin_layout Plain Layout
1786 \begin_layout Plain Layout
1803 \begin_layout ExampleBlock
1804 \begin_inset Argument 1
1807 \begin_layout Plain Layout
1814 \begin_inset Argument 2
1817 \begin_layout Plain Layout
1824 \begin_inset Separator parbreak
1831 \begin_layout Standard
1835 \begin_layout Plain Layout
1839 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1842 \begin_layout Plain Layout
1849 \begin_layout Plain Layout
1853 color{beamerexample}
1856 \begin_layout Plain Layout
1860 pgfsetlinewidth{0.6pt}
1863 \begin_layout Plain Layout
1872 \begin_layout Plain Layout
1881 \begin_layout Plain Layout
1890 \begin_layout Plain Layout
1899 \begin_layout Plain Layout
1906 \begin_layout Plain Layout
1914 pgfbox[center,center]{$t$}}
1917 \begin_layout Plain Layout
1925 pgfbox[center,center]{$s$}}
1928 \begin_layout Plain Layout
1932 color{beamerexample}
1935 \begin_layout Plain Layout
1944 \begin_layout Plain Layout
1948 pgfnodesetsepstart{2pt}
1951 \begin_layout Plain Layout
1955 pgfnodesetsepend{4pt}
1958 \begin_layout Plain Layout
1964 pgfnodeconnline{A}{B}}
1967 \begin_layout Plain Layout
1973 pgfnodeconnline{A}{C}}
1976 \begin_layout Plain Layout
1982 pgfnodeconnline{D}{A}}
1985 \begin_layout Plain Layout
1991 pgfnodeconnline{C}{B}}
1994 \begin_layout Plain Layout
1998 pgfnodeconnline{B}{D}
2001 \begin_layout Plain Layout
2005 pgfnodeconnline{D}{C}
2008 \begin_layout Plain Layout
2013 \begin_layout Plain Layout
2023 pgfbox[left,center]{
2028 \begin_layout Plain Layout
2043 \begin_layout Overprint
2044 \begin_inset Argument item:1
2047 \begin_layout Plain Layout
2054 \begin_inset Separator parbreak
2062 \begin_inset Argument 2
2065 \begin_layout Plain Layout
2066 Variants of Path Finding Problems
2072 \begin_inset Separator parbreak
2079 \begin_layout Description
2080 \begin_inset Argument item:1
2083 \begin_layout Plain Layout
2090 \begin_inset space ~
2093 Problem: Is there a path from
2094 \begin_inset Formula $s$
2098 \begin_inset space ~
2102 \begin_inset Formula $t$
2106 \begin_inset Argument 2
2109 \begin_layout Plain Layout
2110 Approximation Problem:
2118 \begin_layout Description
2119 \begin_inset Argument item:1
2122 \begin_layout Plain Layout
2129 \begin_inset space ~
2132 Problem: Construct a path from
2133 \begin_inset Formula $s$
2137 \begin_inset space ~
2141 \begin_inset Formula $t$
2147 \begin_layout Description
2148 \begin_inset Argument item:1
2151 \begin_layout Plain Layout
2158 \begin_inset space ~
2161 Problem: Construct a shortest path from
2162 \begin_inset Formula $s$
2166 \begin_inset space ~
2170 \begin_inset Formula $t$
2176 \begin_layout Description
2177 \begin_inset Argument item:1
2180 \begin_layout Plain Layout
2187 \begin_inset space ~
2190 Problem: Is the distance of
2191 \begin_inset Formula $s$
2195 \begin_inset space ~
2199 \begin_inset Formula $t$
2203 \begin_inset space ~
2207 \begin_inset Formula $d$
2213 \begin_layout Description
2214 \begin_inset Argument item:1
2217 \begin_layout Plain Layout
2224 \begin_inset space ~
2227 Problem: Construct a path from
2228 \begin_inset Formula $s$
2232 \begin_inset space ~
2236 \begin_inset Formula $t$
2240 \begin_inset Newline newline
2243 approximately their distance.
2249 \begin_layout Section
2253 \begin_layout Subsection
2254 Standard Complexity Classes
2257 \begin_layout Standard
2261 \begin_layout Plain Layout
2265 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2267 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2277 \begin_inset Argument 4
2280 \begin_layout Plain Layout
2281 The Classes L and NL are Defined via
2282 \begin_inset Newline newline
2285 Logspace Turing Machines
2291 \begin_inset Separator parbreak
2298 \begin_layout Standard
2302 \begin_layout Plain Layout
2306 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2309 \begin_layout Plain Layout
2318 \begin_layout Plain Layout
2322 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2325 \begin_layout Plain Layout
2332 \begin_layout Plain Layout
2341 \begin_layout Plain Layout
2345 tape{}{output tape (write only)}{10690836937182}}
2348 \begin_layout Plain Layout
2353 \begin_layout Plain Layout
2360 \begin_layout Plain Layout
2369 \begin_layout Plain Layout
2373 shorttape{work tape (read/write), $O(
2375 log n)$ symbols}{}{42}}
2378 \begin_layout Plain Layout
2387 \begin_layout Plain Layout
2391 pgfbox[center,center]{
2393 pgfuseimage{computer}}}
2396 \begin_layout Plain Layout
2401 \begin_layout Plain Layout
2405 pgfsetlinewidth{0.6pt}
2408 \begin_layout Plain Layout
2415 \begin_layout Plain Layout
2424 \begin_layout Plain Layout
2428 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2431 \begin_layout Plain Layout
2437 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2440 \begin_layout Plain Layout
2446 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2449 \begin_layout Plain Layout
2462 \begin_layout Standard
2463 \begin_inset Separator parbreak
2470 \begin_inset Argument 4
2473 \begin_layout Plain Layout
2474 Logspace Turing Machines Are Quite Powerful
2480 \begin_inset Separator parbreak
2488 \begin_inset Argument 2
2491 \begin_layout Plain Layout
2492 Deterministic logspace machines can compute
2498 \begin_inset Separator parbreak
2505 \begin_layout Itemize
2506 addition, multiplication, and even division
2509 \begin_layout Itemize
2510 reductions used in completeness proofs,
2513 \begin_layout Itemize
2514 reachability in forests.
2523 \begin_inset Argument 2
2526 \begin_layout Plain Layout
2527 Non-deterministic logspace machines can compute
2533 \begin_inset Separator parbreak
2540 \begin_layout Itemize
2541 reachability in graphs,
2544 \begin_layout Itemize
2545 non-reachability in graphs,
2548 \begin_layout Itemize
2549 satisfiability with two literals per clause.
2554 \begin_layout Standard
2555 \begin_inset Separator parbreak
2562 \begin_inset Argument 1
2565 \begin_layout Plain Layout
2572 \begin_inset Argument 3
2575 \begin_layout Plain Layout
2582 \begin_inset Argument 4
2585 \begin_layout Plain Layout
2586 The Complexity Class Hierarchy
2592 \begin_inset Separator parbreak
2599 \begin_layout Standard
2603 \begin_layout Plain Layout
2607 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2610 \begin_layout Plain Layout
2614 pgfsetlinewidth{0.8pt}
2617 \begin_layout Plain Layout
2626 \begin_layout Plain Layout
2630 pgfsetdash{{2pt}}{0pt}
2633 \begin_layout Plain Layout
2641 Class{NC}^2$}{black!50!structure}{2}}
2644 \begin_layout Plain Layout
2650 Class{NL}$}{black!50!structure}{3}
2653 \begin_layout Plain Layout
2659 Class{L}$}{black!50!structure}{4}
2662 \begin_layout Plain Layout
2673 \begin_layout Plain Layout
2679 Class{NC}^1}$}{black!50!structure}{5}
2682 \begin_layout Plain Layout
2687 \begin_layout Plain Layout
2694 \begin_layout Plain Layout
2705 \begin_layout Plain Layout
2711 Class{AC}^0}$}{black}{6}
2714 \begin_layout Plain Layout
2719 \begin_layout Plain Layout
2723 pgfsetlinewidth{1.0pt}
2726 \begin_layout Plain Layout
2733 \begin_layout Plain Layout
2737 pgfxyline(-5,0)(5,0)
2740 \begin_layout Plain Layout
2751 \begin_layout Plain Layout
2761 operatorname{forest}}$}}
2764 \begin_layout Plain Layout
2775 \begin_layout Plain Layout
2794 \begin_layout Plain Layout
2813 \begin_layout Plain Layout
2826 \begin_layout Plain Layout
2834 operatorname{forest}}$,}
2839 \begin_layout Plain Layout
2847 operatorname{forest}}$,}
2852 \begin_layout Plain Layout
2860 operatorname{path}}$,}
2865 \begin_layout Plain Layout
2873 operatorname{path}}$}}}
2876 \begin_layout Plain Layout
2881 \begin_layout Plain Layout
2891 operatorname{tourn}}$}}
2894 \begin_layout Plain Layout
2907 \begin_layout Plain Layout
2915 operatorname{tourn}}$,}
2920 \begin_layout Plain Layout
2931 \begin_layout Plain Layout
2940 \begin_layout Plain Layout
2945 \begin_layout Plain Layout
2951 pgfsetdash{{1pt}}{0pt}%
2954 \begin_layout Plain Layout
2962 operatorname{tourn}}$''}
2965 \begin_layout Plain Layout
2970 \begin_layout Plain Layout
2983 \begin_layout Standard
2984 \begin_inset Separator parbreak
2991 \begin_inset Argument 4
2994 \begin_layout Plain Layout
2995 The Circuit Complexity Classes AC
2996 \begin_inset Formula $^{0}$
3000 \begin_inset Formula $^{1}$
3004 \begin_inset Formula $^{2}$
3008 \begin_inset Newline newline
3011 Limit the Circuit Depth
3017 \begin_inset Separator parbreak
3024 \begin_layout Standard
3028 \begin_layout Plain Layout
3037 \begin_layout Plain Layout
3049 \begin_layout Columns
3050 \begin_inset Argument 1
3053 \begin_layout Plain Layout
3060 \begin_inset Separator parbreak
3067 \begin_layout Column
3072 \begin_inset Argument 2
3075 \begin_layout Plain Layout
3077 \begin_inset Formula $\Class{AC}^{0}$
3086 \begin_inset Separator parbreak
3093 \begin_layout Itemize
3094 \begin_inset Formula $O(1)$
3100 \begin_layout Itemize
3105 \begin_layout Examples
3106 \begin_inset Separator parbreak
3113 \begin_layout Itemize
3114 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3120 \begin_layout Itemize
3121 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3132 \begin_layout Column
3137 \begin_inset Argument 2
3140 \begin_layout Plain Layout
3142 \begin_inset Formula $\Class{NC}^{1}$
3151 \begin_inset Separator parbreak
3158 \begin_layout Itemize
3159 \begin_inset Formula $O(\log n)$
3165 \begin_layout Itemize
3170 \begin_layout Examples
3171 \begin_inset Separator parbreak
3178 \begin_layout Itemize
3179 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3185 \begin_layout Itemize
3186 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3192 \begin_layout Itemize
3193 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3204 \begin_layout Column
3209 \begin_inset Argument 2
3212 \begin_layout Plain Layout
3214 \begin_inset Formula $\Class{NC}^{2}$
3223 \begin_inset Separator parbreak
3230 \begin_layout Itemize
3231 \begin_inset Formula $O(\log^{2}n)$
3237 \begin_layout Itemize
3242 \begin_layout Examples
3243 \begin_inset Separator parbreak
3250 \begin_layout Itemize
3251 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3260 \begin_layout AgainFrame
3261 \begin_inset Argument 1
3264 \begin_layout Plain Layout
3273 \begin_layout Subsection
3274 Standard Complexity Results on Finding Paths
3278 \begin_inset Argument 4
3281 \begin_layout Plain Layout
3282 All Variants of Finding Paths in Directed Graphs
3283 \begin_inset Newline newline
3286 Are Equally Difficult
3292 \begin_inset Separator parbreak
3300 \begin_inset Formula $\Lang{reach}$
3304 \begin_inset Formula $\Lang{distance}$
3308 \begin_inset Formula $\Class{NL}$
3319 \begin_layout Corollary
3320 For directed graphs, we can solve
3321 \begin_inset Separator parbreak
3328 \begin_layout Itemize
3329 the reachability problem in logspace iff
3330 \begin_inset Formula $\Class{L}=\Class{NL}$
3336 \begin_layout Itemize
3337 the construction problem in logspace iff
3338 \begin_inset Formula $\Class{L}=\Class{NL}$
3344 \begin_layout Itemize
3345 the optimization problem in logspace iff
3346 \begin_inset Formula $\Class{L}=\Class{NL}$
3352 \begin_layout Itemize
3353 the approximation problem in logspace iff
3354 \begin_inset Formula $\Class{L}=\Class{NL}$
3362 \begin_layout AgainFrame
3363 \begin_inset Argument 1
3366 \begin_layout Plain Layout
3376 \begin_inset Argument 4
3379 \begin_layout Plain Layout
3380 Finding Paths in Forests and Directed Paths is Easy,
3381 \begin_inset Newline newline
3390 \begin_inset Separator parbreak
3398 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3402 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3406 \begin_inset Formula $\Class{L}$
3412 \begin_layout Standard
3413 \begin_inset Separator parbreak
3420 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3424 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3428 \begin_inset Formula $\Class{L}$
3435 \begin_layout AgainFrame
3436 \begin_inset Argument 1
3439 \begin_layout Plain Layout
3448 \begin_layout Section
3449 Finding Paths in Tournaments
3452 \begin_layout Subsection
3453 Complexity of: Does a Path Exist?
3457 \begin_inset Argument 4
3460 \begin_layout Plain Layout
3461 Definition of the Tournament Reachability Problem
3467 \begin_inset Separator parbreak
3474 \begin_layout Definition
3480 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3488 \begin_inset Formula $(T,s,t)$
3492 \begin_inset Separator parbreak
3499 \begin_layout Enumerate
3500 \begin_inset Formula $T=(V,E)$
3506 \begin_layout Enumerate
3507 there exists a path from
3508 \begin_inset space ~
3512 \begin_inset Formula $s$
3516 \begin_inset space ~
3520 \begin_inset Formula $t$
3528 \begin_layout Standard
3529 \begin_inset Separator parbreak
3536 \begin_inset Argument 4
3539 \begin_layout Plain Layout
3540 The Tournament Reachability Problem is Very Easy
3546 \begin_inset Separator parbreak
3553 \begin_layout Theorem
3554 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3564 \begin_layout AlertBlock
3565 \begin_inset Argument 2
3568 \begin_layout Plain Layout
3575 \begin_inset Separator parbreak
3582 \begin_layout Itemize
3584 \begin_inset Quotes eld
3588 \begin_inset Quotes erd
3592 \begin_inset Formula $\Lang{reach}$
3596 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3602 \begin_layout Itemize
3603 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3611 \begin_layout AgainFrame
3612 \begin_inset Argument 1
3615 \begin_layout Plain Layout
3624 \begin_layout Subsection
3625 Complexity of: Construct a Shortest Path
3629 \begin_inset Argument 4
3632 \begin_layout Plain Layout
3633 Finding a Shortest Path Is as Difficult as
3634 \begin_inset Newline newline
3637 the Distance Problem
3643 \begin_inset Separator parbreak
3650 \begin_layout Definition
3656 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3664 \begin_inset Formula $(T,s,t,d)$
3668 \begin_inset Separator parbreak
3675 \begin_layout Enumerate
3676 \begin_inset Formula $T=(V,E)$
3679 is a tournament in which
3682 \begin_layout Enumerate
3684 \begin_inset Formula $s$
3688 \begin_inset space ~
3692 \begin_inset Formula $t$
3696 \begin_inset space ~
3700 \begin_inset Formula $d$
3708 \begin_layout Standard
3709 \begin_inset Separator parbreak
3716 \begin_inset Argument 4
3719 \begin_layout Plain Layout
3720 The Tournament Distance Problem is Hard
3726 \begin_inset Separator parbreak
3733 \begin_layout Theorem
3734 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3738 \begin_inset Formula $\Class{NL}$
3744 \begin_layout Standard
3745 \begin_inset space \hfill{}
3752 \begin_layout Plain Layout
3756 hyperlink{hierarchy<6>}{
3758 beamerskipbutton{Skip Proof}}
3770 \begin_layout Corollary
3771 Shortest path in tournaments can be constructed
3772 \begin_inset Newline newline
3775 in logarithmic space, iff
3776 \begin_inset Formula $\Class{L}=\Class{NL}$
3786 \begin_layout Corollary
3787 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3794 \begin_layout Standard
3795 \begin_inset Separator parbreak
3802 \begin_inset Argument 4
3805 \begin_layout Plain Layout
3807 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3816 \begin_inset Separator parbreak
3823 \begin_layout Standard
3827 \begin_layout Plain Layout
3839 \begin_layout Columns
3840 \begin_inset Argument 1
3843 \begin_layout Plain Layout
3850 \begin_inset Separator parbreak
3857 \begin_layout Column
3861 \begin_layout Standard
3865 \begin_layout Plain Layout
3880 \begin_inset Argument 2
3883 \begin_layout Plain Layout
3885 \begin_inset Formula $\Lang{reach}$
3889 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3898 \begin_inset Separator parbreak
3905 \begin_layout Enumerate
3906 \begin_inset Argument item:2
3909 \begin_layout Plain Layout
3916 \begin_inset Formula $(G,s,t)$
3920 \begin_inset Formula $\Lang{reach}$
3926 \begin_layout Enumerate
3927 \begin_inset Argument item:2
3930 \begin_layout Plain Layout
3937 \begin_inset Formula $G$
3941 \begin_inset Formula $G'$
3947 \begin_layout Enumerate
3948 \begin_inset Argument item:2
3951 \begin_layout Plain Layout
3958 \begin_inset Newline newline
3962 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3969 \begin_layout Standard
3970 \begin_inset Separator parbreak
3977 \begin_inset Argument 2
3980 \begin_layout Plain Layout
3987 \begin_inset Argument 1
3990 \begin_layout Plain Layout
3997 \begin_inset Separator parbreak
4004 \begin_layout Enumerate
4005 \begin_inset Argument item:2
4008 \begin_layout Plain Layout
4015 \begin_inset space ~
4019 \begin_inset Formula $G$
4023 \begin_inset Newline newline
4027 \begin_inset space ~
4031 \begin_inset Formula $G'$
4037 \begin_layout Enumerate
4038 \begin_inset Argument item:2
4041 \begin_layout Plain Layout
4048 \begin_inset space ~
4052 \begin_inset Formula $G'$
4056 \begin_inset Newline newline
4060 \begin_inset space ~
4064 \begin_inset Formula $G'$
4071 \begin_layout Column
4075 \begin_layout Example
4079 \begin_layout Plain Layout
4083 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
4086 \begin_layout Plain Layout
4090 color{beamerexample}
4093 \begin_layout Plain Layout
4097 pgfsetlinewidth{0.6pt}
4100 \begin_layout Plain Layout
4109 \begin_layout Plain Layout
4118 \begin_layout Plain Layout
4127 \begin_layout Plain Layout
4136 \begin_layout Plain Layout
4143 \begin_layout Plain Layout
4151 pgfbox[center,center]{$s$}}
4154 \begin_layout Plain Layout
4162 pgfbox[center,center]{$t$}}
4165 \begin_layout Plain Layout
4169 color{beamerexample}
4172 \begin_layout Plain Layout
4181 \begin_layout Plain Layout
4185 pgfnodesetsepstart{2pt}
4188 \begin_layout Plain Layout
4192 pgfnodesetsepend{2pt}
4195 \begin_layout Plain Layout
4201 pgfnodeconnline{B}{A}}
4204 \begin_layout Plain Layout
4210 pgfnodeconnline{B}{C}}
4213 \begin_layout Plain Layout
4219 pgfnodeconnline{C}{D}}
4222 \begin_layout Plain Layout
4228 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4231 \begin_layout Plain Layout
4239 pgfbox[left,center]{$G
4244 \begin_layout Plain Layout
4251 \begin_layout Plain Layout
4259 pgfbox[left,center]{$G'
4264 \begin_layout Plain Layout
4273 \begin_layout Plain Layout
4282 \begin_layout Plain Layout
4291 \begin_layout Plain Layout
4300 \begin_layout Plain Layout
4309 \begin_layout Plain Layout
4318 \begin_layout Plain Layout
4327 \begin_layout Plain Layout
4336 \begin_layout Plain Layout
4345 \begin_layout Plain Layout
4354 \begin_layout Plain Layout
4363 \begin_layout Plain Layout
4372 \begin_layout Plain Layout
4381 \begin_layout Plain Layout
4390 \begin_layout Plain Layout
4399 \begin_layout Plain Layout
4408 \begin_layout Plain Layout
4415 \begin_layout Plain Layout
4423 pgfbox[center,center]{$s'$}}
4426 \begin_layout Plain Layout
4434 pgfbox[center,center]{$t'$}}
4437 \begin_layout Plain Layout
4442 \begin_layout Plain Layout
4447 \begin_layout Plain Layout
4454 \begin_layout Plain Layout
4458 pgfsetlinewidth{0.4pt}
4461 \begin_layout Plain Layout
4465 color{beamerexample!25!averagebackgroundcolor}
4468 \begin_layout Plain Layout
4472 pgfnodeconnline{A2}{C1}
4475 \begin_layout Plain Layout
4479 pgfnodeconnline{A2}{D1}
4482 \begin_layout Plain Layout
4486 pgfnodeconnline{B2}{A1}
4489 \begin_layout Plain Layout
4493 pgfnodeconnline{B2}{C1}
4496 \begin_layout Plain Layout
4500 pgfnodeconnline{B2}{D1}
4503 \begin_layout Plain Layout
4507 pgfnodeconnline{C2}{D1}
4510 \begin_layout Plain Layout
4514 pgfnodeconnline{D2}{A1}
4517 \begin_layout Plain Layout
4521 pgfnodeconnline{D2}{B1}
4524 \begin_layout Plain Layout
4528 pgfnodeconnline{A3}{C2}
4531 \begin_layout Plain Layout
4535 pgfnodeconnline{A3}{D2}
4538 \begin_layout Plain Layout
4542 pgfnodeconnline{B3}{A2}
4545 \begin_layout Plain Layout
4549 pgfnodeconnline{B3}{C2}
4552 \begin_layout Plain Layout
4556 pgfnodeconnline{B3}{D2}
4559 \begin_layout Plain Layout
4563 pgfnodeconnline{C3}{D2}
4566 \begin_layout Plain Layout
4570 pgfnodeconnline{D3}{A2}
4573 \begin_layout Plain Layout
4577 pgfnodeconnline{D3}{B2}
4580 \begin_layout Plain Layout
4584 pgfnodeconnline{A4}{C3}
4587 \begin_layout Plain Layout
4591 pgfnodeconnline{A4}{D3}
4594 \begin_layout Plain Layout
4598 pgfnodeconnline{B4}{A3}
4601 \begin_layout Plain Layout
4605 pgfnodeconnline{B4}{C3}
4608 \begin_layout Plain Layout
4612 pgfnodeconnline{B4}{D3}
4615 \begin_layout Plain Layout
4619 pgfnodeconnline{C4}{D3}
4622 \begin_layout Plain Layout
4626 pgfnodeconnline{D4}{A3}
4629 \begin_layout Plain Layout
4633 pgfnodeconnline{D4}{B3}
4636 \begin_layout Plain Layout
4645 \begin_layout Plain Layout
4649 pgfnodeconnline{A1}{B1}
4652 \begin_layout Plain Layout
4656 pgfnodeconnline{B1}{C1}
4659 \begin_layout Plain Layout
4663 pgfnodeconnline{C1}{D1}
4666 \begin_layout Plain Layout
4670 pgfnodeconnline{A2}{B2}
4673 \begin_layout Plain Layout
4677 pgfnodeconnline{B2}{C2}
4680 \begin_layout Plain Layout
4684 pgfnodeconnline{C2}{D2}
4687 \begin_layout Plain Layout
4691 pgfnodeconnline{A3}{B3}
4694 \begin_layout Plain Layout
4698 pgfnodeconnline{B3}{C3}
4701 \begin_layout Plain Layout
4705 pgfnodeconnline{C3}{D3}
4708 \begin_layout Plain Layout
4712 pgfnodeconnline{A4}{B4}
4715 \begin_layout Plain Layout
4719 pgfnodeconnline{B4}{C4}
4722 \begin_layout Plain Layout
4726 pgfnodeconnline{C4}{D4}
4729 \begin_layout Plain Layout
4736 \begin_layout Plain Layout
4740 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4743 \begin_layout Plain Layout
4747 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4750 \begin_layout Plain Layout
4754 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4757 \begin_layout Plain Layout
4761 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4764 \begin_layout Plain Layout
4768 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4771 \begin_layout Plain Layout
4775 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4778 \begin_layout Plain Layout
4782 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4785 \begin_layout Plain Layout
4789 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4792 \begin_layout Plain Layout
4796 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4799 \begin_layout Plain Layout
4803 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4806 \begin_layout Plain Layout
4810 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4813 \begin_layout Plain Layout
4817 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4820 \begin_layout Plain Layout
4824 color{beamerexample}
4827 \begin_layout Plain Layout
4831 pgfsetlinewidth{0.6pt}
4834 \begin_layout Plain Layout
4839 \begin_layout Plain Layout
4846 \begin_layout Plain Layout
4853 \begin_layout Plain Layout
4857 pgfnodeconnline{B1}{A2}
4860 \begin_layout Plain Layout
4864 pgfnodeconnline{B2}{A3}
4867 \begin_layout Plain Layout
4871 pgfnodeconnline{B3}{A4}
4874 \begin_layout Plain Layout
4879 \begin_layout Plain Layout
4886 \begin_layout Plain Layout
4893 \begin_layout Plain Layout
4897 pgfnodeconnline{B1}{C2}
4900 \begin_layout Plain Layout
4904 pgfnodeconnline{B2}{C3}
4907 \begin_layout Plain Layout
4911 pgfnodeconnline{B3}{C4}
4914 \begin_layout Plain Layout
4919 \begin_layout Plain Layout
4926 \begin_layout Plain Layout
4933 \begin_layout Plain Layout
4937 pgfnodeconnline{C1}{D2}
4940 \begin_layout Plain Layout
4946 pgfnodeconnline{C2}{D3}}
4949 \begin_layout Plain Layout
4955 pgfnodeconnline{C3}{D4}}
4958 \begin_layout Plain Layout
4963 \begin_layout Plain Layout
4970 \begin_layout Plain Layout
4977 \begin_layout Plain Layout
4983 pgfnodeconnline{A1}{C2}}
4986 \begin_layout Plain Layout
4992 pgfnodeconnline{A2}{C3}}
4995 \begin_layout Plain Layout
4999 pgfnodeconnline{A3}{C4}
5002 \begin_layout Plain Layout
5007 \begin_layout Plain Layout
5014 \begin_layout Plain Layout
5021 \begin_layout Plain Layout
5027 pgfnodeconnline{A1}{A2}}
5030 \begin_layout Plain Layout
5034 pgfnodeconnline{A2}{A3}
5037 \begin_layout Plain Layout
5041 pgfnodeconnline{A3}{A4}
5044 \begin_layout Plain Layout
5048 pgfnodeconnline{B1}{B2}
5051 \begin_layout Plain Layout
5055 pgfnodeconnline{B2}{B3}
5058 \begin_layout Plain Layout
5062 pgfnodeconnline{B3}{B4}
5065 \begin_layout Plain Layout
5069 pgfnodeconnline{C1}{C2}
5072 \begin_layout Plain Layout
5076 pgfnodeconnline{C2}{C3}
5079 \begin_layout Plain Layout
5083 pgfnodeconnline{C3}{C4}
5086 \begin_layout Plain Layout
5090 pgfnodeconnline{D1}{D2}
5093 \begin_layout Plain Layout
5097 pgfnodeconnline{D2}{D3}
5100 \begin_layout Plain Layout
5106 pgfnodeconnline{D3}{D4}}
5109 \begin_layout Plain Layout
5114 \begin_layout Plain Layout
5128 \begin_layout AgainFrame
5129 \begin_inset Argument 1
5132 \begin_layout Plain Layout
5141 \begin_layout Subsection
5142 Complexity of: Approximating the Shortest Path
5146 \begin_inset Argument 4
5149 \begin_layout Plain Layout
5150 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5156 \begin_inset Separator parbreak
5163 \begin_layout Definition
5168 approximation scheme for
5169 \begin_inset Formula $\Lang{tournament-shortest-path}$
5177 \begin_inset Separator parbreak
5184 \begin_layout Enumerate
5186 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5192 \begin_layout Enumerate
5194 \begin_inset Formula $r>1$
5200 \begin_layout Standard
5204 \begin_layout Itemize
5206 \begin_inset Formula $s$
5210 \begin_inset space ~
5214 \begin_inset Formula $t$
5218 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5226 \begin_layout Standard
5227 \begin_inset Separator parbreak
5234 \begin_inset Argument 4
5237 \begin_layout Plain Layout
5238 There Exists a Logspace Approximation Scheme for
5239 \begin_inset Newline newline
5242 the Tournament Shortest Path Problem
5248 \begin_inset Separator parbreak
5255 \begin_layout Theorem
5256 There exists an approximation scheme for
5257 \begin_inset Formula $\Lang{tournament-shortest-path}$
5261 \begin_inset Formula $1<r<2$
5265 \begin_inset Formula
5267 O\left(\log|V|\log\frac{1}{r-1}\right).
5279 \begin_layout Corollary
5280 In tournaments, paths can be constructed in logarithmic space.
5283 \begin_layout Standard
5284 \begin_inset space \hfill{}
5291 \begin_layout Plain Layout
5295 hyperlink{optimality}{
5297 beamergotobutton{More Details}}
5306 \begin_layout AgainFrame
5307 \begin_inset Argument 1
5310 \begin_layout Plain Layout
5319 \begin_layout Standard
5320 \begin_inset Note Note
5323 \begin_layout Plain Layout
5324 If a frame includes a program listing, the frame needs to be marked as
5325 \begin_inset Quotes eld
5329 \begin_inset Quotes erd
5334 has the FragileFrame layout for this.
5342 \begin_layout FragileFrame
5343 \begin_inset Argument 4
5346 \begin_layout Plain Layout
5347 Just a frame with a program code listing
5355 \begin_layout FragileFrame
5356 This is some program code:
5357 \begin_inset Separator parbreak
5364 \begin_layout Standard
5365 \begin_inset listings
5366 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5370 \begin_layout Plain Layout
5375 \begin_layout Plain Layout
5377 'this is a python function'
5380 \begin_layout Plain Layout
5385 \begin_layout Plain Layout
5390 \begin_layout Plain Layout
5392 'This is a German word: Tschüs'
5395 \begin_layout Plain Layout
5400 \begin_layout Plain Layout
5405 \begin_layout Plain Layout
5407 'this is a python function'
5410 \begin_layout Plain Layout
5421 \begin_layout Section*
5425 \begin_layout Subsection*
5430 \begin_inset Argument 4
5433 \begin_layout Plain Layout
5440 \begin_inset Separator parbreak
5448 \begin_inset Argument 2
5451 \begin_layout Plain Layout
5458 \begin_inset Separator parbreak
5465 \begin_layout Itemize
5479 \begin_inset Formula $\Class{AC}^{0}$
5488 \begin_layout Itemize
5493 logspace approximation scheme
5505 shortest paths in tournaments.
5508 \begin_layout Itemize
5522 \begin_inset Formula $\Class{NL}$
5531 \begin_layout Standard
5532 \begin_inset Separator parbreak
5539 \begin_inset Argument 2
5542 \begin_layout Plain Layout
5549 \begin_inset Separator parbreak
5556 \begin_layout Itemize
5557 The same results apply to graphs with
5558 \begin_inset Newline newline
5561 bounded independence number.
5562 \begin_inset space \hfill{}
5569 \begin_layout Plain Layout
5573 hyperlink{independence}{
5575 beamergotobutton{More Details}}
5583 \begin_layout Itemize
5584 The complexity of finding paths in undirected graphs
5585 \begin_inset Newline newline
5589 \begin_inset space \hfill{}
5596 \begin_layout Plain Layout
5600 hyperlink{undirected}{
5602 beamergotobutton{More Details}}
5612 \begin_layout Subsection*
5617 \begin_inset Argument 4
5620 \begin_layout Plain Layout
5627 \begin_inset Separator parbreak
5634 \begin_layout Standard
5638 \begin_layout Plain Layout
5642 beamertemplatebookbibitems
5650 \begin_layout Bibliography
5651 \begin_inset CommandInset bibitem
5652 LatexCommand bibitem
5658 \begin_inset space ~
5666 \begin_layout Plain Layout
5677 Topics on Tournaments.
5684 \begin_layout Plain Layout
5693 Holt, Rinehart, and Winston, 1968.
5698 \begin_layout Plain Layout
5702 beamertemplatearticlebibitems
5710 \begin_layout Bibliography
5711 \begin_inset CommandInset bibitem
5712 LatexCommand bibitem
5713 key "NickelsenT2002"
5718 \begin_inset space ~
5721 Arfst Nickelsen and Till Tantau.
5726 \begin_layout Plain Layout
5735 On reachability in graphs with bounded independence number.
5739 \begin_layout Plain Layout
5753 , Springer-Verlag, 2002.
5756 \begin_layout Bibliography
5757 \begin_inset CommandInset bibitem
5758 LatexCommand bibitem
5764 \begin_inset space ~
5771 \begin_layout Plain Layout
5780 A logspace approximation scheme for the shortest path problem for graphs
5781 with bounded independence number.
5785 \begin_layout Plain Layout
5799 , Springer-Verlag, 2004.
5804 \begin_layout Plain Layout
5817 \begin_layout Standard
5822 \begin_layout Plain Layout
5826 AtBeginSubsection[]{}
5834 \begin_layout Section
5838 \begin_layout Subsection
5839 Graphs With Bounded Independence Number
5843 \begin_inset Argument 3
5846 \begin_layout Plain Layout
5853 \begin_inset Argument 4
5856 \begin_layout Plain Layout
5857 Definition of Independence Number of a Graph
5863 \begin_inset Separator parbreak
5870 \begin_layout Definition
5880 \begin_inset Formula $\alpha(G)$
5884 \begin_inset Newline newline
5887 is the maximum number of vertices we can pick,
5888 \begin_inset Newline newline
5891 such that there is no edge between them.
5894 \begin_layout Example
5895 Tournaments have independence number 1.
5900 \begin_layout Standard
5901 \begin_inset Separator parbreak
5908 \begin_inset Argument 4
5911 \begin_layout Plain Layout
5912 The Results for Tournaments also Apply to
5913 \begin_inset Newline newline
5916 Graphs With Bounded Independence Number
5922 \begin_inset Separator parbreak
5929 \begin_layout Theorem
5931 \begin_inset space ~
5935 \begin_inset Formula $k$
5946 in graphs with independence number
5947 \begin_inset Newline newline
5951 \begin_inset space ~
5955 \begin_inset Formula $k$
5959 \begin_inset Formula $\Class{AC}^{0}$
5965 \begin_layout Standard
5966 \begin_inset Separator parbreak
5972 \begin_layout Theorem
5974 \begin_inset space ~
5978 \begin_inset Formula $k$
5985 logspace approximation scheme
5989 for approximating the shortest path in graphs with independence number at
5991 \begin_inset space ~
5995 \begin_inset Formula $k$
6001 \begin_layout Standard
6002 \begin_inset Separator parbreak
6008 \begin_layout Theorem
6010 \begin_inset space ~
6014 \begin_inset Formula $k$
6025 in graphs with independence number at most
6026 \begin_inset space ~
6030 \begin_inset Formula $k$
6038 \begin_inset Formula $\Class{NL}$
6047 \begin_layout Subsection
6048 Finding Paths in Undirected Graphs
6052 \begin_inset Argument 1
6055 \begin_layout Plain Layout
6062 \begin_inset Argument 3
6065 \begin_layout Plain Layout
6072 \begin_inset Argument 4
6075 \begin_layout Plain Layout
6076 The Complexity of Finding Paths in Undirected Graphs
6077 \begin_inset Newline newline
6086 \begin_inset Separator parbreak
6094 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6098 \begin_inset Formula $\Class{SL}$
6104 \begin_layout Corollary
6105 For undirected graphs, we can solve
6106 \begin_inset Separator parbreak
6113 \begin_layout Itemize
6114 the reachability problem in logspace iff
6115 \begin_inset Formula $\Class L=\Class{SL}$
6121 \begin_layout Itemize
6122 the construction problem in logspace iff
6123 \begin_inset Flex Alternative
6126 \begin_layout Plain Layout
6127 \begin_inset Argument 1
6130 \begin_layout Plain Layout
6137 \begin_inset Argument 2
6140 \begin_layout Plain Layout
6147 \begin_inset Flex Alert
6150 \begin_layout Plain Layout
6151 \begin_inset Formula $\Class L=\Class{SL}$
6167 \begin_layout Itemize
6168 the optimization problem in logspace iff
6169 \begin_inset Flex Alternative
6172 \begin_layout Plain Layout
6173 \begin_inset Argument 1
6176 \begin_layout Plain Layout
6183 \begin_inset Argument 2
6186 \begin_layout Plain Layout
6193 \begin_inset Flex Alert
6196 \begin_layout Plain Layout
6197 \begin_inset Formula $\Class L=\Class{NL}$
6213 \begin_layout Itemize
6214 the approximation problem in logspace iff ?.
6220 \begin_layout Subsection
6221 The Approximation Scheme is Optimal
6225 \begin_inset Argument 3
6228 \begin_layout Plain Layout
6235 \begin_inset Argument 4
6238 \begin_layout Plain Layout
6239 The Approximation Scheme is Optimal
6245 \begin_inset Separator parbreak
6252 \begin_layout Theorem
6253 Suppose there exists an approximation scheme for
6254 \begin_inset Formula $\Lang{tournament-shortest-path}$
6258 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6263 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6270 \begin_inset Separator parbreak
6277 \begin_layout Enumerate
6278 Suppose the approximation scheme exists.
6279 \begin_inset Newline newline
6283 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6290 \begin_layout Enumerate
6292 \begin_inset Formula $(T,s,t)$
6297 \begin_inset Formula $n$
6300 be the number of vertices.
6303 \begin_layout Enumerate
6304 Run the approximation scheme for
6305 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6309 \begin_inset Newline newline
6313 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6319 \begin_layout Enumerate
6320 The resulting path has optimal length.
6325 \begin_layout Plain Layout