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
268 \begin_layout Standard
269 \begin_inset CommandInset toc
270 LatexCommand tableofcontents
278 \begin_layout Plain Layout
289 \begin_layout Standard
293 \begin_layout Plain Layout
295 % Show the table of contents at the beginning
298 \begin_layout Plain Layout
300 % of every subsection.
303 \begin_layout Plain Layout
307 AtBeginSubsection[]{%
310 \begin_layout Plain Layout
317 \begin_layout Plain Layout
324 \begin_layout Plain Layout
328 tableofcontents[current,currentsubsection]
331 \begin_layout Plain Layout
336 \begin_layout Plain Layout
346 \begin_layout Section
350 \begin_layout Subsection
351 What are Tournaments?
355 \begin_inset Argument 4
358 \begin_layout Plain Layout
359 Tournaments Consist of Jousts Between Knights
368 \begin_layout Columns
377 \begin_layout Standard
381 \begin_layout Plain Layout
385 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
388 \begin_layout Plain Layout
392 pgfnodebox{A}[virtual]{
397 \begin_layout Plain Layout
401 pgfuseimage{knight1}}{2pt}{2pt}
404 \begin_layout Plain Layout
408 pgfnodebox{B}[virtual]{
413 \begin_layout Plain Layout
417 pgfuseimage{knight2}}{2pt}{2pt}
420 \begin_layout Plain Layout
424 pgfnodebox{C}[virtual]{
429 \begin_layout Plain Layout
433 pgfuseimage{knight3}}{2pt}{2pt}
436 \begin_layout Plain Layout
440 pgfnodebox{D}[virtual]{
445 \begin_layout Plain Layout
449 pgfuseimage{knight4}}{2pt}{2pt}
452 \begin_layout Plain Layout
459 \begin_layout Plain Layout
470 \begin_layout Plain Layout
477 \begin_layout Plain Layout
481 pgfsetlinewidth{0.6pt}
484 \begin_layout Plain Layout
488 pgfnodeconnline{A}{B}
491 \begin_layout Plain Layout
495 pgfnodeconnline{A}{C}
498 \begin_layout Plain Layout
502 pgfnodeconnline{D}{A}
505 \begin_layout Plain Layout
509 pgfnodeconnline{C}{B}
512 \begin_layout Plain Layout
516 pgfnodeconnline{B}{D}
519 \begin_layout Plain Layout
523 pgfnodeconnline{C}{D}
526 \begin_layout Plain Layout
531 \begin_layout Plain Layout
548 \begin_inset Argument 2
551 \begin_layout Plain Layout
552 What is a Tournament?
561 \begin_layout Itemize
562 \begin_inset Argument item:2
565 \begin_layout Plain Layout
574 \begin_layout Itemize
575 \begin_inset Argument item:2
578 \begin_layout Plain Layout
584 Every pair has a joust.
587 \begin_layout Itemize
588 \begin_inset Argument item:2
591 \begin_layout Plain Layout
597 In every joust one knight wins.
603 \begin_layout Standard
604 \begin_inset Separator plain
611 \begin_inset Argument 4
614 \begin_layout Plain Layout
615 Tournaments are Complete Directed Graphs
624 \begin_layout Columns
633 \begin_layout Standard
637 \begin_layout Plain Layout
641 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
644 \begin_layout Plain Layout
651 \begin_layout Plain Layout
655 pgfsetlinewidth{0.6pt}
658 \begin_layout Plain Layout
667 \begin_layout Plain Layout
676 \begin_layout Plain Layout
685 \begin_layout Plain Layout
694 \begin_layout Plain Layout
701 \begin_layout Plain Layout
709 pgfbox[center,center]{$v_2$}}
712 \begin_layout Plain Layout
720 pgfbox[center,center]{$v_3$}}
723 \begin_layout Plain Layout
731 pgfbox[center,center]{$v_4$}}
734 \begin_layout Plain Layout
742 pgfbox[center,center]{$v_1$}}
745 \begin_layout Plain Layout
752 \begin_layout Plain Layout
761 \begin_layout Plain Layout
765 pgfnodesetsepstart{2pt}
768 \begin_layout Plain Layout
772 pgfnodesetsepend{4pt}
775 \begin_layout Plain Layout
779 pgfnodeconnline{A}{B}
782 \begin_layout Plain Layout
786 pgfnodeconnline{A}{C}
789 \begin_layout Plain Layout
793 pgfnodeconnline{D}{A}
796 \begin_layout Plain Layout
800 pgfnodeconnline{C}{B}
803 \begin_layout Plain Layout
807 pgfnodeconnline{B}{D}
810 \begin_layout Plain Layout
814 pgfnodeconnline{D}{C}
817 \begin_layout Plain Layout
833 \begin_layout Definition
834 \begin_inset Argument 1
837 \begin_layout Plain Layout
855 \begin_layout Enumerate
859 \begin_layout Enumerate
860 with exactly one edge between
861 \begin_inset Newline newline
864 any two different vertices.
870 \begin_layout Standard
871 \begin_inset Separator plain
878 \begin_inset Argument 2
881 \begin_layout Plain Layout
888 \begin_inset Argument 4
891 \begin_layout Plain Layout
892 Tournaments Arise Naturally in Different Situations
901 \begin_layout ExampleBlock
902 \begin_inset Argument 2
905 \begin_layout Plain Layout
906 Applications in Ordering Theory
915 \begin_layout Standard
916 Elements in a set need to be sorted.
918 \begin_inset Newline newline
921 The comparison relation may be cyclic, however.
925 \begin_layout Standard
926 \begin_inset Separator plain
932 \begin_layout ExampleBlock
933 \begin_inset Argument 2
936 \begin_layout Plain Layout
937 Applications in Sociology
946 \begin_layout Standard
947 Several candidates apply for a position.
948 \begin_inset Newline newline
951 Reviewers decide for any two candidates whom they prefer.
956 \begin_layout Standard
957 \begin_inset Separator plain
963 \begin_layout ExampleBlock
964 \begin_inset Argument 2
967 \begin_layout Plain Layout
968 Applications in Structural Complexity Theory
977 \begin_layout Standard
979 \begin_inset Formula $L$
982 is given and a selector function
983 \begin_inset Formula $f$
987 \begin_inset Newline newline
990 It chooses from any two words the one more likely to be in
991 \begin_inset Formula $f$
999 \begin_layout Subsection
1000 What Does ``Finding Paths'' Mean?
1004 \begin_inset Argument 4
1007 \begin_layout Plain Layout
1008 ``Finding Paths'' is Ambiguous
1018 \begin_inset Argument 2
1021 \begin_layout Plain Layout
1023 \begin_inset Flex Only
1026 \begin_layout Plain Layout
1027 \begin_inset Argument 1
1030 \begin_layout Plain Layout
1036 Path Finding Problems
1042 \begin_inset Flex Only
1045 \begin_layout Plain Layout
1046 \begin_inset Argument 1
1049 \begin_layout Plain Layout
1056 \begin_inset Formula $\Lang{reach}$
1065 \begin_inset Flex Only
1068 \begin_layout Plain Layout
1069 \begin_inset Argument 1
1072 \begin_layout Plain Layout
1078 the Construction Problem
1084 \begin_inset Flex Only
1087 \begin_layout Plain Layout
1088 \begin_inset Argument 1
1091 \begin_layout Plain Layout
1097 the Optimization Problem
1103 \begin_inset Flex Only
1106 \begin_layout Plain Layout
1107 \begin_inset Argument 1
1110 \begin_layout Plain Layout
1117 \begin_inset Formula $\Lang{distance}$
1126 \begin_inset Flex Only
1129 \begin_layout Plain Layout
1130 \begin_inset Argument 1
1133 \begin_layout Plain Layout
1139 the Approximation Problem
1153 \begin_layout Itemize
1163 \begin_inset Formula $G=(V,E)$
1175 \begin_inset Formula $s\in V$
1187 \begin_inset Formula $t\in V$
1193 \begin_layout Itemize
1194 \begin_inset Argument item:2
1197 \begin_layout Plain Layout
1210 \begin_inset space ~
1214 \begin_inset Formula $d$
1221 \begin_layout Plain Layout
1233 \begin_layout Itemize
1234 \begin_inset Argument item:2
1237 \begin_layout Plain Layout
1252 \begin_inset Formula $r>1$
1259 \begin_layout Standard
1263 \begin_layout Plain Layout
1275 \begin_layout Overprint
1276 \begin_inset Argument item:1
1279 \begin_layout Plain Layout
1289 \begin_layout Columns
1290 \begin_inset Argument 1
1293 \begin_layout Plain Layout
1303 \begin_layout Standard
1304 \begin_inset Flex Alternative
1307 \begin_layout Plain Layout
1308 \begin_inset Argument 1
1311 \begin_layout Plain Layout
1318 \begin_inset Argument 2
1321 \begin_layout Plain Layout
1325 \begin_layout Plain Layout
1345 \begin_layout Plain Layout
1362 \begin_layout ExampleBlock
1363 \begin_inset Argument 2
1366 \begin_layout Plain Layout
1376 \begin_layout Standard
1380 \begin_layout Plain Layout
1384 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1387 \begin_layout Plain Layout
1391 \begin_layout Plain Layout
1395 color{beamerexample}
1398 \begin_layout Plain Layout
1402 \begin_layout Plain Layout
1406 pgfsetlinewidth{0.6pt}
1409 \begin_layout Plain Layout
1413 \begin_layout Plain Layout
1422 \begin_layout Plain Layout
1426 \begin_layout Plain Layout
1435 \begin_layout Plain Layout
1439 \begin_layout Plain Layout
1448 \begin_layout Plain Layout
1452 \begin_layout Plain Layout
1461 \begin_layout Plain Layout
1465 \begin_layout Plain Layout
1469 \begin_layout Plain Layout
1473 \begin_layout Plain Layout
1480 \begin_layout Plain Layout
1484 \begin_layout Plain Layout
1492 pgfbox[center,center]{$t$}}
1495 \begin_layout Plain Layout
1499 \begin_layout Plain Layout
1507 pgfbox[center,center]{$s$}}
1510 \begin_layout Plain Layout
1514 \begin_layout Plain Layout
1518 \begin_layout Plain Layout
1522 \begin_layout Plain Layout
1526 color{beamerexample}
1529 \begin_layout Plain Layout
1533 \begin_layout Plain Layout
1542 \begin_layout Plain Layout
1546 \begin_layout Plain Layout
1550 pgfnodesetsepstart{2pt}
1553 \begin_layout Plain Layout
1557 \begin_layout Plain Layout
1561 pgfnodesetsepend{4pt}
1564 \begin_layout Plain Layout
1568 \begin_layout Plain Layout
1572 pgfnodeconnline{A}{B}
1575 \begin_layout Plain Layout
1579 \begin_layout Plain Layout
1583 pgfnodeconnline{A}{C}
1586 \begin_layout Plain Layout
1590 \begin_layout Plain Layout
1594 pgfnodeconnline{D}{A}
1597 \begin_layout Plain Layout
1601 \begin_layout Plain Layout
1605 pgfnodeconnline{C}{B}
1608 \begin_layout Plain Layout
1612 \begin_layout Plain Layout
1616 pgfnodeconnline{B}{D}
1619 \begin_layout Plain Layout
1623 \begin_layout Plain Layout
1627 pgfnodeconnline{D}{C}
1630 \begin_layout Plain Layout
1634 \begin_layout Plain Layout
1638 \begin_layout Plain Layout
1642 \begin_layout Plain Layout
1652 pgfbox[left,center]{, $d=2$}}}
1655 \begin_layout Plain Layout
1659 \begin_layout Plain Layout
1669 pgfbox[left,center]{, $r=1.5$}}}
1672 \begin_layout Plain Layout
1676 \begin_layout Plain Layout
1686 pgfbox[left,center]{, $r=1.25$}}}
1689 \begin_layout Plain Layout
1693 \begin_layout Plain Layout
1706 \begin_layout Standard
1707 \begin_inset Flex Only
1710 \begin_layout Plain Layout
1711 \begin_inset Argument 1
1714 \begin_layout Plain Layout
1724 \begin_layout Plain Layout
1741 \begin_layout ExampleBlock
1742 \begin_inset Argument 1
1745 \begin_layout Plain Layout
1752 \begin_inset Argument 2
1755 \begin_layout Plain Layout
1765 \begin_layout Standard
1769 \begin_layout Plain Layout
1773 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1776 \begin_layout Plain Layout
1783 \begin_layout Plain Layout
1787 color{beamerexample}
1790 \begin_layout Plain Layout
1794 pgfsetlinewidth{0.6pt}
1797 \begin_layout Plain Layout
1806 \begin_layout Plain Layout
1815 \begin_layout Plain Layout
1824 \begin_layout Plain Layout
1833 \begin_layout Plain Layout
1840 \begin_layout Plain Layout
1848 pgfbox[center,center]{$t$}}
1851 \begin_layout Plain Layout
1859 pgfbox[center,center]{$s$}}
1862 \begin_layout Plain Layout
1866 color{beamerexample}
1869 \begin_layout Plain Layout
1878 \begin_layout Plain Layout
1882 pgfnodesetsepstart{2pt}
1885 \begin_layout Plain Layout
1889 pgfnodesetsepend{4pt}
1892 \begin_layout Plain Layout
1898 pgfnodeconnline{A}{B}}
1901 \begin_layout Plain Layout
1907 pgfnodeconnline{A}{C}}
1910 \begin_layout Plain Layout
1916 pgfnodeconnline{D}{A}}
1919 \begin_layout Plain Layout
1925 pgfnodeconnline{C}{B}}
1928 \begin_layout Plain Layout
1932 pgfnodeconnline{B}{D}
1935 \begin_layout Plain Layout
1939 pgfnodeconnline{D}{C}
1942 \begin_layout Plain Layout
1947 \begin_layout Plain Layout
1957 pgfbox[left,center]{
1962 \begin_layout Plain Layout
1977 \begin_layout Overprint
1978 \begin_inset Argument item:1
1981 \begin_layout Plain Layout
1992 \begin_inset Argument 2
1995 \begin_layout Plain Layout
1996 Variants of Path Finding Problems
2005 \begin_layout Description
2006 \begin_inset Argument item:1
2009 \begin_layout Plain Layout
2016 \begin_inset space ~
2019 Problem: Is there a path from
2020 \begin_inset Formula $s$
2024 \begin_inset space ~
2028 \begin_inset Formula $t$
2032 \begin_inset Argument 2
2035 \begin_layout Plain Layout
2036 Approximation Problem:
2044 \begin_layout Description
2045 \begin_inset Argument item:1
2048 \begin_layout Plain Layout
2055 \begin_inset space ~
2058 Problem: Construct a path from
2059 \begin_inset Formula $s$
2063 \begin_inset space ~
2067 \begin_inset Formula $t$
2073 \begin_layout Description
2074 \begin_inset Argument item:1
2077 \begin_layout Plain Layout
2084 \begin_inset space ~
2087 Problem: Construct a shortest path from
2088 \begin_inset Formula $s$
2092 \begin_inset space ~
2096 \begin_inset Formula $t$
2102 \begin_layout Description
2103 \begin_inset Argument item:1
2106 \begin_layout Plain Layout
2113 \begin_inset space ~
2116 Problem: Is the distance of
2117 \begin_inset Formula $s$
2121 \begin_inset space ~
2125 \begin_inset Formula $t$
2129 \begin_inset space ~
2133 \begin_inset Formula $d$
2139 \begin_layout Description
2140 \begin_inset Argument item:1
2143 \begin_layout Plain Layout
2150 \begin_inset space ~
2153 Problem: Construct a path from
2154 \begin_inset Formula $s$
2158 \begin_inset space ~
2162 \begin_inset Formula $t$
2166 \begin_inset Newline newline
2169 approximately their distance.
2175 \begin_layout Section
2179 \begin_layout Subsection
2180 Standard Complexity Classes
2183 \begin_layout Standard
2187 \begin_layout Plain Layout
2191 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2193 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2203 \begin_inset Argument 4
2206 \begin_layout Plain Layout
2207 The Classes L and NL are Defined via
2208 \begin_inset Newline newline
2211 Logspace Turing Machines
2220 \begin_layout Standard
2224 \begin_layout Plain Layout
2228 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2231 \begin_layout Plain Layout
2240 \begin_layout Plain Layout
2244 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2247 \begin_layout Plain Layout
2254 \begin_layout Plain Layout
2263 \begin_layout Plain Layout
2267 tape{}{output tape (write only)}{10690836937182}}
2270 \begin_layout Plain Layout
2275 \begin_layout Plain Layout
2282 \begin_layout Plain Layout
2291 \begin_layout Plain Layout
2295 shorttape{work tape (read/write), $O(
2297 log n)$ symbols}{}{42}}
2300 \begin_layout Plain Layout
2309 \begin_layout Plain Layout
2313 pgfbox[center,center]{
2315 pgfuseimage{computer}}}
2318 \begin_layout Plain Layout
2323 \begin_layout Plain Layout
2327 pgfsetlinewidth{0.6pt}
2330 \begin_layout Plain Layout
2337 \begin_layout Plain Layout
2346 \begin_layout Plain Layout
2350 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2353 \begin_layout Plain Layout
2359 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2362 \begin_layout Plain Layout
2368 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2371 \begin_layout Plain Layout
2384 \begin_layout Standard
2385 \begin_inset Separator plain
2392 \begin_inset Argument 4
2395 \begin_layout Plain Layout
2396 Logspace Turing Machines Are Quite Powerful
2406 \begin_inset Argument 2
2409 \begin_layout Plain Layout
2410 Deterministic logspace machines can compute
2419 \begin_layout Itemize
2420 addition, multiplication, and even division
2423 \begin_layout Itemize
2424 reductions used in completeness proofs,
2427 \begin_layout Itemize
2428 reachability in forests.
2437 \begin_inset Argument 2
2440 \begin_layout Plain Layout
2441 Non-deterministic logspace machines can compute
2450 \begin_layout Itemize
2451 reachability in graphs,
2454 \begin_layout Itemize
2455 non-reachability in graphs,
2458 \begin_layout Itemize
2459 satisfiability with two literals per clause.
2464 \begin_layout Standard
2465 \begin_inset Separator plain
2472 \begin_inset Argument 1
2475 \begin_layout Plain Layout
2482 \begin_inset Argument 3
2485 \begin_layout Plain Layout
2492 \begin_inset Argument 4
2495 \begin_layout Plain Layout
2496 The Complexity Class Hierarchy
2505 \begin_layout Standard
2509 \begin_layout Plain Layout
2513 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2516 \begin_layout Plain Layout
2520 pgfsetlinewidth{0.8pt}
2523 \begin_layout Plain Layout
2532 \begin_layout Plain Layout
2536 pgfsetdash{{2pt}}{0pt}
2539 \begin_layout Plain Layout
2547 Class{NC}^2$}{black!50!structure}{2}}
2550 \begin_layout Plain Layout
2556 Class{NL}$}{black!50!structure}{3}
2559 \begin_layout Plain Layout
2565 Class{L}$}{black!50!structure}{4}
2568 \begin_layout Plain Layout
2579 \begin_layout Plain Layout
2585 Class{NC}^1}$}{black!50!structure}{5}
2588 \begin_layout Plain Layout
2593 \begin_layout Plain Layout
2600 \begin_layout Plain Layout
2611 \begin_layout Plain Layout
2617 Class{AC}^0}$}{black}{6}
2620 \begin_layout Plain Layout
2625 \begin_layout Plain Layout
2629 pgfsetlinewidth{1.0pt}
2632 \begin_layout Plain Layout
2639 \begin_layout Plain Layout
2643 pgfxyline(-5,0)(5,0)
2646 \begin_layout Plain Layout
2657 \begin_layout Plain Layout
2667 operatorname{forest}}$}}
2670 \begin_layout Plain Layout
2681 \begin_layout Plain Layout
2700 \begin_layout Plain Layout
2719 \begin_layout Plain Layout
2732 \begin_layout Plain Layout
2740 operatorname{forest}}$,}
2745 \begin_layout Plain Layout
2753 operatorname{forest}}$,}
2758 \begin_layout Plain Layout
2766 operatorname{path}}$,}
2771 \begin_layout Plain Layout
2779 operatorname{path}}$}}}
2782 \begin_layout Plain Layout
2787 \begin_layout Plain Layout
2797 operatorname{tourn}}$}}
2800 \begin_layout Plain Layout
2813 \begin_layout Plain Layout
2821 operatorname{tourn}}$,}
2826 \begin_layout Plain Layout
2837 \begin_layout Plain Layout
2846 \begin_layout Plain Layout
2851 \begin_layout Plain Layout
2857 pgfsetdash{{1pt}}{0pt}%
2860 \begin_layout Plain Layout
2868 operatorname{tourn}}$''}
2871 \begin_layout Plain Layout
2876 \begin_layout Plain Layout
2889 \begin_layout Standard
2890 \begin_inset Separator plain
2897 \begin_inset Argument 4
2900 \begin_layout Plain Layout
2901 The Circuit Complexity Classes AC
2902 \begin_inset Formula $^{0}$
2906 \begin_inset Formula $^{1}$
2910 \begin_inset Formula $^{2}$
2914 \begin_inset Newline newline
2917 Limit the Circuit Depth
2926 \begin_layout Standard
2930 \begin_layout Plain Layout
2939 \begin_layout Plain Layout
2951 \begin_layout Columns
2952 \begin_inset Argument 1
2955 \begin_layout Plain Layout
2965 \begin_layout Column
2970 \begin_inset Argument 2
2973 \begin_layout Plain Layout
2975 \begin_inset Formula $\Class{AC}^{0}$
2987 \begin_layout Itemize
2988 \begin_inset Formula $O(1)$
2994 \begin_layout Itemize
2999 \begin_layout Examples
3004 \begin_layout Itemize
3005 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3011 \begin_layout Itemize
3012 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3023 \begin_layout Column
3028 \begin_inset Argument 2
3031 \begin_layout Plain Layout
3033 \begin_inset Formula $\Class{NC}^{1}$
3045 \begin_layout Itemize
3046 \begin_inset Formula $O(\log n)$
3052 \begin_layout Itemize
3057 \begin_layout Examples
3062 \begin_layout Itemize
3063 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3069 \begin_layout Itemize
3070 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3076 \begin_layout Itemize
3077 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3088 \begin_layout Column
3093 \begin_inset Argument 2
3096 \begin_layout Plain Layout
3098 \begin_inset Formula $\Class{NC}^{2}$
3110 \begin_layout Itemize
3111 \begin_inset Formula $O(\log^{2}n)$
3117 \begin_layout Itemize
3122 \begin_layout Examples
3127 \begin_layout Itemize
3128 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3137 \begin_layout AgainFrame
3138 \begin_inset Argument 1
3141 \begin_layout Plain Layout
3150 \begin_layout Subsection
3151 Standard Complexity Results on Finding Paths
3155 \begin_inset Argument 4
3158 \begin_layout Plain Layout
3159 All Variants of Finding Paths in Directed Graphs
3160 \begin_inset Newline newline
3163 Are Equally Difficult
3173 \begin_inset Formula $\Lang{reach}$
3177 \begin_inset Formula $\Lang{distance}$
3181 \begin_inset Formula $\Class{NL}$
3192 \begin_layout Corollary
3193 For directed graphs, we can solve
3197 \begin_layout Itemize
3198 the reachability problem in logspace iff
3199 \begin_inset Formula $\Class{L}=\Class{NL}$
3205 \begin_layout Itemize
3206 the construction problem in logspace iff
3207 \begin_inset Formula $\Class{L}=\Class{NL}$
3213 \begin_layout Itemize
3214 the optimization problem in logspace iff
3215 \begin_inset Formula $\Class{L}=\Class{NL}$
3221 \begin_layout Itemize
3222 the approximation problem in logspace iff
3223 \begin_inset Formula $\Class{L}=\Class{NL}$
3231 \begin_layout AgainFrame
3232 \begin_inset Argument 1
3235 \begin_layout Plain Layout
3245 \begin_inset Argument 4
3248 \begin_layout Plain Layout
3249 Finding Paths in Forests and Directed Paths is Easy,
3250 \begin_inset Newline newline
3263 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3267 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3271 \begin_inset Formula $\Class{L}$
3277 \begin_layout Standard
3278 \begin_inset Separator plain
3285 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3289 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3293 \begin_inset Formula $\Class{L}$
3300 \begin_layout AgainFrame
3301 \begin_inset Argument 1
3304 \begin_layout Plain Layout
3313 \begin_layout Section
3314 Finding Paths in Tournaments
3317 \begin_layout Subsection
3318 Complexity of: Does a Path Exist?
3322 \begin_inset Argument 4
3325 \begin_layout Plain Layout
3326 Definition of the Tournament Reachability Problem
3335 \begin_layout Definition
3341 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3349 \begin_inset Formula $(T,s,t)$
3356 \begin_layout Enumerate
3357 \begin_inset Formula $T=(V,E)$
3363 \begin_layout Enumerate
3364 there exists a path from
3365 \begin_inset space ~
3369 \begin_inset Formula $s$
3373 \begin_inset space ~
3377 \begin_inset Formula $t$
3385 \begin_layout Standard
3386 \begin_inset Separator plain
3393 \begin_inset Argument 4
3396 \begin_layout Plain Layout
3397 The Tournament Reachability Problem is Very Easy
3406 \begin_layout Theorem
3407 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3417 \begin_layout AlertBlock
3418 \begin_inset Argument 2
3421 \begin_layout Plain Layout
3431 \begin_layout Itemize
3433 \begin_inset Quotes eld
3437 \begin_inset Quotes erd
3441 \begin_inset Formula $\Lang{reach}$
3445 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3451 \begin_layout Itemize
3452 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3460 \begin_layout AgainFrame
3461 \begin_inset Argument 1
3464 \begin_layout Plain Layout
3473 \begin_layout Subsection
3474 Complexity of: Construct a Shortest Path
3478 \begin_inset Argument 4
3481 \begin_layout Plain Layout
3482 Finding a Shortest Path Is as Difficult as
3483 \begin_inset Newline newline
3486 the Distance Problem
3495 \begin_layout Definition
3501 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3509 \begin_inset Formula $(T,s,t,d)$
3516 \begin_layout Enumerate
3517 \begin_inset Formula $T=(V,E)$
3520 is a tournament in which
3523 \begin_layout Enumerate
3525 \begin_inset Formula $s$
3529 \begin_inset space ~
3533 \begin_inset Formula $t$
3537 \begin_inset space ~
3541 \begin_inset Formula $d$
3549 \begin_layout Standard
3550 \begin_inset Separator plain
3557 \begin_inset Argument 4
3560 \begin_layout Plain Layout
3561 The Tournament Distance Problem is Hard
3570 \begin_layout Theorem
3571 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3575 \begin_inset Formula $\Class{NL}$
3581 \begin_layout Standard
3582 \begin_inset space \hfill{}
3589 \begin_layout Plain Layout
3593 hyperlink{hierarchy<6>}{
3595 beamerskipbutton{Skip Proof}}
3607 \begin_layout Corollary
3608 Shortest path in tournaments can be constructed
3609 \begin_inset Newline newline
3612 in logarithmic space, iff
3613 \begin_inset Formula $\Class{L}=\Class{NL}$
3623 \begin_layout Corollary
3624 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3631 \begin_layout Standard
3632 \begin_inset Separator plain
3639 \begin_inset Argument 4
3642 \begin_layout Plain Layout
3644 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3656 \begin_layout Standard
3660 \begin_layout Plain Layout
3672 \begin_layout Columns
3673 \begin_inset Argument 1
3676 \begin_layout Plain Layout
3686 \begin_layout Column
3690 \begin_layout Standard
3694 \begin_layout Plain Layout
3709 \begin_inset Argument 2
3712 \begin_layout Plain Layout
3714 \begin_inset Formula $\Lang{reach}$
3718 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3730 \begin_layout Enumerate
3731 \begin_inset Argument item:2
3734 \begin_layout Plain Layout
3741 \begin_inset Formula $(G,s,t)$
3745 \begin_inset Formula $\Lang{reach}$
3751 \begin_layout Enumerate
3752 \begin_inset Argument item:2
3755 \begin_layout Plain Layout
3762 \begin_inset Formula $G$
3766 \begin_inset Formula $G'$
3772 \begin_layout Enumerate
3773 \begin_inset Argument item:2
3776 \begin_layout Plain Layout
3783 \begin_inset Newline newline
3787 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3794 \begin_layout Standard
3795 \begin_inset Separator plain
3802 \begin_inset Argument 2
3805 \begin_layout Plain Layout
3812 \begin_inset Argument 1
3815 \begin_layout Plain Layout
3825 \begin_layout Enumerate
3826 \begin_inset Argument item:2
3829 \begin_layout Plain Layout
3836 \begin_inset space ~
3840 \begin_inset Formula $G$
3844 \begin_inset Newline newline
3848 \begin_inset space ~
3852 \begin_inset Formula $G'$
3858 \begin_layout Enumerate
3859 \begin_inset Argument item:2
3862 \begin_layout Plain Layout
3869 \begin_inset space ~
3873 \begin_inset Formula $G'$
3877 \begin_inset Newline newline
3881 \begin_inset space ~
3885 \begin_inset Formula $G'$
3892 \begin_layout Column
3896 \begin_layout Example
3900 \begin_layout Plain Layout
3904 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3907 \begin_layout Plain Layout
3911 color{beamerexample}
3914 \begin_layout Plain Layout
3918 pgfsetlinewidth{0.6pt}
3921 \begin_layout Plain Layout
3930 \begin_layout Plain Layout
3939 \begin_layout Plain Layout
3948 \begin_layout Plain Layout
3957 \begin_layout Plain Layout
3964 \begin_layout Plain Layout
3972 pgfbox[center,center]{$s$}}
3975 \begin_layout Plain Layout
3983 pgfbox[center,center]{$t$}}
3986 \begin_layout Plain Layout
3990 color{beamerexample}
3993 \begin_layout Plain Layout
4002 \begin_layout Plain Layout
4006 pgfnodesetsepstart{2pt}
4009 \begin_layout Plain Layout
4013 pgfnodesetsepend{2pt}
4016 \begin_layout Plain Layout
4022 pgfnodeconnline{B}{A}}
4025 \begin_layout Plain Layout
4031 pgfnodeconnline{B}{C}}
4034 \begin_layout Plain Layout
4040 pgfnodeconnline{C}{D}}
4043 \begin_layout Plain Layout
4049 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4052 \begin_layout Plain Layout
4060 pgfbox[left,center]{$G
4065 \begin_layout Plain Layout
4072 \begin_layout Plain Layout
4080 pgfbox[left,center]{$G'
4085 \begin_layout Plain Layout
4094 \begin_layout Plain Layout
4103 \begin_layout Plain Layout
4112 \begin_layout Plain Layout
4121 \begin_layout Plain Layout
4130 \begin_layout Plain Layout
4139 \begin_layout Plain Layout
4148 \begin_layout Plain Layout
4157 \begin_layout Plain Layout
4166 \begin_layout Plain Layout
4175 \begin_layout Plain Layout
4184 \begin_layout Plain Layout
4193 \begin_layout Plain Layout
4202 \begin_layout Plain Layout
4211 \begin_layout Plain Layout
4220 \begin_layout Plain Layout
4229 \begin_layout Plain Layout
4236 \begin_layout Plain Layout
4244 pgfbox[center,center]{$s'$}}
4247 \begin_layout Plain Layout
4255 pgfbox[center,center]{$t'$}}
4258 \begin_layout Plain Layout
4263 \begin_layout Plain Layout
4268 \begin_layout Plain Layout
4275 \begin_layout Plain Layout
4279 pgfsetlinewidth{0.4pt}
4282 \begin_layout Plain Layout
4286 color{beamerexample!25!averagebackgroundcolor}
4289 \begin_layout Plain Layout
4293 pgfnodeconnline{A2}{C1}
4296 \begin_layout Plain Layout
4300 pgfnodeconnline{A2}{D1}
4303 \begin_layout Plain Layout
4307 pgfnodeconnline{B2}{A1}
4310 \begin_layout Plain Layout
4314 pgfnodeconnline{B2}{C1}
4317 \begin_layout Plain Layout
4321 pgfnodeconnline{B2}{D1}
4324 \begin_layout Plain Layout
4328 pgfnodeconnline{C2}{D1}
4331 \begin_layout Plain Layout
4335 pgfnodeconnline{D2}{A1}
4338 \begin_layout Plain Layout
4342 pgfnodeconnline{D2}{B1}
4345 \begin_layout Plain Layout
4349 pgfnodeconnline{A3}{C2}
4352 \begin_layout Plain Layout
4356 pgfnodeconnline{A3}{D2}
4359 \begin_layout Plain Layout
4363 pgfnodeconnline{B3}{A2}
4366 \begin_layout Plain Layout
4370 pgfnodeconnline{B3}{C2}
4373 \begin_layout Plain Layout
4377 pgfnodeconnline{B3}{D2}
4380 \begin_layout Plain Layout
4384 pgfnodeconnline{C3}{D2}
4387 \begin_layout Plain Layout
4391 pgfnodeconnline{D3}{A2}
4394 \begin_layout Plain Layout
4398 pgfnodeconnline{D3}{B2}
4401 \begin_layout Plain Layout
4405 pgfnodeconnline{A4}{C3}
4408 \begin_layout Plain Layout
4412 pgfnodeconnline{A4}{D3}
4415 \begin_layout Plain Layout
4419 pgfnodeconnline{B4}{A3}
4422 \begin_layout Plain Layout
4426 pgfnodeconnline{B4}{C3}
4429 \begin_layout Plain Layout
4433 pgfnodeconnline{B4}{D3}
4436 \begin_layout Plain Layout
4440 pgfnodeconnline{C4}{D3}
4443 \begin_layout Plain Layout
4447 pgfnodeconnline{D4}{A3}
4450 \begin_layout Plain Layout
4454 pgfnodeconnline{D4}{B3}
4457 \begin_layout Plain Layout
4466 \begin_layout Plain Layout
4470 pgfnodeconnline{A1}{B1}
4473 \begin_layout Plain Layout
4477 pgfnodeconnline{B1}{C1}
4480 \begin_layout Plain Layout
4484 pgfnodeconnline{C1}{D1}
4487 \begin_layout Plain Layout
4491 pgfnodeconnline{A2}{B2}
4494 \begin_layout Plain Layout
4498 pgfnodeconnline{B2}{C2}
4501 \begin_layout Plain Layout
4505 pgfnodeconnline{C2}{D2}
4508 \begin_layout Plain Layout
4512 pgfnodeconnline{A3}{B3}
4515 \begin_layout Plain Layout
4519 pgfnodeconnline{B3}{C3}
4522 \begin_layout Plain Layout
4526 pgfnodeconnline{C3}{D3}
4529 \begin_layout Plain Layout
4533 pgfnodeconnline{A4}{B4}
4536 \begin_layout Plain Layout
4540 pgfnodeconnline{B4}{C4}
4543 \begin_layout Plain Layout
4547 pgfnodeconnline{C4}{D4}
4550 \begin_layout Plain Layout
4557 \begin_layout Plain Layout
4561 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4564 \begin_layout Plain Layout
4568 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4571 \begin_layout Plain Layout
4575 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4578 \begin_layout Plain Layout
4582 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4585 \begin_layout Plain Layout
4589 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4592 \begin_layout Plain Layout
4596 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4599 \begin_layout Plain Layout
4603 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4606 \begin_layout Plain Layout
4610 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4613 \begin_layout Plain Layout
4617 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4620 \begin_layout Plain Layout
4624 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4627 \begin_layout Plain Layout
4631 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4634 \begin_layout Plain Layout
4638 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4641 \begin_layout Plain Layout
4645 color{beamerexample}
4648 \begin_layout Plain Layout
4652 pgfsetlinewidth{0.6pt}
4655 \begin_layout Plain Layout
4660 \begin_layout Plain Layout
4667 \begin_layout Plain Layout
4674 \begin_layout Plain Layout
4678 pgfnodeconnline{B1}{A2}
4681 \begin_layout Plain Layout
4685 pgfnodeconnline{B2}{A3}
4688 \begin_layout Plain Layout
4692 pgfnodeconnline{B3}{A4}
4695 \begin_layout Plain Layout
4700 \begin_layout Plain Layout
4707 \begin_layout Plain Layout
4714 \begin_layout Plain Layout
4718 pgfnodeconnline{B1}{C2}
4721 \begin_layout Plain Layout
4725 pgfnodeconnline{B2}{C3}
4728 \begin_layout Plain Layout
4732 pgfnodeconnline{B3}{C4}
4735 \begin_layout Plain Layout
4740 \begin_layout Plain Layout
4747 \begin_layout Plain Layout
4754 \begin_layout Plain Layout
4758 pgfnodeconnline{C1}{D2}
4761 \begin_layout Plain Layout
4767 pgfnodeconnline{C2}{D3}}
4770 \begin_layout Plain Layout
4776 pgfnodeconnline{C3}{D4}}
4779 \begin_layout Plain Layout
4784 \begin_layout Plain Layout
4791 \begin_layout Plain Layout
4798 \begin_layout Plain Layout
4804 pgfnodeconnline{A1}{C2}}
4807 \begin_layout Plain Layout
4813 pgfnodeconnline{A2}{C3}}
4816 \begin_layout Plain Layout
4820 pgfnodeconnline{A3}{C4}
4823 \begin_layout Plain Layout
4828 \begin_layout Plain Layout
4835 \begin_layout Plain Layout
4842 \begin_layout Plain Layout
4848 pgfnodeconnline{A1}{A2}}
4851 \begin_layout Plain Layout
4855 pgfnodeconnline{A2}{A3}
4858 \begin_layout Plain Layout
4862 pgfnodeconnline{A3}{A4}
4865 \begin_layout Plain Layout
4869 pgfnodeconnline{B1}{B2}
4872 \begin_layout Plain Layout
4876 pgfnodeconnline{B2}{B3}
4879 \begin_layout Plain Layout
4883 pgfnodeconnline{B3}{B4}
4886 \begin_layout Plain Layout
4890 pgfnodeconnline{C1}{C2}
4893 \begin_layout Plain Layout
4897 pgfnodeconnline{C2}{C3}
4900 \begin_layout Plain Layout
4904 pgfnodeconnline{C3}{C4}
4907 \begin_layout Plain Layout
4911 pgfnodeconnline{D1}{D2}
4914 \begin_layout Plain Layout
4918 pgfnodeconnline{D2}{D3}
4921 \begin_layout Plain Layout
4927 pgfnodeconnline{D3}{D4}}
4930 \begin_layout Plain Layout
4935 \begin_layout Plain Layout
4949 \begin_layout AgainFrame
4950 \begin_inset Argument 1
4953 \begin_layout Plain Layout
4962 \begin_layout Subsection
4963 Complexity of: Approximating the Shortest Path
4967 \begin_inset Argument 4
4970 \begin_layout Plain Layout
4971 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
4980 \begin_layout Definition
4985 approximation scheme for
4986 \begin_inset Formula $\Lang{tournament-shortest-path}$
4997 \begin_layout Enumerate
4999 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5005 \begin_layout Enumerate
5007 \begin_inset Formula $r>1$
5013 \begin_layout Standard
5017 \begin_layout Itemize
5019 \begin_inset Formula $s$
5023 \begin_inset space ~
5027 \begin_inset Formula $t$
5031 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5039 \begin_layout Standard
5040 \begin_inset Separator plain
5047 \begin_inset Argument 4
5050 \begin_layout Plain Layout
5051 There Exists a Logspace Approximation Scheme for
5052 \begin_inset Newline newline
5055 the Tournament Shortest Path Problem
5064 \begin_layout Theorem
5065 There exists an approximation scheme for
5066 \begin_inset Formula $\Lang{tournament-shortest-path}$
5070 \begin_inset Formula $1<r<2$
5074 \begin_inset Formula
5076 O\left(\log|V|\log\frac{1}{r-1}\right).
5088 \begin_layout Corollary
5089 In tournaments, paths can be constructed in logarithmic space.
5092 \begin_layout Standard
5093 \begin_inset space \hfill{}
5100 \begin_layout Plain Layout
5104 hyperlink{optimality}{
5106 beamergotobutton{More Details}}
5115 \begin_layout AgainFrame
5116 \begin_inset Argument 1
5119 \begin_layout Plain Layout
5128 \begin_layout Standard
5129 \begin_inset Note Note
5132 \begin_layout Plain Layout
5133 If a frame includes a program listing, the frame needs to be marked as
5134 \begin_inset Quotes eld
5138 \begin_inset Quotes erd
5143 has the FragileFrame layout for this.
5151 \begin_layout FragileFrame
5152 \begin_inset Argument 4
5155 \begin_layout Plain Layout
5156 Just a frame with a program code listing
5164 \begin_layout FragileFrame
5165 This is some program code:
5169 \begin_layout Standard
5170 \begin_inset listings
5171 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5175 \begin_layout Plain Layout
5180 \begin_layout Plain Layout
5182 'this is a python function'
5185 \begin_layout Plain Layout
5190 \begin_layout Plain Layout
5195 \begin_layout Plain Layout
5197 'This is a German word: Tschüs'
5200 \begin_layout Plain Layout
5205 \begin_layout Plain Layout
5210 \begin_layout Plain Layout
5212 'this is a python function'
5215 \begin_layout Plain Layout
5226 \begin_layout Section*
5230 \begin_layout Subsection*
5235 \begin_inset Argument 4
5238 \begin_layout Plain Layout
5249 \begin_inset Argument 2
5252 \begin_layout Plain Layout
5262 \begin_layout Itemize
5276 \begin_inset Formula $\Class{AC}^{0}$
5285 \begin_layout Itemize
5290 logspace approximation scheme
5302 shortest paths in tournaments.
5305 \begin_layout Itemize
5319 \begin_inset Formula $\Class{NL}$
5328 \begin_layout Standard
5329 \begin_inset Separator plain
5336 \begin_inset Argument 2
5339 \begin_layout Plain Layout
5349 \begin_layout Itemize
5350 The same results apply to graphs with
5351 \begin_inset Newline newline
5354 bounded independence number.
5355 \begin_inset space \hfill{}
5362 \begin_layout Plain Layout
5366 hyperlink{independence}{
5368 beamergotobutton{More Details}}
5376 \begin_layout Itemize
5377 The complexity of finding paths in undirected graphs
5378 \begin_inset Newline newline
5382 \begin_inset space \hfill{}
5389 \begin_layout Plain Layout
5393 hyperlink{undirected}{
5395 beamergotobutton{More Details}}
5405 \begin_layout Subsection*
5410 \begin_inset Argument 4
5413 \begin_layout Plain Layout
5423 \begin_layout Standard
5427 \begin_layout Plain Layout
5431 beamertemplatebookbibitems
5439 \begin_layout Bibliography
5440 \begin_inset CommandInset bibitem
5441 LatexCommand bibitem
5447 \begin_inset space ~
5455 \begin_layout Plain Layout
5466 Topics on Tournaments.
5473 \begin_layout Plain Layout
5482 Holt, Rinehart, and Winston, 1968.
5487 \begin_layout Plain Layout
5491 beamertemplatearticlebibitems
5499 \begin_layout Bibliography
5500 \begin_inset CommandInset bibitem
5501 LatexCommand bibitem
5502 key "NickelsenT2002"
5507 \begin_inset space ~
5510 Arfst Nickelsen and Till Tantau.
5515 \begin_layout Plain Layout
5524 On reachability in graphs with bounded independence number.
5528 \begin_layout Plain Layout
5542 , Springer-Verlag, 2002.
5545 \begin_layout Bibliography
5546 \begin_inset CommandInset bibitem
5547 LatexCommand bibitem
5553 \begin_inset space ~
5560 \begin_layout Plain Layout
5569 A logspace approximation scheme for the shortest path problem for graphs
5570 with bounded independence number.
5574 \begin_layout Plain Layout
5588 , Springer-Verlag, 2004.
5593 \begin_layout Plain Layout
5606 \begin_layout Standard
5611 \begin_layout Plain Layout
5615 AtBeginSubsection[]{}
5623 \begin_layout Section
5627 \begin_layout Subsection
5628 Graphs With Bounded Independence Number
5632 \begin_inset Argument 3
5635 \begin_layout Plain Layout
5642 \begin_inset Argument 4
5645 \begin_layout Plain Layout
5646 Definition of Independence Number of a Graph
5655 \begin_layout Definition
5665 \begin_inset Formula $\alpha(G)$
5669 \begin_inset Newline newline
5672 is the maximum number of vertices we can pick,
5673 \begin_inset Newline newline
5676 such that there is no edge between them.
5679 \begin_layout Example
5680 Tournaments have independence number 1.
5685 \begin_layout Standard
5686 \begin_inset Separator plain
5693 \begin_inset Argument 4
5696 \begin_layout Plain Layout
5697 The Results for Tournaments also Apply to
5698 \begin_inset Newline newline
5701 Graphs With Bounded Independence Number
5710 \begin_layout Theorem
5712 \begin_inset space ~
5716 \begin_inset Formula $k$
5727 in graphs with independence number
5728 \begin_inset Newline newline
5732 \begin_inset space ~
5736 \begin_inset Formula $k$
5740 \begin_inset Formula $\Class{AC}^{0}$
5746 \begin_layout Standard
5747 \begin_inset Separator plain
5753 \begin_layout Theorem
5755 \begin_inset space ~
5759 \begin_inset Formula $k$
5766 logspace approximation scheme
5770 for approximating the shortest path in graphs with independence number at
5772 \begin_inset space ~
5776 \begin_inset Formula $k$
5782 \begin_layout Standard
5783 \begin_inset Separator plain
5789 \begin_layout Theorem
5791 \begin_inset space ~
5795 \begin_inset Formula $k$
5806 in graphs with independence number at most
5807 \begin_inset space ~
5811 \begin_inset Formula $k$
5819 \begin_inset Formula $\Class{NL}$
5828 \begin_layout Subsection
5829 Finding Paths in Undirected Graphs
5833 \begin_inset Argument 1
5836 \begin_layout Plain Layout
5843 \begin_inset Argument 3
5846 \begin_layout Plain Layout
5853 \begin_inset Argument 4
5856 \begin_layout Plain Layout
5857 The Complexity of Finding Paths in Undirected Graphs
5858 \begin_inset Newline newline
5871 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5875 \begin_inset Formula $\Class{SL}$
5881 \begin_layout Corollary
5882 For undirected graphs, we can solve
5886 \begin_layout Itemize
5887 the reachability problem in logspace iff
5888 \begin_inset Formula $\Class L=\Class{SL}$
5894 \begin_layout Itemize
5895 the construction problem in logspace iff
5896 \begin_inset Flex Alternative
5899 \begin_layout Plain Layout
5900 \begin_inset Argument 1
5903 \begin_layout Plain Layout
5910 \begin_inset Argument 2
5913 \begin_layout Plain Layout
5920 \begin_inset Flex Alert
5923 \begin_layout Plain Layout
5924 \begin_inset Formula $\Class L=\Class{SL}$
5940 \begin_layout Itemize
5941 the optimization problem in logspace iff
5942 \begin_inset Flex Alternative
5945 \begin_layout Plain Layout
5946 \begin_inset Argument 1
5949 \begin_layout Plain Layout
5956 \begin_inset Argument 2
5959 \begin_layout Plain Layout
5966 \begin_inset Flex Alert
5969 \begin_layout Plain Layout
5970 \begin_inset Formula $\Class L=\Class{NL}$
5986 \begin_layout Itemize
5987 the approximation problem in logspace iff ?.
5993 \begin_layout Subsection
5994 The Approximation Scheme is Optimal
5998 \begin_inset Argument 3
6001 \begin_layout Plain Layout
6008 \begin_inset Argument 4
6011 \begin_layout Plain Layout
6012 The Approximation Scheme is Optimal
6021 \begin_layout Theorem
6022 Suppose there exists an approximation scheme for
6023 \begin_inset Formula $\Lang{tournament-shortest-path}$
6027 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6032 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6043 \begin_layout Enumerate
6044 Suppose the approximation scheme exists.
6045 \begin_inset Newline newline
6049 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6056 \begin_layout Enumerate
6058 \begin_inset Formula $(T,s,t)$
6063 \begin_inset Formula $n$
6066 be the number of vertices.
6069 \begin_layout Enumerate
6070 Run the approximation scheme for
6071 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6075 \begin_inset Newline newline
6079 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6085 \begin_layout Enumerate
6086 The resulting path has optimal length.
6091 \begin_layout Plain Layout