1 #LyX 2.3 created this file. For more info see http://www.lyx.org/
5 \save_transient_properties true
6 \origin /systemlyxdir/examples/Presentations/
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 "lmodern" "default"
161 \font_sans "lmss" "default"
162 \font_typewriter "lmtt" "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 \use_dash_ligatures false
173 \default_output_format default
175 \bibtex_command default
176 \index_command default
177 \paperfontsize default
182 \use_package amsmath 2
183 \use_package amssymb 2
184 \use_package cancel 1
186 \use_package mathdots 1
187 \use_package mathtools 1
188 \use_package mhchem 1
189 \use_package stackrel 1
190 \use_package stmaryrd 1
191 \use_package undertilde 1
193 \cite_engine_type default
197 \paperorientation portrait
208 \paragraph_separation indent
209 \paragraph_indentation default
211 \math_numbering_side default
212 \quotes_style english
216 \paperpagestyle default
217 \tracking_changes false
218 \output_changes false
221 \html_be_strict false
228 \begin_inset Newline newline
231 Finding Paths in Tournaments
238 \begin_layout Institute
239 International Computer Science Institute
240 \begin_inset Newline newline
244 \begin_inset Argument 1
247 \begin_layout Plain Layout
261 \begin_inset Argument 4
264 \begin_layout Plain Layout
274 \begin_layout Standard
275 \begin_inset CommandInset toc
276 LatexCommand tableofcontents
284 \begin_layout Plain Layout
295 \begin_layout Standard
299 \begin_layout Plain Layout
301 % Show the table of contents at the beginning
304 \begin_layout Plain Layout
306 % of every subsection.
309 \begin_layout Plain Layout
313 AtBeginSubsection[]{%
316 \begin_layout Plain Layout
323 \begin_layout Plain Layout
330 \begin_layout Plain Layout
334 tableofcontents[current,currentsubsection]
337 \begin_layout Plain Layout
342 \begin_layout Plain Layout
352 \begin_layout Section
356 \begin_layout Subsection
357 What are Tournaments?
361 \begin_inset Argument 4
364 \begin_layout Plain Layout
365 Tournaments Consist of Jousts Between Knights
374 \begin_layout Columns
383 \begin_layout Standard
387 \begin_layout Plain Layout
391 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
394 \begin_layout Plain Layout
398 pgfnodebox{A}[virtual]{
403 \begin_layout Plain Layout
407 pgfuseimage{knight1}}{2pt}{2pt}
410 \begin_layout Plain Layout
414 pgfnodebox{B}[virtual]{
419 \begin_layout Plain Layout
423 pgfuseimage{knight2}}{2pt}{2pt}
426 \begin_layout Plain Layout
430 pgfnodebox{C}[virtual]{
435 \begin_layout Plain Layout
439 pgfuseimage{knight3}}{2pt}{2pt}
442 \begin_layout Plain Layout
446 pgfnodebox{D}[virtual]{
451 \begin_layout Plain Layout
455 pgfuseimage{knight4}}{2pt}{2pt}
458 \begin_layout Plain Layout
465 \begin_layout Plain Layout
476 \begin_layout Plain Layout
483 \begin_layout Plain Layout
487 pgfsetlinewidth{0.6pt}
490 \begin_layout Plain Layout
494 pgfnodeconnline{A}{B}
497 \begin_layout Plain Layout
501 pgfnodeconnline{A}{C}
504 \begin_layout Plain Layout
508 pgfnodeconnline{D}{A}
511 \begin_layout Plain Layout
515 pgfnodeconnline{C}{B}
518 \begin_layout Plain Layout
522 pgfnodeconnline{B}{D}
525 \begin_layout Plain Layout
529 pgfnodeconnline{C}{D}
532 \begin_layout Plain Layout
537 \begin_layout Plain Layout
554 \begin_inset Argument 2
557 \begin_layout Plain Layout
558 What is a Tournament?
567 \begin_layout Itemize
568 \begin_inset Argument item:2
571 \begin_layout Plain Layout
581 \begin_layout Itemize
582 \begin_inset Argument item:2
585 \begin_layout Plain Layout
592 Every pair has a joust.
595 \begin_layout Itemize
596 \begin_inset Argument item:2
599 \begin_layout Plain Layout
606 In every joust one knight wins.
612 \begin_layout Standard
613 \begin_inset Separator plain
620 \begin_inset Argument 4
623 \begin_layout Plain Layout
624 Tournaments are Complete Directed Graphs
633 \begin_layout Columns
642 \begin_layout Standard
646 \begin_layout Plain Layout
650 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
653 \begin_layout Plain Layout
660 \begin_layout Plain Layout
664 pgfsetlinewidth{0.6pt}
667 \begin_layout Plain Layout
676 \begin_layout Plain Layout
685 \begin_layout Plain Layout
694 \begin_layout Plain Layout
703 \begin_layout Plain Layout
710 \begin_layout Plain Layout
718 pgfbox[center,center]{$v_2$}}
721 \begin_layout Plain Layout
729 pgfbox[center,center]{$v_3$}}
732 \begin_layout Plain Layout
740 pgfbox[center,center]{$v_4$}}
743 \begin_layout Plain Layout
751 pgfbox[center,center]{$v_1$}}
754 \begin_layout Plain Layout
761 \begin_layout Plain Layout
770 \begin_layout Plain Layout
774 pgfnodesetsepstart{2pt}
777 \begin_layout Plain Layout
781 pgfnodesetsepend{4pt}
784 \begin_layout Plain Layout
788 pgfnodeconnline{A}{B}
791 \begin_layout Plain Layout
795 pgfnodeconnline{A}{C}
798 \begin_layout Plain Layout
802 pgfnodeconnline{D}{A}
805 \begin_layout Plain Layout
809 pgfnodeconnline{C}{B}
812 \begin_layout Plain Layout
816 pgfnodeconnline{B}{D}
819 \begin_layout Plain Layout
823 pgfnodeconnline{D}{C}
826 \begin_layout Plain Layout
842 \begin_layout Definition
843 \begin_inset Argument 1
846 \begin_layout Plain Layout
865 \begin_layout Enumerate
869 \begin_layout Enumerate
870 with exactly one edge between
871 \begin_inset Newline newline
874 any two different vertices.
880 \begin_layout Standard
881 \begin_inset Separator plain
888 \begin_inset Argument 2
891 \begin_layout Plain Layout
899 \begin_inset Argument 4
902 \begin_layout Plain Layout
903 Tournaments Arise Naturally in Different Situations
912 \begin_layout ExampleBlock
913 \begin_inset Argument 2
916 \begin_layout Plain Layout
917 Applications in Ordering Theory
926 \begin_layout Standard
927 Elements in a set need to be sorted.
929 \begin_inset Newline newline
932 The comparison relation may be cyclic, however.
936 \begin_layout Standard
937 \begin_inset Separator plain
943 \begin_layout ExampleBlock
944 \begin_inset Argument 2
947 \begin_layout Plain Layout
948 Applications in Sociology
957 \begin_layout Standard
958 Several candidates apply for a position.
959 \begin_inset Newline newline
962 Reviewers decide for any two candidates whom they prefer.
967 \begin_layout Standard
968 \begin_inset Separator plain
974 \begin_layout ExampleBlock
975 \begin_inset Argument 2
978 \begin_layout Plain Layout
979 Applications in Structural Complexity Theory
988 \begin_layout Standard
990 \begin_inset Formula $L$
993 is given and a selector function
994 \begin_inset Formula $f$
998 \begin_inset Newline newline
1001 It chooses from any two words the one more likely to be in
1002 \begin_inset Formula $f$
1010 \begin_layout Subsection
1011 What Does ``Finding Paths'' Mean?
1015 \begin_inset Argument 4
1018 \begin_layout Plain Layout
1019 ``Finding Paths'' is Ambiguous
1029 \begin_inset Argument 2
1032 \begin_layout Plain Layout
1034 \begin_inset Flex Only
1037 \begin_layout Plain Layout
1038 \begin_inset Argument 1
1041 \begin_layout Plain Layout
1048 Path Finding Problems
1054 \begin_inset Flex Only
1057 \begin_layout Plain Layout
1058 \begin_inset Argument 1
1061 \begin_layout Plain Layout
1069 \begin_inset Formula $\Lang{reach}$
1078 \begin_inset Flex Only
1081 \begin_layout Plain Layout
1082 \begin_inset Argument 1
1085 \begin_layout Plain Layout
1092 the Construction Problem
1098 \begin_inset Flex Only
1101 \begin_layout Plain Layout
1102 \begin_inset Argument 1
1105 \begin_layout Plain Layout
1112 the Optimization Problem
1118 \begin_inset Flex Only
1121 \begin_layout Plain Layout
1122 \begin_inset Argument 1
1125 \begin_layout Plain Layout
1133 \begin_inset Formula $\Lang{distance}$
1142 \begin_inset Flex Only
1145 \begin_layout Plain Layout
1146 \begin_inset Argument 1
1149 \begin_layout Plain Layout
1156 the Approximation Problem
1170 \begin_layout Itemize
1180 \begin_inset Formula $G=(V,E)$
1192 \begin_inset Formula $s\in V$
1204 \begin_inset Formula $t\in V$
1210 \begin_layout Itemize
1211 \begin_inset Argument item:2
1214 \begin_layout Plain Layout
1228 \begin_inset space ~
1232 \begin_inset Formula $d$
1239 \begin_layout Plain Layout
1251 \begin_layout Itemize
1252 \begin_inset Argument item:2
1255 \begin_layout Plain Layout
1271 \begin_inset Formula $r>1$
1278 \begin_layout Standard
1282 \begin_layout Plain Layout
1294 \begin_layout Overprint
1295 \begin_inset Argument item:1
1298 \begin_layout Plain Layout
1309 \begin_layout Columns
1310 \begin_inset Argument 1
1313 \begin_layout Plain Layout
1323 \begin_layout Standard
1324 \begin_inset Flex Alternative
1327 \begin_layout Plain Layout
1328 \begin_inset Argument 1
1331 \begin_layout Plain Layout
1339 \begin_inset Argument 2
1342 \begin_layout Plain Layout
1346 \begin_layout Plain Layout
1366 \begin_layout Plain Layout
1383 \begin_layout ExampleBlock
1384 \begin_inset Argument 2
1387 \begin_layout Plain Layout
1397 \begin_layout Standard
1401 \begin_layout Plain Layout
1405 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1408 \begin_layout Plain Layout
1412 \begin_layout Plain Layout
1416 color{beamerexample}
1419 \begin_layout Plain Layout
1423 \begin_layout Plain Layout
1427 pgfsetlinewidth{0.6pt}
1430 \begin_layout Plain Layout
1434 \begin_layout Plain Layout
1443 \begin_layout Plain Layout
1447 \begin_layout Plain Layout
1456 \begin_layout Plain Layout
1460 \begin_layout Plain Layout
1469 \begin_layout Plain Layout
1473 \begin_layout Plain Layout
1482 \begin_layout Plain Layout
1486 \begin_layout Plain Layout
1490 \begin_layout Plain Layout
1494 \begin_layout Plain Layout
1501 \begin_layout Plain Layout
1505 \begin_layout Plain Layout
1513 pgfbox[center,center]{$t$}}
1516 \begin_layout Plain Layout
1520 \begin_layout Plain Layout
1528 pgfbox[center,center]{$s$}}
1531 \begin_layout Plain Layout
1535 \begin_layout Plain Layout
1539 \begin_layout Plain Layout
1543 \begin_layout Plain Layout
1547 color{beamerexample}
1550 \begin_layout Plain Layout
1554 \begin_layout Plain Layout
1563 \begin_layout Plain Layout
1567 \begin_layout Plain Layout
1571 pgfnodesetsepstart{2pt}
1574 \begin_layout Plain Layout
1578 \begin_layout Plain Layout
1582 pgfnodesetsepend{4pt}
1585 \begin_layout Plain Layout
1589 \begin_layout Plain Layout
1593 pgfnodeconnline{A}{B}
1596 \begin_layout Plain Layout
1600 \begin_layout Plain Layout
1604 pgfnodeconnline{A}{C}
1607 \begin_layout Plain Layout
1611 \begin_layout Plain Layout
1615 pgfnodeconnline{D}{A}
1618 \begin_layout Plain Layout
1622 \begin_layout Plain Layout
1626 pgfnodeconnline{C}{B}
1629 \begin_layout Plain Layout
1633 \begin_layout Plain Layout
1637 pgfnodeconnline{B}{D}
1640 \begin_layout Plain Layout
1644 \begin_layout Plain Layout
1648 pgfnodeconnline{D}{C}
1651 \begin_layout Plain Layout
1655 \begin_layout Plain Layout
1659 \begin_layout Plain Layout
1663 \begin_layout Plain Layout
1673 pgfbox[left,center]{, $d=2$}}}
1676 \begin_layout Plain Layout
1680 \begin_layout Plain Layout
1690 pgfbox[left,center]{, $r=1.5$}}}
1693 \begin_layout Plain Layout
1697 \begin_layout Plain Layout
1707 pgfbox[left,center]{, $r=1.25$}}}
1710 \begin_layout Plain Layout
1714 \begin_layout Plain Layout
1727 \begin_layout Standard
1728 \begin_inset Flex Only
1731 \begin_layout Plain Layout
1732 \begin_inset Argument 1
1735 \begin_layout Plain Layout
1746 \begin_layout Plain Layout
1763 \begin_layout ExampleBlock
1764 \begin_inset Argument 1
1767 \begin_layout Plain Layout
1775 \begin_inset Argument 2
1778 \begin_layout Plain Layout
1788 \begin_layout Standard
1792 \begin_layout Plain Layout
1796 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1799 \begin_layout Plain Layout
1806 \begin_layout Plain Layout
1810 color{beamerexample}
1813 \begin_layout Plain Layout
1817 pgfsetlinewidth{0.6pt}
1820 \begin_layout Plain Layout
1829 \begin_layout Plain Layout
1838 \begin_layout Plain Layout
1847 \begin_layout Plain Layout
1856 \begin_layout Plain Layout
1863 \begin_layout Plain Layout
1871 pgfbox[center,center]{$t$}}
1874 \begin_layout Plain Layout
1882 pgfbox[center,center]{$s$}}
1885 \begin_layout Plain Layout
1889 color{beamerexample}
1892 \begin_layout Plain Layout
1901 \begin_layout Plain Layout
1905 pgfnodesetsepstart{2pt}
1908 \begin_layout Plain Layout
1912 pgfnodesetsepend{4pt}
1915 \begin_layout Plain Layout
1921 pgfnodeconnline{A}{B}}
1924 \begin_layout Plain Layout
1930 pgfnodeconnline{A}{C}}
1933 \begin_layout Plain Layout
1939 pgfnodeconnline{D}{A}}
1942 \begin_layout Plain Layout
1948 pgfnodeconnline{C}{B}}
1951 \begin_layout Plain Layout
1955 pgfnodeconnline{B}{D}
1958 \begin_layout Plain Layout
1962 pgfnodeconnline{D}{C}
1965 \begin_layout Plain Layout
1970 \begin_layout Plain Layout
1980 pgfbox[left,center]{
1985 \begin_layout Plain Layout
2000 \begin_layout Overprint
2001 \begin_inset Argument item:1
2004 \begin_layout Plain Layout
2016 \begin_inset Argument 2
2019 \begin_layout Plain Layout
2020 Variants of Path Finding Problems
2029 \begin_layout Description
2030 \begin_inset Argument item:1
2033 \begin_layout Plain Layout
2041 \begin_inset space ~
2044 Problem: Is there a path from
2045 \begin_inset Formula $s$
2049 \begin_inset space ~
2053 \begin_inset Formula $t$
2057 \begin_inset Argument 2
2060 \begin_layout Plain Layout
2061 Approximation Problem:
2069 \begin_layout Description
2070 \begin_inset Argument item:1
2073 \begin_layout Plain Layout
2081 \begin_inset space ~
2084 Problem: Construct a path from
2085 \begin_inset Formula $s$
2089 \begin_inset space ~
2093 \begin_inset Formula $t$
2099 \begin_layout Description
2100 \begin_inset Argument item:1
2103 \begin_layout Plain Layout
2111 \begin_inset space ~
2114 Problem: Construct a shortest path from
2115 \begin_inset Formula $s$
2119 \begin_inset space ~
2123 \begin_inset Formula $t$
2129 \begin_layout Description
2130 \begin_inset Argument item:1
2133 \begin_layout Plain Layout
2141 \begin_inset space ~
2144 Problem: Is the distance of
2145 \begin_inset Formula $s$
2149 \begin_inset space ~
2153 \begin_inset Formula $t$
2157 \begin_inset space ~
2161 \begin_inset Formula $d$
2167 \begin_layout Description
2168 \begin_inset Argument item:1
2171 \begin_layout Plain Layout
2179 \begin_inset space ~
2182 Problem: Construct a path from
2183 \begin_inset Formula $s$
2187 \begin_inset space ~
2191 \begin_inset Formula $t$
2195 \begin_inset Newline newline
2198 approximately their distance.
2204 \begin_layout Section
2208 \begin_layout Subsection
2209 Standard Complexity Classes
2212 \begin_layout Standard
2216 \begin_layout Plain Layout
2220 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2222 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2232 \begin_inset Argument 4
2235 \begin_layout Plain Layout
2236 The Classes L and NL are Defined via
2237 \begin_inset Newline newline
2240 Logspace Turing Machines
2249 \begin_layout Standard
2253 \begin_layout Plain Layout
2257 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2260 \begin_layout Plain Layout
2269 \begin_layout Plain Layout
2273 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2276 \begin_layout Plain Layout
2283 \begin_layout Plain Layout
2292 \begin_layout Plain Layout
2296 tape{}{output tape (write only)}{10690836937182}}
2299 \begin_layout Plain Layout
2304 \begin_layout Plain Layout
2311 \begin_layout Plain Layout
2320 \begin_layout Plain Layout
2324 shorttape{work tape (read/write), $O(
2326 log n)$ symbols}{}{42}}
2329 \begin_layout Plain Layout
2338 \begin_layout Plain Layout
2342 pgfbox[center,center]{
2344 pgfuseimage{computer}}}
2347 \begin_layout Plain Layout
2352 \begin_layout Plain Layout
2356 pgfsetlinewidth{0.6pt}
2359 \begin_layout Plain Layout
2366 \begin_layout Plain Layout
2375 \begin_layout Plain Layout
2379 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2382 \begin_layout Plain Layout
2388 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2391 \begin_layout Plain Layout
2397 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2400 \begin_layout Plain Layout
2413 \begin_layout Standard
2414 \begin_inset Separator plain
2421 \begin_inset Argument 4
2424 \begin_layout Plain Layout
2425 Logspace Turing Machines Are Quite Powerful
2435 \begin_inset Argument 2
2438 \begin_layout Plain Layout
2439 Deterministic logspace machines can compute
2448 \begin_layout Itemize
2449 addition, multiplication, and even division
2452 \begin_layout Itemize
2453 reductions used in completeness proofs,
2456 \begin_layout Itemize
2457 reachability in forests.
2466 \begin_inset Argument 2
2469 \begin_layout Plain Layout
2470 Non-deterministic logspace machines can compute
2479 \begin_layout Itemize
2480 reachability in graphs,
2483 \begin_layout Itemize
2484 non-reachability in graphs,
2487 \begin_layout Itemize
2488 satisfiability with two literals per clause.
2493 \begin_layout Standard
2494 \begin_inset Separator plain
2501 \begin_inset Argument 1
2504 \begin_layout Plain Layout
2512 \begin_inset Argument 3
2515 \begin_layout Plain Layout
2522 \begin_inset Argument 4
2525 \begin_layout Plain Layout
2526 The Complexity Class Hierarchy
2535 \begin_layout Standard
2539 \begin_layout Plain Layout
2543 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2546 \begin_layout Plain Layout
2550 pgfsetlinewidth{0.8pt}
2553 \begin_layout Plain Layout
2562 \begin_layout Plain Layout
2566 pgfsetdash{{2pt}}{0pt}
2569 \begin_layout Plain Layout
2577 Class{NC}^2$}{black!50!structure}{2}}
2580 \begin_layout Plain Layout
2586 Class{NL}$}{black!50!structure}{3}
2589 \begin_layout Plain Layout
2595 Class{L}$}{black!50!structure}{4}
2598 \begin_layout Plain Layout
2609 \begin_layout Plain Layout
2615 Class{NC}^1}$}{black!50!structure}{5}
2618 \begin_layout Plain Layout
2623 \begin_layout Plain Layout
2630 \begin_layout Plain Layout
2641 \begin_layout Plain Layout
2647 Class{AC}^0}$}{black}{6}
2650 \begin_layout Plain Layout
2655 \begin_layout Plain Layout
2659 pgfsetlinewidth{1.0pt}
2662 \begin_layout Plain Layout
2669 \begin_layout Plain Layout
2673 pgfxyline(-5,0)(5,0)
2676 \begin_layout Plain Layout
2687 \begin_layout Plain Layout
2697 operatorname{forest}}$}}
2700 \begin_layout Plain Layout
2711 \begin_layout Plain Layout
2730 \begin_layout Plain Layout
2749 \begin_layout Plain Layout
2762 \begin_layout Plain Layout
2770 operatorname{forest}}$,}
2775 \begin_layout Plain Layout
2783 operatorname{forest}}$,}
2788 \begin_layout Plain Layout
2796 operatorname{path}}$,}
2801 \begin_layout Plain Layout
2809 operatorname{path}}$}}}
2812 \begin_layout Plain Layout
2817 \begin_layout Plain Layout
2827 operatorname{tourn}}$}}
2830 \begin_layout Plain Layout
2843 \begin_layout Plain Layout
2851 operatorname{tourn}}$,}
2856 \begin_layout Plain Layout
2867 \begin_layout Plain Layout
2876 \begin_layout Plain Layout
2881 \begin_layout Plain Layout
2887 pgfsetdash{{1pt}}{0pt}%
2890 \begin_layout Plain Layout
2898 operatorname{tourn}}$''}
2901 \begin_layout Plain Layout
2906 \begin_layout Plain Layout
2919 \begin_layout Standard
2920 \begin_inset Separator plain
2927 \begin_inset Argument 4
2930 \begin_layout Plain Layout
2931 The Circuit Complexity Classes AC
2932 \begin_inset Formula $^{0}$
2936 \begin_inset Formula $^{1}$
2940 \begin_inset Formula $^{2}$
2944 \begin_inset Newline newline
2947 Limit the Circuit Depth
2956 \begin_layout Standard
2960 \begin_layout Plain Layout
2969 \begin_layout Plain Layout
2981 \begin_layout Columns
2982 \begin_inset Argument 1
2985 \begin_layout Plain Layout
2995 \begin_layout Column
3000 \begin_inset Argument 2
3003 \begin_layout Plain Layout
3005 \begin_inset Formula $\Class{AC}^{0}$
3017 \begin_layout Itemize
3018 \begin_inset Formula $O(1)$
3024 \begin_layout Itemize
3029 \begin_layout Examples
3034 \begin_layout Itemize
3035 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3041 \begin_layout Itemize
3042 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3053 \begin_layout Column
3058 \begin_inset Argument 2
3061 \begin_layout Plain Layout
3063 \begin_inset Formula $\Class{NC}^{1}$
3075 \begin_layout Itemize
3076 \begin_inset Formula $O(\log n)$
3082 \begin_layout Itemize
3087 \begin_layout Examples
3092 \begin_layout Itemize
3093 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3099 \begin_layout Itemize
3100 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3106 \begin_layout Itemize
3107 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3118 \begin_layout Column
3123 \begin_inset Argument 2
3126 \begin_layout Plain Layout
3128 \begin_inset Formula $\Class{NC}^{2}$
3140 \begin_layout Itemize
3141 \begin_inset Formula $O(\log^{2}n)$
3147 \begin_layout Itemize
3152 \begin_layout Examples
3157 \begin_layout Itemize
3158 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3167 \begin_layout AgainFrame
3168 \begin_inset Argument 1
3171 \begin_layout Plain Layout
3181 \begin_layout Subsection
3182 Standard Complexity Results on Finding Paths
3186 \begin_inset Argument 4
3189 \begin_layout Plain Layout
3190 All Variants of Finding Paths in Directed Graphs
3191 \begin_inset Newline newline
3194 Are Equally Difficult
3204 \begin_inset Formula $\Lang{reach}$
3208 \begin_inset Formula $\Lang{distance}$
3212 \begin_inset Formula $\Class{NL}$
3223 \begin_layout Corollary
3224 For directed graphs, we can solve
3228 \begin_layout Itemize
3229 the reachability problem in logspace iff
3230 \begin_inset Formula $\Class{L}=\Class{NL}$
3236 \begin_layout Itemize
3237 the construction problem in logspace iff
3238 \begin_inset Formula $\Class{L}=\Class{NL}$
3244 \begin_layout Itemize
3245 the optimization problem in logspace iff
3246 \begin_inset Formula $\Class{L}=\Class{NL}$
3252 \begin_layout Itemize
3253 the approximation problem in logspace iff
3254 \begin_inset Formula $\Class{L}=\Class{NL}$
3262 \begin_layout AgainFrame
3263 \begin_inset Argument 1
3266 \begin_layout Plain Layout
3277 \begin_inset Argument 4
3280 \begin_layout Plain Layout
3281 Finding Paths in Forests and Directed Paths is Easy,
3282 \begin_inset Newline newline
3295 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3299 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3303 \begin_inset Formula $\Class{L}$
3309 \begin_layout Standard
3310 \begin_inset Separator plain
3317 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3321 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3325 \begin_inset Formula $\Class{L}$
3332 \begin_layout AgainFrame
3333 \begin_inset Argument 1
3336 \begin_layout Plain Layout
3346 \begin_layout Section
3347 Finding Paths in Tournaments
3350 \begin_layout Subsection
3351 Complexity of: Does a Path Exist?
3355 \begin_inset Argument 4
3358 \begin_layout Plain Layout
3359 Definition of the Tournament Reachability Problem
3368 \begin_layout Definition
3374 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3382 \begin_inset Formula $(T,s,t)$
3389 \begin_layout Enumerate
3390 \begin_inset Formula $T=(V,E)$
3396 \begin_layout Enumerate
3397 there exists a path from
3398 \begin_inset space ~
3402 \begin_inset Formula $s$
3406 \begin_inset space ~
3410 \begin_inset Formula $t$
3418 \begin_layout Standard
3419 \begin_inset Separator plain
3426 \begin_inset Argument 4
3429 \begin_layout Plain Layout
3430 The Tournament Reachability Problem is Very Easy
3439 \begin_layout Theorem
3440 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3450 \begin_layout AlertBlock
3451 \begin_inset Argument 2
3454 \begin_layout Plain Layout
3464 \begin_layout Itemize
3466 \begin_inset Quotes eld
3470 \begin_inset Quotes erd
3474 \begin_inset Formula $\Lang{reach}$
3478 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3484 \begin_layout Itemize
3485 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3493 \begin_layout AgainFrame
3494 \begin_inset Argument 1
3497 \begin_layout Plain Layout
3507 \begin_layout Subsection
3508 Complexity of: Construct a Shortest Path
3512 \begin_inset Argument 4
3515 \begin_layout Plain Layout
3516 Finding a Shortest Path Is as Difficult as
3517 \begin_inset Newline newline
3520 the Distance Problem
3529 \begin_layout Definition
3535 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3543 \begin_inset Formula $(T,s,t,d)$
3550 \begin_layout Enumerate
3551 \begin_inset Formula $T=(V,E)$
3554 is a tournament in which
3557 \begin_layout Enumerate
3559 \begin_inset Formula $s$
3563 \begin_inset space ~
3567 \begin_inset Formula $t$
3571 \begin_inset space ~
3575 \begin_inset Formula $d$
3583 \begin_layout Standard
3584 \begin_inset Separator plain
3591 \begin_inset Argument 4
3594 \begin_layout Plain Layout
3595 The Tournament Distance Problem is Hard
3604 \begin_layout Theorem
3605 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3609 \begin_inset Formula $\Class{NL}$
3615 \begin_layout Standard
3616 \begin_inset space \hfill{}
3623 \begin_layout Plain Layout
3627 hyperlink{hierarchy<6>}{
3629 beamerskipbutton{Skip Proof}}
3641 \begin_layout Corollary
3642 Shortest path in tournaments can be constructed
3643 \begin_inset Newline newline
3646 in logarithmic space, iff
3647 \begin_inset Formula $\Class{L}=\Class{NL}$
3657 \begin_layout Corollary
3658 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3665 \begin_layout Standard
3666 \begin_inset Separator plain
3673 \begin_inset Argument 4
3676 \begin_layout Plain Layout
3678 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3690 \begin_layout Standard
3694 \begin_layout Plain Layout
3706 \begin_layout Columns
3707 \begin_inset Argument 1
3710 \begin_layout Plain Layout
3720 \begin_layout Column
3724 \begin_layout Standard
3728 \begin_layout Plain Layout
3743 \begin_inset Argument 2
3746 \begin_layout Plain Layout
3748 \begin_inset Formula $\Lang{reach}$
3752 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3764 \begin_layout Enumerate
3765 \begin_inset Argument item:2
3768 \begin_layout Plain Layout
3776 \begin_inset Formula $(G,s,t)$
3780 \begin_inset Formula $\Lang{reach}$
3786 \begin_layout Enumerate
3787 \begin_inset Argument item:2
3790 \begin_layout Plain Layout
3798 \begin_inset Formula $G$
3802 \begin_inset Formula $G'$
3808 \begin_layout Enumerate
3809 \begin_inset Argument item:2
3812 \begin_layout Plain Layout
3820 \begin_inset Newline newline
3824 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3831 \begin_layout Standard
3832 \begin_inset Separator plain
3839 \begin_inset Argument 2
3842 \begin_layout Plain Layout
3849 \begin_inset Argument 1
3852 \begin_layout Plain Layout
3863 \begin_layout Enumerate
3864 \begin_inset Argument item:2
3867 \begin_layout Plain Layout
3875 \begin_inset space ~
3879 \begin_inset Formula $G$
3883 \begin_inset Newline newline
3887 \begin_inset space ~
3891 \begin_inset Formula $G'$
3897 \begin_layout Enumerate
3898 \begin_inset Argument item:2
3901 \begin_layout Plain Layout
3909 \begin_inset space ~
3913 \begin_inset Formula $G'$
3917 \begin_inset Newline newline
3921 \begin_inset space ~
3925 \begin_inset Formula $G'$
3932 \begin_layout Column
3936 \begin_layout Example
3940 \begin_layout Plain Layout
3944 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3947 \begin_layout Plain Layout
3951 color{beamerexample}
3954 \begin_layout Plain Layout
3958 pgfsetlinewidth{0.6pt}
3961 \begin_layout Plain Layout
3970 \begin_layout Plain Layout
3979 \begin_layout Plain Layout
3988 \begin_layout Plain Layout
3997 \begin_layout Plain Layout
4004 \begin_layout Plain Layout
4012 pgfbox[center,center]{$s$}}
4015 \begin_layout Plain Layout
4023 pgfbox[center,center]{$t$}}
4026 \begin_layout Plain Layout
4030 color{beamerexample}
4033 \begin_layout Plain Layout
4042 \begin_layout Plain Layout
4046 pgfnodesetsepstart{2pt}
4049 \begin_layout Plain Layout
4053 pgfnodesetsepend{2pt}
4056 \begin_layout Plain Layout
4062 pgfnodeconnline{B}{A}}
4065 \begin_layout Plain Layout
4071 pgfnodeconnline{B}{C}}
4074 \begin_layout Plain Layout
4080 pgfnodeconnline{C}{D}}
4083 \begin_layout Plain Layout
4089 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4092 \begin_layout Plain Layout
4100 pgfbox[left,center]{$G
4105 \begin_layout Plain Layout
4112 \begin_layout Plain Layout
4120 pgfbox[left,center]{$G'
4125 \begin_layout Plain Layout
4134 \begin_layout Plain Layout
4143 \begin_layout Plain Layout
4152 \begin_layout Plain Layout
4161 \begin_layout Plain Layout
4170 \begin_layout Plain Layout
4179 \begin_layout Plain Layout
4188 \begin_layout Plain Layout
4197 \begin_layout Plain Layout
4206 \begin_layout Plain Layout
4215 \begin_layout Plain Layout
4224 \begin_layout Plain Layout
4233 \begin_layout Plain Layout
4242 \begin_layout Plain Layout
4251 \begin_layout Plain Layout
4260 \begin_layout Plain Layout
4269 \begin_layout Plain Layout
4276 \begin_layout Plain Layout
4284 pgfbox[center,center]{$s'$}}
4287 \begin_layout Plain Layout
4295 pgfbox[center,center]{$t'$}}
4298 \begin_layout Plain Layout
4303 \begin_layout Plain Layout
4308 \begin_layout Plain Layout
4315 \begin_layout Plain Layout
4319 pgfsetlinewidth{0.4pt}
4322 \begin_layout Plain Layout
4326 color{beamerexample!25!averagebackgroundcolor}
4329 \begin_layout Plain Layout
4333 pgfnodeconnline{A2}{C1}
4336 \begin_layout Plain Layout
4340 pgfnodeconnline{A2}{D1}
4343 \begin_layout Plain Layout
4347 pgfnodeconnline{B2}{A1}
4350 \begin_layout Plain Layout
4354 pgfnodeconnline{B2}{C1}
4357 \begin_layout Plain Layout
4361 pgfnodeconnline{B2}{D1}
4364 \begin_layout Plain Layout
4368 pgfnodeconnline{C2}{D1}
4371 \begin_layout Plain Layout
4375 pgfnodeconnline{D2}{A1}
4378 \begin_layout Plain Layout
4382 pgfnodeconnline{D2}{B1}
4385 \begin_layout Plain Layout
4389 pgfnodeconnline{A3}{C2}
4392 \begin_layout Plain Layout
4396 pgfnodeconnline{A3}{D2}
4399 \begin_layout Plain Layout
4403 pgfnodeconnline{B3}{A2}
4406 \begin_layout Plain Layout
4410 pgfnodeconnline{B3}{C2}
4413 \begin_layout Plain Layout
4417 pgfnodeconnline{B3}{D2}
4420 \begin_layout Plain Layout
4424 pgfnodeconnline{C3}{D2}
4427 \begin_layout Plain Layout
4431 pgfnodeconnline{D3}{A2}
4434 \begin_layout Plain Layout
4438 pgfnodeconnline{D3}{B2}
4441 \begin_layout Plain Layout
4445 pgfnodeconnline{A4}{C3}
4448 \begin_layout Plain Layout
4452 pgfnodeconnline{A4}{D3}
4455 \begin_layout Plain Layout
4459 pgfnodeconnline{B4}{A3}
4462 \begin_layout Plain Layout
4466 pgfnodeconnline{B4}{C3}
4469 \begin_layout Plain Layout
4473 pgfnodeconnline{B4}{D3}
4476 \begin_layout Plain Layout
4480 pgfnodeconnline{C4}{D3}
4483 \begin_layout Plain Layout
4487 pgfnodeconnline{D4}{A3}
4490 \begin_layout Plain Layout
4494 pgfnodeconnline{D4}{B3}
4497 \begin_layout Plain Layout
4506 \begin_layout Plain Layout
4510 pgfnodeconnline{A1}{B1}
4513 \begin_layout Plain Layout
4517 pgfnodeconnline{B1}{C1}
4520 \begin_layout Plain Layout
4524 pgfnodeconnline{C1}{D1}
4527 \begin_layout Plain Layout
4531 pgfnodeconnline{A2}{B2}
4534 \begin_layout Plain Layout
4538 pgfnodeconnline{B2}{C2}
4541 \begin_layout Plain Layout
4545 pgfnodeconnline{C2}{D2}
4548 \begin_layout Plain Layout
4552 pgfnodeconnline{A3}{B3}
4555 \begin_layout Plain Layout
4559 pgfnodeconnline{B3}{C3}
4562 \begin_layout Plain Layout
4566 pgfnodeconnline{C3}{D3}
4569 \begin_layout Plain Layout
4573 pgfnodeconnline{A4}{B4}
4576 \begin_layout Plain Layout
4580 pgfnodeconnline{B4}{C4}
4583 \begin_layout Plain Layout
4587 pgfnodeconnline{C4}{D4}
4590 \begin_layout Plain Layout
4597 \begin_layout Plain Layout
4601 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4604 \begin_layout Plain Layout
4608 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4611 \begin_layout Plain Layout
4615 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4618 \begin_layout Plain Layout
4622 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4625 \begin_layout Plain Layout
4629 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4632 \begin_layout Plain Layout
4636 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4639 \begin_layout Plain Layout
4643 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4646 \begin_layout Plain Layout
4650 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4653 \begin_layout Plain Layout
4657 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4660 \begin_layout Plain Layout
4664 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4667 \begin_layout Plain Layout
4671 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4674 \begin_layout Plain Layout
4678 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4681 \begin_layout Plain Layout
4685 color{beamerexample}
4688 \begin_layout Plain Layout
4692 pgfsetlinewidth{0.6pt}
4695 \begin_layout Plain Layout
4700 \begin_layout Plain Layout
4707 \begin_layout Plain Layout
4714 \begin_layout Plain Layout
4718 pgfnodeconnline{B1}{A2}
4721 \begin_layout Plain Layout
4725 pgfnodeconnline{B2}{A3}
4728 \begin_layout Plain Layout
4732 pgfnodeconnline{B3}{A4}
4735 \begin_layout Plain Layout
4740 \begin_layout Plain Layout
4747 \begin_layout Plain Layout
4754 \begin_layout Plain Layout
4758 pgfnodeconnline{B1}{C2}
4761 \begin_layout Plain Layout
4765 pgfnodeconnline{B2}{C3}
4768 \begin_layout Plain Layout
4772 pgfnodeconnline{B3}{C4}
4775 \begin_layout Plain Layout
4780 \begin_layout Plain Layout
4787 \begin_layout Plain Layout
4794 \begin_layout Plain Layout
4798 pgfnodeconnline{C1}{D2}
4801 \begin_layout Plain Layout
4807 pgfnodeconnline{C2}{D3}}
4810 \begin_layout Plain Layout
4816 pgfnodeconnline{C3}{D4}}
4819 \begin_layout Plain Layout
4824 \begin_layout Plain Layout
4831 \begin_layout Plain Layout
4838 \begin_layout Plain Layout
4844 pgfnodeconnline{A1}{C2}}
4847 \begin_layout Plain Layout
4853 pgfnodeconnline{A2}{C3}}
4856 \begin_layout Plain Layout
4860 pgfnodeconnline{A3}{C4}
4863 \begin_layout Plain Layout
4868 \begin_layout Plain Layout
4875 \begin_layout Plain Layout
4882 \begin_layout Plain Layout
4888 pgfnodeconnline{A1}{A2}}
4891 \begin_layout Plain Layout
4895 pgfnodeconnline{A2}{A3}
4898 \begin_layout Plain Layout
4902 pgfnodeconnline{A3}{A4}
4905 \begin_layout Plain Layout
4909 pgfnodeconnline{B1}{B2}
4912 \begin_layout Plain Layout
4916 pgfnodeconnline{B2}{B3}
4919 \begin_layout Plain Layout
4923 pgfnodeconnline{B3}{B4}
4926 \begin_layout Plain Layout
4930 pgfnodeconnline{C1}{C2}
4933 \begin_layout Plain Layout
4937 pgfnodeconnline{C2}{C3}
4940 \begin_layout Plain Layout
4944 pgfnodeconnline{C3}{C4}
4947 \begin_layout Plain Layout
4951 pgfnodeconnline{D1}{D2}
4954 \begin_layout Plain Layout
4958 pgfnodeconnline{D2}{D3}
4961 \begin_layout Plain Layout
4967 pgfnodeconnline{D3}{D4}}
4970 \begin_layout Plain Layout
4975 \begin_layout Plain Layout
4989 \begin_layout AgainFrame
4990 \begin_inset Argument 1
4993 \begin_layout Plain Layout
5003 \begin_layout Subsection
5004 Complexity of: Approximating the Shortest Path
5008 \begin_inset Argument 4
5011 \begin_layout Plain Layout
5012 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5021 \begin_layout Definition
5026 approximation scheme for
5027 \begin_inset Formula $\Lang{tournament-shortest-path}$
5038 \begin_layout Enumerate
5040 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5046 \begin_layout Enumerate
5048 \begin_inset Formula $r>1$
5054 \begin_layout Standard
5058 \begin_layout Itemize
5060 \begin_inset Formula $s$
5064 \begin_inset space ~
5068 \begin_inset Formula $t$
5072 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5080 \begin_layout Standard
5081 \begin_inset Separator plain
5088 \begin_inset Argument 4
5091 \begin_layout Plain Layout
5092 There Exists a Logspace Approximation Scheme for
5093 \begin_inset Newline newline
5096 the Tournament Shortest Path Problem
5105 \begin_layout Theorem
5106 There exists an approximation scheme for
5107 \begin_inset Formula $\Lang{tournament-shortest-path}$
5111 \begin_inset Formula $1<r<2$
5115 \begin_inset Formula
5117 O\left(\log|V|\log\frac{1}{r-1}\right).
5129 \begin_layout Corollary
5130 In tournaments, paths can be constructed in logarithmic space.
5133 \begin_layout Standard
5134 \begin_inset space \hfill{}
5141 \begin_layout Plain Layout
5145 hyperlink{optimality}{
5147 beamergotobutton{More Details}}
5156 \begin_layout AgainFrame
5157 \begin_inset Argument 1
5160 \begin_layout Plain Layout
5170 \begin_layout Standard
5171 \begin_inset Note Note
5174 \begin_layout Plain Layout
5175 If a frame includes a program listing, the frame needs to be marked as
5176 \begin_inset Quotes eld
5180 \begin_inset Quotes erd
5185 has the FragileFrame layout for this.
5193 \begin_layout FragileFrame
5194 \begin_inset Argument 4
5197 \begin_layout Plain Layout
5198 Just a frame with a program code listing
5206 \begin_layout FragileFrame
5207 This is some program code:
5211 \begin_layout Standard
5212 \begin_inset listings
5213 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5217 \begin_layout Plain Layout
5222 \begin_layout Plain Layout
5224 'this is a python function'
5227 \begin_layout Plain Layout
5232 \begin_layout Plain Layout
5237 \begin_layout Plain Layout
5239 'This is a German word: Tschüs'
5242 \begin_layout Plain Layout
5247 \begin_layout Plain Layout
5252 \begin_layout Plain Layout
5254 'this is a python function'
5257 \begin_layout Plain Layout
5268 \begin_layout Section*
5272 \begin_layout Subsection*
5277 \begin_inset Argument 4
5280 \begin_layout Plain Layout
5291 \begin_inset Argument 2
5294 \begin_layout Plain Layout
5304 \begin_layout Itemize
5318 \begin_inset Formula $\Class{AC}^{0}$
5327 \begin_layout Itemize
5332 logspace approximation scheme
5344 shortest paths in tournaments.
5347 \begin_layout Itemize
5361 \begin_inset Formula $\Class{NL}$
5370 \begin_layout Standard
5371 \begin_inset Separator plain
5378 \begin_inset Argument 2
5381 \begin_layout Plain Layout
5391 \begin_layout Itemize
5392 The same results apply to graphs with
5393 \begin_inset Newline newline
5396 bounded independence number.
5397 \begin_inset space \hfill{}
5404 \begin_layout Plain Layout
5408 hyperlink{independence}{
5410 beamergotobutton{More Details}}
5418 \begin_layout Itemize
5419 The complexity of finding paths in undirected graphs
5420 \begin_inset Newline newline
5424 \begin_inset space \hfill{}
5431 \begin_layout Plain Layout
5435 hyperlink{undirected}{
5437 beamergotobutton{More Details}}
5447 \begin_layout Subsection*
5452 \begin_inset Argument 4
5455 \begin_layout Plain Layout
5465 \begin_layout Standard
5469 \begin_layout Plain Layout
5473 beamertemplatebookbibitems
5481 \begin_layout Bibliography
5482 \begin_inset CommandInset bibitem
5483 LatexCommand bibitem
5490 \begin_inset space ~
5498 \begin_layout Plain Layout
5509 Topics on Tournaments.
5516 \begin_layout Plain Layout
5525 Holt, Rinehart, and Winston, 1968.
5530 \begin_layout Plain Layout
5534 beamertemplatearticlebibitems
5542 \begin_layout Bibliography
5543 \begin_inset CommandInset bibitem
5544 LatexCommand bibitem
5545 key "NickelsenT2002"
5551 \begin_inset space ~
5554 Arfst Nickelsen and Till Tantau.
5559 \begin_layout Plain Layout
5568 On reachability in graphs with bounded independence number.
5572 \begin_layout Plain Layout
5586 , Springer-Verlag, 2002.
5589 \begin_layout Bibliography
5590 \begin_inset CommandInset bibitem
5591 LatexCommand bibitem
5598 \begin_inset space ~
5605 \begin_layout Plain Layout
5614 A logspace approximation scheme for the shortest path problem for graphs
5615 with bounded independence number.
5619 \begin_layout Plain Layout
5633 , Springer-Verlag, 2004.
5638 \begin_layout Plain Layout
5651 \begin_layout Standard
5656 \begin_layout Plain Layout
5660 AtBeginSubsection[]{}
5668 \begin_layout Section
5672 \begin_layout Subsection
5673 Graphs With Bounded Independence Number
5677 \begin_inset Argument 3
5680 \begin_layout Plain Layout
5687 \begin_inset Argument 4
5690 \begin_layout Plain Layout
5691 Definition of Independence Number of a Graph
5700 \begin_layout Definition
5710 \begin_inset Formula $\alpha(G)$
5714 \begin_inset Newline newline
5717 is the maximum number of vertices we can pick,
5718 \begin_inset Newline newline
5721 such that there is no edge between them.
5724 \begin_layout Example
5725 Tournaments have independence number 1.
5730 \begin_layout Standard
5731 \begin_inset Separator plain
5738 \begin_inset Argument 4
5741 \begin_layout Plain Layout
5742 The Results for Tournaments also Apply to
5743 \begin_inset Newline newline
5746 Graphs With Bounded Independence Number
5755 \begin_layout Theorem
5757 \begin_inset space ~
5761 \begin_inset Formula $k$
5772 in graphs with independence number
5773 \begin_inset Newline newline
5777 \begin_inset space ~
5781 \begin_inset Formula $k$
5785 \begin_inset Formula $\Class{AC}^{0}$
5791 \begin_layout Standard
5792 \begin_inset Separator plain
5798 \begin_layout Theorem
5800 \begin_inset space ~
5804 \begin_inset Formula $k$
5811 logspace approximation scheme
5815 for approximating the shortest path in graphs with independence number at
5817 \begin_inset space ~
5821 \begin_inset Formula $k$
5827 \begin_layout Standard
5828 \begin_inset Separator plain
5834 \begin_layout Theorem
5836 \begin_inset space ~
5840 \begin_inset Formula $k$
5851 in graphs with independence number at most
5852 \begin_inset space ~
5856 \begin_inset Formula $k$
5864 \begin_inset Formula $\Class{NL}$
5873 \begin_layout Subsection
5874 Finding Paths in Undirected Graphs
5878 \begin_inset Argument 1
5881 \begin_layout Plain Layout
5889 \begin_inset Argument 3
5892 \begin_layout Plain Layout
5899 \begin_inset Argument 4
5902 \begin_layout Plain Layout
5903 The Complexity of Finding Paths in Undirected Graphs
5904 \begin_inset Newline newline
5917 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5921 \begin_inset Formula $\Class{SL}$
5927 \begin_layout Corollary
5928 For undirected graphs, we can solve
5932 \begin_layout Itemize
5933 the reachability problem in logspace iff
5934 \begin_inset Formula $\Class L=\Class{SL}$
5940 \begin_layout Itemize
5941 the construction problem in logspace iff
5942 \begin_inset Flex Alternative
5945 \begin_layout Plain Layout
5946 \begin_inset Argument 1
5949 \begin_layout Plain Layout
5957 \begin_inset Argument 2
5960 \begin_layout Plain Layout
5967 \begin_inset Flex Alert
5970 \begin_layout Plain Layout
5971 \begin_inset Formula $\Class L=\Class{SL}$
5987 \begin_layout Itemize
5988 the optimization problem in logspace iff
5989 \begin_inset Flex Alternative
5992 \begin_layout Plain Layout
5993 \begin_inset Argument 1
5996 \begin_layout Plain Layout
6004 \begin_inset Argument 2
6007 \begin_layout Plain Layout
6014 \begin_inset Flex Alert
6017 \begin_layout Plain Layout
6018 \begin_inset Formula $\Class L=\Class{NL}$
6034 \begin_layout Itemize
6035 the approximation problem in logspace iff ?.
6041 \begin_layout Subsection
6042 The Approximation Scheme is Optimal
6046 \begin_inset Argument 3
6049 \begin_layout Plain Layout
6056 \begin_inset Argument 4
6059 \begin_layout Plain Layout
6060 The Approximation Scheme is Optimal
6069 \begin_layout Theorem
6070 Suppose there exists an approximation scheme for
6071 \begin_inset Formula $\Lang{tournament-shortest-path}$
6075 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6080 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6091 \begin_layout Enumerate
6092 Suppose the approximation scheme exists.
6093 \begin_inset Newline newline
6097 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6104 \begin_layout Enumerate
6106 \begin_inset Formula $(T,s,t)$
6111 \begin_inset Formula $n$
6114 be the number of vertices.
6117 \begin_layout Enumerate
6118 Run the approximation scheme for
6119 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6123 \begin_inset Newline newline
6127 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6133 \begin_layout Enumerate
6134 The resulting path has optimal length.
6139 \begin_layout Plain Layout