1 #LyX 2.2 created this file. For more info see http://www.lyx.org/
5 \origin /systemlyxdir/examples/
8 \beamertemplateshadingbackground{red!5}{structure!5}
10 \usepackage{beamerthemeshadow}
11 \usepackage{pgfnodes,pgfarrows,pgfheaps}
13 \beamertemplatetransparentcovereddynamicmedium
16 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
17 \logo{\pgfuseimage{icsi-logo}}
22 \newcommand{\Class}[1]{\operatorname{\mathchoice
28 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
30 % This gets defined by beamerbasecolor.sty, but only at the beginning of
32 \colorlet{averagebackgroundcolor}{normal text.bg}
34 \newcommand{\tape}[3]{%
35 \color{structure!30!averagebackgroundcolor}
36 \pgfmoveto{\pgfxy(-0.5,0)}
37 \pgflineto{\pgfxy(-0.6,0.1)}
38 \pgflineto{\pgfxy(-0.4,0.2)}
39 \pgflineto{\pgfxy(-0.6,0.3)}
40 \pgflineto{\pgfxy(-0.4,0.4)}
41 \pgflineto{\pgfxy(-0.5,0.5)}
42 \pgflineto{\pgfxy(4,0.5)}
43 \pgflineto{\pgfxy(4.1,0.4)}
44 \pgflineto{\pgfxy(3.9,0.3)}
45 \pgflineto{\pgfxy(4.1,0.2)}
46 \pgflineto{\pgfxy(3.9,0.1)}
47 \pgflineto{\pgfxy(4,0)}
52 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
53 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
56 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
59 \newcommand{\shorttape}[3]{%
60 \color{structure!30!averagebackgroundcolor}
61 \pgfmoveto{\pgfxy(-0.5,0)}
62 \pgflineto{\pgfxy(-0.6,0.1)}
63 \pgflineto{\pgfxy(-0.4,0.2)}
64 \pgflineto{\pgfxy(-0.6,0.3)}
65 \pgflineto{\pgfxy(-0.4,0.4)}
66 \pgflineto{\pgfxy(-0.5,0.5)}
67 \pgflineto{\pgfxy(1,0.5)}
68 \pgflineto{\pgfxy(1.1,0.4)}
69 \pgflineto{\pgfxy(0.9,0.3)}
70 \pgflineto{\pgfxy(1.1,0.2)}
71 \pgflineto{\pgfxy(0.9,0.1)}
72 \pgflineto{\pgfxy(1,0)}
77 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
78 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
81 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
84 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
85 {color(0pt)=(black); color(1cm)=(structure!65!white)}
86 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
87 {color(0pt)=(black); color(1cm)=(structure!55!white)}
88 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
89 {color(0pt)=(black); color(1cm)=(structure!45!white)}
90 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
91 {color(0pt)=(black); color(1cm)=(structure!35!white)}
92 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
93 {color(0pt)=(black); color(1cm)=(structure!25!white)}
94 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
95 {color(0pt)=(black); color(1cm)=(red!35!white)}
97 \newcommand{\heap}[5]{%
100 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
102 \begin{pgfmagnify}{1}{#1}
103 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
109 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
113 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
117 \newcommand{\langat}[2]{%
118 \color{black!30!beamerexample}
119 \pgfsetlinewidth{0.6pt}
120 \pgfsetendarrow{\pgfarrowdot}
121 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
122 \color{beamerexample}
123 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
126 \newcommand{\langatother}[2]{%
127 \color{black!30!beamerexample}
128 \pgfsetlinewidth{0.6pt}
129 \pgfsetendarrow{\pgfarrowdot}
130 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
131 \color{beamerexample}
132 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
136 \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}
139 \pgfdeclareradialshading{graphnode}
140 {\pgfpoint{-3pt}{3.6pt}}%
141 {color(0cm)=(beamerexample!15);
142 color(2.63pt)=(beamerexample!75);
143 color(5.26pt)=(beamerexample!70!black);
144 color(7.6pt)=(beamerexample!50!black);
145 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
147 \newcommand{\graphnode}[2]{
148 \pgfnodecircle{#1}[virtual]{#2}{8pt}
149 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
153 \use_default_options false
154 \maintain_unincluded_children false
156 \language_package default
159 \font_roman "times" "default"
160 \font_sans "default" "default"
161 \font_typewriter "default" "default"
162 \font_math "auto" "auto"
163 \font_default_family default
164 \use_non_tex_fonts false
167 \font_sf_scale 100 100
168 \font_tt_scale 100 100
170 \default_output_format default
172 \bibtex_command default
173 \index_command default
174 \paperfontsize default
179 \use_package amsmath 2
180 \use_package amssymb 2
181 \use_package cancel 0
183 \use_package mathdots 1
184 \use_package mathtools 0
185 \use_package mhchem 1
186 \use_package stackrel 0
187 \use_package stmaryrd 0
188 \use_package undertilde 0
190 \cite_engine_type default
194 \paperorientation portrait
204 \paragraph_separation indent
205 \paragraph_indentation default
206 \quotes_language english
209 \paperpagestyle default
210 \tracking_changes false
211 \output_changes false
214 \html_be_strict false
221 \begin_inset Newline newline
224 Finding Paths in Tournaments
231 \begin_layout Institute
232 International Computer Science Institute
233 \begin_inset Newline newline
237 \begin_inset Argument 1
240 \begin_layout Plain Layout
254 \begin_inset Argument 4
257 \begin_layout Plain Layout
264 \begin_inset Separator parbreak
270 \begin_layout Standard
271 \begin_inset CommandInset toc
272 LatexCommand tableofcontents
280 \begin_layout Plain Layout
291 \begin_layout Standard
295 \begin_layout Plain Layout
297 % Show the table of contents at the beginning
300 \begin_layout Plain Layout
302 % of every subsection.
305 \begin_layout Plain Layout
309 AtBeginSubsection[]{%
312 \begin_layout Plain Layout
319 \begin_layout Plain Layout
326 \begin_layout Plain Layout
330 tableofcontents[current,currentsubsection]
333 \begin_layout Plain Layout
338 \begin_layout Plain Layout
348 \begin_layout Section
352 \begin_layout Subsection
353 What are Tournaments?
357 \begin_inset Argument 4
360 \begin_layout Plain Layout
361 Tournaments Consist of Jousts Between Knights
367 \begin_inset Separator parbreak
373 \begin_layout Columns
375 \begin_inset Separator parbreak
385 \begin_layout Standard
389 \begin_layout Plain Layout
393 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
396 \begin_layout Plain Layout
400 pgfnodebox{A}[virtual]{
405 \begin_layout Plain Layout
409 pgfuseimage{knight1}}{2pt}{2pt}
412 \begin_layout Plain Layout
416 pgfnodebox{B}[virtual]{
421 \begin_layout Plain Layout
425 pgfuseimage{knight2}}{2pt}{2pt}
428 \begin_layout Plain Layout
432 pgfnodebox{C}[virtual]{
437 \begin_layout Plain Layout
441 pgfuseimage{knight3}}{2pt}{2pt}
444 \begin_layout Plain Layout
448 pgfnodebox{D}[virtual]{
453 \begin_layout Plain Layout
457 pgfuseimage{knight4}}{2pt}{2pt}
460 \begin_layout Plain Layout
467 \begin_layout Plain Layout
478 \begin_layout Plain Layout
485 \begin_layout Plain Layout
489 pgfsetlinewidth{0.6pt}
492 \begin_layout Plain Layout
496 pgfnodeconnline{A}{B}
499 \begin_layout Plain Layout
503 pgfnodeconnline{A}{C}
506 \begin_layout Plain Layout
510 pgfnodeconnline{D}{A}
513 \begin_layout Plain Layout
517 pgfnodeconnline{C}{B}
520 \begin_layout Plain Layout
524 pgfnodeconnline{B}{D}
527 \begin_layout Plain Layout
531 pgfnodeconnline{C}{D}
534 \begin_layout Plain Layout
539 \begin_layout Plain Layout
556 \begin_inset Argument 2
559 \begin_layout Plain Layout
560 What is a Tournament?
566 \begin_inset Separator parbreak
572 \begin_layout Itemize
573 \begin_inset Argument item:2
576 \begin_layout Plain Layout
585 \begin_layout Itemize
586 \begin_inset Argument item:2
589 \begin_layout Plain Layout
595 Every pair has a joust.
598 \begin_layout Itemize
599 \begin_inset Argument item:2
602 \begin_layout Plain Layout
608 In every joust one knight wins.
614 \begin_layout Standard
616 \begin_inset Separator parbreak
623 \begin_inset Argument 4
626 \begin_layout Plain Layout
627 Tournaments are Complete Directed Graphs
633 \begin_inset Separator parbreak
639 \begin_layout Columns
641 \begin_inset Separator parbreak
651 \begin_layout Standard
655 \begin_layout Plain Layout
659 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
662 \begin_layout Plain Layout
669 \begin_layout Plain Layout
673 pgfsetlinewidth{0.6pt}
676 \begin_layout Plain Layout
685 \begin_layout Plain Layout
694 \begin_layout Plain Layout
703 \begin_layout Plain Layout
712 \begin_layout Plain Layout
719 \begin_layout Plain Layout
727 pgfbox[center,center]{$v_2$}}
730 \begin_layout Plain Layout
738 pgfbox[center,center]{$v_3$}}
741 \begin_layout Plain Layout
749 pgfbox[center,center]{$v_4$}}
752 \begin_layout Plain Layout
760 pgfbox[center,center]{$v_1$}}
763 \begin_layout Plain Layout
770 \begin_layout Plain Layout
779 \begin_layout Plain Layout
783 pgfnodesetsepstart{2pt}
786 \begin_layout Plain Layout
790 pgfnodesetsepend{4pt}
793 \begin_layout Plain Layout
797 pgfnodeconnline{A}{B}
800 \begin_layout Plain Layout
804 pgfnodeconnline{A}{C}
807 \begin_layout Plain Layout
811 pgfnodeconnline{D}{A}
814 \begin_layout Plain Layout
818 pgfnodeconnline{C}{B}
821 \begin_layout Plain Layout
825 pgfnodeconnline{B}{D}
828 \begin_layout Plain Layout
832 pgfnodeconnline{D}{C}
835 \begin_layout Plain Layout
851 \begin_layout Definition
852 \begin_inset Argument 1
855 \begin_layout Plain Layout
871 \begin_inset Separator parbreak
877 \begin_layout Enumerate
881 \begin_layout Enumerate
882 with exactly one edge between
883 \begin_inset Newline newline
886 any two different vertices.
892 \begin_layout Standard
894 \begin_inset Separator parbreak
901 \begin_inset Argument 2
904 \begin_layout Plain Layout
911 \begin_inset Argument 4
914 \begin_layout Plain Layout
915 Tournaments Arise Naturally in Different Situations
921 \begin_inset Separator parbreak
927 \begin_layout ExampleBlock
928 \begin_inset Argument 2
931 \begin_layout Plain Layout
932 Applications in Ordering Theory
938 \begin_inset Separator parbreak
944 \begin_layout Standard
945 Elements in a set need to be sorted.
947 \begin_inset Newline newline
950 The comparison relation may be cyclic, however.
954 \begin_layout Standard
956 \begin_inset Separator parbreak
962 \begin_layout ExampleBlock
963 \begin_inset Argument 2
966 \begin_layout Plain Layout
967 Applications in Sociology
973 \begin_inset Separator parbreak
979 \begin_layout Standard
980 Several candidates apply for a position.
981 \begin_inset Newline newline
984 Reviewers decide for any two candidates whom they prefer.
989 \begin_layout Standard
991 \begin_inset Separator parbreak
997 \begin_layout ExampleBlock
998 \begin_inset Argument 2
1001 \begin_layout Plain Layout
1002 Applications in Structural Complexity Theory
1008 \begin_inset Separator parbreak
1014 \begin_layout Standard
1016 \begin_inset Formula $L$
1019 is given and a selector function
1020 \begin_inset Formula $f$
1024 \begin_inset Newline newline
1027 It chooses from any two words the one more likely to be in
1028 \begin_inset Formula $f$
1036 \begin_layout Subsection
1037 What Does ``Finding Paths'' Mean?
1041 \begin_inset Argument 4
1044 \begin_layout Plain Layout
1045 ``Finding Paths'' is Ambiguous
1051 \begin_inset Separator parbreak
1058 \begin_inset Argument 2
1061 \begin_layout Plain Layout
1063 \begin_inset Flex Only
1066 \begin_layout Plain Layout
1067 \begin_inset Argument 1
1070 \begin_layout Plain Layout
1076 Path Finding Problems
1082 \begin_inset Flex Only
1085 \begin_layout Plain Layout
1086 \begin_inset Argument 1
1089 \begin_layout Plain Layout
1096 \begin_inset Formula $\Lang{reach}$
1105 \begin_inset Flex Only
1108 \begin_layout Plain Layout
1109 \begin_inset Argument 1
1112 \begin_layout Plain Layout
1118 the Construction Problem
1124 \begin_inset Flex Only
1127 \begin_layout Plain Layout
1128 \begin_inset Argument 1
1131 \begin_layout Plain Layout
1137 the Optimization Problem
1143 \begin_inset Flex Only
1146 \begin_layout Plain Layout
1147 \begin_inset Argument 1
1150 \begin_layout Plain Layout
1157 \begin_inset Formula $\Lang{distance}$
1166 \begin_inset Flex Only
1169 \begin_layout Plain Layout
1170 \begin_inset Argument 1
1173 \begin_layout Plain Layout
1179 the Approximation Problem
1190 \begin_inset Separator parbreak
1196 \begin_layout Itemize
1206 \begin_inset Formula $G=(V,E)$
1218 \begin_inset Formula $s\in V$
1230 \begin_inset Formula $t\in V$
1236 \begin_layout Itemize
1237 \begin_inset Argument item:2
1240 \begin_layout Plain Layout
1253 \begin_inset space ~
1257 \begin_inset Formula $d$
1264 \begin_layout Plain Layout
1276 \begin_layout Itemize
1277 \begin_inset Argument item:2
1280 \begin_layout Plain Layout
1295 \begin_inset Formula $r>1$
1302 \begin_layout Standard
1306 \begin_layout Plain Layout
1318 \begin_layout Overprint
1319 \begin_inset Argument item:1
1322 \begin_layout Plain Layout
1329 \begin_inset Separator parbreak
1335 \begin_layout Columns
1336 \begin_inset Argument 1
1339 \begin_layout Plain Layout
1346 \begin_inset Separator parbreak
1352 \begin_layout Standard
1353 \begin_inset Flex Alternative
1356 \begin_layout Plain Layout
1357 \begin_inset Argument 1
1360 \begin_layout Plain Layout
1367 \begin_inset Argument 2
1370 \begin_layout Plain Layout
1374 \begin_layout Plain Layout
1394 \begin_layout Plain Layout
1411 \begin_layout ExampleBlock
1412 \begin_inset Argument 2
1415 \begin_layout Plain Layout
1422 \begin_inset Separator parbreak
1428 \begin_layout Standard
1432 \begin_layout Plain Layout
1436 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1439 \begin_layout Plain Layout
1443 \begin_layout Plain Layout
1447 color{beamerexample}
1450 \begin_layout Plain Layout
1454 \begin_layout Plain Layout
1458 pgfsetlinewidth{0.6pt}
1461 \begin_layout Plain Layout
1465 \begin_layout Plain Layout
1474 \begin_layout Plain Layout
1478 \begin_layout Plain Layout
1487 \begin_layout Plain Layout
1491 \begin_layout Plain Layout
1500 \begin_layout Plain Layout
1504 \begin_layout Plain Layout
1513 \begin_layout Plain Layout
1517 \begin_layout Plain Layout
1521 \begin_layout Plain Layout
1525 \begin_layout Plain Layout
1532 \begin_layout Plain Layout
1536 \begin_layout Plain Layout
1544 pgfbox[center,center]{$t$}}
1547 \begin_layout Plain Layout
1551 \begin_layout Plain Layout
1559 pgfbox[center,center]{$s$}}
1562 \begin_layout Plain Layout
1566 \begin_layout Plain Layout
1570 \begin_layout Plain Layout
1574 \begin_layout Plain Layout
1578 color{beamerexample}
1581 \begin_layout Plain Layout
1585 \begin_layout Plain Layout
1594 \begin_layout Plain Layout
1598 \begin_layout Plain Layout
1602 pgfnodesetsepstart{2pt}
1605 \begin_layout Plain Layout
1609 \begin_layout Plain Layout
1613 pgfnodesetsepend{4pt}
1616 \begin_layout Plain Layout
1620 \begin_layout Plain Layout
1624 pgfnodeconnline{A}{B}
1627 \begin_layout Plain Layout
1631 \begin_layout Plain Layout
1635 pgfnodeconnline{A}{C}
1638 \begin_layout Plain Layout
1642 \begin_layout Plain Layout
1646 pgfnodeconnline{D}{A}
1649 \begin_layout Plain Layout
1653 \begin_layout Plain Layout
1657 pgfnodeconnline{C}{B}
1660 \begin_layout Plain Layout
1664 \begin_layout Plain Layout
1668 pgfnodeconnline{B}{D}
1671 \begin_layout Plain Layout
1675 \begin_layout Plain Layout
1679 pgfnodeconnline{D}{C}
1682 \begin_layout Plain Layout
1686 \begin_layout Plain Layout
1690 \begin_layout Plain Layout
1694 \begin_layout Plain Layout
1704 pgfbox[left,center]{, $d=2$}}}
1707 \begin_layout Plain Layout
1711 \begin_layout Plain Layout
1721 pgfbox[left,center]{, $r=1.5$}}}
1724 \begin_layout Plain Layout
1728 \begin_layout Plain Layout
1738 pgfbox[left,center]{, $r=1.25$}}}
1741 \begin_layout Plain Layout
1745 \begin_layout Plain Layout
1758 \begin_layout Standard
1759 \begin_inset Flex Only
1762 \begin_layout Plain Layout
1763 \begin_inset Argument 1
1766 \begin_layout Plain Layout
1776 \begin_layout Plain Layout
1793 \begin_layout ExampleBlock
1794 \begin_inset Argument 1
1797 \begin_layout Plain Layout
1804 \begin_inset Argument 2
1807 \begin_layout Plain Layout
1814 \begin_inset Separator parbreak
1820 \begin_layout Standard
1824 \begin_layout Plain Layout
1828 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1831 \begin_layout Plain Layout
1838 \begin_layout Plain Layout
1842 color{beamerexample}
1845 \begin_layout Plain Layout
1849 pgfsetlinewidth{0.6pt}
1852 \begin_layout Plain Layout
1861 \begin_layout Plain Layout
1870 \begin_layout Plain Layout
1879 \begin_layout Plain Layout
1888 \begin_layout Plain Layout
1895 \begin_layout Plain Layout
1903 pgfbox[center,center]{$t$}}
1906 \begin_layout Plain Layout
1914 pgfbox[center,center]{$s$}}
1917 \begin_layout Plain Layout
1921 color{beamerexample}
1924 \begin_layout Plain Layout
1933 \begin_layout Plain Layout
1937 pgfnodesetsepstart{2pt}
1940 \begin_layout Plain Layout
1944 pgfnodesetsepend{4pt}
1947 \begin_layout Plain Layout
1953 pgfnodeconnline{A}{B}}
1956 \begin_layout Plain Layout
1962 pgfnodeconnline{A}{C}}
1965 \begin_layout Plain Layout
1971 pgfnodeconnline{D}{A}}
1974 \begin_layout Plain Layout
1980 pgfnodeconnline{C}{B}}
1983 \begin_layout Plain Layout
1987 pgfnodeconnline{B}{D}
1990 \begin_layout Plain Layout
1994 pgfnodeconnline{D}{C}
1997 \begin_layout Plain Layout
2002 \begin_layout Plain Layout
2012 pgfbox[left,center]{
2017 \begin_layout Plain Layout
2032 \begin_layout Overprint
2033 \begin_inset Argument item:1
2036 \begin_layout Plain Layout
2043 \begin_inset Separator parbreak
2050 \begin_inset Argument 2
2053 \begin_layout Plain Layout
2054 Variants of Path Finding Problems
2060 \begin_inset Separator parbreak
2066 \begin_layout Description
2067 \begin_inset Argument item:1
2070 \begin_layout Plain Layout
2077 \begin_inset space ~
2080 Problem: Is there a path from
2081 \begin_inset Formula $s$
2085 \begin_inset space ~
2089 \begin_inset Formula $t$
2093 \begin_inset Argument 2
2096 \begin_layout Plain Layout
2097 Approximation Problem:
2105 \begin_layout Description
2106 \begin_inset Argument item:1
2109 \begin_layout Plain Layout
2116 \begin_inset space ~
2119 Problem: Construct a path from
2120 \begin_inset Formula $s$
2124 \begin_inset space ~
2128 \begin_inset Formula $t$
2134 \begin_layout Description
2135 \begin_inset Argument item:1
2138 \begin_layout Plain Layout
2145 \begin_inset space ~
2148 Problem: Construct a shortest path from
2149 \begin_inset Formula $s$
2153 \begin_inset space ~
2157 \begin_inset Formula $t$
2163 \begin_layout Description
2164 \begin_inset Argument item:1
2167 \begin_layout Plain Layout
2174 \begin_inset space ~
2177 Problem: Is the distance of
2178 \begin_inset Formula $s$
2182 \begin_inset space ~
2186 \begin_inset Formula $t$
2190 \begin_inset space ~
2194 \begin_inset Formula $d$
2200 \begin_layout Description
2201 \begin_inset Argument item:1
2204 \begin_layout Plain Layout
2211 \begin_inset space ~
2214 Problem: Construct a path from
2215 \begin_inset Formula $s$
2219 \begin_inset space ~
2223 \begin_inset Formula $t$
2227 \begin_inset Newline newline
2230 approximately their distance.
2236 \begin_layout Section
2240 \begin_layout Subsection
2241 Standard Complexity Classes
2244 \begin_layout Standard
2248 \begin_layout Plain Layout
2252 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2254 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2264 \begin_inset Argument 4
2267 \begin_layout Plain Layout
2268 The Classes L and NL are Defined via
2269 \begin_inset Newline newline
2272 Logspace Turing Machines
2278 \begin_inset Separator parbreak
2284 \begin_layout Standard
2288 \begin_layout Plain Layout
2292 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2295 \begin_layout Plain Layout
2304 \begin_layout Plain Layout
2308 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2311 \begin_layout Plain Layout
2318 \begin_layout Plain Layout
2327 \begin_layout Plain Layout
2331 tape{}{output tape (write only)}{10690836937182}}
2334 \begin_layout Plain Layout
2339 \begin_layout Plain Layout
2346 \begin_layout Plain Layout
2355 \begin_layout Plain Layout
2359 shorttape{work tape (read/write), $O(
2361 log n)$ symbols}{}{42}}
2364 \begin_layout Plain Layout
2373 \begin_layout Plain Layout
2377 pgfbox[center,center]{
2379 pgfuseimage{computer}}}
2382 \begin_layout Plain Layout
2387 \begin_layout Plain Layout
2391 pgfsetlinewidth{0.6pt}
2394 \begin_layout Plain Layout
2401 \begin_layout Plain Layout
2410 \begin_layout Plain Layout
2414 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2417 \begin_layout Plain Layout
2423 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2426 \begin_layout Plain Layout
2432 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2435 \begin_layout Plain Layout
2448 \begin_layout Standard
2450 \begin_inset Separator parbreak
2457 \begin_inset Argument 4
2460 \begin_layout Plain Layout
2461 Logspace Turing Machines Are Quite Powerful
2467 \begin_inset Separator parbreak
2474 \begin_inset Argument 2
2477 \begin_layout Plain Layout
2478 Deterministic logspace machines can compute
2484 \begin_inset Separator parbreak
2490 \begin_layout Itemize
2491 addition, multiplication, and even division
2494 \begin_layout Itemize
2495 reductions used in completeness proofs,
2498 \begin_layout Itemize
2499 reachability in forests.
2508 \begin_inset Argument 2
2511 \begin_layout Plain Layout
2512 Non-deterministic logspace machines can compute
2518 \begin_inset Separator parbreak
2524 \begin_layout Itemize
2525 reachability in graphs,
2528 \begin_layout Itemize
2529 non-reachability in graphs,
2532 \begin_layout Itemize
2533 satisfiability with two literals per clause.
2538 \begin_layout Standard
2540 \begin_inset Separator parbreak
2547 \begin_inset Argument 1
2550 \begin_layout Plain Layout
2557 \begin_inset Argument 3
2560 \begin_layout Plain Layout
2567 \begin_inset Argument 4
2570 \begin_layout Plain Layout
2571 The Complexity Class Hierarchy
2577 \begin_inset Separator parbreak
2583 \begin_layout Standard
2587 \begin_layout Plain Layout
2591 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2594 \begin_layout Plain Layout
2598 pgfsetlinewidth{0.8pt}
2601 \begin_layout Plain Layout
2610 \begin_layout Plain Layout
2614 pgfsetdash{{2pt}}{0pt}
2617 \begin_layout Plain Layout
2625 Class{NC}^2$}{black!50!structure}{2}}
2628 \begin_layout Plain Layout
2634 Class{NL}$}{black!50!structure}{3}
2637 \begin_layout Plain Layout
2643 Class{L}$}{black!50!structure}{4}
2646 \begin_layout Plain Layout
2657 \begin_layout Plain Layout
2663 Class{NC}^1}$}{black!50!structure}{5}
2666 \begin_layout Plain Layout
2671 \begin_layout Plain Layout
2678 \begin_layout Plain Layout
2689 \begin_layout Plain Layout
2695 Class{AC}^0}$}{black}{6}
2698 \begin_layout Plain Layout
2703 \begin_layout Plain Layout
2707 pgfsetlinewidth{1.0pt}
2710 \begin_layout Plain Layout
2717 \begin_layout Plain Layout
2721 pgfxyline(-5,0)(5,0)
2724 \begin_layout Plain Layout
2735 \begin_layout Plain Layout
2745 operatorname{forest}}$}}
2748 \begin_layout Plain Layout
2759 \begin_layout Plain Layout
2778 \begin_layout Plain Layout
2797 \begin_layout Plain Layout
2810 \begin_layout Plain Layout
2818 operatorname{forest}}$,}
2823 \begin_layout Plain Layout
2831 operatorname{forest}}$,}
2836 \begin_layout Plain Layout
2844 operatorname{path}}$,}
2849 \begin_layout Plain Layout
2857 operatorname{path}}$}}}
2860 \begin_layout Plain Layout
2865 \begin_layout Plain Layout
2875 operatorname{tourn}}$}}
2878 \begin_layout Plain Layout
2891 \begin_layout Plain Layout
2899 operatorname{tourn}}$,}
2904 \begin_layout Plain Layout
2915 \begin_layout Plain Layout
2924 \begin_layout Plain Layout
2929 \begin_layout Plain Layout
2935 pgfsetdash{{1pt}}{0pt}%
2938 \begin_layout Plain Layout
2946 operatorname{tourn}}$''}
2949 \begin_layout Plain Layout
2954 \begin_layout Plain Layout
2967 \begin_layout Standard
2969 \begin_inset Separator parbreak
2976 \begin_inset Argument 4
2979 \begin_layout Plain Layout
2980 The Circuit Complexity Classes AC
2981 \begin_inset Formula $^{0}$
2985 \begin_inset Formula $^{1}$
2989 \begin_inset Formula $^{2}$
2993 \begin_inset Newline newline
2996 Limit the Circuit Depth
3002 \begin_inset Separator parbreak
3008 \begin_layout Standard
3012 \begin_layout Plain Layout
3021 \begin_layout Plain Layout
3033 \begin_layout Columns
3034 \begin_inset Argument 1
3037 \begin_layout Plain Layout
3044 \begin_inset Separator parbreak
3050 \begin_layout Column
3055 \begin_inset Argument 2
3058 \begin_layout Plain Layout
3060 \begin_inset Formula $\Class{AC}^{0}$
3069 \begin_inset Separator parbreak
3075 \begin_layout Itemize
3076 \begin_inset Formula $O(1)$
3082 \begin_layout Itemize
3087 \begin_layout Examples
3089 \begin_inset Separator parbreak
3095 \begin_layout Itemize
3096 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3102 \begin_layout Itemize
3103 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3114 \begin_layout Column
3119 \begin_inset Argument 2
3122 \begin_layout Plain Layout
3124 \begin_inset Formula $\Class{NC}^{1}$
3133 \begin_inset Separator parbreak
3139 \begin_layout Itemize
3140 \begin_inset Formula $O(\log n)$
3146 \begin_layout Itemize
3151 \begin_layout Examples
3153 \begin_inset Separator parbreak
3159 \begin_layout Itemize
3160 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3166 \begin_layout Itemize
3167 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3173 \begin_layout Itemize
3174 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3185 \begin_layout Column
3190 \begin_inset Argument 2
3193 \begin_layout Plain Layout
3195 \begin_inset Formula $\Class{NC}^{2}$
3204 \begin_inset Separator parbreak
3210 \begin_layout Itemize
3211 \begin_inset Formula $O(\log^{2}n)$
3217 \begin_layout Itemize
3222 \begin_layout Examples
3224 \begin_inset Separator parbreak
3230 \begin_layout Itemize
3231 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3240 \begin_layout AgainFrame
3241 \begin_inset Argument 1
3244 \begin_layout Plain Layout
3253 \begin_layout Subsection
3254 Standard Complexity Results on Finding Paths
3258 \begin_inset Argument 4
3261 \begin_layout Plain Layout
3262 All Variants of Finding Paths in Directed Graphs
3263 \begin_inset Newline newline
3266 Are Equally Difficult
3272 \begin_inset Separator parbreak
3279 \begin_inset Formula $\Lang{reach}$
3283 \begin_inset Formula $\Lang{distance}$
3287 \begin_inset Formula $\Class{NL}$
3298 \begin_layout Corollary
3299 For directed graphs, we can solve
3300 \begin_inset Separator parbreak
3306 \begin_layout Itemize
3307 the reachability problem in logspace iff
3308 \begin_inset Formula $\Class{L}=\Class{NL}$
3314 \begin_layout Itemize
3315 the construction problem in logspace iff
3316 \begin_inset Formula $\Class{L}=\Class{NL}$
3322 \begin_layout Itemize
3323 the optimization problem in logspace iff
3324 \begin_inset Formula $\Class{L}=\Class{NL}$
3330 \begin_layout Itemize
3331 the approximation problem in logspace iff
3332 \begin_inset Formula $\Class{L}=\Class{NL}$
3340 \begin_layout AgainFrame
3341 \begin_inset Argument 1
3344 \begin_layout Plain Layout
3354 \begin_inset Argument 4
3357 \begin_layout Plain Layout
3358 Finding Paths in Forests and Directed Paths is Easy,
3359 \begin_inset Newline newline
3368 \begin_inset Separator parbreak
3375 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3379 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3383 \begin_inset Formula $\Class{L}$
3389 \begin_layout Standard
3391 \begin_inset Separator parbreak
3398 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3402 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3406 \begin_inset Formula $\Class{L}$
3413 \begin_layout AgainFrame
3414 \begin_inset Argument 1
3417 \begin_layout Plain Layout
3426 \begin_layout Section
3427 Finding Paths in Tournaments
3430 \begin_layout Subsection
3431 Complexity of: Does a Path Exist?
3435 \begin_inset Argument 4
3438 \begin_layout Plain Layout
3439 Definition of the Tournament Reachability Problem
3445 \begin_inset Separator parbreak
3451 \begin_layout Definition
3457 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3465 \begin_inset Formula $(T,s,t)$
3470 \begin_inset Separator parbreak
3476 \begin_layout Enumerate
3477 \begin_inset Formula $T=(V,E)$
3483 \begin_layout Enumerate
3484 there exists a path from
3485 \begin_inset space ~
3489 \begin_inset Formula $s$
3493 \begin_inset space ~
3497 \begin_inset Formula $t$
3505 \begin_layout Standard
3507 \begin_inset Separator parbreak
3514 \begin_inset Argument 4
3517 \begin_layout Plain Layout
3518 The Tournament Reachability Problem is Very Easy
3524 \begin_inset Separator parbreak
3530 \begin_layout Theorem
3531 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3541 \begin_layout AlertBlock
3542 \begin_inset Argument 2
3545 \begin_layout Plain Layout
3552 \begin_inset Separator parbreak
3558 \begin_layout Itemize
3560 \begin_inset Quotes eld
3564 \begin_inset Quotes erd
3568 \begin_inset Formula $\Lang{reach}$
3572 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3578 \begin_layout Itemize
3579 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3587 \begin_layout AgainFrame
3588 \begin_inset Argument 1
3591 \begin_layout Plain Layout
3600 \begin_layout Subsection
3601 Complexity of: Construct a Shortest Path
3605 \begin_inset Argument 4
3608 \begin_layout Plain Layout
3609 Finding a Shortest Path Is as Difficult as
3610 \begin_inset Newline newline
3613 the Distance Problem
3619 \begin_inset Separator parbreak
3625 \begin_layout Definition
3631 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3639 \begin_inset Formula $(T,s,t,d)$
3644 \begin_inset Separator parbreak
3650 \begin_layout Enumerate
3651 \begin_inset Formula $T=(V,E)$
3654 is a tournament in which
3657 \begin_layout Enumerate
3659 \begin_inset Formula $s$
3663 \begin_inset space ~
3667 \begin_inset Formula $t$
3671 \begin_inset space ~
3675 \begin_inset Formula $d$
3683 \begin_layout Standard
3685 \begin_inset Separator parbreak
3692 \begin_inset Argument 4
3695 \begin_layout Plain Layout
3696 The Tournament Distance Problem is Hard
3702 \begin_inset Separator parbreak
3708 \begin_layout Theorem
3709 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3713 \begin_inset Formula $\Class{NL}$
3719 \begin_layout Standard
3720 \begin_inset space \hfill{}
3727 \begin_layout Plain Layout
3731 hyperlink{hierarchy<6>}{
3733 beamerskipbutton{Skip Proof}}
3745 \begin_layout Corollary
3746 Shortest path in tournaments can be constructed
3747 \begin_inset Newline newline
3750 in logarithmic space, iff
3751 \begin_inset Formula $\Class{L}=\Class{NL}$
3761 \begin_layout Corollary
3762 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3769 \begin_layout Standard
3771 \begin_inset Separator parbreak
3778 \begin_inset Argument 4
3781 \begin_layout Plain Layout
3783 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3792 \begin_inset Separator parbreak
3798 \begin_layout Standard
3802 \begin_layout Plain Layout
3814 \begin_layout Columns
3815 \begin_inset Argument 1
3818 \begin_layout Plain Layout
3825 \begin_inset Separator parbreak
3831 \begin_layout Column
3835 \begin_layout Standard
3839 \begin_layout Plain Layout
3854 \begin_inset Argument 2
3857 \begin_layout Plain Layout
3859 \begin_inset Formula $\Lang{reach}$
3863 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3872 \begin_inset Separator parbreak
3878 \begin_layout Enumerate
3879 \begin_inset Argument item:2
3882 \begin_layout Plain Layout
3889 \begin_inset Formula $(G,s,t)$
3893 \begin_inset Formula $\Lang{reach}$
3899 \begin_layout Enumerate
3900 \begin_inset Argument item:2
3903 \begin_layout Plain Layout
3910 \begin_inset Formula $G$
3914 \begin_inset Formula $G'$
3920 \begin_layout Enumerate
3921 \begin_inset Argument item:2
3924 \begin_layout Plain Layout
3931 \begin_inset Newline newline
3935 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3942 \begin_layout Standard
3944 \begin_inset Separator parbreak
3951 \begin_inset Argument 2
3954 \begin_layout Plain Layout
3961 \begin_inset Argument 1
3964 \begin_layout Plain Layout
3971 \begin_inset Separator parbreak
3977 \begin_layout Enumerate
3978 \begin_inset Argument item:2
3981 \begin_layout Plain Layout
3988 \begin_inset space ~
3992 \begin_inset Formula $G$
3996 \begin_inset Newline newline
4000 \begin_inset space ~
4004 \begin_inset Formula $G'$
4010 \begin_layout Enumerate
4011 \begin_inset Argument item:2
4014 \begin_layout Plain Layout
4021 \begin_inset space ~
4025 \begin_inset Formula $G'$
4029 \begin_inset Newline newline
4033 \begin_inset space ~
4037 \begin_inset Formula $G'$
4044 \begin_layout Column
4048 \begin_layout Example
4052 \begin_layout Plain Layout
4056 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
4059 \begin_layout Plain Layout
4063 color{beamerexample}
4066 \begin_layout Plain Layout
4070 pgfsetlinewidth{0.6pt}
4073 \begin_layout Plain Layout
4082 \begin_layout Plain Layout
4091 \begin_layout Plain Layout
4100 \begin_layout Plain Layout
4109 \begin_layout Plain Layout
4116 \begin_layout Plain Layout
4124 pgfbox[center,center]{$s$}}
4127 \begin_layout Plain Layout
4135 pgfbox[center,center]{$t$}}
4138 \begin_layout Plain Layout
4142 color{beamerexample}
4145 \begin_layout Plain Layout
4154 \begin_layout Plain Layout
4158 pgfnodesetsepstart{2pt}
4161 \begin_layout Plain Layout
4165 pgfnodesetsepend{2pt}
4168 \begin_layout Plain Layout
4174 pgfnodeconnline{B}{A}}
4177 \begin_layout Plain Layout
4183 pgfnodeconnline{B}{C}}
4186 \begin_layout Plain Layout
4192 pgfnodeconnline{C}{D}}
4195 \begin_layout Plain Layout
4201 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4204 \begin_layout Plain Layout
4212 pgfbox[left,center]{$G
4217 \begin_layout Plain Layout
4224 \begin_layout Plain Layout
4232 pgfbox[left,center]{$G'
4237 \begin_layout Plain Layout
4246 \begin_layout Plain Layout
4255 \begin_layout Plain Layout
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
4388 \begin_layout Plain Layout
4396 pgfbox[center,center]{$s'$}}
4399 \begin_layout Plain Layout
4407 pgfbox[center,center]{$t'$}}
4410 \begin_layout Plain Layout
4415 \begin_layout Plain Layout
4420 \begin_layout Plain Layout
4427 \begin_layout Plain Layout
4431 pgfsetlinewidth{0.4pt}
4434 \begin_layout Plain Layout
4438 color{beamerexample!25!averagebackgroundcolor}
4441 \begin_layout Plain Layout
4445 pgfnodeconnline{A2}{C1}
4448 \begin_layout Plain Layout
4452 pgfnodeconnline{A2}{D1}
4455 \begin_layout Plain Layout
4459 pgfnodeconnline{B2}{A1}
4462 \begin_layout Plain Layout
4466 pgfnodeconnline{B2}{C1}
4469 \begin_layout Plain Layout
4473 pgfnodeconnline{B2}{D1}
4476 \begin_layout Plain Layout
4480 pgfnodeconnline{C2}{D1}
4483 \begin_layout Plain Layout
4487 pgfnodeconnline{D2}{A1}
4490 \begin_layout Plain Layout
4494 pgfnodeconnline{D2}{B1}
4497 \begin_layout Plain Layout
4501 pgfnodeconnline{A3}{C2}
4504 \begin_layout Plain Layout
4508 pgfnodeconnline{A3}{D2}
4511 \begin_layout Plain Layout
4515 pgfnodeconnline{B3}{A2}
4518 \begin_layout Plain Layout
4522 pgfnodeconnline{B3}{C2}
4525 \begin_layout Plain Layout
4529 pgfnodeconnline{B3}{D2}
4532 \begin_layout Plain Layout
4536 pgfnodeconnline{C3}{D2}
4539 \begin_layout Plain Layout
4543 pgfnodeconnline{D3}{A2}
4546 \begin_layout Plain Layout
4550 pgfnodeconnline{D3}{B2}
4553 \begin_layout Plain Layout
4557 pgfnodeconnline{A4}{C3}
4560 \begin_layout Plain Layout
4564 pgfnodeconnline{A4}{D3}
4567 \begin_layout Plain Layout
4571 pgfnodeconnline{B4}{A3}
4574 \begin_layout Plain Layout
4578 pgfnodeconnline{B4}{C3}
4581 \begin_layout Plain Layout
4585 pgfnodeconnline{B4}{D3}
4588 \begin_layout Plain Layout
4592 pgfnodeconnline{C4}{D3}
4595 \begin_layout Plain Layout
4599 pgfnodeconnline{D4}{A3}
4602 \begin_layout Plain Layout
4606 pgfnodeconnline{D4}{B3}
4609 \begin_layout Plain Layout
4618 \begin_layout Plain Layout
4622 pgfnodeconnline{A1}{B1}
4625 \begin_layout Plain Layout
4629 pgfnodeconnline{B1}{C1}
4632 \begin_layout Plain Layout
4636 pgfnodeconnline{C1}{D1}
4639 \begin_layout Plain Layout
4643 pgfnodeconnline{A2}{B2}
4646 \begin_layout Plain Layout
4650 pgfnodeconnline{B2}{C2}
4653 \begin_layout Plain Layout
4657 pgfnodeconnline{C2}{D2}
4660 \begin_layout Plain Layout
4664 pgfnodeconnline{A3}{B3}
4667 \begin_layout Plain Layout
4671 pgfnodeconnline{B3}{C3}
4674 \begin_layout Plain Layout
4678 pgfnodeconnline{C3}{D3}
4681 \begin_layout Plain Layout
4685 pgfnodeconnline{A4}{B4}
4688 \begin_layout Plain Layout
4692 pgfnodeconnline{B4}{C4}
4695 \begin_layout Plain Layout
4699 pgfnodeconnline{C4}{D4}
4702 \begin_layout Plain Layout
4709 \begin_layout Plain Layout
4713 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4716 \begin_layout Plain Layout
4720 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4723 \begin_layout Plain Layout
4727 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4730 \begin_layout Plain Layout
4734 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4737 \begin_layout Plain Layout
4741 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4744 \begin_layout Plain Layout
4748 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4751 \begin_layout Plain Layout
4755 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4758 \begin_layout Plain Layout
4762 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4765 \begin_layout Plain Layout
4769 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4772 \begin_layout Plain Layout
4776 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4779 \begin_layout Plain Layout
4783 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4786 \begin_layout Plain Layout
4790 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4793 \begin_layout Plain Layout
4797 color{beamerexample}
4800 \begin_layout Plain Layout
4804 pgfsetlinewidth{0.6pt}
4807 \begin_layout Plain Layout
4812 \begin_layout Plain Layout
4819 \begin_layout Plain Layout
4826 \begin_layout Plain Layout
4830 pgfnodeconnline{B1}{A2}
4833 \begin_layout Plain Layout
4837 pgfnodeconnline{B2}{A3}
4840 \begin_layout Plain Layout
4844 pgfnodeconnline{B3}{A4}
4847 \begin_layout Plain Layout
4852 \begin_layout Plain Layout
4859 \begin_layout Plain Layout
4866 \begin_layout Plain Layout
4870 pgfnodeconnline{B1}{C2}
4873 \begin_layout Plain Layout
4877 pgfnodeconnline{B2}{C3}
4880 \begin_layout Plain Layout
4884 pgfnodeconnline{B3}{C4}
4887 \begin_layout Plain Layout
4892 \begin_layout Plain Layout
4899 \begin_layout Plain Layout
4906 \begin_layout Plain Layout
4910 pgfnodeconnline{C1}{D2}
4913 \begin_layout Plain Layout
4919 pgfnodeconnline{C2}{D3}}
4922 \begin_layout Plain Layout
4928 pgfnodeconnline{C3}{D4}}
4931 \begin_layout Plain Layout
4936 \begin_layout Plain Layout
4943 \begin_layout Plain Layout
4950 \begin_layout Plain Layout
4956 pgfnodeconnline{A1}{C2}}
4959 \begin_layout Plain Layout
4965 pgfnodeconnline{A2}{C3}}
4968 \begin_layout Plain Layout
4972 pgfnodeconnline{A3}{C4}
4975 \begin_layout Plain Layout
4980 \begin_layout Plain Layout
4987 \begin_layout Plain Layout
4994 \begin_layout Plain Layout
5000 pgfnodeconnline{A1}{A2}}
5003 \begin_layout Plain Layout
5007 pgfnodeconnline{A2}{A3}
5010 \begin_layout Plain Layout
5014 pgfnodeconnline{A3}{A4}
5017 \begin_layout Plain Layout
5021 pgfnodeconnline{B1}{B2}
5024 \begin_layout Plain Layout
5028 pgfnodeconnline{B2}{B3}
5031 \begin_layout Plain Layout
5035 pgfnodeconnline{B3}{B4}
5038 \begin_layout Plain Layout
5042 pgfnodeconnline{C1}{C2}
5045 \begin_layout Plain Layout
5049 pgfnodeconnline{C2}{C3}
5052 \begin_layout Plain Layout
5056 pgfnodeconnline{C3}{C4}
5059 \begin_layout Plain Layout
5063 pgfnodeconnline{D1}{D2}
5066 \begin_layout Plain Layout
5070 pgfnodeconnline{D2}{D3}
5073 \begin_layout Plain Layout
5079 pgfnodeconnline{D3}{D4}}
5082 \begin_layout Plain Layout
5087 \begin_layout Plain Layout
5101 \begin_layout AgainFrame
5102 \begin_inset Argument 1
5105 \begin_layout Plain Layout
5114 \begin_layout Subsection
5115 Complexity of: Approximating the Shortest Path
5119 \begin_inset Argument 4
5122 \begin_layout Plain Layout
5123 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5129 \begin_inset Separator parbreak
5135 \begin_layout Definition
5140 approximation scheme for
5141 \begin_inset Formula $\Lang{tournament-shortest-path}$
5150 \begin_inset Separator parbreak
5156 \begin_layout Enumerate
5158 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5164 \begin_layout Enumerate
5166 \begin_inset Formula $r>1$
5172 \begin_layout Standard
5176 \begin_layout Itemize
5178 \begin_inset Formula $s$
5182 \begin_inset space ~
5186 \begin_inset Formula $t$
5190 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5198 \begin_layout Standard
5200 \begin_inset Separator parbreak
5207 \begin_inset Argument 4
5210 \begin_layout Plain Layout
5211 There Exists a Logspace Approximation Scheme for
5212 \begin_inset Newline newline
5215 the Tournament Shortest Path Problem
5221 \begin_inset Separator parbreak
5227 \begin_layout Theorem
5228 There exists an approximation scheme for
5229 \begin_inset Formula $\Lang{tournament-shortest-path}$
5233 \begin_inset Formula $1<r<2$
5237 \begin_inset Formula
5239 O\left(\log|V|\log\frac{1}{r-1}\right).
5251 \begin_layout Corollary
5252 In tournaments, paths can be constructed in logarithmic space.
5255 \begin_layout Standard
5256 \begin_inset space \hfill{}
5263 \begin_layout Plain Layout
5267 hyperlink{optimality}{
5269 beamergotobutton{More Details}}
5278 \begin_layout AgainFrame
5279 \begin_inset Argument 1
5282 \begin_layout Plain Layout
5291 \begin_layout Standard
5292 \begin_inset Note Note
5295 \begin_layout Plain Layout
5296 If a frame includes a program listing, the frame needs to be marked as
5297 \begin_inset Quotes eld
5301 \begin_inset Quotes erd
5305 \SpecialCharNoPassThru LyX
5306 has the FragileFrame layout for this.
5314 \begin_layout FragileFrame
5315 \begin_inset Argument 4
5318 \begin_layout Plain Layout
5319 Just a frame with a program code listing
5327 \begin_layout FragileFrame
5328 This is some program code:
5329 \begin_inset Separator parbreak
5335 \begin_layout Standard
5336 \begin_inset listings
5337 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5341 \begin_layout Plain Layout
5346 \begin_layout Plain Layout
5348 'this is a python function'
5351 \begin_layout Plain Layout
5356 \begin_layout Plain Layout
5361 \begin_layout Plain Layout
5363 'This is a German word: Tschüs'
5366 \begin_layout Plain Layout
5371 \begin_layout Plain Layout
5376 \begin_layout Plain Layout
5378 'this is a python function'
5381 \begin_layout Plain Layout
5392 \begin_layout Section*
5396 \begin_layout Subsection*
5401 \begin_inset Argument 4
5404 \begin_layout Plain Layout
5411 \begin_inset Separator parbreak
5418 \begin_inset Argument 2
5421 \begin_layout Plain Layout
5428 \begin_inset Separator parbreak
5434 \begin_layout Itemize
5448 \begin_inset Formula $\Class{AC}^{0}$
5457 \begin_layout Itemize
5462 logspace approximation scheme
5474 shortest paths in tournaments.
5477 \begin_layout Itemize
5491 \begin_inset Formula $\Class{NL}$
5500 \begin_layout Standard
5502 \begin_inset Separator parbreak
5509 \begin_inset Argument 2
5512 \begin_layout Plain Layout
5519 \begin_inset Separator parbreak
5525 \begin_layout Itemize
5526 The same results apply to graphs with
5527 \begin_inset Newline newline
5530 bounded independence number.
5531 \begin_inset space \hfill{}
5538 \begin_layout Plain Layout
5542 hyperlink{independence}{
5544 beamergotobutton{More Details}}
5552 \begin_layout Itemize
5553 The complexity of finding paths in undirected graphs
5554 \begin_inset Newline newline
5558 \begin_inset space \hfill{}
5565 \begin_layout Plain Layout
5569 hyperlink{undirected}{
5571 beamergotobutton{More Details}}
5581 \begin_layout Subsection*
5586 \begin_inset Argument 4
5589 \begin_layout Plain Layout
5596 \begin_inset Separator parbreak
5602 \begin_layout Standard
5606 \begin_layout Plain Layout
5610 beamertemplatebookbibitems
5618 \begin_layout Bibliography
5619 \begin_inset CommandInset bibitem
5620 LatexCommand bibitem
5626 \begin_inset space ~
5634 \begin_layout Plain Layout
5645 Topics on Tournaments.
5652 \begin_layout Plain Layout
5661 Holt, Rinehart, and Winston, 1968.
5666 \begin_layout Plain Layout
5670 beamertemplatearticlebibitems
5678 \begin_layout Bibliography
5679 \begin_inset CommandInset bibitem
5680 LatexCommand bibitem
5681 key "NickelsenT2002"
5686 \begin_inset space ~
5689 Arfst Nickelsen and Till Tantau.
5694 \begin_layout Plain Layout
5703 On reachability in graphs with bounded independence number.
5707 \begin_layout Plain Layout
5721 , Springer-Verlag, 2002.
5724 \begin_layout Bibliography
5725 \begin_inset CommandInset bibitem
5726 LatexCommand bibitem
5732 \begin_inset space ~
5739 \begin_layout Plain Layout
5748 A logspace approximation scheme for the shortest path problem for graphs
5749 with bounded independence number.
5753 \begin_layout Plain Layout
5767 , Springer-Verlag, 2004.
5772 \begin_layout Plain Layout
5785 \begin_layout Standard
5790 \begin_layout Plain Layout
5794 AtBeginSubsection[]{}
5802 \begin_layout Section
5806 \begin_layout Subsection
5807 Graphs With Bounded Independence Number
5811 \begin_inset Argument 3
5814 \begin_layout Plain Layout
5821 \begin_inset Argument 4
5824 \begin_layout Plain Layout
5825 Definition of Independence Number of a Graph
5831 \begin_inset Separator parbreak
5837 \begin_layout Definition
5847 \begin_inset Formula $\alpha(G)$
5851 \begin_inset Newline newline
5854 is the maximum number of vertices we can pick,
5855 \begin_inset Newline newline
5858 such that there is no edge between them.
5861 \begin_layout Example
5862 Tournaments have independence number 1.
5867 \begin_layout Standard
5869 \begin_inset Separator parbreak
5876 \begin_inset Argument 4
5879 \begin_layout Plain Layout
5880 The Results for Tournaments also Apply to
5881 \begin_inset Newline newline
5884 Graphs With Bounded Independence Number
5890 \begin_inset Separator parbreak
5896 \begin_layout Theorem
5898 \begin_inset space ~
5902 \begin_inset Formula $k$
5913 in graphs with independence number
5914 \begin_inset Newline newline
5918 \begin_inset space ~
5922 \begin_inset Formula $k$
5926 \begin_inset Formula $\Class{AC}^{0}$
5932 \begin_layout Standard
5934 \begin_inset Separator parbreak
5940 \begin_layout Theorem
5942 \begin_inset space ~
5946 \begin_inset Formula $k$
5953 logspace approximation scheme
5957 for approximating the shortest path in graphs with independence number at
5959 \begin_inset space ~
5963 \begin_inset Formula $k$
5969 \begin_layout Standard
5971 \begin_inset Separator parbreak
5977 \begin_layout Theorem
5979 \begin_inset space ~
5983 \begin_inset Formula $k$
5994 in graphs with independence number at most
5995 \begin_inset space ~
5999 \begin_inset Formula $k$
6007 \begin_inset Formula $\Class{NL}$
6016 \begin_layout Subsection
6017 Finding Paths in Undirected Graphs
6021 \begin_inset Argument 1
6024 \begin_layout Plain Layout
6031 \begin_inset Argument 3
6034 \begin_layout Plain Layout
6041 \begin_inset Argument 4
6044 \begin_layout Plain Layout
6045 The Complexity of Finding Paths in Undirected Graphs
6046 \begin_inset Newline newline
6055 \begin_inset Separator parbreak
6062 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6066 \begin_inset Formula $\Class{SL}$
6072 \begin_layout Corollary
6073 For undirected graphs, we can solve
6074 \begin_inset Separator parbreak
6080 \begin_layout Itemize
6081 the reachability problem in logspace iff
6082 \begin_inset Formula $\Class L=\Class{SL}$
6088 \begin_layout Itemize
6089 the construction problem in logspace iff
6090 \begin_inset Flex Alternative
6093 \begin_layout Plain Layout
6094 \begin_inset Argument 1
6097 \begin_layout Plain Layout
6104 \begin_inset Argument 2
6107 \begin_layout Plain Layout
6114 \begin_inset Flex Alert
6117 \begin_layout Plain Layout
6118 \begin_inset Formula $\Class L=\Class{SL}$
6134 \begin_layout Itemize
6135 the optimization problem in logspace iff
6136 \begin_inset Flex Alternative
6139 \begin_layout Plain Layout
6140 \begin_inset Argument 1
6143 \begin_layout Plain Layout
6150 \begin_inset Argument 2
6153 \begin_layout Plain Layout
6160 \begin_inset Flex Alert
6163 \begin_layout Plain Layout
6164 \begin_inset Formula $\Class L=\Class{NL}$
6180 \begin_layout Itemize
6181 the approximation problem in logspace iff ?.
6187 \begin_layout Subsection
6188 The Approximation Scheme is Optimal
6192 \begin_inset Argument 3
6195 \begin_layout Plain Layout
6202 \begin_inset Argument 4
6205 \begin_layout Plain Layout
6206 The Approximation Scheme is Optimal
6212 \begin_inset Separator parbreak
6218 \begin_layout Theorem
6219 Suppose there exists an approximation scheme for
6220 \begin_inset Formula $\Lang{tournament-shortest-path}$
6224 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6229 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6237 \begin_inset Separator parbreak
6243 \begin_layout Enumerate
6244 Suppose the approximation scheme exists.
6245 \begin_inset Newline newline
6249 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6256 \begin_layout Enumerate
6258 \begin_inset Formula $(T,s,t)$
6263 \begin_inset Formula $n$
6266 be the number of vertices.
6269 \begin_layout Enumerate
6270 Run the approximation scheme for
6271 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6275 \begin_inset Newline newline
6279 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6285 \begin_layout Enumerate
6286 The resulting path has optimal length.
6291 \begin_layout Plain Layout