1 #LyX 2.1 created this file. For more info see http://www.lyx.org/
7 \beamertemplateshadingbackground{red!5}{structure!5}
9 \usepackage{beamerthemeshadow}
10 \usepackage{pgfnodes,pgfarrows,pgfheaps}
12 \beamertemplatetransparentcovereddynamicmedium
15 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
16 \logo{\pgfuseimage{icsi-logo}}
21 \newcommand{\Class}[1]{\operatorname{\mathchoice
27 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
29 % This gets defined by beamerbasecolor.sty, but only at the beginning of
31 \colorlet{averagebackgroundcolor}{normal text.bg}
33 \newcommand{\tape}[3]{%
34 \color{structure!30!averagebackgroundcolor}
35 \pgfmoveto{\pgfxy(-0.5,0)}
36 \pgflineto{\pgfxy(-0.6,0.1)}
37 \pgflineto{\pgfxy(-0.4,0.2)}
38 \pgflineto{\pgfxy(-0.6,0.3)}
39 \pgflineto{\pgfxy(-0.4,0.4)}
40 \pgflineto{\pgfxy(-0.5,0.5)}
41 \pgflineto{\pgfxy(4,0.5)}
42 \pgflineto{\pgfxy(4.1,0.4)}
43 \pgflineto{\pgfxy(3.9,0.3)}
44 \pgflineto{\pgfxy(4.1,0.2)}
45 \pgflineto{\pgfxy(3.9,0.1)}
46 \pgflineto{\pgfxy(4,0)}
51 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
52 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
55 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
58 \newcommand{\shorttape}[3]{%
59 \color{structure!30!averagebackgroundcolor}
60 \pgfmoveto{\pgfxy(-0.5,0)}
61 \pgflineto{\pgfxy(-0.6,0.1)}
62 \pgflineto{\pgfxy(-0.4,0.2)}
63 \pgflineto{\pgfxy(-0.6,0.3)}
64 \pgflineto{\pgfxy(-0.4,0.4)}
65 \pgflineto{\pgfxy(-0.5,0.5)}
66 \pgflineto{\pgfxy(1,0.5)}
67 \pgflineto{\pgfxy(1.1,0.4)}
68 \pgflineto{\pgfxy(0.9,0.3)}
69 \pgflineto{\pgfxy(1.1,0.2)}
70 \pgflineto{\pgfxy(0.9,0.1)}
71 \pgflineto{\pgfxy(1,0)}
76 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
77 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
80 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
83 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
84 {color(0pt)=(black); color(1cm)=(structure!65!white)}
85 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
86 {color(0pt)=(black); color(1cm)=(structure!55!white)}
87 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
88 {color(0pt)=(black); color(1cm)=(structure!45!white)}
89 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
90 {color(0pt)=(black); color(1cm)=(structure!35!white)}
91 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
92 {color(0pt)=(black); color(1cm)=(structure!25!white)}
93 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
94 {color(0pt)=(black); color(1cm)=(red!35!white)}
96 \newcommand{\heap}[5]{%
99 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
101 \begin{pgfmagnify}{1}{#1}
102 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
108 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
112 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
116 \newcommand{\langat}[2]{%
117 \color{black!30!beamerexample}
118 \pgfsetlinewidth{0.6pt}
119 \pgfsetendarrow{\pgfarrowdot}
120 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
121 \color{beamerexample}
122 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
125 \newcommand{\langatother}[2]{%
126 \color{black!30!beamerexample}
127 \pgfsetlinewidth{0.6pt}
128 \pgfsetendarrow{\pgfarrowdot}
129 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
130 \color{beamerexample}
131 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
135 \pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
138 \pgfdeclareradialshading{graphnode}
139 {\pgfpoint{-3pt}{3.6pt}}%
140 {color(0cm)=(beamerexample!15);
141 color(2.63pt)=(beamerexample!75);
142 color(5.26pt)=(beamerexample!70!black);
143 color(7.6pt)=(beamerexample!50!black);
144 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
146 \newcommand{\graphnode}[2]{
147 \pgfnodecircle{#1}[virtual]{#2}{8pt}
148 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
152 \use_default_options false
153 \maintain_unincluded_children false
155 \language_package default
160 \font_typewriter default
162 \font_default_family default
163 \use_non_tex_fonts false
169 \default_output_format default
171 \bibtex_command default
172 \index_command default
173 \paperfontsize default
178 \use_package amsmath 2
179 \use_package amssymb 2
180 \use_package cancel 0
182 \use_package mathdots 1
183 \use_package mathtools 0
184 \use_package mhchem 1
185 \use_package stackrel 0
186 \use_package stmaryrd 0
187 \use_package undertilde 0
189 \cite_engine_type numerical
193 \paperorientation portrait
203 \paragraph_separation indent
204 \paragraph_indentation default
205 \quotes_language english
208 \paperpagestyle default
209 \tracking_changes false
210 \output_changes false
213 \html_be_strict false
220 \begin_inset Newline newline
223 Finding Paths in Tournaments
230 \begin_layout Institute
231 International Computer Science Institute
232 \begin_inset Newline newline
236 \begin_inset Argument 1
239 \begin_layout Plain Layout
253 \begin_inset Argument 4
256 \begin_layout Plain Layout
266 \begin_layout Standard
267 \begin_inset CommandInset toc
268 LatexCommand tableofcontents
276 \begin_layout Plain Layout
287 \begin_layout Standard
291 \begin_layout Plain Layout
293 % Show the table of contents at the beginning
296 \begin_layout Plain Layout
298 % of every subsection.
301 \begin_layout Plain Layout
305 AtBeginSubsection[]{%
308 \begin_layout Plain Layout
315 \begin_layout Plain Layout
322 \begin_layout Plain Layout
326 tableofcontents[current,currentsubsection]
329 \begin_layout Plain Layout
334 \begin_layout Plain Layout
344 \begin_layout Section
348 \begin_layout Subsection
349 What are Tournaments?
353 \begin_inset Argument 4
356 \begin_layout Plain Layout
357 Tournaments Consist of Jousts Between Knights
366 \begin_layout Columns
375 \begin_layout Standard
379 \begin_layout Plain Layout
383 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
386 \begin_layout Plain Layout
390 pgfnodebox{A}[virtual]{
395 \begin_layout Plain Layout
399 pgfuseimage{knight1}}{2pt}{2pt}
402 \begin_layout Plain Layout
406 pgfnodebox{B}[virtual]{
411 \begin_layout Plain Layout
415 pgfuseimage{knight2}}{2pt}{2pt}
418 \begin_layout Plain Layout
422 pgfnodebox{C}[virtual]{
427 \begin_layout Plain Layout
431 pgfuseimage{knight3}}{2pt}{2pt}
434 \begin_layout Plain Layout
438 pgfnodebox{D}[virtual]{
443 \begin_layout Plain Layout
447 pgfuseimage{knight4}}{2pt}{2pt}
450 \begin_layout Plain Layout
457 \begin_layout Plain Layout
468 \begin_layout Plain Layout
475 \begin_layout Plain Layout
479 pgfsetlinewidth{0.6pt}
482 \begin_layout Plain Layout
486 pgfnodeconnline{A}{B}
489 \begin_layout Plain Layout
493 pgfnodeconnline{A}{C}
496 \begin_layout Plain Layout
500 pgfnodeconnline{D}{A}
503 \begin_layout Plain Layout
507 pgfnodeconnline{C}{B}
510 \begin_layout Plain Layout
514 pgfnodeconnline{B}{D}
517 \begin_layout Plain Layout
521 pgfnodeconnline{C}{D}
524 \begin_layout Plain Layout
529 \begin_layout Plain Layout
546 \begin_inset Argument 2
549 \begin_layout Plain Layout
550 What is a Tournament?
559 \begin_layout Itemize
560 \begin_inset Argument item:2
563 \begin_layout Plain Layout
572 \begin_layout Itemize
573 \begin_inset Argument item:2
576 \begin_layout Plain Layout
582 Every pair has a joust.
585 \begin_layout Itemize
586 \begin_inset Argument item:2
589 \begin_layout Plain Layout
595 In every joust one knight wins.
601 \begin_layout Separator
606 \begin_inset Argument 4
609 \begin_layout Plain Layout
610 Tournaments are Complete Directed Graphs
619 \begin_layout Columns
628 \begin_layout Standard
632 \begin_layout Plain Layout
636 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
639 \begin_layout Plain Layout
646 \begin_layout Plain Layout
650 pgfsetlinewidth{0.6pt}
653 \begin_layout Plain Layout
662 \begin_layout Plain Layout
671 \begin_layout Plain Layout
680 \begin_layout Plain Layout
689 \begin_layout Plain Layout
696 \begin_layout Plain Layout
704 pgfbox[center,center]{$v_2$}}
707 \begin_layout Plain Layout
715 pgfbox[center,center]{$v_3$}}
718 \begin_layout Plain Layout
726 pgfbox[center,center]{$v_4$}}
729 \begin_layout Plain Layout
737 pgfbox[center,center]{$v_1$}}
740 \begin_layout Plain Layout
747 \begin_layout Plain Layout
756 \begin_layout Plain Layout
760 pgfnodesetsepstart{2pt}
763 \begin_layout Plain Layout
767 pgfnodesetsepend{4pt}
770 \begin_layout Plain Layout
774 pgfnodeconnline{A}{B}
777 \begin_layout Plain Layout
781 pgfnodeconnline{A}{C}
784 \begin_layout Plain Layout
788 pgfnodeconnline{D}{A}
791 \begin_layout Plain Layout
795 pgfnodeconnline{C}{B}
798 \begin_layout Plain Layout
802 pgfnodeconnline{B}{D}
805 \begin_layout Plain Layout
809 pgfnodeconnline{D}{C}
812 \begin_layout Plain Layout
828 \begin_layout Definition
829 \begin_inset Argument 1
832 \begin_layout Plain Layout
850 \begin_layout Enumerate
854 \begin_layout Enumerate
855 with exactly one edge between
856 \begin_inset Newline newline
859 any two different vertices.
865 \begin_layout Separator
870 \begin_inset Argument 2
873 \begin_layout Plain Layout
880 \begin_inset Argument 4
883 \begin_layout Plain Layout
884 Tournaments Arise Naturally in Different Situations
893 \begin_layout ExampleBlock
894 \begin_inset Argument 2
897 \begin_layout Plain Layout
898 Applications in Ordering Theory
907 \begin_layout Standard
908 Elements in a set need to be sorted.
910 \begin_inset Newline newline
913 The comparison relation may be cyclic, however.
917 \begin_layout Separator
921 \begin_layout ExampleBlock
922 \begin_inset Argument 2
925 \begin_layout Plain Layout
926 Applications in Sociology
935 \begin_layout Standard
936 Several candidates apply for a position.
937 \begin_inset Newline newline
940 Reviewers decide for any two candidates whom they prefer.
945 \begin_layout Separator
949 \begin_layout ExampleBlock
950 \begin_inset Argument 2
953 \begin_layout Plain Layout
954 Applications in Structural Complexity Theory
963 \begin_layout Standard
965 \begin_inset Formula $L$
968 is given and a selector function
969 \begin_inset Formula $f$
973 \begin_inset Newline newline
976 It chooses from any two words the one more likely to be in
977 \begin_inset Formula $f$
985 \begin_layout Subsection
986 What Does ``Finding Paths'' Mean?
990 \begin_inset Argument 4
993 \begin_layout Plain Layout
994 ``Finding Paths'' is Ambiguous
1004 \begin_inset Argument 2
1007 \begin_layout Plain Layout
1009 \begin_inset Flex Only
1012 \begin_layout Plain Layout
1013 \begin_inset Argument 1
1016 \begin_layout Plain Layout
1022 Path Finding Problems
1028 \begin_inset Flex Only
1031 \begin_layout Plain Layout
1032 \begin_inset Argument 1
1035 \begin_layout Plain Layout
1042 \begin_inset Formula $\Lang{reach}$
1051 \begin_inset Flex Only
1054 \begin_layout Plain Layout
1055 \begin_inset Argument 1
1058 \begin_layout Plain Layout
1064 the Construction Problem
1070 \begin_inset Flex Only
1073 \begin_layout Plain Layout
1074 \begin_inset Argument 1
1077 \begin_layout Plain Layout
1083 the Optimization Problem
1089 \begin_inset Flex Only
1092 \begin_layout Plain Layout
1093 \begin_inset Argument 1
1096 \begin_layout Plain Layout
1103 \begin_inset Formula $\Lang{distance}$
1112 \begin_inset Flex Only
1115 \begin_layout Plain Layout
1116 \begin_inset Argument 1
1119 \begin_layout Plain Layout
1125 the Approximation Problem
1139 \begin_layout Itemize
1149 \begin_inset Formula $G=(V,E)$
1161 \begin_inset Formula $s\in V$
1173 \begin_inset Formula $t\in V$
1179 \begin_layout Itemize
1180 \begin_inset Argument item:2
1183 \begin_layout Plain Layout
1196 \begin_inset space ~
1200 \begin_inset Formula $d$
1207 \begin_layout Plain Layout
1219 \begin_layout Itemize
1220 \begin_inset Argument item:2
1223 \begin_layout Plain Layout
1238 \begin_inset Formula $r>1$
1245 \begin_layout Standard
1249 \begin_layout Plain Layout
1261 \begin_layout Overprint
1262 \begin_inset Argument item:1
1265 \begin_layout Plain Layout
1275 \begin_layout Columns
1276 \begin_inset Argument 1
1279 \begin_layout Plain Layout
1289 \begin_layout Standard
1290 \begin_inset Flex Alternative
1293 \begin_layout Plain Layout
1294 \begin_inset Argument 1
1297 \begin_layout Plain Layout
1304 \begin_inset Argument 2
1307 \begin_layout Plain Layout
1311 \begin_layout Plain Layout
1331 \begin_layout Plain Layout
1348 \begin_layout ExampleBlock
1349 \begin_inset Argument 2
1352 \begin_layout Plain Layout
1362 \begin_layout Standard
1366 \begin_layout Plain Layout
1370 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1373 \begin_layout Plain Layout
1377 \begin_layout Plain Layout
1381 color{beamerexample}
1384 \begin_layout Plain Layout
1388 \begin_layout Plain Layout
1392 pgfsetlinewidth{0.6pt}
1395 \begin_layout Plain Layout
1399 \begin_layout Plain Layout
1408 \begin_layout Plain Layout
1412 \begin_layout Plain Layout
1421 \begin_layout Plain Layout
1425 \begin_layout Plain Layout
1434 \begin_layout Plain Layout
1438 \begin_layout Plain Layout
1447 \begin_layout Plain Layout
1451 \begin_layout Plain Layout
1455 \begin_layout Plain Layout
1459 \begin_layout Plain Layout
1466 \begin_layout Plain Layout
1470 \begin_layout Plain Layout
1478 pgfbox[center,center]{$t$}}
1481 \begin_layout Plain Layout
1485 \begin_layout Plain Layout
1493 pgfbox[center,center]{$s$}}
1496 \begin_layout Plain Layout
1500 \begin_layout Plain Layout
1504 \begin_layout Plain Layout
1508 \begin_layout Plain Layout
1512 color{beamerexample}
1515 \begin_layout Plain Layout
1519 \begin_layout Plain Layout
1528 \begin_layout Plain Layout
1532 \begin_layout Plain Layout
1536 pgfnodesetsepstart{2pt}
1539 \begin_layout Plain Layout
1543 \begin_layout Plain Layout
1547 pgfnodesetsepend{4pt}
1550 \begin_layout Plain Layout
1554 \begin_layout Plain Layout
1558 pgfnodeconnline{A}{B}
1561 \begin_layout Plain Layout
1565 \begin_layout Plain Layout
1569 pgfnodeconnline{A}{C}
1572 \begin_layout Plain Layout
1576 \begin_layout Plain Layout
1580 pgfnodeconnline{D}{A}
1583 \begin_layout Plain Layout
1587 \begin_layout Plain Layout
1591 pgfnodeconnline{C}{B}
1594 \begin_layout Plain Layout
1598 \begin_layout Plain Layout
1602 pgfnodeconnline{B}{D}
1605 \begin_layout Plain Layout
1609 \begin_layout Plain Layout
1613 pgfnodeconnline{D}{C}
1616 \begin_layout Plain Layout
1620 \begin_layout Plain Layout
1624 \begin_layout Plain Layout
1628 \begin_layout Plain Layout
1638 pgfbox[left,center]{, $d=2$}}}
1641 \begin_layout Plain Layout
1645 \begin_layout Plain Layout
1655 pgfbox[left,center]{, $r=1.5$}}}
1658 \begin_layout Plain Layout
1662 \begin_layout Plain Layout
1672 pgfbox[left,center]{, $r=1.25$}}}
1675 \begin_layout Plain Layout
1679 \begin_layout Plain Layout
1692 \begin_layout Standard
1693 \begin_inset Flex Only
1696 \begin_layout Plain Layout
1697 \begin_inset Argument 1
1700 \begin_layout Plain Layout
1710 \begin_layout Plain Layout
1727 \begin_layout ExampleBlock
1728 \begin_inset Argument 1
1731 \begin_layout Plain Layout
1738 \begin_inset Argument 2
1741 \begin_layout Plain Layout
1751 \begin_layout Standard
1755 \begin_layout Plain Layout
1759 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1762 \begin_layout Plain Layout
1769 \begin_layout Plain Layout
1773 color{beamerexample}
1776 \begin_layout Plain Layout
1780 pgfsetlinewidth{0.6pt}
1783 \begin_layout Plain Layout
1792 \begin_layout Plain Layout
1801 \begin_layout Plain Layout
1810 \begin_layout Plain Layout
1819 \begin_layout Plain Layout
1826 \begin_layout Plain Layout
1834 pgfbox[center,center]{$t$}}
1837 \begin_layout Plain Layout
1845 pgfbox[center,center]{$s$}}
1848 \begin_layout Plain Layout
1852 color{beamerexample}
1855 \begin_layout Plain Layout
1864 \begin_layout Plain Layout
1868 pgfnodesetsepstart{2pt}
1871 \begin_layout Plain Layout
1875 pgfnodesetsepend{4pt}
1878 \begin_layout Plain Layout
1884 pgfnodeconnline{A}{B}}
1887 \begin_layout Plain Layout
1893 pgfnodeconnline{A}{C}}
1896 \begin_layout Plain Layout
1902 pgfnodeconnline{D}{A}}
1905 \begin_layout Plain Layout
1911 pgfnodeconnline{C}{B}}
1914 \begin_layout Plain Layout
1918 pgfnodeconnline{B}{D}
1921 \begin_layout Plain Layout
1925 pgfnodeconnline{D}{C}
1928 \begin_layout Plain Layout
1933 \begin_layout Plain Layout
1943 pgfbox[left,center]{
1948 \begin_layout Plain Layout
1963 \begin_layout Overprint
1964 \begin_inset Argument item:1
1967 \begin_layout Plain Layout
1978 \begin_inset Argument 2
1981 \begin_layout Plain Layout
1982 Variants of Path Finding Problems
1991 \begin_layout Description
1992 \begin_inset Argument item:1
1995 \begin_layout Plain Layout
2002 \begin_inset space ~
2005 Problem: Is there a path from
2006 \begin_inset Formula $s$
2010 \begin_inset space ~
2014 \begin_inset Formula $t$
2018 \begin_inset Argument 2
2021 \begin_layout Plain Layout
2022 Approximation Problem:
2030 \begin_layout Description
2031 \begin_inset Argument item:1
2034 \begin_layout Plain Layout
2041 \begin_inset space ~
2044 Problem: Construct a path from
2045 \begin_inset Formula $s$
2049 \begin_inset space ~
2053 \begin_inset Formula $t$
2059 \begin_layout Description
2060 \begin_inset Argument item:1
2063 \begin_layout Plain Layout
2070 \begin_inset space ~
2073 Problem: Construct a shortest path from
2074 \begin_inset Formula $s$
2078 \begin_inset space ~
2082 \begin_inset Formula $t$
2088 \begin_layout Description
2089 \begin_inset Argument item:1
2092 \begin_layout Plain Layout
2099 \begin_inset space ~
2102 Problem: Is the distance of
2103 \begin_inset Formula $s$
2107 \begin_inset space ~
2111 \begin_inset Formula $t$
2115 \begin_inset space ~
2119 \begin_inset Formula $d$
2125 \begin_layout Description
2126 \begin_inset Argument item:1
2129 \begin_layout Plain Layout
2136 \begin_inset space ~
2139 Problem: Construct a path from
2140 \begin_inset Formula $s$
2144 \begin_inset space ~
2148 \begin_inset Formula $t$
2152 \begin_inset Newline newline
2155 approximately their distance.
2161 \begin_layout Section
2165 \begin_layout Subsection
2166 Standard Complexity Classes
2169 \begin_layout Standard
2173 \begin_layout Plain Layout
2177 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2179 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2189 \begin_inset Argument 4
2192 \begin_layout Plain Layout
2193 The Classes L and NL are Defined via
2194 \begin_inset Newline newline
2197 Logspace Turing Machines
2206 \begin_layout Standard
2210 \begin_layout Plain Layout
2214 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2217 \begin_layout Plain Layout
2226 \begin_layout Plain Layout
2230 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2233 \begin_layout Plain Layout
2240 \begin_layout Plain Layout
2249 \begin_layout Plain Layout
2253 tape{}{output tape (write only)}{10690836937182}}
2256 \begin_layout Plain Layout
2261 \begin_layout Plain Layout
2268 \begin_layout Plain Layout
2277 \begin_layout Plain Layout
2281 shorttape{work tape (read/write), $O(
2283 log n)$ symbols}{}{42}}
2286 \begin_layout Plain Layout
2295 \begin_layout Plain Layout
2299 pgfbox[center,center]{
2301 pgfuseimage{computer}}}
2304 \begin_layout Plain Layout
2309 \begin_layout Plain Layout
2313 pgfsetlinewidth{0.6pt}
2316 \begin_layout Plain Layout
2323 \begin_layout Plain Layout
2332 \begin_layout Plain Layout
2336 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2339 \begin_layout Plain Layout
2345 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2348 \begin_layout Plain Layout
2354 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2357 \begin_layout Plain Layout
2370 \begin_layout Separator
2375 \begin_inset Argument 4
2378 \begin_layout Plain Layout
2379 Logspace Turing Machines Are Quite Powerful
2389 \begin_inset Argument 2
2392 \begin_layout Plain Layout
2393 Deterministic logspace machines can compute
2402 \begin_layout Itemize
2403 addition, multiplication, and even division
2406 \begin_layout Itemize
2407 reductions used in completeness proofs,
2410 \begin_layout Itemize
2411 reachability in forests.
2420 \begin_inset Argument 2
2423 \begin_layout Plain Layout
2424 Non-deterministic logspace machines can compute
2433 \begin_layout Itemize
2434 reachability in graphs,
2437 \begin_layout Itemize
2438 non-reachability in graphs,
2441 \begin_layout Itemize
2442 satisfiability with two literals per clause.
2447 \begin_layout Separator
2452 \begin_inset Argument 1
2455 \begin_layout Plain Layout
2462 \begin_inset Argument 3
2465 \begin_layout Plain Layout
2472 \begin_inset Argument 4
2475 \begin_layout Plain Layout
2476 The Complexity Class Hierarchy
2485 \begin_layout Standard
2489 \begin_layout Plain Layout
2493 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2496 \begin_layout Plain Layout
2500 pgfsetlinewidth{0.8pt}
2503 \begin_layout Plain Layout
2512 \begin_layout Plain Layout
2516 pgfsetdash{{2pt}}{0pt}
2519 \begin_layout Plain Layout
2527 Class{NC}^2$}{black!50!structure}{2}}
2530 \begin_layout Plain Layout
2536 Class{NL}$}{black!50!structure}{3}
2539 \begin_layout Plain Layout
2545 Class{L}$}{black!50!structure}{4}
2548 \begin_layout Plain Layout
2559 \begin_layout Plain Layout
2565 Class{NC}^1}$}{black!50!structure}{5}
2568 \begin_layout Plain Layout
2573 \begin_layout Plain Layout
2580 \begin_layout Plain Layout
2591 \begin_layout Plain Layout
2597 Class{AC}^0}$}{black}{6}
2600 \begin_layout Plain Layout
2605 \begin_layout Plain Layout
2609 pgfsetlinewidth{1.0pt}
2612 \begin_layout Plain Layout
2619 \begin_layout Plain Layout
2623 pgfxyline(-5,0)(5,0)
2626 \begin_layout Plain Layout
2637 \begin_layout Plain Layout
2647 operatorname{forest}}$}}
2650 \begin_layout Plain Layout
2661 \begin_layout Plain Layout
2680 \begin_layout Plain Layout
2699 \begin_layout Plain Layout
2712 \begin_layout Plain Layout
2720 operatorname{forest}}$,}
2725 \begin_layout Plain Layout
2733 operatorname{forest}}$,}
2738 \begin_layout Plain Layout
2746 operatorname{path}}$,}
2751 \begin_layout Plain Layout
2759 operatorname{path}}$}}}
2762 \begin_layout Plain Layout
2767 \begin_layout Plain Layout
2777 operatorname{tourn}}$}}
2780 \begin_layout Plain Layout
2793 \begin_layout Plain Layout
2801 operatorname{tourn}}$,}
2806 \begin_layout Plain Layout
2817 \begin_layout Plain Layout
2826 \begin_layout Plain Layout
2831 \begin_layout Plain Layout
2837 pgfsetdash{{1pt}}{0pt}%
2840 \begin_layout Plain Layout
2848 operatorname{tourn}}$''}
2851 \begin_layout Plain Layout
2856 \begin_layout Plain Layout
2869 \begin_layout Separator
2874 \begin_inset Argument 4
2877 \begin_layout Plain Layout
2878 The Circuit Complexity Classes AC
2879 \begin_inset Formula $^{0}$
2883 \begin_inset Formula $^{1}$
2887 \begin_inset Formula $^{2}$
2891 \begin_inset Newline newline
2894 Limit the Circuit Depth
2903 \begin_layout Standard
2907 \begin_layout Plain Layout
2916 \begin_layout Plain Layout
2928 \begin_layout Columns
2929 \begin_inset Argument 1
2932 \begin_layout Plain Layout
2942 \begin_layout Column
2947 \begin_inset Argument 2
2950 \begin_layout Plain Layout
2952 \begin_inset Formula $\Class{AC}^{0}$
2964 \begin_layout Itemize
2965 \begin_inset Formula $O(1)$
2971 \begin_layout Itemize
2976 \begin_layout Examples
2981 \begin_layout Itemize
2982 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
2988 \begin_layout Itemize
2989 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3000 \begin_layout Column
3005 \begin_inset Argument 2
3008 \begin_layout Plain Layout
3010 \begin_inset Formula $\Class{NC}^{1}$
3022 \begin_layout Itemize
3023 \begin_inset Formula $O(\log n)$
3029 \begin_layout Itemize
3034 \begin_layout Examples
3039 \begin_layout Itemize
3040 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3046 \begin_layout Itemize
3047 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3053 \begin_layout Itemize
3054 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3065 \begin_layout Column
3070 \begin_inset Argument 2
3073 \begin_layout Plain Layout
3075 \begin_inset Formula $\Class{NC}^{2}$
3087 \begin_layout Itemize
3088 \begin_inset Formula $O(\log^{2}n)$
3094 \begin_layout Itemize
3099 \begin_layout Examples
3104 \begin_layout Itemize
3105 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3114 \begin_layout AgainFrame
3115 \begin_inset Argument 1
3118 \begin_layout Plain Layout
3127 \begin_layout Subsection
3128 Standard Complexity Results on Finding Paths
3132 \begin_inset Argument 4
3135 \begin_layout Plain Layout
3136 All Variants of Finding Paths in Directed Graphs
3137 \begin_inset Newline newline
3140 Are Equally Difficult
3150 \begin_inset Formula $\Lang{reach}$
3154 \begin_inset Formula $\Lang{distance}$
3158 \begin_inset Formula $\Class{NL}$
3169 \begin_layout Corollary
3170 For directed graphs, we can solve
3174 \begin_layout Itemize
3175 the reachability problem in logspace iff
3176 \begin_inset Formula $\Class{L}=\Class{NL}$
3182 \begin_layout Itemize
3183 the construction problem in logspace iff
3184 \begin_inset Formula $\Class{L}=\Class{NL}$
3190 \begin_layout Itemize
3191 the optimization problem in logspace iff
3192 \begin_inset Formula $\Class{L}=\Class{NL}$
3198 \begin_layout Itemize
3199 the approximation problem in logspace iff
3200 \begin_inset Formula $\Class{L}=\Class{NL}$
3208 \begin_layout AgainFrame
3209 \begin_inset Argument 1
3212 \begin_layout Plain Layout
3222 \begin_inset Argument 4
3225 \begin_layout Plain Layout
3226 Finding Paths in Forests and Directed Paths is Easy,
3227 \begin_inset Newline newline
3240 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3244 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3248 \begin_inset Formula $\Class{L}$
3254 \begin_layout Separator
3259 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3263 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3267 \begin_inset Formula $\Class{L}$
3274 \begin_layout AgainFrame
3275 \begin_inset Argument 1
3278 \begin_layout Plain Layout
3287 \begin_layout Section
3288 Finding Paths in Tournaments
3291 \begin_layout Subsection
3292 Complexity of: Does a Path Exist?
3296 \begin_inset Argument 4
3299 \begin_layout Plain Layout
3300 Definition of the Tournament Reachability Problem
3309 \begin_layout Definition
3315 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3323 \begin_inset Formula $(T,s,t)$
3330 \begin_layout Enumerate
3331 \begin_inset Formula $T=(V,E)$
3337 \begin_layout Enumerate
3338 there exists a path from
3339 \begin_inset space ~
3343 \begin_inset Formula $s$
3347 \begin_inset space ~
3351 \begin_inset Formula $t$
3359 \begin_layout Separator
3364 \begin_inset Argument 4
3367 \begin_layout Plain Layout
3368 The Tournament Reachability Problem is Very Easy
3377 \begin_layout Theorem
3378 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3388 \begin_layout AlertBlock
3389 \begin_inset Argument 2
3392 \begin_layout Plain Layout
3402 \begin_layout Itemize
3404 \begin_inset Quotes eld
3408 \begin_inset Quotes erd
3412 \begin_inset Formula $\Lang{reach}$
3416 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3422 \begin_layout Itemize
3423 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3431 \begin_layout AgainFrame
3432 \begin_inset Argument 1
3435 \begin_layout Plain Layout
3444 \begin_layout Subsection
3445 Complexity of: Construct a Shortest Path
3449 \begin_inset Argument 4
3452 \begin_layout Plain Layout
3453 Finding a Shortest Path Is as Difficult as
3454 \begin_inset Newline newline
3457 the Distance Problem
3466 \begin_layout Definition
3472 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3480 \begin_inset Formula $(T,s,t,d)$
3487 \begin_layout Enumerate
3488 \begin_inset Formula $T=(V,E)$
3491 is a tournament in which
3494 \begin_layout Enumerate
3496 \begin_inset Formula $s$
3500 \begin_inset space ~
3504 \begin_inset Formula $t$
3508 \begin_inset space ~
3512 \begin_inset Formula $d$
3520 \begin_layout Separator
3525 \begin_inset Argument 4
3528 \begin_layout Plain Layout
3529 The Tournament Distance Problem is Hard
3538 \begin_layout Theorem
3539 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3543 \begin_inset Formula $\Class{NL}$
3549 \begin_layout Standard
3550 \begin_inset space \hfill{}
3557 \begin_layout Plain Layout
3561 hyperlink{hierarchy<6>}{
3563 beamerskipbutton{Skip Proof}}
3575 \begin_layout Corollary
3576 Shortest path in tournaments can be constructed
3577 \begin_inset Newline newline
3580 in logarithmic space, iff
3581 \begin_inset Formula $\Class{L}=\Class{NL}$
3591 \begin_layout Corollary
3592 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3599 \begin_layout Separator
3604 \begin_inset Argument 4
3607 \begin_layout Plain Layout
3609 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3621 \begin_layout Standard
3625 \begin_layout Plain Layout
3637 \begin_layout Columns
3638 \begin_inset Argument 1
3641 \begin_layout Plain Layout
3651 \begin_layout Column
3655 \begin_layout Standard
3659 \begin_layout Plain Layout
3674 \begin_inset Argument 2
3677 \begin_layout Plain Layout
3679 \begin_inset Formula $\Lang{reach}$
3683 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3695 \begin_layout Enumerate
3696 \begin_inset Argument item:2
3699 \begin_layout Plain Layout
3706 \begin_inset Formula $(G,s,t)$
3710 \begin_inset Formula $\Lang{reach}$
3716 \begin_layout Enumerate
3717 \begin_inset Argument item:2
3720 \begin_layout Plain Layout
3727 \begin_inset Formula $G$
3731 \begin_inset Formula $G'$
3737 \begin_layout Enumerate
3738 \begin_inset Argument item:2
3741 \begin_layout Plain Layout
3748 \begin_inset Newline newline
3752 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3759 \begin_layout Separator
3764 \begin_inset Argument 2
3767 \begin_layout Plain Layout
3774 \begin_inset Argument 1
3777 \begin_layout Plain Layout
3787 \begin_layout Enumerate
3788 \begin_inset Argument item:2
3791 \begin_layout Plain Layout
3798 \begin_inset space ~
3802 \begin_inset Formula $G$
3806 \begin_inset Newline newline
3810 \begin_inset space ~
3814 \begin_inset Formula $G'$
3820 \begin_layout Enumerate
3821 \begin_inset Argument item:2
3824 \begin_layout Plain Layout
3831 \begin_inset space ~
3835 \begin_inset Formula $G'$
3839 \begin_inset Newline newline
3843 \begin_inset space ~
3847 \begin_inset Formula $G'$
3854 \begin_layout Column
3858 \begin_layout Example
3862 \begin_layout Plain Layout
3866 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3869 \begin_layout Plain Layout
3873 color{beamerexample}
3876 \begin_layout Plain Layout
3880 pgfsetlinewidth{0.6pt}
3883 \begin_layout Plain Layout
3892 \begin_layout Plain Layout
3901 \begin_layout Plain Layout
3910 \begin_layout Plain Layout
3919 \begin_layout Plain Layout
3926 \begin_layout Plain Layout
3934 pgfbox[center,center]{$s$}}
3937 \begin_layout Plain Layout
3945 pgfbox[center,center]{$t$}}
3948 \begin_layout Plain Layout
3952 color{beamerexample}
3955 \begin_layout Plain Layout
3964 \begin_layout Plain Layout
3968 pgfnodesetsepstart{2pt}
3971 \begin_layout Plain Layout
3975 pgfnodesetsepend{2pt}
3978 \begin_layout Plain Layout
3984 pgfnodeconnline{B}{A}}
3987 \begin_layout Plain Layout
3993 pgfnodeconnline{B}{C}}
3996 \begin_layout Plain Layout
4002 pgfnodeconnline{C}{D}}
4005 \begin_layout Plain Layout
4011 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4014 \begin_layout Plain Layout
4022 pgfbox[left,center]{$G
4027 \begin_layout Plain Layout
4034 \begin_layout Plain Layout
4042 pgfbox[left,center]{$G'
4047 \begin_layout Plain Layout
4056 \begin_layout Plain Layout
4065 \begin_layout Plain Layout
4074 \begin_layout Plain Layout
4083 \begin_layout Plain Layout
4092 \begin_layout Plain Layout
4101 \begin_layout Plain Layout
4110 \begin_layout Plain Layout
4119 \begin_layout Plain Layout
4128 \begin_layout Plain Layout
4137 \begin_layout Plain Layout
4146 \begin_layout Plain Layout
4155 \begin_layout Plain Layout
4164 \begin_layout Plain Layout
4173 \begin_layout Plain Layout
4182 \begin_layout Plain Layout
4191 \begin_layout Plain Layout
4198 \begin_layout Plain Layout
4206 pgfbox[center,center]{$s'$}}
4209 \begin_layout Plain Layout
4217 pgfbox[center,center]{$t'$}}
4220 \begin_layout Plain Layout
4225 \begin_layout Plain Layout
4230 \begin_layout Plain Layout
4237 \begin_layout Plain Layout
4241 pgfsetlinewidth{0.4pt}
4244 \begin_layout Plain Layout
4248 color{beamerexample!25!averagebackgroundcolor}
4251 \begin_layout Plain Layout
4255 pgfnodeconnline{A2}{C1}
4258 \begin_layout Plain Layout
4262 pgfnodeconnline{A2}{D1}
4265 \begin_layout Plain Layout
4269 pgfnodeconnline{B2}{A1}
4272 \begin_layout Plain Layout
4276 pgfnodeconnline{B2}{C1}
4279 \begin_layout Plain Layout
4283 pgfnodeconnline{B2}{D1}
4286 \begin_layout Plain Layout
4290 pgfnodeconnline{C2}{D1}
4293 \begin_layout Plain Layout
4297 pgfnodeconnline{D2}{A1}
4300 \begin_layout Plain Layout
4304 pgfnodeconnline{D2}{B1}
4307 \begin_layout Plain Layout
4311 pgfnodeconnline{A3}{C2}
4314 \begin_layout Plain Layout
4318 pgfnodeconnline{A3}{D2}
4321 \begin_layout Plain Layout
4325 pgfnodeconnline{B3}{A2}
4328 \begin_layout Plain Layout
4332 pgfnodeconnline{B3}{C2}
4335 \begin_layout Plain Layout
4339 pgfnodeconnline{B3}{D2}
4342 \begin_layout Plain Layout
4346 pgfnodeconnline{C3}{D2}
4349 \begin_layout Plain Layout
4353 pgfnodeconnline{D3}{A2}
4356 \begin_layout Plain Layout
4360 pgfnodeconnline{D3}{B2}
4363 \begin_layout Plain Layout
4367 pgfnodeconnline{A4}{C3}
4370 \begin_layout Plain Layout
4374 pgfnodeconnline{A4}{D3}
4377 \begin_layout Plain Layout
4381 pgfnodeconnline{B4}{A3}
4384 \begin_layout Plain Layout
4388 pgfnodeconnline{B4}{C3}
4391 \begin_layout Plain Layout
4395 pgfnodeconnline{B4}{D3}
4398 \begin_layout Plain Layout
4402 pgfnodeconnline{C4}{D3}
4405 \begin_layout Plain Layout
4409 pgfnodeconnline{D4}{A3}
4412 \begin_layout Plain Layout
4416 pgfnodeconnline{D4}{B3}
4419 \begin_layout Plain Layout
4428 \begin_layout Plain Layout
4432 pgfnodeconnline{A1}{B1}
4435 \begin_layout Plain Layout
4439 pgfnodeconnline{B1}{C1}
4442 \begin_layout Plain Layout
4446 pgfnodeconnline{C1}{D1}
4449 \begin_layout Plain Layout
4453 pgfnodeconnline{A2}{B2}
4456 \begin_layout Plain Layout
4460 pgfnodeconnline{B2}{C2}
4463 \begin_layout Plain Layout
4467 pgfnodeconnline{C2}{D2}
4470 \begin_layout Plain Layout
4474 pgfnodeconnline{A3}{B3}
4477 \begin_layout Plain Layout
4481 pgfnodeconnline{B3}{C3}
4484 \begin_layout Plain Layout
4488 pgfnodeconnline{C3}{D3}
4491 \begin_layout Plain Layout
4495 pgfnodeconnline{A4}{B4}
4498 \begin_layout Plain Layout
4502 pgfnodeconnline{B4}{C4}
4505 \begin_layout Plain Layout
4509 pgfnodeconnline{C4}{D4}
4512 \begin_layout Plain Layout
4519 \begin_layout Plain Layout
4523 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4526 \begin_layout Plain Layout
4530 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4533 \begin_layout Plain Layout
4537 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4540 \begin_layout Plain Layout
4544 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4547 \begin_layout Plain Layout
4551 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4554 \begin_layout Plain Layout
4558 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4561 \begin_layout Plain Layout
4565 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4568 \begin_layout Plain Layout
4572 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4575 \begin_layout Plain Layout
4579 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4582 \begin_layout Plain Layout
4586 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4589 \begin_layout Plain Layout
4593 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4596 \begin_layout Plain Layout
4600 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4603 \begin_layout Plain Layout
4607 color{beamerexample}
4610 \begin_layout Plain Layout
4614 pgfsetlinewidth{0.6pt}
4617 \begin_layout Plain Layout
4622 \begin_layout Plain Layout
4629 \begin_layout Plain Layout
4636 \begin_layout Plain Layout
4640 pgfnodeconnline{B1}{A2}
4643 \begin_layout Plain Layout
4647 pgfnodeconnline{B2}{A3}
4650 \begin_layout Plain Layout
4654 pgfnodeconnline{B3}{A4}
4657 \begin_layout Plain Layout
4662 \begin_layout Plain Layout
4669 \begin_layout Plain Layout
4676 \begin_layout Plain Layout
4680 pgfnodeconnline{B1}{C2}
4683 \begin_layout Plain Layout
4687 pgfnodeconnline{B2}{C3}
4690 \begin_layout Plain Layout
4694 pgfnodeconnline{B3}{C4}
4697 \begin_layout Plain Layout
4702 \begin_layout Plain Layout
4709 \begin_layout Plain Layout
4716 \begin_layout Plain Layout
4720 pgfnodeconnline{C1}{D2}
4723 \begin_layout Plain Layout
4729 pgfnodeconnline{C2}{D3}}
4732 \begin_layout Plain Layout
4738 pgfnodeconnline{C3}{D4}}
4741 \begin_layout Plain Layout
4746 \begin_layout Plain Layout
4753 \begin_layout Plain Layout
4760 \begin_layout Plain Layout
4766 pgfnodeconnline{A1}{C2}}
4769 \begin_layout Plain Layout
4775 pgfnodeconnline{A2}{C3}}
4778 \begin_layout Plain Layout
4782 pgfnodeconnline{A3}{C4}
4785 \begin_layout Plain Layout
4790 \begin_layout Plain Layout
4797 \begin_layout Plain Layout
4804 \begin_layout Plain Layout
4810 pgfnodeconnline{A1}{A2}}
4813 \begin_layout Plain Layout
4817 pgfnodeconnline{A2}{A3}
4820 \begin_layout Plain Layout
4824 pgfnodeconnline{A3}{A4}
4827 \begin_layout Plain Layout
4831 pgfnodeconnline{B1}{B2}
4834 \begin_layout Plain Layout
4838 pgfnodeconnline{B2}{B3}
4841 \begin_layout Plain Layout
4845 pgfnodeconnline{B3}{B4}
4848 \begin_layout Plain Layout
4852 pgfnodeconnline{C1}{C2}
4855 \begin_layout Plain Layout
4859 pgfnodeconnline{C2}{C3}
4862 \begin_layout Plain Layout
4866 pgfnodeconnline{C3}{C4}
4869 \begin_layout Plain Layout
4873 pgfnodeconnline{D1}{D2}
4876 \begin_layout Plain Layout
4880 pgfnodeconnline{D2}{D3}
4883 \begin_layout Plain Layout
4889 pgfnodeconnline{D3}{D4}}
4892 \begin_layout Plain Layout
4897 \begin_layout Plain Layout
4911 \begin_layout AgainFrame
4912 \begin_inset Argument 1
4915 \begin_layout Plain Layout
4924 \begin_layout Subsection
4925 Complexity of: Approximating the Shortest Path
4929 \begin_inset Argument 4
4932 \begin_layout Plain Layout
4933 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
4942 \begin_layout Definition
4947 approximation scheme for
4948 \begin_inset Formula $\Lang{tournament-shortest-path}$
4959 \begin_layout Enumerate
4961 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
4967 \begin_layout Enumerate
4969 \begin_inset Formula $r>1$
4975 \begin_layout Standard
4979 \begin_layout Itemize
4981 \begin_inset Formula $s$
4985 \begin_inset space ~
4989 \begin_inset Formula $t$
4993 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5001 \begin_layout Separator
5006 \begin_inset Argument 4
5009 \begin_layout Plain Layout
5010 There Exists a Logspace Approximation Scheme for
5011 \begin_inset Newline newline
5014 the Tournament Shortest Path Problem
5023 \begin_layout Theorem
5024 There exists an approximation scheme for
5025 \begin_inset Formula $\Lang{tournament-shortest-path}$
5029 \begin_inset Formula $1<r<2$
5033 \begin_inset Formula
5035 O\left(\log|V|\log\frac{1}{r-1}\right).
5047 \begin_layout Corollary
5048 In tournaments, paths can be constructed in logarithmic space.
5051 \begin_layout Standard
5052 \begin_inset space \hfill{}
5059 \begin_layout Plain Layout
5063 hyperlink{optimality}{
5065 beamergotobutton{More Details}}
5074 \begin_layout AgainFrame
5075 \begin_inset Argument 1
5078 \begin_layout Plain Layout
5087 \begin_layout Standard
5088 \begin_inset Note Note
5091 \begin_layout Plain Layout
5092 If a frame includes a program listing, the frame needs to be marked as
5093 \begin_inset Quotes eld
5097 \begin_inset Quotes erd
5101 LyX has the FragileFrame layout for this.
5109 \begin_layout FragileFrame
5110 \begin_inset Argument 4
5113 \begin_layout Plain Layout
5114 Just a frame with a program code listing
5122 \begin_layout FragileFrame
5123 This is some program code:
5127 \begin_layout Standard
5128 \begin_inset listings
5129 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5133 \begin_layout Plain Layout
5138 \begin_layout Plain Layout
5140 'this is a python function'
5143 \begin_layout Plain Layout
5148 \begin_layout Plain Layout
5153 \begin_layout Plain Layout
5155 'This is a German word: Tschüs'
5158 \begin_layout Plain Layout
5163 \begin_layout Plain Layout
5168 \begin_layout Plain Layout
5170 'this is a python function'
5173 \begin_layout Plain Layout
5184 \begin_layout Section*
5188 \begin_layout Subsection*
5193 \begin_inset Argument 4
5196 \begin_layout Plain Layout
5207 \begin_inset Argument 2
5210 \begin_layout Plain Layout
5220 \begin_layout Itemize
5234 \begin_inset Formula $\Class{AC}^{0}$
5243 \begin_layout Itemize
5248 logspace approximation scheme
5260 shortest paths in tournaments.
5263 \begin_layout Itemize
5277 \begin_inset Formula $\Class{NL}$
5286 \begin_layout Separator
5291 \begin_inset Argument 2
5294 \begin_layout Plain Layout
5304 \begin_layout Itemize
5305 The same results apply to graphs with
5306 \begin_inset Newline newline
5309 bounded independence number.
5310 \begin_inset space \hfill{}
5317 \begin_layout Plain Layout
5321 hyperlink{independence}{
5323 beamergotobutton{More Details}}
5331 \begin_layout Itemize
5332 The complexity of finding paths in undirected graphs
5333 \begin_inset Newline newline
5337 \begin_inset space \hfill{}
5344 \begin_layout Plain Layout
5348 hyperlink{undirected}{
5350 beamergotobutton{More Details}}
5360 \begin_layout Subsection*
5365 \begin_inset Argument 4
5368 \begin_layout Plain Layout
5378 \begin_layout Standard
5382 \begin_layout Plain Layout
5386 beamertemplatebookbibitems
5394 \begin_layout Bibliography
5395 \begin_inset CommandInset bibitem
5396 LatexCommand bibitem
5402 \begin_inset space ~
5410 \begin_layout Plain Layout
5421 Topics on Tournaments.
5428 \begin_layout Plain Layout
5437 Holt, Rinehart, and Winston, 1968.
5442 \begin_layout Plain Layout
5446 beamertemplatearticlebibitems
5454 \begin_layout Bibliography
5455 \begin_inset CommandInset bibitem
5456 LatexCommand bibitem
5457 key "NickelsenT2002"
5462 \begin_inset space ~
5465 Arfst Nickelsen and Till Tantau.
5470 \begin_layout Plain Layout
5479 On reachability in graphs with bounded independence number.
5483 \begin_layout Plain Layout
5497 , Springer-Verlag, 2002.
5500 \begin_layout Bibliography
5501 \begin_inset CommandInset bibitem
5502 LatexCommand bibitem
5508 \begin_inset space ~
5515 \begin_layout Plain Layout
5524 A logspace approximation scheme for the shortest path problem for graphs
5525 with bounded independence number.
5529 \begin_layout Plain Layout
5543 , Springer-Verlag, 2004.
5548 \begin_layout Plain Layout
5561 \begin_layout Standard
5566 \begin_layout Plain Layout
5570 AtBeginSubsection[]{}
5578 \begin_layout Section
5582 \begin_layout Subsection
5583 Graphs With Bounded Independence Number
5587 \begin_inset Argument 3
5590 \begin_layout Plain Layout
5597 \begin_inset Argument 4
5600 \begin_layout Plain Layout
5601 Definition of Independence Number of a Graph
5610 \begin_layout Definition
5620 \begin_inset Formula $\alpha(G)$
5624 \begin_inset Newline newline
5627 is the maximum number of vertices we can pick,
5628 \begin_inset Newline newline
5631 such that there is no edge between them.
5634 \begin_layout Example
5635 Tournaments have independence number 1.
5640 \begin_layout Separator
5645 \begin_inset Argument 4
5648 \begin_layout Plain Layout
5649 The Results for Tournaments also Apply to
5650 \begin_inset Newline newline
5653 Graphs With Bounded Independence Number
5662 \begin_layout Theorem
5664 \begin_inset space ~
5668 \begin_inset Formula $k$
5679 in graphs with independence number
5680 \begin_inset Newline newline
5684 \begin_inset space ~
5688 \begin_inset Formula $k$
5692 \begin_inset Formula $\Class{AC}^{0}$
5698 \begin_layout Separator
5702 \begin_layout Theorem
5704 \begin_inset space ~
5708 \begin_inset Formula $k$
5715 logspace approximation scheme
5719 for approximating the shortest path in graphs with independence number at
5721 \begin_inset space ~
5725 \begin_inset Formula $k$
5731 \begin_layout Separator
5735 \begin_layout Theorem
5737 \begin_inset space ~
5741 \begin_inset Formula $k$
5752 in graphs with independence number at most
5753 \begin_inset space ~
5757 \begin_inset Formula $k$
5765 \begin_inset Formula $\Class{NL}$
5774 \begin_layout Subsection
5775 Finding Paths in Undirected Graphs
5779 \begin_inset Argument 1
5782 \begin_layout Plain Layout
5789 \begin_inset Argument 3
5792 \begin_layout Plain Layout
5799 \begin_inset Argument 4
5802 \begin_layout Plain Layout
5803 The Complexity of Finding Paths in Undirected Graphs
5804 \begin_inset Newline newline
5817 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5821 \begin_inset Formula $\Class{SL}$
5827 \begin_layout Corollary
5828 For undirected graphs, we can solve
5832 \begin_layout Itemize
5833 the reachability problem in logspace iff
5834 \begin_inset Formula $\Class L=\Class{SL}$
5840 \begin_layout Itemize
5841 the construction problem in logspace iff
5842 \begin_inset Flex Alternative
5845 \begin_layout Plain Layout
5846 \begin_inset Argument 1
5849 \begin_layout Plain Layout
5856 \begin_inset Argument 2
5859 \begin_layout Plain Layout
5866 \begin_inset Flex Alert
5869 \begin_layout Plain Layout
5870 \begin_inset Formula $\Class L=\Class{SL}$
5886 \begin_layout Itemize
5887 the optimization problem in logspace iff
5888 \begin_inset Flex Alternative
5891 \begin_layout Plain Layout
5892 \begin_inset Argument 1
5895 \begin_layout Plain Layout
5902 \begin_inset Argument 2
5905 \begin_layout Plain Layout
5912 \begin_inset Flex Alert
5915 \begin_layout Plain Layout
5916 \begin_inset Formula $\Class L=\Class{NL}$
5932 \begin_layout Itemize
5933 the approximation problem in logspace iff ?.
5939 \begin_layout Subsection
5940 The Approximation Scheme is Optimal
5944 \begin_inset Argument 3
5947 \begin_layout Plain Layout
5954 \begin_inset Argument 4
5957 \begin_layout Plain Layout
5958 The Approximation Scheme is Optimal
5967 \begin_layout Theorem
5968 Suppose there exists an approximation scheme for
5969 \begin_inset Formula $\Lang{tournament-shortest-path}$
5973 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
5978 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
5989 \begin_layout Enumerate
5990 Suppose the approximation scheme exists.
5991 \begin_inset Newline newline
5995 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6002 \begin_layout Enumerate
6004 \begin_inset Formula $(T,s,t)$
6009 \begin_inset Formula $n$
6012 be the number of vertices.
6015 \begin_layout Enumerate
6016 Run the approximation scheme for
6017 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6021 \begin_inset Newline newline
6025 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6031 \begin_layout Enumerate
6032 The resulting path has optimal length.
6037 \begin_layout Plain Layout