1 #LyX 2.3 created this file. For more info see http://www.lyx.org/
5 \save_transient_properties true
6 \origin /systemlyxdir/examples/
9 \beamertemplateshadingbackground{red!5}{structure!5}
11 \usepackage{beamerthemeshadow}
12 \usepackage{pgfnodes,pgfarrows,pgfheaps}
14 \beamertemplatetransparentcovereddynamicmedium
17 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
18 \logo{\pgfuseimage{icsi-logo}}
23 \newcommand{\Class}[1]{\operatorname{\mathchoice
29 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
31 % This gets defined by beamerbasecolor.sty, but only at the beginning of
33 \colorlet{averagebackgroundcolor}{normal text.bg}
35 \newcommand{\tape}[3]{%
36 \color{structure!30!averagebackgroundcolor}
37 \pgfmoveto{\pgfxy(-0.5,0)}
38 \pgflineto{\pgfxy(-0.6,0.1)}
39 \pgflineto{\pgfxy(-0.4,0.2)}
40 \pgflineto{\pgfxy(-0.6,0.3)}
41 \pgflineto{\pgfxy(-0.4,0.4)}
42 \pgflineto{\pgfxy(-0.5,0.5)}
43 \pgflineto{\pgfxy(4,0.5)}
44 \pgflineto{\pgfxy(4.1,0.4)}
45 \pgflineto{\pgfxy(3.9,0.3)}
46 \pgflineto{\pgfxy(4.1,0.2)}
47 \pgflineto{\pgfxy(3.9,0.1)}
48 \pgflineto{\pgfxy(4,0)}
53 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
54 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
57 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
60 \newcommand{\shorttape}[3]{%
61 \color{structure!30!averagebackgroundcolor}
62 \pgfmoveto{\pgfxy(-0.5,0)}
63 \pgflineto{\pgfxy(-0.6,0.1)}
64 \pgflineto{\pgfxy(-0.4,0.2)}
65 \pgflineto{\pgfxy(-0.6,0.3)}
66 \pgflineto{\pgfxy(-0.4,0.4)}
67 \pgflineto{\pgfxy(-0.5,0.5)}
68 \pgflineto{\pgfxy(1,0.5)}
69 \pgflineto{\pgfxy(1.1,0.4)}
70 \pgflineto{\pgfxy(0.9,0.3)}
71 \pgflineto{\pgfxy(1.1,0.2)}
72 \pgflineto{\pgfxy(0.9,0.1)}
73 \pgflineto{\pgfxy(1,0)}
78 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
79 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
82 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
85 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
86 {color(0pt)=(black); color(1cm)=(structure!65!white)}
87 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
88 {color(0pt)=(black); color(1cm)=(structure!55!white)}
89 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
90 {color(0pt)=(black); color(1cm)=(structure!45!white)}
91 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
92 {color(0pt)=(black); color(1cm)=(structure!35!white)}
93 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
94 {color(0pt)=(black); color(1cm)=(structure!25!white)}
95 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
96 {color(0pt)=(black); color(1cm)=(red!35!white)}
98 \newcommand{\heap}[5]{%
101 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
103 \begin{pgfmagnify}{1}{#1}
104 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
110 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
114 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
118 \newcommand{\langat}[2]{%
119 \color{black!30!beamerexample}
120 \pgfsetlinewidth{0.6pt}
121 \pgfsetendarrow{\pgfarrowdot}
122 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
123 \color{beamerexample}
124 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
127 \newcommand{\langatother}[2]{%
128 \color{black!30!beamerexample}
129 \pgfsetlinewidth{0.6pt}
130 \pgfsetendarrow{\pgfarrowdot}
131 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
132 \color{beamerexample}
133 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
137 \pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
140 \pgfdeclareradialshading{graphnode}
141 {\pgfpoint{-3pt}{3.6pt}}%
142 {color(0cm)=(beamerexample!15);
143 color(2.63pt)=(beamerexample!75);
144 color(5.26pt)=(beamerexample!70!black);
145 color(7.6pt)=(beamerexample!50!black);
146 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
148 \newcommand{\graphnode}[2]{
149 \pgfnodecircle{#1}[virtual]{#2}{8pt}
150 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
154 \use_default_options false
155 \maintain_unincluded_children false
157 \language_package default
160 \font_roman "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 0
186 \use_package mathdots 1
187 \use_package mathtools 0
188 \use_package mhchem 1
189 \use_package stackrel 0
190 \use_package stmaryrd 0
191 \use_package undertilde 0
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
580 \begin_layout Itemize
581 \begin_inset Argument item:2
584 \begin_layout Plain Layout
590 Every pair has a joust.
593 \begin_layout Itemize
594 \begin_inset Argument item:2
597 \begin_layout Plain Layout
603 In every joust one knight wins.
609 \begin_layout Standard
610 \begin_inset Separator plain
617 \begin_inset Argument 4
620 \begin_layout Plain Layout
621 Tournaments are Complete Directed Graphs
630 \begin_layout Columns
639 \begin_layout Standard
643 \begin_layout Plain Layout
647 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
650 \begin_layout Plain Layout
657 \begin_layout Plain Layout
661 pgfsetlinewidth{0.6pt}
664 \begin_layout Plain Layout
673 \begin_layout Plain Layout
682 \begin_layout Plain Layout
691 \begin_layout Plain Layout
700 \begin_layout Plain Layout
707 \begin_layout Plain Layout
715 pgfbox[center,center]{$v_2$}}
718 \begin_layout Plain Layout
726 pgfbox[center,center]{$v_3$}}
729 \begin_layout Plain Layout
737 pgfbox[center,center]{$v_4$}}
740 \begin_layout Plain Layout
748 pgfbox[center,center]{$v_1$}}
751 \begin_layout Plain Layout
758 \begin_layout Plain Layout
767 \begin_layout Plain Layout
771 pgfnodesetsepstart{2pt}
774 \begin_layout Plain Layout
778 pgfnodesetsepend{4pt}
781 \begin_layout Plain Layout
785 pgfnodeconnline{A}{B}
788 \begin_layout Plain Layout
792 pgfnodeconnline{A}{C}
795 \begin_layout Plain Layout
799 pgfnodeconnline{D}{A}
802 \begin_layout Plain Layout
806 pgfnodeconnline{C}{B}
809 \begin_layout Plain Layout
813 pgfnodeconnline{B}{D}
816 \begin_layout Plain Layout
820 pgfnodeconnline{D}{C}
823 \begin_layout Plain Layout
839 \begin_layout Definition
840 \begin_inset Argument 1
843 \begin_layout Plain Layout
861 \begin_layout Enumerate
865 \begin_layout Enumerate
866 with exactly one edge between
867 \begin_inset Newline newline
870 any two different vertices.
876 \begin_layout Standard
877 \begin_inset Separator plain
884 \begin_inset Argument 2
887 \begin_layout Plain Layout
894 \begin_inset Argument 4
897 \begin_layout Plain Layout
898 Tournaments Arise Naturally in Different Situations
907 \begin_layout ExampleBlock
908 \begin_inset Argument 2
911 \begin_layout Plain Layout
912 Applications in Ordering Theory
921 \begin_layout Standard
922 Elements in a set need to be sorted.
924 \begin_inset Newline newline
927 The comparison relation may be cyclic, however.
931 \begin_layout Standard
932 \begin_inset Separator plain
938 \begin_layout ExampleBlock
939 \begin_inset Argument 2
942 \begin_layout Plain Layout
943 Applications in Sociology
952 \begin_layout Standard
953 Several candidates apply for a position.
954 \begin_inset Newline newline
957 Reviewers decide for any two candidates whom they prefer.
962 \begin_layout Standard
963 \begin_inset Separator plain
969 \begin_layout ExampleBlock
970 \begin_inset Argument 2
973 \begin_layout Plain Layout
974 Applications in Structural Complexity Theory
983 \begin_layout Standard
985 \begin_inset Formula $L$
988 is given and a selector function
989 \begin_inset Formula $f$
993 \begin_inset Newline newline
996 It chooses from any two words the one more likely to be in
997 \begin_inset Formula $f$
1005 \begin_layout Subsection
1006 What Does ``Finding Paths'' Mean?
1010 \begin_inset Argument 4
1013 \begin_layout Plain Layout
1014 ``Finding Paths'' is Ambiguous
1024 \begin_inset Argument 2
1027 \begin_layout Plain Layout
1029 \begin_inset Flex Only
1032 \begin_layout Plain Layout
1033 \begin_inset Argument 1
1036 \begin_layout Plain Layout
1042 Path Finding Problems
1048 \begin_inset Flex Only
1051 \begin_layout Plain Layout
1052 \begin_inset Argument 1
1055 \begin_layout Plain Layout
1062 \begin_inset Formula $\Lang{reach}$
1071 \begin_inset Flex Only
1074 \begin_layout Plain Layout
1075 \begin_inset Argument 1
1078 \begin_layout Plain Layout
1084 the Construction Problem
1090 \begin_inset Flex Only
1093 \begin_layout Plain Layout
1094 \begin_inset Argument 1
1097 \begin_layout Plain Layout
1103 the Optimization Problem
1109 \begin_inset Flex Only
1112 \begin_layout Plain Layout
1113 \begin_inset Argument 1
1116 \begin_layout Plain Layout
1123 \begin_inset Formula $\Lang{distance}$
1132 \begin_inset Flex Only
1135 \begin_layout Plain Layout
1136 \begin_inset Argument 1
1139 \begin_layout Plain Layout
1145 the Approximation Problem
1159 \begin_layout Itemize
1169 \begin_inset Formula $G=(V,E)$
1181 \begin_inset Formula $s\in V$
1193 \begin_inset Formula $t\in V$
1199 \begin_layout Itemize
1200 \begin_inset Argument item:2
1203 \begin_layout Plain Layout
1216 \begin_inset space ~
1220 \begin_inset Formula $d$
1227 \begin_layout Plain Layout
1239 \begin_layout Itemize
1240 \begin_inset Argument item:2
1243 \begin_layout Plain Layout
1258 \begin_inset Formula $r>1$
1265 \begin_layout Standard
1269 \begin_layout Plain Layout
1281 \begin_layout Overprint
1282 \begin_inset Argument item:1
1285 \begin_layout Plain Layout
1295 \begin_layout Columns
1296 \begin_inset Argument 1
1299 \begin_layout Plain Layout
1309 \begin_layout Standard
1310 \begin_inset Flex Alternative
1313 \begin_layout Plain Layout
1314 \begin_inset Argument 1
1317 \begin_layout Plain Layout
1324 \begin_inset Argument 2
1327 \begin_layout Plain Layout
1331 \begin_layout Plain Layout
1351 \begin_layout Plain Layout
1368 \begin_layout ExampleBlock
1369 \begin_inset Argument 2
1372 \begin_layout Plain Layout
1382 \begin_layout Standard
1386 \begin_layout Plain Layout
1390 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1393 \begin_layout Plain Layout
1397 \begin_layout Plain Layout
1401 color{beamerexample}
1404 \begin_layout Plain Layout
1408 \begin_layout Plain Layout
1412 pgfsetlinewidth{0.6pt}
1415 \begin_layout Plain Layout
1419 \begin_layout Plain Layout
1428 \begin_layout Plain Layout
1432 \begin_layout Plain Layout
1441 \begin_layout Plain Layout
1445 \begin_layout Plain Layout
1454 \begin_layout Plain Layout
1458 \begin_layout Plain Layout
1467 \begin_layout Plain Layout
1471 \begin_layout Plain Layout
1475 \begin_layout Plain Layout
1479 \begin_layout Plain Layout
1486 \begin_layout Plain Layout
1490 \begin_layout Plain Layout
1498 pgfbox[center,center]{$t$}}
1501 \begin_layout Plain Layout
1505 \begin_layout Plain Layout
1513 pgfbox[center,center]{$s$}}
1516 \begin_layout Plain Layout
1520 \begin_layout Plain Layout
1524 \begin_layout Plain Layout
1528 \begin_layout Plain Layout
1532 color{beamerexample}
1535 \begin_layout Plain Layout
1539 \begin_layout Plain Layout
1548 \begin_layout Plain Layout
1552 \begin_layout Plain Layout
1556 pgfnodesetsepstart{2pt}
1559 \begin_layout Plain Layout
1563 \begin_layout Plain Layout
1567 pgfnodesetsepend{4pt}
1570 \begin_layout Plain Layout
1574 \begin_layout Plain Layout
1578 pgfnodeconnline{A}{B}
1581 \begin_layout Plain Layout
1585 \begin_layout Plain Layout
1589 pgfnodeconnline{A}{C}
1592 \begin_layout Plain Layout
1596 \begin_layout Plain Layout
1600 pgfnodeconnline{D}{A}
1603 \begin_layout Plain Layout
1607 \begin_layout Plain Layout
1611 pgfnodeconnline{C}{B}
1614 \begin_layout Plain Layout
1618 \begin_layout Plain Layout
1622 pgfnodeconnline{B}{D}
1625 \begin_layout Plain Layout
1629 \begin_layout Plain Layout
1633 pgfnodeconnline{D}{C}
1636 \begin_layout Plain Layout
1640 \begin_layout Plain Layout
1644 \begin_layout Plain Layout
1648 \begin_layout Plain Layout
1658 pgfbox[left,center]{, $d=2$}}}
1661 \begin_layout Plain Layout
1665 \begin_layout Plain Layout
1675 pgfbox[left,center]{, $r=1.5$}}}
1678 \begin_layout Plain Layout
1682 \begin_layout Plain Layout
1692 pgfbox[left,center]{, $r=1.25$}}}
1695 \begin_layout Plain Layout
1699 \begin_layout Plain Layout
1712 \begin_layout Standard
1713 \begin_inset Flex Only
1716 \begin_layout Plain Layout
1717 \begin_inset Argument 1
1720 \begin_layout Plain Layout
1730 \begin_layout Plain Layout
1747 \begin_layout ExampleBlock
1748 \begin_inset Argument 1
1751 \begin_layout Plain Layout
1758 \begin_inset Argument 2
1761 \begin_layout Plain Layout
1771 \begin_layout Standard
1775 \begin_layout Plain Layout
1779 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1782 \begin_layout Plain Layout
1789 \begin_layout Plain Layout
1793 color{beamerexample}
1796 \begin_layout Plain Layout
1800 pgfsetlinewidth{0.6pt}
1803 \begin_layout Plain Layout
1812 \begin_layout Plain Layout
1821 \begin_layout Plain Layout
1830 \begin_layout Plain Layout
1839 \begin_layout Plain Layout
1846 \begin_layout Plain Layout
1854 pgfbox[center,center]{$t$}}
1857 \begin_layout Plain Layout
1865 pgfbox[center,center]{$s$}}
1868 \begin_layout Plain Layout
1872 color{beamerexample}
1875 \begin_layout Plain Layout
1884 \begin_layout Plain Layout
1888 pgfnodesetsepstart{2pt}
1891 \begin_layout Plain Layout
1895 pgfnodesetsepend{4pt}
1898 \begin_layout Plain Layout
1904 pgfnodeconnline{A}{B}}
1907 \begin_layout Plain Layout
1913 pgfnodeconnline{A}{C}}
1916 \begin_layout Plain Layout
1922 pgfnodeconnline{D}{A}}
1925 \begin_layout Plain Layout
1931 pgfnodeconnline{C}{B}}
1934 \begin_layout Plain Layout
1938 pgfnodeconnline{B}{D}
1941 \begin_layout Plain Layout
1945 pgfnodeconnline{D}{C}
1948 \begin_layout Plain Layout
1953 \begin_layout Plain Layout
1963 pgfbox[left,center]{
1968 \begin_layout Plain Layout
1983 \begin_layout Overprint
1984 \begin_inset Argument item:1
1987 \begin_layout Plain Layout
1998 \begin_inset Argument 2
2001 \begin_layout Plain Layout
2002 Variants of Path Finding Problems
2011 \begin_layout Description
2012 \begin_inset Argument item:1
2015 \begin_layout Plain Layout
2022 \begin_inset space ~
2025 Problem: Is there a path from
2026 \begin_inset Formula $s$
2030 \begin_inset space ~
2034 \begin_inset Formula $t$
2038 \begin_inset Argument 2
2041 \begin_layout Plain Layout
2042 Approximation Problem:
2050 \begin_layout Description
2051 \begin_inset Argument item:1
2054 \begin_layout Plain Layout
2061 \begin_inset space ~
2064 Problem: Construct a path from
2065 \begin_inset Formula $s$
2069 \begin_inset space ~
2073 \begin_inset Formula $t$
2079 \begin_layout Description
2080 \begin_inset Argument item:1
2083 \begin_layout Plain Layout
2090 \begin_inset space ~
2093 Problem: Construct a shortest path from
2094 \begin_inset Formula $s$
2098 \begin_inset space ~
2102 \begin_inset Formula $t$
2108 \begin_layout Description
2109 \begin_inset Argument item:1
2112 \begin_layout Plain Layout
2119 \begin_inset space ~
2122 Problem: Is the distance of
2123 \begin_inset Formula $s$
2127 \begin_inset space ~
2131 \begin_inset Formula $t$
2135 \begin_inset space ~
2139 \begin_inset Formula $d$
2145 \begin_layout Description
2146 \begin_inset Argument item:1
2149 \begin_layout Plain Layout
2156 \begin_inset space ~
2159 Problem: Construct a path from
2160 \begin_inset Formula $s$
2164 \begin_inset space ~
2168 \begin_inset Formula $t$
2172 \begin_inset Newline newline
2175 approximately their distance.
2181 \begin_layout Section
2185 \begin_layout Subsection
2186 Standard Complexity Classes
2189 \begin_layout Standard
2193 \begin_layout Plain Layout
2197 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2199 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2209 \begin_inset Argument 4
2212 \begin_layout Plain Layout
2213 The Classes L and NL are Defined via
2214 \begin_inset Newline newline
2217 Logspace Turing Machines
2226 \begin_layout Standard
2230 \begin_layout Plain Layout
2234 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2237 \begin_layout Plain Layout
2246 \begin_layout Plain Layout
2250 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2253 \begin_layout Plain Layout
2260 \begin_layout Plain Layout
2269 \begin_layout Plain Layout
2273 tape{}{output tape (write only)}{10690836937182}}
2276 \begin_layout Plain Layout
2281 \begin_layout Plain Layout
2288 \begin_layout Plain Layout
2297 \begin_layout Plain Layout
2301 shorttape{work tape (read/write), $O(
2303 log n)$ symbols}{}{42}}
2306 \begin_layout Plain Layout
2315 \begin_layout Plain Layout
2319 pgfbox[center,center]{
2321 pgfuseimage{computer}}}
2324 \begin_layout Plain Layout
2329 \begin_layout Plain Layout
2333 pgfsetlinewidth{0.6pt}
2336 \begin_layout Plain Layout
2343 \begin_layout Plain Layout
2352 \begin_layout Plain Layout
2356 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2359 \begin_layout Plain Layout
2365 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2368 \begin_layout Plain Layout
2374 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2377 \begin_layout Plain Layout
2390 \begin_layout Standard
2391 \begin_inset Separator plain
2398 \begin_inset Argument 4
2401 \begin_layout Plain Layout
2402 Logspace Turing Machines Are Quite Powerful
2412 \begin_inset Argument 2
2415 \begin_layout Plain Layout
2416 Deterministic logspace machines can compute
2425 \begin_layout Itemize
2426 addition, multiplication, and even division
2429 \begin_layout Itemize
2430 reductions used in completeness proofs,
2433 \begin_layout Itemize
2434 reachability in forests.
2443 \begin_inset Argument 2
2446 \begin_layout Plain Layout
2447 Non-deterministic logspace machines can compute
2456 \begin_layout Itemize
2457 reachability in graphs,
2460 \begin_layout Itemize
2461 non-reachability in graphs,
2464 \begin_layout Itemize
2465 satisfiability with two literals per clause.
2470 \begin_layout Standard
2471 \begin_inset Separator plain
2478 \begin_inset Argument 1
2481 \begin_layout Plain Layout
2488 \begin_inset Argument 3
2491 \begin_layout Plain Layout
2498 \begin_inset Argument 4
2501 \begin_layout Plain Layout
2502 The Complexity Class Hierarchy
2511 \begin_layout Standard
2515 \begin_layout Plain Layout
2519 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2522 \begin_layout Plain Layout
2526 pgfsetlinewidth{0.8pt}
2529 \begin_layout Plain Layout
2538 \begin_layout Plain Layout
2542 pgfsetdash{{2pt}}{0pt}
2545 \begin_layout Plain Layout
2553 Class{NC}^2$}{black!50!structure}{2}}
2556 \begin_layout Plain Layout
2562 Class{NL}$}{black!50!structure}{3}
2565 \begin_layout Plain Layout
2571 Class{L}$}{black!50!structure}{4}
2574 \begin_layout Plain Layout
2585 \begin_layout Plain Layout
2591 Class{NC}^1}$}{black!50!structure}{5}
2594 \begin_layout Plain Layout
2599 \begin_layout Plain Layout
2606 \begin_layout Plain Layout
2617 \begin_layout Plain Layout
2623 Class{AC}^0}$}{black}{6}
2626 \begin_layout Plain Layout
2631 \begin_layout Plain Layout
2635 pgfsetlinewidth{1.0pt}
2638 \begin_layout Plain Layout
2645 \begin_layout Plain Layout
2649 pgfxyline(-5,0)(5,0)
2652 \begin_layout Plain Layout
2663 \begin_layout Plain Layout
2673 operatorname{forest}}$}}
2676 \begin_layout Plain Layout
2687 \begin_layout Plain Layout
2706 \begin_layout Plain Layout
2725 \begin_layout Plain Layout
2738 \begin_layout Plain Layout
2746 operatorname{forest}}$,}
2751 \begin_layout Plain Layout
2759 operatorname{forest}}$,}
2764 \begin_layout Plain Layout
2772 operatorname{path}}$,}
2777 \begin_layout Plain Layout
2785 operatorname{path}}$}}}
2788 \begin_layout Plain Layout
2793 \begin_layout Plain Layout
2803 operatorname{tourn}}$}}
2806 \begin_layout Plain Layout
2819 \begin_layout Plain Layout
2827 operatorname{tourn}}$,}
2832 \begin_layout Plain Layout
2843 \begin_layout Plain Layout
2852 \begin_layout Plain Layout
2857 \begin_layout Plain Layout
2863 pgfsetdash{{1pt}}{0pt}%
2866 \begin_layout Plain Layout
2874 operatorname{tourn}}$''}
2877 \begin_layout Plain Layout
2882 \begin_layout Plain Layout
2895 \begin_layout Standard
2896 \begin_inset Separator plain
2903 \begin_inset Argument 4
2906 \begin_layout Plain Layout
2907 The Circuit Complexity Classes AC
2908 \begin_inset Formula $^{0}$
2912 \begin_inset Formula $^{1}$
2916 \begin_inset Formula $^{2}$
2920 \begin_inset Newline newline
2923 Limit the Circuit Depth
2932 \begin_layout Standard
2936 \begin_layout Plain Layout
2945 \begin_layout Plain Layout
2957 \begin_layout Columns
2958 \begin_inset Argument 1
2961 \begin_layout Plain Layout
2971 \begin_layout Column
2976 \begin_inset Argument 2
2979 \begin_layout Plain Layout
2981 \begin_inset Formula $\Class{AC}^{0}$
2993 \begin_layout Itemize
2994 \begin_inset Formula $O(1)$
3000 \begin_layout Itemize
3005 \begin_layout Examples
3010 \begin_layout Itemize
3011 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3017 \begin_layout Itemize
3018 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3029 \begin_layout Column
3034 \begin_inset Argument 2
3037 \begin_layout Plain Layout
3039 \begin_inset Formula $\Class{NC}^{1}$
3051 \begin_layout Itemize
3052 \begin_inset Formula $O(\log n)$
3058 \begin_layout Itemize
3063 \begin_layout Examples
3068 \begin_layout Itemize
3069 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3075 \begin_layout Itemize
3076 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3082 \begin_layout Itemize
3083 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3094 \begin_layout Column
3099 \begin_inset Argument 2
3102 \begin_layout Plain Layout
3104 \begin_inset Formula $\Class{NC}^{2}$
3116 \begin_layout Itemize
3117 \begin_inset Formula $O(\log^{2}n)$
3123 \begin_layout Itemize
3128 \begin_layout Examples
3133 \begin_layout Itemize
3134 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3143 \begin_layout AgainFrame
3144 \begin_inset Argument 1
3147 \begin_layout Plain Layout
3156 \begin_layout Subsection
3157 Standard Complexity Results on Finding Paths
3161 \begin_inset Argument 4
3164 \begin_layout Plain Layout
3165 All Variants of Finding Paths in Directed Graphs
3166 \begin_inset Newline newline
3169 Are Equally Difficult
3179 \begin_inset Formula $\Lang{reach}$
3183 \begin_inset Formula $\Lang{distance}$
3187 \begin_inset Formula $\Class{NL}$
3198 \begin_layout Corollary
3199 For directed graphs, we can solve
3203 \begin_layout Itemize
3204 the reachability problem in logspace iff
3205 \begin_inset Formula $\Class{L}=\Class{NL}$
3211 \begin_layout Itemize
3212 the construction problem in logspace iff
3213 \begin_inset Formula $\Class{L}=\Class{NL}$
3219 \begin_layout Itemize
3220 the optimization problem in logspace iff
3221 \begin_inset Formula $\Class{L}=\Class{NL}$
3227 \begin_layout Itemize
3228 the approximation problem in logspace iff
3229 \begin_inset Formula $\Class{L}=\Class{NL}$
3237 \begin_layout AgainFrame
3238 \begin_inset Argument 1
3241 \begin_layout Plain Layout
3251 \begin_inset Argument 4
3254 \begin_layout Plain Layout
3255 Finding Paths in Forests and Directed Paths is Easy,
3256 \begin_inset Newline newline
3269 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3273 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3277 \begin_inset Formula $\Class{L}$
3283 \begin_layout Standard
3284 \begin_inset Separator plain
3291 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3295 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3299 \begin_inset Formula $\Class{L}$
3306 \begin_layout AgainFrame
3307 \begin_inset Argument 1
3310 \begin_layout Plain Layout
3319 \begin_layout Section
3320 Finding Paths in Tournaments
3323 \begin_layout Subsection
3324 Complexity of: Does a Path Exist?
3328 \begin_inset Argument 4
3331 \begin_layout Plain Layout
3332 Definition of the Tournament Reachability Problem
3341 \begin_layout Definition
3347 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3355 \begin_inset Formula $(T,s,t)$
3362 \begin_layout Enumerate
3363 \begin_inset Formula $T=(V,E)$
3369 \begin_layout Enumerate
3370 there exists a path from
3371 \begin_inset space ~
3375 \begin_inset Formula $s$
3379 \begin_inset space ~
3383 \begin_inset Formula $t$
3391 \begin_layout Standard
3392 \begin_inset Separator plain
3399 \begin_inset Argument 4
3402 \begin_layout Plain Layout
3403 The Tournament Reachability Problem is Very Easy
3412 \begin_layout Theorem
3413 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3423 \begin_layout AlertBlock
3424 \begin_inset Argument 2
3427 \begin_layout Plain Layout
3437 \begin_layout Itemize
3439 \begin_inset Quotes eld
3443 \begin_inset Quotes erd
3447 \begin_inset Formula $\Lang{reach}$
3451 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3457 \begin_layout Itemize
3458 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3466 \begin_layout AgainFrame
3467 \begin_inset Argument 1
3470 \begin_layout Plain Layout
3479 \begin_layout Subsection
3480 Complexity of: Construct a Shortest Path
3484 \begin_inset Argument 4
3487 \begin_layout Plain Layout
3488 Finding a Shortest Path Is as Difficult as
3489 \begin_inset Newline newline
3492 the Distance Problem
3501 \begin_layout Definition
3507 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3515 \begin_inset Formula $(T,s,t,d)$
3522 \begin_layout Enumerate
3523 \begin_inset Formula $T=(V,E)$
3526 is a tournament in which
3529 \begin_layout Enumerate
3531 \begin_inset Formula $s$
3535 \begin_inset space ~
3539 \begin_inset Formula $t$
3543 \begin_inset space ~
3547 \begin_inset Formula $d$
3555 \begin_layout Standard
3556 \begin_inset Separator plain
3563 \begin_inset Argument 4
3566 \begin_layout Plain Layout
3567 The Tournament Distance Problem is Hard
3576 \begin_layout Theorem
3577 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3581 \begin_inset Formula $\Class{NL}$
3587 \begin_layout Standard
3588 \begin_inset space \hfill{}
3595 \begin_layout Plain Layout
3599 hyperlink{hierarchy<6>}{
3601 beamerskipbutton{Skip Proof}}
3613 \begin_layout Corollary
3614 Shortest path in tournaments can be constructed
3615 \begin_inset Newline newline
3618 in logarithmic space, iff
3619 \begin_inset Formula $\Class{L}=\Class{NL}$
3629 \begin_layout Corollary
3630 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3637 \begin_layout Standard
3638 \begin_inset Separator plain
3645 \begin_inset Argument 4
3648 \begin_layout Plain Layout
3650 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3662 \begin_layout Standard
3666 \begin_layout Plain Layout
3678 \begin_layout Columns
3679 \begin_inset Argument 1
3682 \begin_layout Plain Layout
3692 \begin_layout Column
3696 \begin_layout Standard
3700 \begin_layout Plain Layout
3715 \begin_inset Argument 2
3718 \begin_layout Plain Layout
3720 \begin_inset Formula $\Lang{reach}$
3724 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3736 \begin_layout Enumerate
3737 \begin_inset Argument item:2
3740 \begin_layout Plain Layout
3747 \begin_inset Formula $(G,s,t)$
3751 \begin_inset Formula $\Lang{reach}$
3757 \begin_layout Enumerate
3758 \begin_inset Argument item:2
3761 \begin_layout Plain Layout
3768 \begin_inset Formula $G$
3772 \begin_inset Formula $G'$
3778 \begin_layout Enumerate
3779 \begin_inset Argument item:2
3782 \begin_layout Plain Layout
3789 \begin_inset Newline newline
3793 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3800 \begin_layout Standard
3801 \begin_inset Separator plain
3808 \begin_inset Argument 2
3811 \begin_layout Plain Layout
3818 \begin_inset Argument 1
3821 \begin_layout Plain Layout
3831 \begin_layout Enumerate
3832 \begin_inset Argument item:2
3835 \begin_layout Plain Layout
3842 \begin_inset space ~
3846 \begin_inset Formula $G$
3850 \begin_inset Newline newline
3854 \begin_inset space ~
3858 \begin_inset Formula $G'$
3864 \begin_layout Enumerate
3865 \begin_inset Argument item:2
3868 \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'$
3898 \begin_layout Column
3902 \begin_layout Example
3906 \begin_layout Plain Layout
3910 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3913 \begin_layout Plain Layout
3917 color{beamerexample}
3920 \begin_layout Plain Layout
3924 pgfsetlinewidth{0.6pt}
3927 \begin_layout Plain Layout
3936 \begin_layout Plain Layout
3945 \begin_layout Plain Layout
3954 \begin_layout Plain Layout
3963 \begin_layout Plain Layout
3970 \begin_layout Plain Layout
3978 pgfbox[center,center]{$s$}}
3981 \begin_layout Plain Layout
3989 pgfbox[center,center]{$t$}}
3992 \begin_layout Plain Layout
3996 color{beamerexample}
3999 \begin_layout Plain Layout
4008 \begin_layout Plain Layout
4012 pgfnodesetsepstart{2pt}
4015 \begin_layout Plain Layout
4019 pgfnodesetsepend{2pt}
4022 \begin_layout Plain Layout
4028 pgfnodeconnline{B}{A}}
4031 \begin_layout Plain Layout
4037 pgfnodeconnline{B}{C}}
4040 \begin_layout Plain Layout
4046 pgfnodeconnline{C}{D}}
4049 \begin_layout Plain Layout
4055 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4058 \begin_layout Plain Layout
4066 pgfbox[left,center]{$G
4071 \begin_layout Plain Layout
4078 \begin_layout Plain Layout
4086 pgfbox[left,center]{$G'
4091 \begin_layout Plain Layout
4100 \begin_layout Plain Layout
4109 \begin_layout Plain Layout
4118 \begin_layout Plain Layout
4127 \begin_layout Plain Layout
4136 \begin_layout Plain Layout
4145 \begin_layout Plain Layout
4154 \begin_layout Plain Layout
4163 \begin_layout Plain Layout
4172 \begin_layout Plain Layout
4181 \begin_layout Plain Layout
4190 \begin_layout Plain Layout
4199 \begin_layout Plain Layout
4208 \begin_layout Plain Layout
4217 \begin_layout Plain Layout
4226 \begin_layout Plain Layout
4235 \begin_layout Plain Layout
4242 \begin_layout Plain Layout
4250 pgfbox[center,center]{$s'$}}
4253 \begin_layout Plain Layout
4261 pgfbox[center,center]{$t'$}}
4264 \begin_layout Plain Layout
4269 \begin_layout Plain Layout
4274 \begin_layout Plain Layout
4281 \begin_layout Plain Layout
4285 pgfsetlinewidth{0.4pt}
4288 \begin_layout Plain Layout
4292 color{beamerexample!25!averagebackgroundcolor}
4295 \begin_layout Plain Layout
4299 pgfnodeconnline{A2}{C1}
4302 \begin_layout Plain Layout
4306 pgfnodeconnline{A2}{D1}
4309 \begin_layout Plain Layout
4313 pgfnodeconnline{B2}{A1}
4316 \begin_layout Plain Layout
4320 pgfnodeconnline{B2}{C1}
4323 \begin_layout Plain Layout
4327 pgfnodeconnline{B2}{D1}
4330 \begin_layout Plain Layout
4334 pgfnodeconnline{C2}{D1}
4337 \begin_layout Plain Layout
4341 pgfnodeconnline{D2}{A1}
4344 \begin_layout Plain Layout
4348 pgfnodeconnline{D2}{B1}
4351 \begin_layout Plain Layout
4355 pgfnodeconnline{A3}{C2}
4358 \begin_layout Plain Layout
4362 pgfnodeconnline{A3}{D2}
4365 \begin_layout Plain Layout
4369 pgfnodeconnline{B3}{A2}
4372 \begin_layout Plain Layout
4376 pgfnodeconnline{B3}{C2}
4379 \begin_layout Plain Layout
4383 pgfnodeconnline{B3}{D2}
4386 \begin_layout Plain Layout
4390 pgfnodeconnline{C3}{D2}
4393 \begin_layout Plain Layout
4397 pgfnodeconnline{D3}{A2}
4400 \begin_layout Plain Layout
4404 pgfnodeconnline{D3}{B2}
4407 \begin_layout Plain Layout
4411 pgfnodeconnline{A4}{C3}
4414 \begin_layout Plain Layout
4418 pgfnodeconnline{A4}{D3}
4421 \begin_layout Plain Layout
4425 pgfnodeconnline{B4}{A3}
4428 \begin_layout Plain Layout
4432 pgfnodeconnline{B4}{C3}
4435 \begin_layout Plain Layout
4439 pgfnodeconnline{B4}{D3}
4442 \begin_layout Plain Layout
4446 pgfnodeconnline{C4}{D3}
4449 \begin_layout Plain Layout
4453 pgfnodeconnline{D4}{A3}
4456 \begin_layout Plain Layout
4460 pgfnodeconnline{D4}{B3}
4463 \begin_layout Plain Layout
4472 \begin_layout Plain Layout
4476 pgfnodeconnline{A1}{B1}
4479 \begin_layout Plain Layout
4483 pgfnodeconnline{B1}{C1}
4486 \begin_layout Plain Layout
4490 pgfnodeconnline{C1}{D1}
4493 \begin_layout Plain Layout
4497 pgfnodeconnline{A2}{B2}
4500 \begin_layout Plain Layout
4504 pgfnodeconnline{B2}{C2}
4507 \begin_layout Plain Layout
4511 pgfnodeconnline{C2}{D2}
4514 \begin_layout Plain Layout
4518 pgfnodeconnline{A3}{B3}
4521 \begin_layout Plain Layout
4525 pgfnodeconnline{B3}{C3}
4528 \begin_layout Plain Layout
4532 pgfnodeconnline{C3}{D3}
4535 \begin_layout Plain Layout
4539 pgfnodeconnline{A4}{B4}
4542 \begin_layout Plain Layout
4546 pgfnodeconnline{B4}{C4}
4549 \begin_layout Plain Layout
4553 pgfnodeconnline{C4}{D4}
4556 \begin_layout Plain Layout
4563 \begin_layout Plain Layout
4567 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4570 \begin_layout Plain Layout
4574 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4577 \begin_layout Plain Layout
4581 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4584 \begin_layout Plain Layout
4588 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4591 \begin_layout Plain Layout
4595 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4598 \begin_layout Plain Layout
4602 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4605 \begin_layout Plain Layout
4609 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4612 \begin_layout Plain Layout
4616 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4619 \begin_layout Plain Layout
4623 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4626 \begin_layout Plain Layout
4630 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4633 \begin_layout Plain Layout
4637 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4640 \begin_layout Plain Layout
4644 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4647 \begin_layout Plain Layout
4651 color{beamerexample}
4654 \begin_layout Plain Layout
4658 pgfsetlinewidth{0.6pt}
4661 \begin_layout Plain Layout
4666 \begin_layout Plain Layout
4673 \begin_layout Plain Layout
4680 \begin_layout Plain Layout
4684 pgfnodeconnline{B1}{A2}
4687 \begin_layout Plain Layout
4691 pgfnodeconnline{B2}{A3}
4694 \begin_layout Plain Layout
4698 pgfnodeconnline{B3}{A4}
4701 \begin_layout Plain Layout
4706 \begin_layout Plain Layout
4713 \begin_layout Plain Layout
4720 \begin_layout Plain Layout
4724 pgfnodeconnline{B1}{C2}
4727 \begin_layout Plain Layout
4731 pgfnodeconnline{B2}{C3}
4734 \begin_layout Plain Layout
4738 pgfnodeconnline{B3}{C4}
4741 \begin_layout Plain Layout
4746 \begin_layout Plain Layout
4753 \begin_layout Plain Layout
4760 \begin_layout Plain Layout
4764 pgfnodeconnline{C1}{D2}
4767 \begin_layout Plain Layout
4773 pgfnodeconnline{C2}{D3}}
4776 \begin_layout Plain Layout
4782 pgfnodeconnline{C3}{D4}}
4785 \begin_layout Plain Layout
4790 \begin_layout Plain Layout
4797 \begin_layout Plain Layout
4804 \begin_layout Plain Layout
4810 pgfnodeconnline{A1}{C2}}
4813 \begin_layout Plain Layout
4819 pgfnodeconnline{A2}{C3}}
4822 \begin_layout Plain Layout
4826 pgfnodeconnline{A3}{C4}
4829 \begin_layout Plain Layout
4834 \begin_layout Plain Layout
4841 \begin_layout Plain Layout
4848 \begin_layout Plain Layout
4854 pgfnodeconnline{A1}{A2}}
4857 \begin_layout Plain Layout
4861 pgfnodeconnline{A2}{A3}
4864 \begin_layout Plain Layout
4868 pgfnodeconnline{A3}{A4}
4871 \begin_layout Plain Layout
4875 pgfnodeconnline{B1}{B2}
4878 \begin_layout Plain Layout
4882 pgfnodeconnline{B2}{B3}
4885 \begin_layout Plain Layout
4889 pgfnodeconnline{B3}{B4}
4892 \begin_layout Plain Layout
4896 pgfnodeconnline{C1}{C2}
4899 \begin_layout Plain Layout
4903 pgfnodeconnline{C2}{C3}
4906 \begin_layout Plain Layout
4910 pgfnodeconnline{C3}{C4}
4913 \begin_layout Plain Layout
4917 pgfnodeconnline{D1}{D2}
4920 \begin_layout Plain Layout
4924 pgfnodeconnline{D2}{D3}
4927 \begin_layout Plain Layout
4933 pgfnodeconnline{D3}{D4}}
4936 \begin_layout Plain Layout
4941 \begin_layout Plain Layout
4955 \begin_layout AgainFrame
4956 \begin_inset Argument 1
4959 \begin_layout Plain Layout
4968 \begin_layout Subsection
4969 Complexity of: Approximating the Shortest Path
4973 \begin_inset Argument 4
4976 \begin_layout Plain Layout
4977 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
4986 \begin_layout Definition
4991 approximation scheme for
4992 \begin_inset Formula $\Lang{tournament-shortest-path}$
5003 \begin_layout Enumerate
5005 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5011 \begin_layout Enumerate
5013 \begin_inset Formula $r>1$
5019 \begin_layout Standard
5023 \begin_layout Itemize
5025 \begin_inset Formula $s$
5029 \begin_inset space ~
5033 \begin_inset Formula $t$
5037 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5045 \begin_layout Standard
5046 \begin_inset Separator plain
5053 \begin_inset Argument 4
5056 \begin_layout Plain Layout
5057 There Exists a Logspace Approximation Scheme for
5058 \begin_inset Newline newline
5061 the Tournament Shortest Path Problem
5070 \begin_layout Theorem
5071 There exists an approximation scheme for
5072 \begin_inset Formula $\Lang{tournament-shortest-path}$
5076 \begin_inset Formula $1<r<2$
5080 \begin_inset Formula
5082 O\left(\log|V|\log\frac{1}{r-1}\right).
5094 \begin_layout Corollary
5095 In tournaments, paths can be constructed in logarithmic space.
5098 \begin_layout Standard
5099 \begin_inset space \hfill{}
5106 \begin_layout Plain Layout
5110 hyperlink{optimality}{
5112 beamergotobutton{More Details}}
5121 \begin_layout AgainFrame
5122 \begin_inset Argument 1
5125 \begin_layout Plain Layout
5134 \begin_layout Standard
5135 \begin_inset Note Note
5138 \begin_layout Plain Layout
5139 If a frame includes a program listing, the frame needs to be marked as
5140 \begin_inset Quotes eld
5144 \begin_inset Quotes erd
5149 has the FragileFrame layout for this.
5157 \begin_layout FragileFrame
5158 \begin_inset Argument 4
5161 \begin_layout Plain Layout
5162 Just a frame with a program code listing
5170 \begin_layout FragileFrame
5171 This is some program code:
5175 \begin_layout Standard
5176 \begin_inset listings
5177 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5181 \begin_layout Plain Layout
5186 \begin_layout Plain Layout
5188 'this is a python function'
5191 \begin_layout Plain Layout
5196 \begin_layout Plain Layout
5201 \begin_layout Plain Layout
5203 'This is a German word: Tschüs'
5206 \begin_layout Plain Layout
5211 \begin_layout Plain Layout
5216 \begin_layout Plain Layout
5218 'this is a python function'
5221 \begin_layout Plain Layout
5232 \begin_layout Section*
5236 \begin_layout Subsection*
5241 \begin_inset Argument 4
5244 \begin_layout Plain Layout
5255 \begin_inset Argument 2
5258 \begin_layout Plain Layout
5268 \begin_layout Itemize
5282 \begin_inset Formula $\Class{AC}^{0}$
5291 \begin_layout Itemize
5296 logspace approximation scheme
5308 shortest paths in tournaments.
5311 \begin_layout Itemize
5325 \begin_inset Formula $\Class{NL}$
5334 \begin_layout Standard
5335 \begin_inset Separator plain
5342 \begin_inset Argument 2
5345 \begin_layout Plain Layout
5355 \begin_layout Itemize
5356 The same results apply to graphs with
5357 \begin_inset Newline newline
5360 bounded independence number.
5361 \begin_inset space \hfill{}
5368 \begin_layout Plain Layout
5372 hyperlink{independence}{
5374 beamergotobutton{More Details}}
5382 \begin_layout Itemize
5383 The complexity of finding paths in undirected graphs
5384 \begin_inset Newline newline
5388 \begin_inset space \hfill{}
5395 \begin_layout Plain Layout
5399 hyperlink{undirected}{
5401 beamergotobutton{More Details}}
5411 \begin_layout Subsection*
5416 \begin_inset Argument 4
5419 \begin_layout Plain Layout
5429 \begin_layout Standard
5433 \begin_layout Plain Layout
5437 beamertemplatebookbibitems
5445 \begin_layout Bibliography
5446 \begin_inset CommandInset bibitem
5447 LatexCommand bibitem
5454 \begin_inset space ~
5462 \begin_layout Plain Layout
5473 Topics on Tournaments.
5480 \begin_layout Plain Layout
5489 Holt, Rinehart, and Winston, 1968.
5494 \begin_layout Plain Layout
5498 beamertemplatearticlebibitems
5506 \begin_layout Bibliography
5507 \begin_inset CommandInset bibitem
5508 LatexCommand bibitem
5509 key "NickelsenT2002"
5515 \begin_inset space ~
5518 Arfst Nickelsen and Till Tantau.
5523 \begin_layout Plain Layout
5532 On reachability in graphs with bounded independence number.
5536 \begin_layout Plain Layout
5550 , Springer-Verlag, 2002.
5553 \begin_layout Bibliography
5554 \begin_inset CommandInset bibitem
5555 LatexCommand bibitem
5562 \begin_inset space ~
5569 \begin_layout Plain Layout
5578 A logspace approximation scheme for the shortest path problem for graphs
5579 with bounded independence number.
5583 \begin_layout Plain Layout
5597 , Springer-Verlag, 2004.
5602 \begin_layout Plain Layout
5615 \begin_layout Standard
5620 \begin_layout Plain Layout
5624 AtBeginSubsection[]{}
5632 \begin_layout Section
5636 \begin_layout Subsection
5637 Graphs With Bounded Independence Number
5641 \begin_inset Argument 3
5644 \begin_layout Plain Layout
5651 \begin_inset Argument 4
5654 \begin_layout Plain Layout
5655 Definition of Independence Number of a Graph
5664 \begin_layout Definition
5674 \begin_inset Formula $\alpha(G)$
5678 \begin_inset Newline newline
5681 is the maximum number of vertices we can pick,
5682 \begin_inset Newline newline
5685 such that there is no edge between them.
5688 \begin_layout Example
5689 Tournaments have independence number 1.
5694 \begin_layout Standard
5695 \begin_inset Separator plain
5702 \begin_inset Argument 4
5705 \begin_layout Plain Layout
5706 The Results for Tournaments also Apply to
5707 \begin_inset Newline newline
5710 Graphs With Bounded Independence Number
5719 \begin_layout Theorem
5721 \begin_inset space ~
5725 \begin_inset Formula $k$
5736 in graphs with independence number
5737 \begin_inset Newline newline
5741 \begin_inset space ~
5745 \begin_inset Formula $k$
5749 \begin_inset Formula $\Class{AC}^{0}$
5755 \begin_layout Standard
5756 \begin_inset Separator plain
5762 \begin_layout Theorem
5764 \begin_inset space ~
5768 \begin_inset Formula $k$
5775 logspace approximation scheme
5779 for approximating the shortest path in graphs with independence number at
5781 \begin_inset space ~
5785 \begin_inset Formula $k$
5791 \begin_layout Standard
5792 \begin_inset Separator plain
5798 \begin_layout Theorem
5800 \begin_inset space ~
5804 \begin_inset Formula $k$
5815 in graphs with independence number at most
5816 \begin_inset space ~
5820 \begin_inset Formula $k$
5828 \begin_inset Formula $\Class{NL}$
5837 \begin_layout Subsection
5838 Finding Paths in Undirected Graphs
5842 \begin_inset Argument 1
5845 \begin_layout Plain Layout
5852 \begin_inset Argument 3
5855 \begin_layout Plain Layout
5862 \begin_inset Argument 4
5865 \begin_layout Plain Layout
5866 The Complexity of Finding Paths in Undirected Graphs
5867 \begin_inset Newline newline
5880 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5884 \begin_inset Formula $\Class{SL}$
5890 \begin_layout Corollary
5891 For undirected graphs, we can solve
5895 \begin_layout Itemize
5896 the reachability problem in logspace iff
5897 \begin_inset Formula $\Class L=\Class{SL}$
5903 \begin_layout Itemize
5904 the construction problem in logspace iff
5905 \begin_inset Flex Alternative
5908 \begin_layout Plain Layout
5909 \begin_inset Argument 1
5912 \begin_layout Plain Layout
5919 \begin_inset Argument 2
5922 \begin_layout Plain Layout
5929 \begin_inset Flex Alert
5932 \begin_layout Plain Layout
5933 \begin_inset Formula $\Class L=\Class{SL}$
5949 \begin_layout Itemize
5950 the optimization problem in logspace iff
5951 \begin_inset Flex Alternative
5954 \begin_layout Plain Layout
5955 \begin_inset Argument 1
5958 \begin_layout Plain Layout
5965 \begin_inset Argument 2
5968 \begin_layout Plain Layout
5975 \begin_inset Flex Alert
5978 \begin_layout Plain Layout
5979 \begin_inset Formula $\Class L=\Class{NL}$
5995 \begin_layout Itemize
5996 the approximation problem in logspace iff ?.
6002 \begin_layout Subsection
6003 The Approximation Scheme is Optimal
6007 \begin_inset Argument 3
6010 \begin_layout Plain Layout
6017 \begin_inset Argument 4
6020 \begin_layout Plain Layout
6021 The Approximation Scheme is Optimal
6030 \begin_layout Theorem
6031 Suppose there exists an approximation scheme for
6032 \begin_inset Formula $\Lang{tournament-shortest-path}$
6036 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6041 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6052 \begin_layout Enumerate
6053 Suppose the approximation scheme exists.
6054 \begin_inset Newline newline
6058 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6065 \begin_layout Enumerate
6067 \begin_inset Formula $(T,s,t)$
6072 \begin_inset Formula $n$
6075 be the number of vertices.
6078 \begin_layout Enumerate
6079 Run the approximation scheme for
6080 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6084 \begin_inset Newline newline
6088 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6094 \begin_layout Enumerate
6095 The resulting path has optimal length.
6100 \begin_layout Plain Layout