1 #LyX 2.1 created this file. For more info see http://www.lyx.org/
7 \beamertemplateshadingbackground{red!5}{structure!5}
9 \usepackage{beamerthemeshadow}
10 \usepackage{pgfnodes,pgfarrows,pgfheaps}
12 \beamertemplatetransparentcovereddynamicmedium
15 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
16 \logo{\pgfuseimage{icsi-logo}}
21 \newcommand{\Class}[1]{\operatorname{\mathchoice
27 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
29 % This gets defined by beamerbasecolor.sty, but only at the beginning of
31 \colorlet{averagebackgroundcolor}{normal text.bg}
33 \newcommand{\tape}[3]{%
34 \color{structure!30!averagebackgroundcolor}
35 \pgfmoveto{\pgfxy(-0.5,0)}
36 \pgflineto{\pgfxy(-0.6,0.1)}
37 \pgflineto{\pgfxy(-0.4,0.2)}
38 \pgflineto{\pgfxy(-0.6,0.3)}
39 \pgflineto{\pgfxy(-0.4,0.4)}
40 \pgflineto{\pgfxy(-0.5,0.5)}
41 \pgflineto{\pgfxy(4,0.5)}
42 \pgflineto{\pgfxy(4.1,0.4)}
43 \pgflineto{\pgfxy(3.9,0.3)}
44 \pgflineto{\pgfxy(4.1,0.2)}
45 \pgflineto{\pgfxy(3.9,0.1)}
46 \pgflineto{\pgfxy(4,0)}
51 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
52 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
55 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
58 \newcommand{\shorttape}[3]{%
59 \color{structure!30!averagebackgroundcolor}
60 \pgfmoveto{\pgfxy(-0.5,0)}
61 \pgflineto{\pgfxy(-0.6,0.1)}
62 \pgflineto{\pgfxy(-0.4,0.2)}
63 \pgflineto{\pgfxy(-0.6,0.3)}
64 \pgflineto{\pgfxy(-0.4,0.4)}
65 \pgflineto{\pgfxy(-0.5,0.5)}
66 \pgflineto{\pgfxy(1,0.5)}
67 \pgflineto{\pgfxy(1.1,0.4)}
68 \pgflineto{\pgfxy(0.9,0.3)}
69 \pgflineto{\pgfxy(1.1,0.2)}
70 \pgflineto{\pgfxy(0.9,0.1)}
71 \pgflineto{\pgfxy(1,0)}
76 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
77 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
80 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
83 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
84 {color(0pt)=(black); color(1cm)=(structure!65!white)}
85 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
86 {color(0pt)=(black); color(1cm)=(structure!55!white)}
87 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
88 {color(0pt)=(black); color(1cm)=(structure!45!white)}
89 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
90 {color(0pt)=(black); color(1cm)=(structure!35!white)}
91 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
92 {color(0pt)=(black); color(1cm)=(structure!25!white)}
93 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
94 {color(0pt)=(black); color(1cm)=(red!35!white)}
96 \newcommand{\heap}[5]{%
99 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
101 \begin{pgfmagnify}{1}{#1}
102 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
108 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
112 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
116 \newcommand{\langat}[2]{%
117 \color{black!30!beamerexample}
118 \pgfsetlinewidth{0.6pt}
119 \pgfsetendarrow{\pgfarrowdot}
120 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
121 \color{beamerexample}
122 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
125 \newcommand{\langatother}[2]{%
126 \color{black!30!beamerexample}
127 \pgfsetlinewidth{0.6pt}
128 \pgfsetendarrow{\pgfarrowdot}
129 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
130 \color{beamerexample}
131 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
135 \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}
138 \pgfdeclareradialshading{graphnode}
139 {\pgfpoint{-3pt}{3.6pt}}%
140 {color(0cm)=(beamerexample!15);
141 color(2.63pt)=(beamerexample!75);
142 color(5.26pt)=(beamerexample!70!black);
143 color(7.6pt)=(beamerexample!50!black);
144 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
146 \newcommand{\graphnode}[2]{
147 \pgfnodecircle{#1}[virtual]{#2}{8pt}
148 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
152 \use_default_options false
153 \maintain_unincluded_children false
155 \language_package default
160 \font_typewriter default
162 \font_default_family default
163 \use_non_tex_fonts false
169 \default_output_format default
171 \bibtex_command default
172 \index_command default
173 \paperfontsize default
178 \use_package amsmath 2
179 \use_package amssymb 2
181 \use_package mathdots 1
182 \use_package mathtools 0
183 \use_package mhchem 1
184 \use_package stackrel 0
185 \use_package stmaryrd 0
186 \use_package undertilde 0
188 \cite_engine_type numerical
192 \paperorientation portrait
202 \paragraph_separation indent
203 \paragraph_indentation default
204 \quotes_language english
207 \paperpagestyle default
208 \tracking_changes false
209 \output_changes false
212 \html_be_strict false
219 \begin_inset Newline newline
222 Finding Paths in Tournaments
229 \begin_layout Institute
230 International Computer Science Institute
231 \begin_inset Newline newline
235 \begin_inset Argument 1
238 \begin_layout Plain Layout
251 \begin_layout BeginFrame
255 \begin_layout Standard
256 \begin_inset CommandInset toc
257 LatexCommand tableofcontents
265 \begin_layout Plain Layout
275 \begin_layout EndFrame
279 \begin_layout Standard
283 \begin_layout Plain Layout
285 % Show the table of contents at the beginning
288 \begin_layout Plain Layout
290 % of every subsection.
293 \begin_layout Plain Layout
297 AtBeginSubsection[]{%
300 \begin_layout Plain Layout
307 \begin_layout Plain Layout
314 \begin_layout Plain Layout
318 tableofcontents[current,currentsubsection]
321 \begin_layout Plain Layout
326 \begin_layout Plain Layout
336 \begin_layout Section
340 \begin_layout Subsection
341 What are Tournaments?
344 \begin_layout BeginFrame
345 Tournaments Consist of Jousts Between Knights
348 \begin_layout Columns
357 \begin_layout Standard
361 \begin_layout Plain Layout
365 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
368 \begin_layout Plain Layout
372 pgfnodebox{A}[virtual]{
377 \begin_layout Plain Layout
381 pgfuseimage{knight1}}{2pt}{2pt}
384 \begin_layout Plain Layout
388 pgfnodebox{B}[virtual]{
393 \begin_layout Plain Layout
397 pgfuseimage{knight2}}{2pt}{2pt}
400 \begin_layout Plain Layout
404 pgfnodebox{C}[virtual]{
409 \begin_layout Plain Layout
413 pgfuseimage{knight3}}{2pt}{2pt}
416 \begin_layout Plain Layout
420 pgfnodebox{D}[virtual]{
425 \begin_layout Plain Layout
429 pgfuseimage{knight4}}{2pt}{2pt}
432 \begin_layout Plain Layout
439 \begin_layout Plain Layout
450 \begin_layout Plain Layout
457 \begin_layout Plain Layout
461 pgfsetlinewidth{0.6pt}
464 \begin_layout Plain Layout
468 pgfnodeconnline{A}{B}
471 \begin_layout Plain Layout
475 pgfnodeconnline{A}{C}
478 \begin_layout Plain Layout
482 pgfnodeconnline{D}{A}
485 \begin_layout Plain Layout
489 pgfnodeconnline{C}{B}
492 \begin_layout Plain Layout
496 pgfnodeconnline{B}{D}
499 \begin_layout Plain Layout
503 pgfnodeconnline{C}{D}
506 \begin_layout Plain Layout
511 \begin_layout Plain Layout
528 \begin_inset Argument 2
531 \begin_layout Plain Layout
532 What is a Tournament?
541 \begin_layout Itemize
542 \begin_inset Argument item:2
545 \begin_layout Plain Layout
554 \begin_layout Itemize
555 \begin_inset Argument item:2
558 \begin_layout Plain Layout
564 Every pair has a joust.
567 \begin_layout Itemize
568 \begin_inset Argument item:2
571 \begin_layout Plain Layout
577 In every joust one knight wins.
582 \begin_layout BeginFrame
583 Tournaments are Complete Directed Graphs
586 \begin_layout Columns
595 \begin_layout Standard
599 \begin_layout Plain Layout
603 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
606 \begin_layout Plain Layout
613 \begin_layout Plain Layout
617 pgfsetlinewidth{0.6pt}
620 \begin_layout Plain Layout
629 \begin_layout Plain Layout
638 \begin_layout Plain Layout
647 \begin_layout Plain Layout
656 \begin_layout Plain Layout
663 \begin_layout Plain Layout
671 pgfbox[center,center]{$v_2$}}
674 \begin_layout Plain Layout
682 pgfbox[center,center]{$v_3$}}
685 \begin_layout Plain Layout
693 pgfbox[center,center]{$v_4$}}
696 \begin_layout Plain Layout
704 pgfbox[center,center]{$v_1$}}
707 \begin_layout Plain Layout
714 \begin_layout Plain Layout
723 \begin_layout Plain Layout
727 pgfnodesetsepstart{2pt}
730 \begin_layout Plain Layout
734 pgfnodesetsepend{4pt}
737 \begin_layout Plain Layout
741 pgfnodeconnline{A}{B}
744 \begin_layout Plain Layout
748 pgfnodeconnline{A}{C}
751 \begin_layout Plain Layout
755 pgfnodeconnline{D}{A}
758 \begin_layout Plain Layout
762 pgfnodeconnline{C}{B}
765 \begin_layout Plain Layout
769 pgfnodeconnline{B}{D}
772 \begin_layout Plain Layout
776 pgfnodeconnline{D}{C}
779 \begin_layout Plain Layout
795 \begin_layout Definition
796 \begin_inset Argument 1
799 \begin_layout Plain Layout
817 \begin_layout Enumerate
821 \begin_layout Enumerate
822 with exactly one edge between
823 \begin_inset Newline newline
826 any two different vertices.
831 \begin_layout BeginFrame
835 \begin_layout Plain Layout
842 Tournaments Arise Naturally in Different Situations
845 \begin_layout ExampleBlock
846 \begin_inset Argument 2
849 \begin_layout Plain Layout
850 Applications in Ordering Theory
859 \begin_layout Standard
860 Elements in a set need to be sorted.
862 \begin_inset Newline newline
865 The comparison relation may be cyclic, however.
869 \begin_layout Separator
873 \begin_layout ExampleBlock
874 \begin_inset Argument 2
877 \begin_layout Plain Layout
878 Applications in Sociology
887 \begin_layout Standard
888 Several candidates apply for a position.
889 \begin_inset Newline newline
892 Reviewers decide for any two candidates whom they prefer.
897 \begin_layout Separator
901 \begin_layout ExampleBlock
902 \begin_inset Argument 2
905 \begin_layout Plain Layout
906 Applications in Structural Complexity Theory
915 \begin_layout Standard
917 \begin_inset Formula $L$
920 is given and a selector function
921 \begin_inset Formula $f$
925 \begin_inset Newline newline
928 It chooses from any two words the one more likely to be in
929 \begin_inset Formula $f$
936 \begin_layout Subsection
937 What Does ``Finding Paths'' Mean?
940 \begin_layout BeginFrame
941 ``Finding Paths'' is Ambiguous
945 \begin_inset Argument 2
948 \begin_layout Plain Layout
950 \begin_inset Flex Only
953 \begin_layout Plain Layout
954 \begin_inset Argument 1
957 \begin_layout Plain Layout
963 Path Finding Problems
969 \begin_inset Flex Only
972 \begin_layout Plain Layout
973 \begin_inset Argument 1
976 \begin_layout Plain Layout
983 \begin_inset Formula $\Lang{reach}$
992 \begin_inset Flex Only
995 \begin_layout Plain Layout
996 \begin_inset Argument 1
999 \begin_layout Plain Layout
1005 the Construction Problem
1011 \begin_inset Flex Only
1014 \begin_layout Plain Layout
1015 \begin_inset Argument 1
1018 \begin_layout Plain Layout
1024 the Optimization Problem
1030 \begin_inset Flex Only
1033 \begin_layout Plain Layout
1034 \begin_inset Argument 1
1037 \begin_layout Plain Layout
1044 \begin_inset Formula $\Lang{distance}$
1053 \begin_inset Flex Only
1056 \begin_layout Plain Layout
1057 \begin_inset Argument 1
1060 \begin_layout Plain Layout
1066 the Approximation Problem
1080 \begin_layout Itemize
1090 \begin_inset Formula $G=(V,E)$
1102 \begin_inset Formula $s\in V$
1114 \begin_inset Formula $t\in V$
1120 \begin_layout Itemize
1121 \begin_inset Argument item:2
1124 \begin_layout Plain Layout
1137 \begin_inset space ~
1141 \begin_inset Formula $d$
1148 \begin_layout Plain Layout
1160 \begin_layout Itemize
1161 \begin_inset Argument item:2
1164 \begin_layout Plain Layout
1179 \begin_inset Formula $r>1$
1186 \begin_layout Standard
1190 \begin_layout Plain Layout
1202 \begin_layout Overprint
1203 \begin_inset Argument item:1
1206 \begin_layout Plain Layout
1216 \begin_layout Columns
1217 \begin_inset Argument 1
1220 \begin_layout Plain Layout
1230 \begin_layout Standard
1231 \begin_inset Flex Alternative
1234 \begin_layout Plain Layout
1235 \begin_inset Argument 1
1238 \begin_layout Plain Layout
1245 \begin_inset Argument 2
1248 \begin_layout Plain Layout
1252 \begin_layout Plain Layout
1272 \begin_layout Plain Layout
1289 \begin_layout ExampleBlock
1290 \begin_inset Argument 2
1293 \begin_layout Plain Layout
1303 \begin_layout Standard
1307 \begin_layout Plain Layout
1311 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1314 \begin_layout Plain Layout
1318 \begin_layout Plain Layout
1322 color{beamerexample}
1325 \begin_layout Plain Layout
1329 \begin_layout Plain Layout
1333 pgfsetlinewidth{0.6pt}
1336 \begin_layout Plain Layout
1340 \begin_layout Plain Layout
1349 \begin_layout Plain Layout
1353 \begin_layout Plain Layout
1362 \begin_layout Plain Layout
1366 \begin_layout Plain Layout
1375 \begin_layout Plain Layout
1379 \begin_layout Plain Layout
1388 \begin_layout Plain Layout
1392 \begin_layout Plain Layout
1396 \begin_layout Plain Layout
1400 \begin_layout Plain Layout
1407 \begin_layout Plain Layout
1411 \begin_layout Plain Layout
1419 pgfbox[center,center]{$t$}}
1422 \begin_layout Plain Layout
1426 \begin_layout Plain Layout
1434 pgfbox[center,center]{$s$}}
1437 \begin_layout Plain Layout
1441 \begin_layout Plain Layout
1445 \begin_layout Plain Layout
1449 \begin_layout Plain Layout
1453 color{beamerexample}
1456 \begin_layout Plain Layout
1460 \begin_layout Plain Layout
1469 \begin_layout Plain Layout
1473 \begin_layout Plain Layout
1477 pgfnodesetsepstart{2pt}
1480 \begin_layout Plain Layout
1484 \begin_layout Plain Layout
1488 pgfnodesetsepend{4pt}
1491 \begin_layout Plain Layout
1495 \begin_layout Plain Layout
1499 pgfnodeconnline{A}{B}
1502 \begin_layout Plain Layout
1506 \begin_layout Plain Layout
1510 pgfnodeconnline{A}{C}
1513 \begin_layout Plain Layout
1517 \begin_layout Plain Layout
1521 pgfnodeconnline{D}{A}
1524 \begin_layout Plain Layout
1528 \begin_layout Plain Layout
1532 pgfnodeconnline{C}{B}
1535 \begin_layout Plain Layout
1539 \begin_layout Plain Layout
1543 pgfnodeconnline{B}{D}
1546 \begin_layout Plain Layout
1550 \begin_layout Plain Layout
1554 pgfnodeconnline{D}{C}
1557 \begin_layout Plain Layout
1561 \begin_layout Plain Layout
1565 \begin_layout Plain Layout
1569 \begin_layout Plain Layout
1579 pgfbox[left,center]{, $d=2$}}}
1582 \begin_layout Plain Layout
1586 \begin_layout Plain Layout
1596 pgfbox[left,center]{, $r=1.5$}}}
1599 \begin_layout Plain Layout
1603 \begin_layout Plain Layout
1613 pgfbox[left,center]{, $r=1.25$}}}
1616 \begin_layout Plain Layout
1620 \begin_layout Plain Layout
1633 \begin_layout Standard
1634 \begin_inset Flex Only
1637 \begin_layout Plain Layout
1638 \begin_inset Argument 1
1641 \begin_layout Plain Layout
1651 \begin_layout Plain Layout
1668 \begin_layout ExampleBlock
1669 \begin_inset Argument 1
1672 \begin_layout Plain Layout
1679 \begin_inset Argument 2
1682 \begin_layout Plain Layout
1692 \begin_layout Standard
1696 \begin_layout Plain Layout
1700 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1703 \begin_layout Plain Layout
1710 \begin_layout Plain Layout
1714 color{beamerexample}
1717 \begin_layout Plain Layout
1721 pgfsetlinewidth{0.6pt}
1724 \begin_layout Plain Layout
1733 \begin_layout Plain Layout
1742 \begin_layout Plain Layout
1751 \begin_layout Plain Layout
1760 \begin_layout Plain Layout
1767 \begin_layout Plain Layout
1775 pgfbox[center,center]{$t$}}
1778 \begin_layout Plain Layout
1786 pgfbox[center,center]{$s$}}
1789 \begin_layout Plain Layout
1793 color{beamerexample}
1796 \begin_layout Plain Layout
1805 \begin_layout Plain Layout
1809 pgfnodesetsepstart{2pt}
1812 \begin_layout Plain Layout
1816 pgfnodesetsepend{4pt}
1819 \begin_layout Plain Layout
1825 pgfnodeconnline{A}{B}}
1828 \begin_layout Plain Layout
1834 pgfnodeconnline{A}{C}}
1837 \begin_layout Plain Layout
1843 pgfnodeconnline{D}{A}}
1846 \begin_layout Plain Layout
1852 pgfnodeconnline{C}{B}}
1855 \begin_layout Plain Layout
1859 pgfnodeconnline{B}{D}
1862 \begin_layout Plain Layout
1866 pgfnodeconnline{D}{C}
1869 \begin_layout Plain Layout
1874 \begin_layout Plain Layout
1884 pgfbox[left,center]{
1889 \begin_layout Plain Layout
1904 \begin_layout Overprint
1905 \begin_inset Argument item:1
1908 \begin_layout Plain Layout
1919 \begin_inset Argument 2
1922 \begin_layout Plain Layout
1923 Variants of Path Finding Problems
1932 \begin_layout Description
1933 \begin_inset Argument item:1
1936 \begin_layout Plain Layout
1943 \begin_inset space ~
1946 Problem: Is there a path from
1947 \begin_inset Formula $s$
1951 \begin_inset space ~
1955 \begin_inset Formula $t$
1959 \begin_inset Argument 2
1962 \begin_layout Plain Layout
1963 Approximation Problem:
1971 \begin_layout Description
1972 \begin_inset Argument item:1
1975 \begin_layout Plain Layout
1982 \begin_inset space ~
1985 Problem: Construct a path from
1986 \begin_inset Formula $s$
1990 \begin_inset space ~
1994 \begin_inset Formula $t$
2000 \begin_layout Description
2001 \begin_inset Argument item:1
2004 \begin_layout Plain Layout
2011 \begin_inset space ~
2014 Problem: Construct a shortest path from
2015 \begin_inset Formula $s$
2019 \begin_inset space ~
2023 \begin_inset Formula $t$
2029 \begin_layout Description
2030 \begin_inset Argument item:1
2033 \begin_layout Plain Layout
2040 \begin_inset space ~
2043 Problem: Is the distance of
2044 \begin_inset Formula $s$
2048 \begin_inset space ~
2052 \begin_inset Formula $t$
2056 \begin_inset space ~
2060 \begin_inset Formula $d$
2066 \begin_layout Description
2067 \begin_inset Argument item:1
2070 \begin_layout Plain Layout
2077 \begin_inset space ~
2080 Problem: Construct a path from
2081 \begin_inset Formula $s$
2085 \begin_inset space ~
2089 \begin_inset Formula $t$
2093 \begin_inset Newline newline
2096 approximately their distance.
2101 \begin_layout Section
2105 \begin_layout Subsection
2106 Standard Complexity Classes
2109 \begin_layout Standard
2113 \begin_layout Plain Layout
2117 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2119 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2128 \begin_layout BeginFrame
2129 The Classes L and NL are Defined via
2130 \begin_inset Newline newline
2133 Logspace Turing Machines
2136 \begin_layout Standard
2140 \begin_layout Plain Layout
2144 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2147 \begin_layout Plain Layout
2156 \begin_layout Plain Layout
2160 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2163 \begin_layout Plain Layout
2170 \begin_layout Plain Layout
2179 \begin_layout Plain Layout
2183 tape{}{output tape (write only)}{10690836937182}}
2186 \begin_layout Plain Layout
2191 \begin_layout Plain Layout
2198 \begin_layout Plain Layout
2207 \begin_layout Plain Layout
2211 shorttape{work tape (read/write), $O(
2213 log n)$ symbols}{}{42}}
2216 \begin_layout Plain Layout
2225 \begin_layout Plain Layout
2229 pgfbox[center,center]{
2231 pgfuseimage{computer}}}
2234 \begin_layout Plain Layout
2239 \begin_layout Plain Layout
2243 pgfsetlinewidth{0.6pt}
2246 \begin_layout Plain Layout
2253 \begin_layout Plain Layout
2262 \begin_layout Plain Layout
2266 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2269 \begin_layout Plain Layout
2275 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2278 \begin_layout Plain Layout
2284 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2287 \begin_layout Plain Layout
2299 \begin_layout BeginFrame
2300 Logspace Turing Machines Are Quite Powerful
2304 \begin_inset Argument 2
2307 \begin_layout Plain Layout
2308 Deterministic logspace machines can compute
2317 \begin_layout Itemize
2318 addition, multiplication, and even division
2321 \begin_layout Itemize
2322 reductions used in completeness proofs,
2325 \begin_layout Itemize
2326 reachability in forests.
2335 \begin_inset Argument 2
2338 \begin_layout Plain Layout
2339 Non-deterministic logspace machines can compute
2348 \begin_layout Itemize
2349 reachability in graphs,
2352 \begin_layout Itemize
2353 non-reachability in graphs,
2356 \begin_layout Itemize
2357 satisfiability with two literals per clause.
2361 \begin_layout BeginFrame
2365 \begin_layout Plain Layout
2367 <1>[label=hierarchy]
2372 The Complexity Class Hierarchy
2375 \begin_layout Standard
2379 \begin_layout Plain Layout
2383 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2386 \begin_layout Plain Layout
2390 pgfsetlinewidth{0.8pt}
2393 \begin_layout Plain Layout
2402 \begin_layout Plain Layout
2406 pgfsetdash{{2pt}}{0pt}
2409 \begin_layout Plain Layout
2417 Class{NC}^2$}{black!50!structure}{2}}
2420 \begin_layout Plain Layout
2426 Class{NL}$}{black!50!structure}{3}
2429 \begin_layout Plain Layout
2435 Class{L}$}{black!50!structure}{4}
2438 \begin_layout Plain Layout
2449 \begin_layout Plain Layout
2455 Class{NC}^1}$}{black!50!structure}{5}
2458 \begin_layout Plain Layout
2463 \begin_layout Plain Layout
2470 \begin_layout Plain Layout
2481 \begin_layout Plain Layout
2487 Class{AC}^0}$}{black}{6}
2490 \begin_layout Plain Layout
2495 \begin_layout Plain Layout
2499 pgfsetlinewidth{1.0pt}
2502 \begin_layout Plain Layout
2509 \begin_layout Plain Layout
2513 pgfxyline(-5,0)(5,0)
2516 \begin_layout Plain Layout
2527 \begin_layout Plain Layout
2537 operatorname{forest}}$}}
2540 \begin_layout Plain Layout
2551 \begin_layout Plain Layout
2570 \begin_layout Plain Layout
2589 \begin_layout Plain Layout
2602 \begin_layout Plain Layout
2610 operatorname{forest}}$,}
2615 \begin_layout Plain Layout
2623 operatorname{forest}}$,}
2628 \begin_layout Plain Layout
2636 operatorname{path}}$,}
2641 \begin_layout Plain Layout
2649 operatorname{path}}$}}}
2652 \begin_layout Plain Layout
2657 \begin_layout Plain Layout
2667 operatorname{tourn}}$}}
2670 \begin_layout Plain Layout
2683 \begin_layout Plain Layout
2691 operatorname{tourn}}$,}
2696 \begin_layout Plain Layout
2707 \begin_layout Plain Layout
2716 \begin_layout Plain Layout
2721 \begin_layout Plain Layout
2727 pgfsetdash{{1pt}}{0pt}%
2730 \begin_layout Plain Layout
2738 operatorname{tourn}}$''}
2741 \begin_layout Plain Layout
2746 \begin_layout Plain Layout
2758 \begin_layout BeginFrame
2759 The Circuit Complexity Classes AC
2760 \begin_inset Formula $^{0}$
2764 \begin_inset Formula $^{1}$
2768 \begin_inset Formula $^{2}$
2772 \begin_inset Newline newline
2775 Limit the Circuit Depth
2778 \begin_layout Standard
2782 \begin_layout Plain Layout
2791 \begin_layout Plain Layout
2803 \begin_layout Columns
2804 \begin_inset Argument 1
2807 \begin_layout Plain Layout
2817 \begin_layout Column
2822 \begin_inset Argument 2
2825 \begin_layout Plain Layout
2827 \begin_inset Formula $\Class{AC}^{0}$
2839 \begin_layout Itemize
2840 \begin_inset Formula $O(1)$
2846 \begin_layout Itemize
2851 \begin_layout Examples
2856 \begin_layout Itemize
2857 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
2863 \begin_layout Itemize
2864 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
2875 \begin_layout Column
2880 \begin_inset Argument 2
2883 \begin_layout Plain Layout
2885 \begin_inset Formula $\Class{NC}^{1}$
2897 \begin_layout Itemize
2898 \begin_inset Formula $O(\log n)$
2904 \begin_layout Itemize
2909 \begin_layout Examples
2914 \begin_layout Itemize
2915 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
2921 \begin_layout Itemize
2922 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
2928 \begin_layout Itemize
2929 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
2940 \begin_layout Column
2945 \begin_inset Argument 2
2948 \begin_layout Plain Layout
2950 \begin_inset Formula $\Class{NC}^{2}$
2962 \begin_layout Itemize
2963 \begin_inset Formula $O(\log^{2}n)$
2969 \begin_layout Itemize
2974 \begin_layout Examples
2979 \begin_layout Itemize
2980 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
2988 \begin_layout AgainFrame
2989 \begin_inset Argument 1
2992 \begin_layout Plain Layout
3001 \begin_layout Subsection
3002 Standard Complexity Results on Finding Paths
3005 \begin_layout BeginFrame
3006 All Variants of Finding Paths in Directed Graphs
3007 \begin_inset Newline newline
3010 Are Equally Difficult
3014 \begin_inset Formula $\Lang{reach}$
3018 \begin_inset Formula $\Lang{distance}$
3022 \begin_inset Formula $\Class{NL}$
3033 \begin_layout Corollary
3034 For directed graphs, we can solve
3038 \begin_layout Itemize
3039 the reachability problem in logspace iff
3040 \begin_inset Formula $\Class{L}=\Class{NL}$
3046 \begin_layout Itemize
3047 the construction problem in logspace iff
3048 \begin_inset Formula $\Class{L}=\Class{NL}$
3054 \begin_layout Itemize
3055 the optimization problem in logspace iff
3056 \begin_inset Formula $\Class{L}=\Class{NL}$
3062 \begin_layout Itemize
3063 the approximation problem in logspace iff
3064 \begin_inset Formula $\Class{L}=\Class{NL}$
3071 \begin_layout AgainFrame
3072 \begin_inset Argument 1
3075 \begin_layout Plain Layout
3084 \begin_layout BeginFrame
3085 Finding Paths in Forests and Directed Paths is Easy,
3086 \begin_inset Newline newline
3093 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3097 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3101 \begin_inset Formula $\Class{L}$
3107 \begin_layout Separator
3112 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3116 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3120 \begin_inset Formula $\Class{L}$
3126 \begin_layout AgainFrame
3127 \begin_inset Argument 1
3130 \begin_layout Plain Layout
3139 \begin_layout Section
3140 Finding Paths in Tournaments
3143 \begin_layout Subsection
3144 Complexity of: Does a Path Exist?
3147 \begin_layout BeginFrame
3148 Definition of the Tournament Reachability Problem
3151 \begin_layout Definition
3157 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3165 \begin_inset Formula $(T,s,t)$
3172 \begin_layout Enumerate
3173 \begin_inset Formula $T=(V,E)$
3179 \begin_layout Enumerate
3180 there exists a path from
3181 \begin_inset space ~
3185 \begin_inset Formula $s$
3189 \begin_inset space ~
3193 \begin_inset Formula $t$
3200 \begin_layout BeginFrame
3201 The Tournament Reachability Problem is Very Easy
3204 \begin_layout Theorem
3205 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3215 \begin_layout AlertBlock
3216 \begin_inset Argument 2
3219 \begin_layout Plain Layout
3229 \begin_layout Itemize
3231 \begin_inset Quotes eld
3235 \begin_inset Quotes erd
3239 \begin_inset Formula $\Lang{reach}$
3243 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3249 \begin_layout Itemize
3250 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3257 \begin_layout AgainFrame
3258 \begin_inset Argument 1
3261 \begin_layout Plain Layout
3270 \begin_layout Subsection
3271 Complexity of: Construct a Shortest Path
3274 \begin_layout BeginFrame
3275 Finding a Shortest Path Is as Difficult as
3276 \begin_inset Newline newline
3279 the Distance Problem
3282 \begin_layout Definition
3288 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3296 \begin_inset Formula $(T,s,t,d)$
3303 \begin_layout Enumerate
3304 \begin_inset Formula $T=(V,E)$
3307 is a tournament in which
3310 \begin_layout Enumerate
3312 \begin_inset Formula $s$
3316 \begin_inset space ~
3320 \begin_inset Formula $t$
3324 \begin_inset space ~
3328 \begin_inset Formula $d$
3335 \begin_layout BeginFrame
3336 The Tournament Distance Problem is Hard
3339 \begin_layout Theorem
3340 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3344 \begin_inset Formula $\Class{NL}$
3350 \begin_layout Standard
3351 \begin_inset space \hfill{}
3358 \begin_layout Plain Layout
3362 hyperlink{hierarchy<6>}{
3364 beamerskipbutton{Skip Proof}}
3376 \begin_layout Corollary
3377 Shortest path in tournaments can be constructed
3378 \begin_inset Newline newline
3381 in logarithmic space, iff
3382 \begin_inset Formula $\Class{L}=\Class{NL}$
3392 \begin_layout Corollary
3393 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3399 \begin_layout BeginFrame
3401 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3407 \begin_layout Standard
3411 \begin_layout Plain Layout
3423 \begin_layout Columns
3424 \begin_inset Argument 1
3427 \begin_layout Plain Layout
3437 \begin_layout Column
3441 \begin_layout Standard
3445 \begin_layout Plain Layout
3460 \begin_inset Argument 2
3463 \begin_layout Plain Layout
3465 \begin_inset Formula $\Lang{reach}$
3469 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3481 \begin_layout Enumerate
3482 \begin_inset Argument item:2
3485 \begin_layout Plain Layout
3492 \begin_inset Formula $(G,s,t)$
3496 \begin_inset Formula $\Lang{reach}$
3502 \begin_layout Enumerate
3503 \begin_inset Argument item:2
3506 \begin_layout Plain Layout
3513 \begin_inset Formula $G$
3517 \begin_inset Formula $G'$
3523 \begin_layout Enumerate
3524 \begin_inset Argument item:2
3527 \begin_layout Plain Layout
3534 \begin_inset Newline newline
3538 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3545 \begin_layout Separator
3550 \begin_inset Argument 2
3553 \begin_layout Plain Layout
3560 \begin_inset Argument 1
3563 \begin_layout Plain Layout
3573 \begin_layout Enumerate
3574 \begin_inset Argument item:2
3577 \begin_layout Plain Layout
3584 \begin_inset space ~
3588 \begin_inset Formula $G$
3592 \begin_inset Newline newline
3596 \begin_inset space ~
3600 \begin_inset Formula $G'$
3606 \begin_layout Enumerate
3607 \begin_inset Argument item:2
3610 \begin_layout Plain Layout
3617 \begin_inset space ~
3621 \begin_inset Formula $G'$
3625 \begin_inset Newline newline
3629 \begin_inset space ~
3633 \begin_inset Formula $G'$
3640 \begin_layout Column
3644 \begin_layout Example
3648 \begin_layout Plain Layout
3652 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3655 \begin_layout Plain Layout
3659 color{beamerexample}
3662 \begin_layout Plain Layout
3666 pgfsetlinewidth{0.6pt}
3669 \begin_layout Plain Layout
3678 \begin_layout Plain Layout
3687 \begin_layout Plain Layout
3696 \begin_layout Plain Layout
3705 \begin_layout Plain Layout
3712 \begin_layout Plain Layout
3720 pgfbox[center,center]{$s$}}
3723 \begin_layout Plain Layout
3731 pgfbox[center,center]{$t$}}
3734 \begin_layout Plain Layout
3738 color{beamerexample}
3741 \begin_layout Plain Layout
3750 \begin_layout Plain Layout
3754 pgfnodesetsepstart{2pt}
3757 \begin_layout Plain Layout
3761 pgfnodesetsepend{2pt}
3764 \begin_layout Plain Layout
3770 pgfnodeconnline{B}{A}}
3773 \begin_layout Plain Layout
3779 pgfnodeconnline{B}{C}}
3782 \begin_layout Plain Layout
3788 pgfnodeconnline{C}{D}}
3791 \begin_layout Plain Layout
3797 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
3800 \begin_layout Plain Layout
3808 pgfbox[left,center]{$G
3813 \begin_layout Plain Layout
3820 \begin_layout Plain Layout
3828 pgfbox[left,center]{$G'
3833 \begin_layout Plain Layout
3842 \begin_layout Plain Layout
3851 \begin_layout Plain Layout
3860 \begin_layout Plain Layout
3869 \begin_layout Plain Layout
3878 \begin_layout Plain Layout
3887 \begin_layout Plain Layout
3896 \begin_layout Plain Layout
3905 \begin_layout Plain Layout
3914 \begin_layout Plain Layout
3923 \begin_layout Plain Layout
3932 \begin_layout Plain Layout
3941 \begin_layout Plain Layout
3950 \begin_layout Plain Layout
3959 \begin_layout Plain Layout
3968 \begin_layout Plain Layout
3977 \begin_layout Plain Layout
3984 \begin_layout Plain Layout
3992 pgfbox[center,center]{$s'$}}
3995 \begin_layout Plain Layout
4003 pgfbox[center,center]{$t'$}}
4006 \begin_layout Plain Layout
4011 \begin_layout Plain Layout
4016 \begin_layout Plain Layout
4023 \begin_layout Plain Layout
4027 pgfsetlinewidth{0.4pt}
4030 \begin_layout Plain Layout
4034 color{beamerexample!25!averagebackgroundcolor}
4037 \begin_layout Plain Layout
4041 pgfnodeconnline{A2}{C1}
4044 \begin_layout Plain Layout
4048 pgfnodeconnline{A2}{D1}
4051 \begin_layout Plain Layout
4055 pgfnodeconnline{B2}{A1}
4058 \begin_layout Plain Layout
4062 pgfnodeconnline{B2}{C1}
4065 \begin_layout Plain Layout
4069 pgfnodeconnline{B2}{D1}
4072 \begin_layout Plain Layout
4076 pgfnodeconnline{C2}{D1}
4079 \begin_layout Plain Layout
4083 pgfnodeconnline{D2}{A1}
4086 \begin_layout Plain Layout
4090 pgfnodeconnline{D2}{B1}
4093 \begin_layout Plain Layout
4097 pgfnodeconnline{A3}{C2}
4100 \begin_layout Plain Layout
4104 pgfnodeconnline{A3}{D2}
4107 \begin_layout Plain Layout
4111 pgfnodeconnline{B3}{A2}
4114 \begin_layout Plain Layout
4118 pgfnodeconnline{B3}{C2}
4121 \begin_layout Plain Layout
4125 pgfnodeconnline{B3}{D2}
4128 \begin_layout Plain Layout
4132 pgfnodeconnline{C3}{D2}
4135 \begin_layout Plain Layout
4139 pgfnodeconnline{D3}{A2}
4142 \begin_layout Plain Layout
4146 pgfnodeconnline{D3}{B2}
4149 \begin_layout Plain Layout
4153 pgfnodeconnline{A4}{C3}
4156 \begin_layout Plain Layout
4160 pgfnodeconnline{A4}{D3}
4163 \begin_layout Plain Layout
4167 pgfnodeconnline{B4}{A3}
4170 \begin_layout Plain Layout
4174 pgfnodeconnline{B4}{C3}
4177 \begin_layout Plain Layout
4181 pgfnodeconnline{B4}{D3}
4184 \begin_layout Plain Layout
4188 pgfnodeconnline{C4}{D3}
4191 \begin_layout Plain Layout
4195 pgfnodeconnline{D4}{A3}
4198 \begin_layout Plain Layout
4202 pgfnodeconnline{D4}{B3}
4205 \begin_layout Plain Layout
4214 \begin_layout Plain Layout
4218 pgfnodeconnline{A1}{B1}
4221 \begin_layout Plain Layout
4225 pgfnodeconnline{B1}{C1}
4228 \begin_layout Plain Layout
4232 pgfnodeconnline{C1}{D1}
4235 \begin_layout Plain Layout
4239 pgfnodeconnline{A2}{B2}
4242 \begin_layout Plain Layout
4246 pgfnodeconnline{B2}{C2}
4249 \begin_layout Plain Layout
4253 pgfnodeconnline{C2}{D2}
4256 \begin_layout Plain Layout
4260 pgfnodeconnline{A3}{B3}
4263 \begin_layout Plain Layout
4267 pgfnodeconnline{B3}{C3}
4270 \begin_layout Plain Layout
4274 pgfnodeconnline{C3}{D3}
4277 \begin_layout Plain Layout
4281 pgfnodeconnline{A4}{B4}
4284 \begin_layout Plain Layout
4288 pgfnodeconnline{B4}{C4}
4291 \begin_layout Plain Layout
4295 pgfnodeconnline{C4}{D4}
4298 \begin_layout Plain Layout
4305 \begin_layout Plain Layout
4309 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4312 \begin_layout Plain Layout
4316 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4319 \begin_layout Plain Layout
4323 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4326 \begin_layout Plain Layout
4330 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4333 \begin_layout Plain Layout
4337 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4340 \begin_layout Plain Layout
4344 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4347 \begin_layout Plain Layout
4351 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4354 \begin_layout Plain Layout
4358 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4361 \begin_layout Plain Layout
4365 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4368 \begin_layout Plain Layout
4372 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4375 \begin_layout Plain Layout
4379 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4382 \begin_layout Plain Layout
4386 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4389 \begin_layout Plain Layout
4393 color{beamerexample}
4396 \begin_layout Plain Layout
4400 pgfsetlinewidth{0.6pt}
4403 \begin_layout Plain Layout
4408 \begin_layout Plain Layout
4415 \begin_layout Plain Layout
4422 \begin_layout Plain Layout
4426 pgfnodeconnline{B1}{A2}
4429 \begin_layout Plain Layout
4433 pgfnodeconnline{B2}{A3}
4436 \begin_layout Plain Layout
4440 pgfnodeconnline{B3}{A4}
4443 \begin_layout Plain Layout
4448 \begin_layout Plain Layout
4455 \begin_layout Plain Layout
4462 \begin_layout Plain Layout
4466 pgfnodeconnline{B1}{C2}
4469 \begin_layout Plain Layout
4473 pgfnodeconnline{B2}{C3}
4476 \begin_layout Plain Layout
4480 pgfnodeconnline{B3}{C4}
4483 \begin_layout Plain Layout
4488 \begin_layout Plain Layout
4495 \begin_layout Plain Layout
4502 \begin_layout Plain Layout
4506 pgfnodeconnline{C1}{D2}
4509 \begin_layout Plain Layout
4515 pgfnodeconnline{C2}{D3}}
4518 \begin_layout Plain Layout
4524 pgfnodeconnline{C3}{D4}}
4527 \begin_layout Plain Layout
4532 \begin_layout Plain Layout
4539 \begin_layout Plain Layout
4546 \begin_layout Plain Layout
4552 pgfnodeconnline{A1}{C2}}
4555 \begin_layout Plain Layout
4561 pgfnodeconnline{A2}{C3}}
4564 \begin_layout Plain Layout
4568 pgfnodeconnline{A3}{C4}
4571 \begin_layout Plain Layout
4576 \begin_layout Plain Layout
4583 \begin_layout Plain Layout
4590 \begin_layout Plain Layout
4596 pgfnodeconnline{A1}{A2}}
4599 \begin_layout Plain Layout
4603 pgfnodeconnline{A2}{A3}
4606 \begin_layout Plain Layout
4610 pgfnodeconnline{A3}{A4}
4613 \begin_layout Plain Layout
4617 pgfnodeconnline{B1}{B2}
4620 \begin_layout Plain Layout
4624 pgfnodeconnline{B2}{B3}
4627 \begin_layout Plain Layout
4631 pgfnodeconnline{B3}{B4}
4634 \begin_layout Plain Layout
4638 pgfnodeconnline{C1}{C2}
4641 \begin_layout Plain Layout
4645 pgfnodeconnline{C2}{C3}
4648 \begin_layout Plain Layout
4652 pgfnodeconnline{C3}{C4}
4655 \begin_layout Plain Layout
4659 pgfnodeconnline{D1}{D2}
4662 \begin_layout Plain Layout
4666 pgfnodeconnline{D2}{D3}
4669 \begin_layout Plain Layout
4675 pgfnodeconnline{D3}{D4}}
4678 \begin_layout Plain Layout
4683 \begin_layout Plain Layout
4696 \begin_layout AgainFrame
4697 \begin_inset Argument 1
4700 \begin_layout Plain Layout
4709 \begin_layout Subsection
4710 Complexity of: Approximating the Shortest Path
4713 \begin_layout BeginFrame
4714 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
4717 \begin_layout Definition
4722 approximation scheme for
4723 \begin_inset Formula $\Lang{tournament-shortest-path}$
4734 \begin_layout Enumerate
4736 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
4742 \begin_layout Enumerate
4744 \begin_inset Formula $r>1$
4750 \begin_layout Standard
4754 \begin_layout Itemize
4756 \begin_inset Formula $s$
4760 \begin_inset space ~
4764 \begin_inset Formula $t$
4768 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
4775 \begin_layout BeginFrame
4776 There Exists a Logspace Approximation Scheme for
4777 \begin_inset Newline newline
4780 the Tournament Shortest Path Problem
4783 \begin_layout Theorem
4784 There exists an approximation scheme for
4785 \begin_inset Formula $\Lang{tournament-shortest-path}$
4789 \begin_inset Formula $1<r<2$
4793 \begin_inset Formula
4795 O\left(\log|V|\log\frac{1}{r-1}\right).
4807 \begin_layout Corollary
4808 In tournaments, paths can be constructed in logarithmic space.
4811 \begin_layout Standard
4812 \begin_inset space \hfill{}
4819 \begin_layout Plain Layout
4823 hyperlink{optimality}{
4825 beamergotobutton{More Details}}
4833 \begin_layout AgainFrame
4834 \begin_inset Argument 1
4837 \begin_layout Plain Layout
4846 \begin_layout EndFrame
4850 \begin_layout Standard
4851 \begin_inset Note Note
4854 \begin_layout Plain Layout
4855 If a frame includes a program listing, the frame needs to be marked as
4856 \begin_inset Quotes eld
4860 \begin_inset Quotes erd
4864 LyX has the FragileFrame layout for this.
4872 \begin_layout FragileFrame
4873 \begin_inset Argument 4
4876 \begin_layout Plain Layout
4877 Just a frame with a program code listing
4885 \begin_layout FragileFrame
4886 This is some program code:
4890 \begin_layout Standard
4891 \begin_inset listings
4892 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
4896 \begin_layout Plain Layout
4901 \begin_layout Plain Layout
4903 'this is a python function'
4906 \begin_layout Plain Layout
4911 \begin_layout Plain Layout
4916 \begin_layout Plain Layout
4918 'This is a German word: Tschüs'
4921 \begin_layout Plain Layout
4926 \begin_layout Plain Layout
4931 \begin_layout Plain Layout
4933 'this is a python function'
4936 \begin_layout Plain Layout
4947 \begin_layout Section*
4951 \begin_layout Subsection*
4955 \begin_layout BeginFrame
4960 \begin_inset Argument 2
4963 \begin_layout Plain Layout
4973 \begin_layout Itemize
4987 \begin_inset Formula $\Class{AC}^{0}$
4996 \begin_layout Itemize
5001 logspace approximation scheme
5013 shortest paths in tournaments.
5016 \begin_layout Itemize
5030 \begin_inset Formula $\Class{NL}$
5039 \begin_layout Separator
5044 \begin_inset Argument 2
5047 \begin_layout Plain Layout
5057 \begin_layout Itemize
5058 The same results apply to graphs with
5059 \begin_inset Newline newline
5062 bounded independence number.
5063 \begin_inset space \hfill{}
5070 \begin_layout Plain Layout
5074 hyperlink{independence}{
5076 beamergotobutton{More Details}}
5084 \begin_layout Itemize
5085 The complexity of finding paths in undirected graphs
5086 \begin_inset Newline newline
5090 \begin_inset space \hfill{}
5097 \begin_layout Plain Layout
5101 hyperlink{undirected}{
5103 beamergotobutton{More Details}}
5112 \begin_layout Subsection*
5116 \begin_layout BeginFrame
5120 \begin_layout Standard
5124 \begin_layout Plain Layout
5128 beamertemplatebookbibitems
5136 \begin_layout Bibliography
5137 \labelwidthstring References
5138 \begin_inset CommandInset bibitem
5139 LatexCommand bibitem
5145 \begin_inset space ~
5153 \begin_layout Plain Layout
5164 Topics on Tournaments.
5171 \begin_layout Plain Layout
5180 Holt, Rinehart, and Winston, 1968.
5185 \begin_layout Plain Layout
5189 beamertemplatearticlebibitems
5197 \begin_layout Bibliography
5198 \labelwidthstring References
5199 \begin_inset CommandInset bibitem
5200 LatexCommand bibitem
5201 key "NickelsenT2002"
5206 \begin_inset space ~
5209 Arfst Nickelsen and Till Tantau.
5214 \begin_layout Plain Layout
5223 On reachability in graphs with bounded independence number.
5227 \begin_layout Plain Layout
5241 , Springer-Verlag, 2002.
5244 \begin_layout Bibliography
5245 \labelwidthstring References
5246 \begin_inset CommandInset bibitem
5247 LatexCommand bibitem
5253 \begin_inset space ~
5260 \begin_layout Plain Layout
5269 A logspace approximation scheme for the shortest path problem for graphs
5270 with bounded independence number.
5274 \begin_layout Plain Layout
5288 , Springer-Verlag, 2004.
5293 \begin_layout Plain Layout
5305 \begin_layout EndFrame
5309 \begin_layout Standard
5314 \begin_layout Plain Layout
5318 AtBeginSubsection[]{}
5326 \begin_layout Section
5330 \begin_layout Subsection
5331 Graphs With Bounded Independence Number
5334 \begin_layout BeginFrame
5338 \begin_layout Plain Layout
5340 [label=independence]
5345 Definition of Independence Number of a Graph
5348 \begin_layout Definition
5358 \begin_inset Formula $\alpha(G)$
5362 \begin_inset Newline newline
5365 is the maximum number of vertices we can pick,
5366 \begin_inset Newline newline
5369 such that there is no edge between them.
5372 \begin_layout Example
5373 Tournaments have independence number 1.
5377 \begin_layout BeginFrame
5378 The Results for Tournaments also Apply to
5379 \begin_inset Newline newline
5382 Graphs With Bounded Independence Number
5385 \begin_layout Theorem
5387 \begin_inset space ~
5391 \begin_inset Formula $k$
5402 in graphs with independence number
5403 \begin_inset Newline newline
5407 \begin_inset space ~
5411 \begin_inset Formula $k$
5415 \begin_inset Formula $\Class{AC}^{0}$
5421 \begin_layout Separator
5425 \begin_layout Theorem
5427 \begin_inset space ~
5431 \begin_inset Formula $k$
5438 logspace approximation scheme
5442 for approximating the shortest path in graphs with independence number at
5444 \begin_inset space ~
5448 \begin_inset Formula $k$
5454 \begin_layout Separator
5458 \begin_layout Theorem
5460 \begin_inset space ~
5464 \begin_inset Formula $k$
5475 in graphs with independence number at most
5476 \begin_inset space ~
5480 \begin_inset Formula $k$
5488 \begin_inset Formula $\Class{NL}$
5496 \begin_layout Subsection
5497 Finding Paths in Undirected Graphs
5500 \begin_layout BeginFrame
5504 \begin_layout Plain Layout
5506 <1-2>[label=undirected]
5511 The Complexity of Finding Paths in Undirected Graphs
5512 \begin_inset Newline newline
5519 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5523 \begin_inset Formula $\Class{SL}$
5529 \begin_layout Corollary
5530 For undirected graphs, we can solve
5534 \begin_layout Itemize
5535 the reachability problem in logspace iff
5536 \begin_inset Formula $\Class L=\Class{SL}$
5542 \begin_layout Itemize
5543 the construction problem in logspace iff
5544 \begin_inset Flex Alternative
5547 \begin_layout Plain Layout
5548 \begin_inset Argument 1
5551 \begin_layout Plain Layout
5558 \begin_inset Argument 2
5561 \begin_layout Plain Layout
5568 \begin_inset Flex Alert
5571 \begin_layout Plain Layout
5572 \begin_inset Formula $\Class L=\Class{SL}$
5588 \begin_layout Itemize
5589 the optimization problem in logspace iff
5590 \begin_inset Flex Alternative
5593 \begin_layout Plain Layout
5594 \begin_inset Argument 1
5597 \begin_layout Plain Layout
5604 \begin_inset Argument 2
5607 \begin_layout Plain Layout
5614 \begin_inset Flex Alert
5617 \begin_layout Plain Layout
5618 \begin_inset Formula $\Class L=\Class{NL}$
5634 \begin_layout Itemize
5635 the approximation problem in logspace iff ?.
5640 \begin_layout Subsection
5641 The Approximation Scheme is Optimal
5644 \begin_layout BeginFrame
5648 \begin_layout Plain Layout
5655 The Approximation Scheme is Optimal
5658 \begin_layout Theorem
5659 Suppose there exists an approximation scheme for
5660 \begin_inset Formula $\Lang{tournament-shortest-path}$
5664 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
5669 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
5680 \begin_layout Enumerate
5681 Suppose the approximation scheme exists.
5682 \begin_inset Newline newline
5686 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
5693 \begin_layout Enumerate
5695 \begin_inset Formula $(T,s,t)$
5700 \begin_inset Formula $n$
5703 be the number of vertices.
5706 \begin_layout Enumerate
5707 Run the approximation scheme for
5708 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
5712 \begin_inset Newline newline
5716 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
5722 \begin_layout Enumerate
5723 The resulting path has optimal length.
5728 \begin_layout Plain Layout
5741 \begin_layout EndFrame