1 #LyX 2.4 created this file. For more info see https://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 no
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_typewriter_osf false
169 \font_roman_osf false
170 \font_sf_scale 100 100
171 \font_tt_scale 100 100
173 \use_dash_ligatures false
175 \default_output_format default
177 \bibtex_command default
178 \index_command default
179 \paperfontsize default
184 \use_package amsmath 2
185 \use_package amssymb 2
186 \use_package cancel 1
188 \use_package mathdots 1
189 \use_package mathtools 1
190 \use_package mhchem 1
191 \use_package stackrel 1
192 \use_package stmaryrd 1
193 \use_package undertilde 1
195 \cite_engine_type default
199 \paperorientation portrait
211 \paragraph_separation indent
212 \paragraph_indentation default
214 \math_numbering_side default
215 \quotes_style english
219 \paperpagestyle default
220 \tracking_changes false
221 \postpone_fragile_content false
222 \output_changes false
225 \html_be_strict false
232 \begin_inset Newline newline
235 Finding Paths in Tournaments
242 \begin_layout Institute
243 International Computer Science Institute
244 \begin_inset Newline newline
248 \begin_inset Argument 1
251 \begin_layout Plain Layout
265 \begin_inset Argument 4
268 \begin_layout Plain Layout
278 \begin_layout Standard
279 \begin_inset CommandInset toc
280 LatexCommand tableofcontents
288 \begin_layout Plain Layout
299 \begin_layout Standard
303 \begin_layout Plain Layout
305 % Show the table of contents at the beginning
308 \begin_layout Plain Layout
310 % of every subsection.
313 \begin_layout Plain Layout
317 AtBeginSubsection[]{%
320 \begin_layout Plain Layout
327 \begin_layout Plain Layout
334 \begin_layout Plain Layout
338 tableofcontents[current,currentsubsection]
341 \begin_layout Plain Layout
346 \begin_layout Plain Layout
356 \begin_layout Section
360 \begin_layout Subsection
361 What are Tournaments?
365 \begin_inset Argument 4
368 \begin_layout Plain Layout
369 Tournaments Consist of Jousts Between Knights
378 \begin_layout Columns
387 \begin_layout Standard
391 \begin_layout Plain Layout
395 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
398 \begin_layout Plain Layout
402 pgfnodebox{A}[virtual]{
407 \begin_layout Plain Layout
411 pgfuseimage{knight1}}{2pt}{2pt}
414 \begin_layout Plain Layout
418 pgfnodebox{B}[virtual]{
423 \begin_layout Plain Layout
427 pgfuseimage{knight2}}{2pt}{2pt}
430 \begin_layout Plain Layout
434 pgfnodebox{C}[virtual]{
439 \begin_layout Plain Layout
443 pgfuseimage{knight3}}{2pt}{2pt}
446 \begin_layout Plain Layout
450 pgfnodebox{D}[virtual]{
455 \begin_layout Plain Layout
459 pgfuseimage{knight4}}{2pt}{2pt}
462 \begin_layout Plain Layout
469 \begin_layout Plain Layout
480 \begin_layout Plain Layout
487 \begin_layout Plain Layout
491 pgfsetlinewidth{0.6pt}
494 \begin_layout Plain Layout
498 pgfnodeconnline{A}{B}
501 \begin_layout Plain Layout
505 pgfnodeconnline{A}{C}
508 \begin_layout Plain Layout
512 pgfnodeconnline{D}{A}
515 \begin_layout Plain Layout
519 pgfnodeconnline{C}{B}
522 \begin_layout Plain Layout
526 pgfnodeconnline{B}{D}
529 \begin_layout Plain Layout
533 pgfnodeconnline{C}{D}
536 \begin_layout Plain Layout
541 \begin_layout Plain Layout
558 \begin_inset Argument 2
561 \begin_layout Plain Layout
562 What is a Tournament?
571 \begin_layout Itemize
572 \begin_inset Argument item:2
575 \begin_layout Plain Layout
585 \begin_layout Itemize
586 \begin_inset Argument item:2
589 \begin_layout Plain Layout
596 Every pair has a joust.
599 \begin_layout Itemize
600 \begin_inset Argument item:2
603 \begin_layout Plain Layout
610 In every joust one knight wins.
616 \begin_layout Standard
617 \begin_inset Separator plain
624 \begin_inset Argument 4
627 \begin_layout Plain Layout
628 Tournaments are Complete Directed Graphs
637 \begin_layout Columns
646 \begin_layout Standard
650 \begin_layout Plain Layout
654 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
657 \begin_layout Plain Layout
664 \begin_layout Plain Layout
668 pgfsetlinewidth{0.6pt}
671 \begin_layout Plain Layout
680 \begin_layout Plain Layout
689 \begin_layout Plain Layout
698 \begin_layout Plain Layout
707 \begin_layout Plain Layout
714 \begin_layout Plain Layout
722 pgfbox[center,center]{$v_2$}}
725 \begin_layout Plain Layout
733 pgfbox[center,center]{$v_3$}}
736 \begin_layout Plain Layout
744 pgfbox[center,center]{$v_4$}}
747 \begin_layout Plain Layout
755 pgfbox[center,center]{$v_1$}}
758 \begin_layout Plain Layout
765 \begin_layout Plain Layout
774 \begin_layout Plain Layout
778 pgfnodesetsepstart{2pt}
781 \begin_layout Plain Layout
785 pgfnodesetsepend{4pt}
788 \begin_layout Plain Layout
792 pgfnodeconnline{A}{B}
795 \begin_layout Plain Layout
799 pgfnodeconnline{A}{C}
802 \begin_layout Plain Layout
806 pgfnodeconnline{D}{A}
809 \begin_layout Plain Layout
813 pgfnodeconnline{C}{B}
816 \begin_layout Plain Layout
820 pgfnodeconnline{B}{D}
823 \begin_layout Plain Layout
827 pgfnodeconnline{D}{C}
830 \begin_layout Plain Layout
846 \begin_layout Definition
847 \begin_inset Argument 1
850 \begin_layout Plain Layout
869 \begin_layout Enumerate
873 \begin_layout Enumerate
874 with exactly one edge between
875 \begin_inset Newline newline
878 any two different vertices.
884 \begin_layout Standard
885 \begin_inset Separator plain
892 \begin_inset Argument 2
895 \begin_layout Plain Layout
903 \begin_inset Argument 4
906 \begin_layout Plain Layout
907 Tournaments Arise Naturally in Different Situations
916 \begin_layout ExampleBlock
917 \begin_inset Argument 2
920 \begin_layout Plain Layout
921 Applications in Ordering Theory
930 \begin_layout Standard
931 Elements in a set need to be sorted.
933 \begin_inset Newline newline
936 The comparison relation may be cyclic, however.
940 \begin_layout Standard
941 \begin_inset Separator plain
947 \begin_layout ExampleBlock
948 \begin_inset Argument 2
951 \begin_layout Plain Layout
952 Applications in Sociology
961 \begin_layout Standard
962 Several candidates apply for a position.
963 \begin_inset Newline newline
966 Reviewers decide for any two candidates whom they prefer.
971 \begin_layout Standard
972 \begin_inset Separator plain
978 \begin_layout ExampleBlock
979 \begin_inset Argument 2
982 \begin_layout Plain Layout
983 Applications in Structural Complexity Theory
992 \begin_layout Standard
994 \begin_inset Formula $L$
997 is given and a selector function
998 \begin_inset Formula $f$
1002 \begin_inset Newline newline
1005 It chooses from any two words the one more likely to be in
1006 \begin_inset Formula $f$
1014 \begin_layout Subsection
1015 What Does ``Finding Paths'' Mean?
1019 \begin_inset Argument 4
1022 \begin_layout Plain Layout
1023 ``Finding Paths'' is Ambiguous
1033 \begin_inset Argument 2
1036 \begin_layout Plain Layout
1038 \begin_inset Flex Only
1041 \begin_layout Plain Layout
1042 \begin_inset Argument 1
1045 \begin_layout Plain Layout
1052 Path Finding Problems
1058 \begin_inset Flex Only
1061 \begin_layout Plain Layout
1062 \begin_inset Argument 1
1065 \begin_layout Plain Layout
1073 \begin_inset Formula $\Lang{reach}$
1082 \begin_inset Flex Only
1085 \begin_layout Plain Layout
1086 \begin_inset Argument 1
1089 \begin_layout Plain Layout
1096 the Construction Problem
1102 \begin_inset Flex Only
1105 \begin_layout Plain Layout
1106 \begin_inset Argument 1
1109 \begin_layout Plain Layout
1116 the Optimization Problem
1122 \begin_inset Flex Only
1125 \begin_layout Plain Layout
1126 \begin_inset Argument 1
1129 \begin_layout Plain Layout
1137 \begin_inset Formula $\Lang{distance}$
1146 \begin_inset Flex Only
1149 \begin_layout Plain Layout
1150 \begin_inset Argument 1
1153 \begin_layout Plain Layout
1160 the Approximation Problem
1174 \begin_layout Itemize
1184 \begin_inset Formula $G=(V,E)$
1196 \begin_inset Formula $s\in V$
1208 \begin_inset Formula $t\in V$
1214 \begin_layout Itemize
1215 \begin_inset Argument item:2
1218 \begin_layout Plain Layout
1232 \begin_inset space ~
1236 \begin_inset Formula $d$
1243 \begin_layout Plain Layout
1255 \begin_layout Itemize
1256 \begin_inset Argument item:2
1259 \begin_layout Plain Layout
1275 \begin_inset Formula $r>1$
1282 \begin_layout Standard
1286 \begin_layout Plain Layout
1298 \begin_layout Overprint
1299 \begin_inset Argument item:1
1302 \begin_layout Plain Layout
1313 \begin_layout Columns
1314 \begin_inset Argument 1
1317 \begin_layout Plain Layout
1327 \begin_layout Standard
1328 \begin_inset Flex Alternative
1331 \begin_layout Plain Layout
1332 \begin_inset Argument 1
1335 \begin_layout Plain Layout
1343 \begin_inset Argument 2
1346 \begin_layout Plain Layout
1350 \begin_layout Plain Layout
1370 \begin_layout Plain Layout
1387 \begin_layout ExampleBlock
1388 \begin_inset Argument 2
1391 \begin_layout Plain Layout
1401 \begin_layout Standard
1405 \begin_layout Plain Layout
1409 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1412 \begin_layout Plain Layout
1416 \begin_layout Plain Layout
1420 color{beamerexample}
1423 \begin_layout Plain Layout
1427 \begin_layout Plain Layout
1431 pgfsetlinewidth{0.6pt}
1434 \begin_layout Plain Layout
1438 \begin_layout Plain Layout
1447 \begin_layout Plain Layout
1451 \begin_layout Plain Layout
1460 \begin_layout Plain Layout
1464 \begin_layout Plain Layout
1473 \begin_layout Plain Layout
1477 \begin_layout Plain Layout
1486 \begin_layout Plain Layout
1490 \begin_layout Plain Layout
1494 \begin_layout Plain Layout
1498 \begin_layout Plain Layout
1505 \begin_layout Plain Layout
1509 \begin_layout Plain Layout
1517 pgfbox[center,center]{$t$}}
1520 \begin_layout Plain Layout
1524 \begin_layout Plain Layout
1532 pgfbox[center,center]{$s$}}
1535 \begin_layout Plain Layout
1539 \begin_layout Plain Layout
1543 \begin_layout Plain Layout
1547 \begin_layout Plain Layout
1551 color{beamerexample}
1554 \begin_layout Plain Layout
1558 \begin_layout Plain Layout
1567 \begin_layout Plain Layout
1571 \begin_layout Plain Layout
1575 pgfnodesetsepstart{2pt}
1578 \begin_layout Plain Layout
1582 \begin_layout Plain Layout
1586 pgfnodesetsepend{4pt}
1589 \begin_layout Plain Layout
1593 \begin_layout Plain Layout
1597 pgfnodeconnline{A}{B}
1600 \begin_layout Plain Layout
1604 \begin_layout Plain Layout
1608 pgfnodeconnline{A}{C}
1611 \begin_layout Plain Layout
1615 \begin_layout Plain Layout
1619 pgfnodeconnline{D}{A}
1622 \begin_layout Plain Layout
1626 \begin_layout Plain Layout
1630 pgfnodeconnline{C}{B}
1633 \begin_layout Plain Layout
1637 \begin_layout Plain Layout
1641 pgfnodeconnline{B}{D}
1644 \begin_layout Plain Layout
1648 \begin_layout Plain Layout
1652 pgfnodeconnline{D}{C}
1655 \begin_layout Plain Layout
1659 \begin_layout Plain Layout
1663 \begin_layout Plain Layout
1667 \begin_layout Plain Layout
1677 pgfbox[left,center]{, $d=2$}}}
1680 \begin_layout Plain Layout
1684 \begin_layout Plain Layout
1694 pgfbox[left,center]{, $r=1.5$}}}
1697 \begin_layout Plain Layout
1701 \begin_layout Plain Layout
1711 pgfbox[left,center]{, $r=1.25$}}}
1714 \begin_layout Plain Layout
1718 \begin_layout Plain Layout
1731 \begin_layout Standard
1732 \begin_inset Flex Only
1735 \begin_layout Plain Layout
1736 \begin_inset Argument 1
1739 \begin_layout Plain Layout
1750 \begin_layout Plain Layout
1767 \begin_layout ExampleBlock
1768 \begin_inset Argument 1
1771 \begin_layout Plain Layout
1779 \begin_inset Argument 2
1782 \begin_layout Plain Layout
1792 \begin_layout Standard
1796 \begin_layout Plain Layout
1800 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1803 \begin_layout Plain Layout
1810 \begin_layout Plain Layout
1814 color{beamerexample}
1817 \begin_layout Plain Layout
1821 pgfsetlinewidth{0.6pt}
1824 \begin_layout Plain Layout
1833 \begin_layout Plain Layout
1842 \begin_layout Plain Layout
1851 \begin_layout Plain Layout
1860 \begin_layout Plain Layout
1867 \begin_layout Plain Layout
1875 pgfbox[center,center]{$t$}}
1878 \begin_layout Plain Layout
1886 pgfbox[center,center]{$s$}}
1889 \begin_layout Plain Layout
1893 color{beamerexample}
1896 \begin_layout Plain Layout
1905 \begin_layout Plain Layout
1909 pgfnodesetsepstart{2pt}
1912 \begin_layout Plain Layout
1916 pgfnodesetsepend{4pt}
1919 \begin_layout Plain Layout
1925 pgfnodeconnline{A}{B}}
1928 \begin_layout Plain Layout
1934 pgfnodeconnline{A}{C}}
1937 \begin_layout Plain Layout
1943 pgfnodeconnline{D}{A}}
1946 \begin_layout Plain Layout
1952 pgfnodeconnline{C}{B}}
1955 \begin_layout Plain Layout
1959 pgfnodeconnline{B}{D}
1962 \begin_layout Plain Layout
1966 pgfnodeconnline{D}{C}
1969 \begin_layout Plain Layout
1974 \begin_layout Plain Layout
1984 pgfbox[left,center]{
1989 \begin_layout Plain Layout
2004 \begin_layout Overprint
2005 \begin_inset Argument item:1
2008 \begin_layout Plain Layout
2020 \begin_inset Argument 2
2023 \begin_layout Plain Layout
2024 Variants of Path Finding Problems
2033 \begin_layout Description
2034 \begin_inset Argument item:1
2037 \begin_layout Plain Layout
2045 \begin_inset space ~
2048 Problem: Is there a path from
2049 \begin_inset Formula $s$
2053 \begin_inset space ~
2057 \begin_inset Formula $t$
2061 \begin_inset Argument 2
2064 \begin_layout Plain Layout
2065 Approximation Problem:
2073 \begin_layout Description
2074 \begin_inset Argument item:1
2077 \begin_layout Plain Layout
2085 \begin_inset space ~
2088 Problem: Construct a path from
2089 \begin_inset Formula $s$
2093 \begin_inset space ~
2097 \begin_inset Formula $t$
2103 \begin_layout Description
2104 \begin_inset Argument item:1
2107 \begin_layout Plain Layout
2115 \begin_inset space ~
2118 Problem: Construct a shortest path from
2119 \begin_inset Formula $s$
2123 \begin_inset space ~
2127 \begin_inset Formula $t$
2133 \begin_layout Description
2134 \begin_inset Argument item:1
2137 \begin_layout Plain Layout
2145 \begin_inset space ~
2148 Problem: Is the distance of
2149 \begin_inset Formula $s$
2153 \begin_inset space ~
2157 \begin_inset Formula $t$
2161 \begin_inset space ~
2165 \begin_inset Formula $d$
2171 \begin_layout Description
2172 \begin_inset Argument item:1
2175 \begin_layout Plain Layout
2183 \begin_inset space ~
2186 Problem: Construct a path from
2187 \begin_inset Formula $s$
2191 \begin_inset space ~
2195 \begin_inset Formula $t$
2199 \begin_inset Newline newline
2202 approximately their distance.
2208 \begin_layout Section
2212 \begin_layout Subsection
2213 Standard Complexity Classes
2216 \begin_layout Standard
2220 \begin_layout Plain Layout
2224 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2226 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2236 \begin_inset Argument 4
2239 \begin_layout Plain Layout
2240 The Classes L and NL are Defined via
2241 \begin_inset Newline newline
2244 Logspace Turing Machines
2253 \begin_layout Standard
2257 \begin_layout Plain Layout
2261 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2264 \begin_layout Plain Layout
2273 \begin_layout Plain Layout
2277 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2280 \begin_layout Plain Layout
2287 \begin_layout Plain Layout
2296 \begin_layout Plain Layout
2300 tape{}{output tape (write only)}{10690836937182}}
2303 \begin_layout Plain Layout
2308 \begin_layout Plain Layout
2315 \begin_layout Plain Layout
2324 \begin_layout Plain Layout
2328 shorttape{work tape (read/write), $O(
2330 log n)$ symbols}{}{42}}
2333 \begin_layout Plain Layout
2342 \begin_layout Plain Layout
2346 pgfbox[center,center]{
2348 pgfuseimage{computer}}}
2351 \begin_layout Plain Layout
2356 \begin_layout Plain Layout
2360 pgfsetlinewidth{0.6pt}
2363 \begin_layout Plain Layout
2370 \begin_layout Plain Layout
2379 \begin_layout Plain Layout
2383 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2386 \begin_layout Plain Layout
2392 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2395 \begin_layout Plain Layout
2401 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2404 \begin_layout Plain Layout
2417 \begin_layout Standard
2418 \begin_inset Separator plain
2425 \begin_inset Argument 4
2428 \begin_layout Plain Layout
2429 Logspace Turing Machines Are Quite Powerful
2439 \begin_inset Argument 2
2442 \begin_layout Plain Layout
2443 Deterministic logspace machines can compute
2452 \begin_layout Itemize
2453 addition, multiplication, and even division
2456 \begin_layout Itemize
2457 reductions used in completeness proofs,
2460 \begin_layout Itemize
2461 reachability in forests.
2470 \begin_inset Argument 2
2473 \begin_layout Plain Layout
2474 Non-deterministic logspace machines can compute
2483 \begin_layout Itemize
2484 reachability in graphs,
2487 \begin_layout Itemize
2488 non-reachability in graphs,
2491 \begin_layout Itemize
2492 satisfiability with two literals per clause.
2497 \begin_layout Standard
2498 \begin_inset Separator plain
2505 \begin_inset Argument 1
2508 \begin_layout Plain Layout
2516 \begin_inset Argument 3
2519 \begin_layout Plain Layout
2526 \begin_inset Argument 4
2529 \begin_layout Plain Layout
2530 The Complexity Class Hierarchy
2539 \begin_layout Standard
2543 \begin_layout Plain Layout
2547 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2550 \begin_layout Plain Layout
2554 pgfsetlinewidth{0.8pt}
2557 \begin_layout Plain Layout
2566 \begin_layout Plain Layout
2570 pgfsetdash{{2pt}}{0pt}
2573 \begin_layout Plain Layout
2581 Class{NC}^2$}{black!50!structure}{2}}
2584 \begin_layout Plain Layout
2590 Class{NL}$}{black!50!structure}{3}
2593 \begin_layout Plain Layout
2599 Class{L}$}{black!50!structure}{4}
2602 \begin_layout Plain Layout
2613 \begin_layout Plain Layout
2619 Class{NC}^1}$}{black!50!structure}{5}
2622 \begin_layout Plain Layout
2627 \begin_layout Plain Layout
2634 \begin_layout Plain Layout
2645 \begin_layout Plain Layout
2651 Class{AC}^0}$}{black}{6}
2654 \begin_layout Plain Layout
2659 \begin_layout Plain Layout
2663 pgfsetlinewidth{1.0pt}
2666 \begin_layout Plain Layout
2673 \begin_layout Plain Layout
2677 pgfxyline(-5,0)(5,0)
2680 \begin_layout Plain Layout
2691 \begin_layout Plain Layout
2701 operatorname{forest}}$}}
2704 \begin_layout Plain Layout
2715 \begin_layout Plain Layout
2734 \begin_layout Plain Layout
2753 \begin_layout Plain Layout
2766 \begin_layout Plain Layout
2774 operatorname{forest}}$,}
2779 \begin_layout Plain Layout
2787 operatorname{forest}}$,}
2792 \begin_layout Plain Layout
2800 operatorname{path}}$,}
2805 \begin_layout Plain Layout
2813 operatorname{path}}$}}}
2816 \begin_layout Plain Layout
2821 \begin_layout Plain Layout
2831 operatorname{tourn}}$}}
2834 \begin_layout Plain Layout
2847 \begin_layout Plain Layout
2855 operatorname{tourn}}$,}
2860 \begin_layout Plain Layout
2871 \begin_layout Plain Layout
2880 \begin_layout Plain Layout
2885 \begin_layout Plain Layout
2891 pgfsetdash{{1pt}}{0pt}%
2894 \begin_layout Plain Layout
2902 operatorname{tourn}}$''}
2905 \begin_layout Plain Layout
2910 \begin_layout Plain Layout
2923 \begin_layout Standard
2924 \begin_inset Separator plain
2931 \begin_inset Argument 4
2934 \begin_layout Plain Layout
2935 The Circuit Complexity Classes AC
2936 \begin_inset Formula $^{0}$
2940 \begin_inset Formula $^{1}$
2944 \begin_inset Formula $^{2}$
2948 \begin_inset Newline newline
2951 Limit the Circuit Depth
2960 \begin_layout Standard
2964 \begin_layout Plain Layout
2973 \begin_layout Plain Layout
2985 \begin_layout Columns
2986 \begin_inset Argument 1
2989 \begin_layout Plain Layout
2999 \begin_layout Column
3004 \begin_inset Argument 2
3007 \begin_layout Plain Layout
3009 \begin_inset Formula $\Class{AC}^{0}$
3021 \begin_layout Itemize
3022 \begin_inset Formula $O(1)$
3028 \begin_layout Itemize
3033 \begin_layout Examples
3038 \begin_layout Itemize
3039 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3045 \begin_layout Itemize
3046 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3057 \begin_layout Column
3062 \begin_inset Argument 2
3065 \begin_layout Plain Layout
3067 \begin_inset Formula $\Class{NC}^{1}$
3079 \begin_layout Itemize
3080 \begin_inset Formula $O(\log n)$
3086 \begin_layout Itemize
3091 \begin_layout Examples
3096 \begin_layout Itemize
3097 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3103 \begin_layout Itemize
3104 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3110 \begin_layout Itemize
3111 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3122 \begin_layout Column
3127 \begin_inset Argument 2
3130 \begin_layout Plain Layout
3132 \begin_inset Formula $\Class{NC}^{2}$
3144 \begin_layout Itemize
3145 \begin_inset Formula $O(\log^{2}n)$
3151 \begin_layout Itemize
3156 \begin_layout Examples
3161 \begin_layout Itemize
3162 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3171 \begin_layout AgainFrame
3172 \begin_inset Argument 1
3175 \begin_layout Plain Layout
3185 \begin_layout Subsection
3186 Standard Complexity Results on Finding Paths
3190 \begin_inset Argument 4
3193 \begin_layout Plain Layout
3194 All Variants of Finding Paths in Directed Graphs
3195 \begin_inset Newline newline
3198 Are Equally Difficult
3208 \begin_inset Formula $\Lang{reach}$
3212 \begin_inset Formula $\Lang{distance}$
3216 \begin_inset Formula $\Class{NL}$
3227 \begin_layout Corollary
3228 For directed graphs, we can solve
3232 \begin_layout Itemize
3233 the reachability problem in logspace iff
3234 \begin_inset Formula $\Class{L}=\Class{NL}$
3240 \begin_layout Itemize
3241 the construction problem in logspace iff
3242 \begin_inset Formula $\Class{L}=\Class{NL}$
3248 \begin_layout Itemize
3249 the optimization problem in logspace iff
3250 \begin_inset Formula $\Class{L}=\Class{NL}$
3256 \begin_layout Itemize
3257 the approximation problem in logspace iff
3258 \begin_inset Formula $\Class{L}=\Class{NL}$
3266 \begin_layout AgainFrame
3267 \begin_inset Argument 1
3270 \begin_layout Plain Layout
3281 \begin_inset Argument 4
3284 \begin_layout Plain Layout
3285 Finding Paths in Forests and Directed Paths is Easy,
3286 \begin_inset Newline newline
3299 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3303 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3307 \begin_inset Formula $\Class{L}$
3313 \begin_layout Standard
3314 \begin_inset Separator plain
3321 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3325 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3329 \begin_inset Formula $\Class{L}$
3336 \begin_layout AgainFrame
3337 \begin_inset Argument 1
3340 \begin_layout Plain Layout
3350 \begin_layout Section
3351 Finding Paths in Tournaments
3354 \begin_layout Subsection
3355 Complexity of: Does a Path Exist?
3359 \begin_inset Argument 4
3362 \begin_layout Plain Layout
3363 Definition of the Tournament Reachability Problem
3372 \begin_layout Definition
3378 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3386 \begin_inset Formula $(T,s,t)$
3393 \begin_layout Enumerate
3394 \begin_inset Formula $T=(V,E)$
3400 \begin_layout Enumerate
3401 there exists a path from
3402 \begin_inset space ~
3406 \begin_inset Formula $s$
3410 \begin_inset space ~
3414 \begin_inset Formula $t$
3422 \begin_layout Standard
3423 \begin_inset Separator plain
3430 \begin_inset Argument 4
3433 \begin_layout Plain Layout
3434 The Tournament Reachability Problem is Very Easy
3443 \begin_layout Theorem
3444 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3454 \begin_layout AlertBlock
3455 \begin_inset Argument 2
3458 \begin_layout Plain Layout
3468 \begin_layout Itemize
3470 \begin_inset Quotes eld
3474 \begin_inset Quotes erd
3478 \begin_inset Formula $\Lang{reach}$
3482 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3488 \begin_layout Itemize
3489 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3497 \begin_layout AgainFrame
3498 \begin_inset Argument 1
3501 \begin_layout Plain Layout
3511 \begin_layout Subsection
3512 Complexity of: Construct a Shortest Path
3516 \begin_inset Argument 4
3519 \begin_layout Plain Layout
3520 Finding a Shortest Path Is as Difficult as
3521 \begin_inset Newline newline
3524 the Distance Problem
3533 \begin_layout Definition
3539 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3547 \begin_inset Formula $(T,s,t,d)$
3554 \begin_layout Enumerate
3555 \begin_inset Formula $T=(V,E)$
3558 is a tournament in which
3561 \begin_layout Enumerate
3563 \begin_inset Formula $s$
3567 \begin_inset space ~
3571 \begin_inset Formula $t$
3575 \begin_inset space ~
3579 \begin_inset Formula $d$
3587 \begin_layout Standard
3588 \begin_inset Separator plain
3595 \begin_inset Argument 4
3598 \begin_layout Plain Layout
3599 The Tournament Distance Problem is Hard
3608 \begin_layout Theorem
3609 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3613 \begin_inset Formula $\Class{NL}$
3619 \begin_layout Standard
3620 \begin_inset space \hfill{}
3627 \begin_layout Plain Layout
3631 hyperlink{hierarchy<6>}{
3633 beamerskipbutton{Skip Proof}}
3645 \begin_layout Corollary
3646 Shortest path in tournaments can be constructed
3647 \begin_inset Newline newline
3650 in logarithmic space, iff
3651 \begin_inset Formula $\Class{L}=\Class{NL}$
3661 \begin_layout Corollary
3662 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3669 \begin_layout Standard
3670 \begin_inset Separator plain
3677 \begin_inset Argument 4
3680 \begin_layout Plain Layout
3682 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3694 \begin_layout Standard
3698 \begin_layout Plain Layout
3710 \begin_layout Columns
3711 \begin_inset Argument 1
3714 \begin_layout Plain Layout
3724 \begin_layout Column
3728 \begin_layout Standard
3732 \begin_layout Plain Layout
3747 \begin_inset Argument 2
3750 \begin_layout Plain Layout
3752 \begin_inset Formula $\Lang{reach}$
3756 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3768 \begin_layout Enumerate
3769 \begin_inset Argument item:2
3772 \begin_layout Plain Layout
3780 \begin_inset Formula $(G,s,t)$
3784 \begin_inset Formula $\Lang{reach}$
3790 \begin_layout Enumerate
3791 \begin_inset Argument item:2
3794 \begin_layout Plain Layout
3802 \begin_inset Formula $G$
3806 \begin_inset Formula $G'$
3812 \begin_layout Enumerate
3813 \begin_inset Argument item:2
3816 \begin_layout Plain Layout
3824 \begin_inset Newline newline
3828 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3835 \begin_layout Standard
3836 \begin_inset Separator plain
3843 \begin_inset Argument 2
3846 \begin_layout Plain Layout
3853 \begin_inset Argument 1
3856 \begin_layout Plain Layout
3867 \begin_layout Enumerate
3868 \begin_inset Argument item:2
3871 \begin_layout Plain Layout
3879 \begin_inset space ~
3883 \begin_inset Formula $G$
3887 \begin_inset Newline newline
3891 \begin_inset space ~
3895 \begin_inset Formula $G'$
3901 \begin_layout Enumerate
3902 \begin_inset Argument item:2
3905 \begin_layout Plain Layout
3913 \begin_inset space ~
3917 \begin_inset Formula $G'$
3921 \begin_inset Newline newline
3925 \begin_inset space ~
3929 \begin_inset Formula $G'$
3936 \begin_layout Column
3940 \begin_layout Example
3944 \begin_layout Plain Layout
3948 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3951 \begin_layout Plain Layout
3955 color{beamerexample}
3958 \begin_layout Plain Layout
3962 pgfsetlinewidth{0.6pt}
3965 \begin_layout Plain Layout
3974 \begin_layout Plain Layout
3983 \begin_layout Plain Layout
3992 \begin_layout Plain Layout
4001 \begin_layout Plain Layout
4008 \begin_layout Plain Layout
4016 pgfbox[center,center]{$s$}}
4019 \begin_layout Plain Layout
4027 pgfbox[center,center]{$t$}}
4030 \begin_layout Plain Layout
4034 color{beamerexample}
4037 \begin_layout Plain Layout
4046 \begin_layout Plain Layout
4050 pgfnodesetsepstart{2pt}
4053 \begin_layout Plain Layout
4057 pgfnodesetsepend{2pt}
4060 \begin_layout Plain Layout
4066 pgfnodeconnline{B}{A}}
4069 \begin_layout Plain Layout
4075 pgfnodeconnline{B}{C}}
4078 \begin_layout Plain Layout
4084 pgfnodeconnline{C}{D}}
4087 \begin_layout Plain Layout
4093 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4096 \begin_layout Plain Layout
4104 pgfbox[left,center]{$G
4109 \begin_layout Plain Layout
4116 \begin_layout Plain Layout
4124 pgfbox[left,center]{$G'
4129 \begin_layout Plain Layout
4138 \begin_layout Plain Layout
4147 \begin_layout Plain Layout
4156 \begin_layout Plain Layout
4165 \begin_layout Plain Layout
4174 \begin_layout Plain Layout
4183 \begin_layout Plain Layout
4192 \begin_layout Plain Layout
4201 \begin_layout Plain Layout
4210 \begin_layout Plain Layout
4219 \begin_layout Plain Layout
4228 \begin_layout Plain Layout
4237 \begin_layout Plain Layout
4246 \begin_layout Plain Layout
4255 \begin_layout Plain Layout
4264 \begin_layout Plain Layout
4273 \begin_layout Plain Layout
4280 \begin_layout Plain Layout
4288 pgfbox[center,center]{$s'$}}
4291 \begin_layout Plain Layout
4299 pgfbox[center,center]{$t'$}}
4302 \begin_layout Plain Layout
4307 \begin_layout Plain Layout
4312 \begin_layout Plain Layout
4319 \begin_layout Plain Layout
4323 pgfsetlinewidth{0.4pt}
4326 \begin_layout Plain Layout
4330 color{beamerexample!25!averagebackgroundcolor}
4333 \begin_layout Plain Layout
4337 pgfnodeconnline{A2}{C1}
4340 \begin_layout Plain Layout
4344 pgfnodeconnline{A2}{D1}
4347 \begin_layout Plain Layout
4351 pgfnodeconnline{B2}{A1}
4354 \begin_layout Plain Layout
4358 pgfnodeconnline{B2}{C1}
4361 \begin_layout Plain Layout
4365 pgfnodeconnline{B2}{D1}
4368 \begin_layout Plain Layout
4372 pgfnodeconnline{C2}{D1}
4375 \begin_layout Plain Layout
4379 pgfnodeconnline{D2}{A1}
4382 \begin_layout Plain Layout
4386 pgfnodeconnline{D2}{B1}
4389 \begin_layout Plain Layout
4393 pgfnodeconnline{A3}{C2}
4396 \begin_layout Plain Layout
4400 pgfnodeconnline{A3}{D2}
4403 \begin_layout Plain Layout
4407 pgfnodeconnline{B3}{A2}
4410 \begin_layout Plain Layout
4414 pgfnodeconnline{B3}{C2}
4417 \begin_layout Plain Layout
4421 pgfnodeconnline{B3}{D2}
4424 \begin_layout Plain Layout
4428 pgfnodeconnline{C3}{D2}
4431 \begin_layout Plain Layout
4435 pgfnodeconnline{D3}{A2}
4438 \begin_layout Plain Layout
4442 pgfnodeconnline{D3}{B2}
4445 \begin_layout Plain Layout
4449 pgfnodeconnline{A4}{C3}
4452 \begin_layout Plain Layout
4456 pgfnodeconnline{A4}{D3}
4459 \begin_layout Plain Layout
4463 pgfnodeconnline{B4}{A3}
4466 \begin_layout Plain Layout
4470 pgfnodeconnline{B4}{C3}
4473 \begin_layout Plain Layout
4477 pgfnodeconnline{B4}{D3}
4480 \begin_layout Plain Layout
4484 pgfnodeconnline{C4}{D3}
4487 \begin_layout Plain Layout
4491 pgfnodeconnline{D4}{A3}
4494 \begin_layout Plain Layout
4498 pgfnodeconnline{D4}{B3}
4501 \begin_layout Plain Layout
4510 \begin_layout Plain Layout
4514 pgfnodeconnline{A1}{B1}
4517 \begin_layout Plain Layout
4521 pgfnodeconnline{B1}{C1}
4524 \begin_layout Plain Layout
4528 pgfnodeconnline{C1}{D1}
4531 \begin_layout Plain Layout
4535 pgfnodeconnline{A2}{B2}
4538 \begin_layout Plain Layout
4542 pgfnodeconnline{B2}{C2}
4545 \begin_layout Plain Layout
4549 pgfnodeconnline{C2}{D2}
4552 \begin_layout Plain Layout
4556 pgfnodeconnline{A3}{B3}
4559 \begin_layout Plain Layout
4563 pgfnodeconnline{B3}{C3}
4566 \begin_layout Plain Layout
4570 pgfnodeconnline{C3}{D3}
4573 \begin_layout Plain Layout
4577 pgfnodeconnline{A4}{B4}
4580 \begin_layout Plain Layout
4584 pgfnodeconnline{B4}{C4}
4587 \begin_layout Plain Layout
4591 pgfnodeconnline{C4}{D4}
4594 \begin_layout Plain Layout
4601 \begin_layout Plain Layout
4605 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4608 \begin_layout Plain Layout
4612 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4615 \begin_layout Plain Layout
4619 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4622 \begin_layout Plain Layout
4626 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4629 \begin_layout Plain Layout
4633 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4636 \begin_layout Plain Layout
4640 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4643 \begin_layout Plain Layout
4647 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4650 \begin_layout Plain Layout
4654 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4657 \begin_layout Plain Layout
4661 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4664 \begin_layout Plain Layout
4668 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4671 \begin_layout Plain Layout
4675 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4678 \begin_layout Plain Layout
4682 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4685 \begin_layout Plain Layout
4689 color{beamerexample}
4692 \begin_layout Plain Layout
4696 pgfsetlinewidth{0.6pt}
4699 \begin_layout Plain Layout
4704 \begin_layout Plain Layout
4711 \begin_layout Plain Layout
4718 \begin_layout Plain Layout
4722 pgfnodeconnline{B1}{A2}
4725 \begin_layout Plain Layout
4729 pgfnodeconnline{B2}{A3}
4732 \begin_layout Plain Layout
4736 pgfnodeconnline{B3}{A4}
4739 \begin_layout Plain Layout
4744 \begin_layout Plain Layout
4751 \begin_layout Plain Layout
4758 \begin_layout Plain Layout
4762 pgfnodeconnline{B1}{C2}
4765 \begin_layout Plain Layout
4769 pgfnodeconnline{B2}{C3}
4772 \begin_layout Plain Layout
4776 pgfnodeconnline{B3}{C4}
4779 \begin_layout Plain Layout
4784 \begin_layout Plain Layout
4791 \begin_layout Plain Layout
4798 \begin_layout Plain Layout
4802 pgfnodeconnline{C1}{D2}
4805 \begin_layout Plain Layout
4811 pgfnodeconnline{C2}{D3}}
4814 \begin_layout Plain Layout
4820 pgfnodeconnline{C3}{D4}}
4823 \begin_layout Plain Layout
4828 \begin_layout Plain Layout
4835 \begin_layout Plain Layout
4842 \begin_layout Plain Layout
4848 pgfnodeconnline{A1}{C2}}
4851 \begin_layout Plain Layout
4857 pgfnodeconnline{A2}{C3}}
4860 \begin_layout Plain Layout
4864 pgfnodeconnline{A3}{C4}
4867 \begin_layout Plain Layout
4872 \begin_layout Plain Layout
4879 \begin_layout Plain Layout
4886 \begin_layout Plain Layout
4892 pgfnodeconnline{A1}{A2}}
4895 \begin_layout Plain Layout
4899 pgfnodeconnline{A2}{A3}
4902 \begin_layout Plain Layout
4906 pgfnodeconnline{A3}{A4}
4909 \begin_layout Plain Layout
4913 pgfnodeconnline{B1}{B2}
4916 \begin_layout Plain Layout
4920 pgfnodeconnline{B2}{B3}
4923 \begin_layout Plain Layout
4927 pgfnodeconnline{B3}{B4}
4930 \begin_layout Plain Layout
4934 pgfnodeconnline{C1}{C2}
4937 \begin_layout Plain Layout
4941 pgfnodeconnline{C2}{C3}
4944 \begin_layout Plain Layout
4948 pgfnodeconnline{C3}{C4}
4951 \begin_layout Plain Layout
4955 pgfnodeconnline{D1}{D2}
4958 \begin_layout Plain Layout
4962 pgfnodeconnline{D2}{D3}
4965 \begin_layout Plain Layout
4971 pgfnodeconnline{D3}{D4}}
4974 \begin_layout Plain Layout
4979 \begin_layout Plain Layout
4993 \begin_layout AgainFrame
4994 \begin_inset Argument 1
4997 \begin_layout Plain Layout
5007 \begin_layout Subsection
5008 Complexity of: Approximating the Shortest Path
5012 \begin_inset Argument 4
5015 \begin_layout Plain Layout
5016 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5025 \begin_layout Definition
5030 approximation scheme for
5031 \begin_inset Formula $\Lang{tournament-shortest-path}$
5042 \begin_layout Enumerate
5044 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5050 \begin_layout Enumerate
5052 \begin_inset Formula $r>1$
5058 \begin_layout Standard
5062 \begin_layout Itemize
5064 \begin_inset Formula $s$
5068 \begin_inset space ~
5072 \begin_inset Formula $t$
5076 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5084 \begin_layout Standard
5085 \begin_inset Separator plain
5092 \begin_inset Argument 4
5095 \begin_layout Plain Layout
5096 There Exists a Logspace Approximation Scheme for
5097 \begin_inset Newline newline
5100 the Tournament Shortest Path Problem
5109 \begin_layout Theorem
5110 There exists an approximation scheme for
5111 \begin_inset Formula $\Lang{tournament-shortest-path}$
5115 \begin_inset Formula $1<r<2$
5119 \begin_inset Formula
5121 O\left(\log|V|\log\frac{1}{r-1}\right).
5133 \begin_layout Corollary
5134 In tournaments, paths can be constructed in logarithmic space.
5137 \begin_layout Standard
5138 \begin_inset space \hfill{}
5145 \begin_layout Plain Layout
5149 hyperlink{optimality}{
5151 beamergotobutton{More Details}}
5160 \begin_layout AgainFrame
5161 \begin_inset Argument 1
5164 \begin_layout Plain Layout
5174 \begin_layout Standard
5175 \begin_inset Note Note
5178 \begin_layout Plain Layout
5179 If a frame includes a program listing, the frame needs to be marked as
5180 \begin_inset Quotes eld
5184 \begin_inset Quotes erd
5189 has the FragileFrame layout for this.
5197 \begin_layout FragileFrame
5198 \begin_inset Argument 4
5201 \begin_layout Plain Layout
5202 Just a frame with a program code listing
5210 \begin_layout FragileFrame
5211 This is some program code:
5215 \begin_layout Standard
5216 \begin_inset listings
5217 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5221 \begin_layout Plain Layout
5226 \begin_layout Plain Layout
5228 'this is a python function'
5231 \begin_layout Plain Layout
5236 \begin_layout Plain Layout
5241 \begin_layout Plain Layout
5243 'This is a German word: Tschüs'
5246 \begin_layout Plain Layout
5251 \begin_layout Plain Layout
5256 \begin_layout Plain Layout
5258 'this is a python function'
5261 \begin_layout Plain Layout
5272 \begin_layout Section*
5276 \begin_layout Subsection*
5281 \begin_inset Argument 4
5284 \begin_layout Plain Layout
5295 \begin_inset Argument 2
5298 \begin_layout Plain Layout
5308 \begin_layout Itemize
5322 \begin_inset Formula $\Class{AC}^{0}$
5331 \begin_layout Itemize
5336 logspace approximation scheme
5348 shortest paths in tournaments.
5351 \begin_layout Itemize
5365 \begin_inset Formula $\Class{NL}$
5374 \begin_layout Standard
5375 \begin_inset Separator plain
5382 \begin_inset Argument 2
5385 \begin_layout Plain Layout
5395 \begin_layout Itemize
5396 The same results apply to graphs with
5397 \begin_inset Newline newline
5400 bounded independence number.
5401 \begin_inset space \hfill{}
5408 \begin_layout Plain Layout
5412 hyperlink{independence}{
5414 beamergotobutton{More Details}}
5422 \begin_layout Itemize
5423 The complexity of finding paths in undirected graphs
5424 \begin_inset Newline newline
5428 \begin_inset space \hfill{}
5435 \begin_layout Plain Layout
5439 hyperlink{undirected}{
5441 beamergotobutton{More Details}}
5451 \begin_layout Subsection*
5456 \begin_inset Argument 4
5459 \begin_layout Plain Layout
5469 \begin_layout Standard
5473 \begin_layout Plain Layout
5477 beamertemplatebookbibitems
5485 \begin_layout Bibliography
5486 \begin_inset CommandInset bibitem
5487 LatexCommand bibitem
5494 \begin_inset space ~
5502 \begin_layout Plain Layout
5513 Topics on Tournaments.
5520 \begin_layout Plain Layout
5529 Holt, Rinehart, and Winston, 1968.
5534 \begin_layout Plain Layout
5538 beamertemplatearticlebibitems
5546 \begin_layout Bibliography
5547 \begin_inset CommandInset bibitem
5548 LatexCommand bibitem
5549 key "NickelsenT2002"
5555 \begin_inset space ~
5558 Arfst Nickelsen and Till Tantau.
5563 \begin_layout Plain Layout
5572 On reachability in graphs with bounded independence number.
5576 \begin_layout Plain Layout
5590 , Springer-Verlag, 2002.
5593 \begin_layout Bibliography
5594 \begin_inset CommandInset bibitem
5595 LatexCommand bibitem
5602 \begin_inset space ~
5609 \begin_layout Plain Layout
5618 A logspace approximation scheme for the shortest path problem for graphs
5619 with bounded independence number.
5623 \begin_layout Plain Layout
5637 , Springer-Verlag, 2004.
5642 \begin_layout Plain Layout
5655 \begin_layout Standard
5660 \begin_layout Plain Layout
5664 AtBeginSubsection[]{}
5672 \begin_layout Section
5676 \begin_layout Subsection
5677 Graphs With Bounded Independence Number
5681 \begin_inset Argument 3
5684 \begin_layout Plain Layout
5691 \begin_inset Argument 4
5694 \begin_layout Plain Layout
5695 Definition of Independence Number of a Graph
5704 \begin_layout Definition
5714 \begin_inset Formula $\alpha(G)$
5718 \begin_inset Newline newline
5721 is the maximum number of vertices we can pick,
5722 \begin_inset Newline newline
5725 such that there is no edge between them.
5728 \begin_layout Example
5729 Tournaments have independence number 1.
5734 \begin_layout Standard
5735 \begin_inset Separator plain
5742 \begin_inset Argument 4
5745 \begin_layout Plain Layout
5746 The Results for Tournaments also Apply to
5747 \begin_inset Newline newline
5750 Graphs With Bounded Independence Number
5759 \begin_layout Theorem
5761 \begin_inset space ~
5765 \begin_inset Formula $k$
5776 in graphs with independence number
5777 \begin_inset Newline newline
5781 \begin_inset space ~
5785 \begin_inset Formula $k$
5789 \begin_inset Formula $\Class{AC}^{0}$
5795 \begin_layout Standard
5796 \begin_inset Separator plain
5802 \begin_layout Theorem
5804 \begin_inset space ~
5808 \begin_inset Formula $k$
5815 logspace approximation scheme
5819 for approximating the shortest path in graphs with independence number at
5821 \begin_inset space ~
5825 \begin_inset Formula $k$
5831 \begin_layout Standard
5832 \begin_inset Separator plain
5838 \begin_layout Theorem
5840 \begin_inset space ~
5844 \begin_inset Formula $k$
5855 in graphs with independence number at most
5856 \begin_inset space ~
5860 \begin_inset Formula $k$
5868 \begin_inset Formula $\Class{NL}$
5877 \begin_layout Subsection
5878 Finding Paths in Undirected Graphs
5882 \begin_inset Argument 1
5885 \begin_layout Plain Layout
5893 \begin_inset Argument 3
5896 \begin_layout Plain Layout
5903 \begin_inset Argument 4
5906 \begin_layout Plain Layout
5907 The Complexity of Finding Paths in Undirected Graphs
5908 \begin_inset Newline newline
5921 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5925 \begin_inset Formula $\Class{SL}$
5931 \begin_layout Corollary
5932 For undirected graphs, we can solve
5936 \begin_layout Itemize
5937 the reachability problem in logspace iff
5938 \begin_inset Formula $\Class L=\Class{SL}$
5944 \begin_layout Itemize
5945 the construction problem in logspace iff
5946 \begin_inset Flex Alternative
5949 \begin_layout Plain Layout
5950 \begin_inset Argument 1
5953 \begin_layout Plain Layout
5961 \begin_inset Argument 2
5964 \begin_layout Plain Layout
5971 \begin_inset Flex Alert
5974 \begin_layout Plain Layout
5975 \begin_inset Formula $\Class L=\Class{SL}$
5991 \begin_layout Itemize
5992 the optimization problem in logspace iff
5993 \begin_inset Flex Alternative
5996 \begin_layout Plain Layout
5997 \begin_inset Argument 1
6000 \begin_layout Plain Layout
6008 \begin_inset Argument 2
6011 \begin_layout Plain Layout
6018 \begin_inset Flex Alert
6021 \begin_layout Plain Layout
6022 \begin_inset Formula $\Class L=\Class{NL}$
6038 \begin_layout Itemize
6039 the approximation problem in logspace iff ?.
6045 \begin_layout Subsection
6046 The Approximation Scheme is Optimal
6050 \begin_inset Argument 3
6053 \begin_layout Plain Layout
6060 \begin_inset Argument 4
6063 \begin_layout Plain Layout
6064 The Approximation Scheme is Optimal
6073 \begin_layout Theorem
6074 Suppose there exists an approximation scheme for
6075 \begin_inset Formula $\Lang{tournament-shortest-path}$
6079 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6084 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6095 \begin_layout Enumerate
6096 Suppose the approximation scheme exists.
6097 \begin_inset Newline newline
6101 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6108 \begin_layout Enumerate
6110 \begin_inset Formula $(T,s,t)$
6115 \begin_inset Formula $n$
6118 be the number of vertices.
6121 \begin_layout Enumerate
6122 Run the approximation scheme for
6123 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6127 \begin_inset Newline newline
6131 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6137 \begin_layout Enumerate
6138 The resulting path has optimal length.
6143 \begin_layout Plain Layout