1 #LyX 2.4 created this file. For more info see https://www.lyx.org/
5 \save_transient_properties true
6 \origin /systemlyxdir/examples/Presentations/
9 \beamertemplateshadingbackground{red!5}{structure!5}
11 \usepackage{beamerthemeshadow}
12 \usepackage{pgfnodes,pgfarrows,pgfheaps}
14 \beamertemplatetransparentcovereddynamicmedium
17 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
18 \logo{\pgfuseimage{icsi-logo}}
23 \newcommand{\Class}[1]{\operatorname{\mathchoice
29 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
31 % This gets defined by beamerbasecolor.sty, but only at the beginning of
33 \colorlet{averagebackgroundcolor}{normal text.bg}
35 \newcommand{\tape}[3]{%
36 \color{structure!30!averagebackgroundcolor}
37 \pgfmoveto{\pgfxy(-0.5,0)}
38 \pgflineto{\pgfxy(-0.6,0.1)}
39 \pgflineto{\pgfxy(-0.4,0.2)}
40 \pgflineto{\pgfxy(-0.6,0.3)}
41 \pgflineto{\pgfxy(-0.4,0.4)}
42 \pgflineto{\pgfxy(-0.5,0.5)}
43 \pgflineto{\pgfxy(4,0.5)}
44 \pgflineto{\pgfxy(4.1,0.4)}
45 \pgflineto{\pgfxy(3.9,0.3)}
46 \pgflineto{\pgfxy(4.1,0.2)}
47 \pgflineto{\pgfxy(3.9,0.1)}
48 \pgflineto{\pgfxy(4,0)}
53 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
54 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
57 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
60 \newcommand{\shorttape}[3]{%
61 \color{structure!30!averagebackgroundcolor}
62 \pgfmoveto{\pgfxy(-0.5,0)}
63 \pgflineto{\pgfxy(-0.6,0.1)}
64 \pgflineto{\pgfxy(-0.4,0.2)}
65 \pgflineto{\pgfxy(-0.6,0.3)}
66 \pgflineto{\pgfxy(-0.4,0.4)}
67 \pgflineto{\pgfxy(-0.5,0.5)}
68 \pgflineto{\pgfxy(1,0.5)}
69 \pgflineto{\pgfxy(1.1,0.4)}
70 \pgflineto{\pgfxy(0.9,0.3)}
71 \pgflineto{\pgfxy(1.1,0.2)}
72 \pgflineto{\pgfxy(0.9,0.1)}
73 \pgflineto{\pgfxy(1,0)}
78 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
79 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
82 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
85 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
86 {color(0pt)=(black); color(1cm)=(structure!65!white)}
87 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
88 {color(0pt)=(black); color(1cm)=(structure!55!white)}
89 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
90 {color(0pt)=(black); color(1cm)=(structure!45!white)}
91 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
92 {color(0pt)=(black); color(1cm)=(structure!35!white)}
93 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
94 {color(0pt)=(black); color(1cm)=(structure!25!white)}
95 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
96 {color(0pt)=(black); color(1cm)=(red!35!white)}
98 \newcommand{\heap}[5]{%
101 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
103 \begin{pgfmagnify}{1}{#1}
104 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
110 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
114 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
118 \newcommand{\langat}[2]{%
119 \color{black!30!beamerexample}
120 \pgfsetlinewidth{0.6pt}
121 \pgfsetendarrow{\pgfarrowdot}
122 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
123 \color{beamerexample}
124 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
127 \newcommand{\langatother}[2]{%
128 \color{black!30!beamerexample}
129 \pgfsetlinewidth{0.6pt}
130 \pgfsetendarrow{\pgfarrowdot}
131 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
132 \color{beamerexample}
133 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
137 \pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
140 \pgfdeclareradialshading{graphnode}
141 {\pgfpoint{-3pt}{3.6pt}}%
142 {color(0cm)=(beamerexample!15);
143 color(2.63pt)=(beamerexample!75);
144 color(5.26pt)=(beamerexample!70!black);
145 color(7.6pt)=(beamerexample!50!black);
146 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
148 \newcommand{\graphnode}[2]{
149 \pgfnodecircle{#1}[virtual]{#2}{8pt}
150 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
154 \use_default_options false
155 \maintain_unincluded_children no
157 \language_package default
160 \font_roman "lmodern" "default"
161 \font_sans "lmss" "default"
162 \font_typewriter "lmtt" "default"
163 \font_math "auto" "auto"
164 \font_default_family default
165 \use_non_tex_fonts false
167 \font_roman_osf false
169 \font_typewriter_osf false
170 \font_sf_scale 100 100
171 \font_tt_scale 100 100
173 \use_dash_ligatures false
175 \default_output_format default
177 \bibtex_command default
178 \index_command default
179 \paperfontsize default
184 \use_package amsmath 2
185 \use_package amssymb 2
186 \use_package cancel 1
188 \use_package mathdots 1
189 \use_package mathtools 1
190 \use_package mhchem 1
191 \use_package stackrel 1
192 \use_package stmaryrd 1
193 \use_package undertilde 1
195 \cite_engine_type default
199 \paperorientation portrait
211 \paragraph_separation indent
212 \paragraph_indentation default
214 \math_numbering_side default
215 \quotes_style english
219 \paperpagestyle default
221 \tracking_changes false
222 \output_changes false
224 \postpone_fragile_content false
227 \html_be_strict false
228 \docbook_table_output 0
229 \docbook_mathml_prefix 1
236 \begin_inset Newline newline
239 Finding Paths in Tournaments
246 \begin_layout Institute
247 International Computer Science Institute
248 \begin_inset Newline newline
253 \begin_inset Argument 1
256 \begin_layout Plain Layout
271 \begin_inset Argument 4
274 \begin_layout Plain Layout
284 \begin_layout Standard
285 \begin_inset CommandInset toc
286 LatexCommand tableofcontents
294 \begin_layout Plain Layout
305 \begin_layout Standard
309 \begin_layout Plain Layout
311 % Show the table of contents at the beginning
314 \begin_layout Plain Layout
316 % of every subsection.
319 \begin_layout Plain Layout
323 AtBeginSubsection[]{%
326 \begin_layout Plain Layout
333 \begin_layout Plain Layout
340 \begin_layout Plain Layout
344 tableofcontents[current,currentsubsection]
347 \begin_layout Plain Layout
352 \begin_layout Plain Layout
362 \begin_layout Section
366 \begin_layout Subsection
367 What are Tournaments?
371 \begin_inset Argument 4
374 \begin_layout Plain Layout
375 Tournaments Consist of Jousts Between Knights
384 \begin_layout Columns
393 \begin_layout Standard
397 \begin_layout Plain Layout
401 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
404 \begin_layout Plain Layout
408 pgfnodebox{A}[virtual]{
413 \begin_layout Plain Layout
417 pgfuseimage{knight1}}{2pt}{2pt}
420 \begin_layout Plain Layout
424 pgfnodebox{B}[virtual]{
429 \begin_layout Plain Layout
433 pgfuseimage{knight2}}{2pt}{2pt}
436 \begin_layout Plain Layout
440 pgfnodebox{C}[virtual]{
445 \begin_layout Plain Layout
449 pgfuseimage{knight3}}{2pt}{2pt}
452 \begin_layout Plain Layout
456 pgfnodebox{D}[virtual]{
461 \begin_layout Plain Layout
465 pgfuseimage{knight4}}{2pt}{2pt}
468 \begin_layout Plain Layout
475 \begin_layout Plain Layout
486 \begin_layout Plain Layout
493 \begin_layout Plain Layout
497 pgfsetlinewidth{0.6pt}
500 \begin_layout Plain Layout
504 pgfnodeconnline{A}{B}
507 \begin_layout Plain Layout
511 pgfnodeconnline{A}{C}
514 \begin_layout Plain Layout
518 pgfnodeconnline{D}{A}
521 \begin_layout Plain Layout
525 pgfnodeconnline{C}{B}
528 \begin_layout Plain Layout
532 pgfnodeconnline{B}{D}
535 \begin_layout Plain Layout
539 pgfnodeconnline{C}{D}
542 \begin_layout Plain Layout
547 \begin_layout Plain Layout
564 \begin_inset Argument 2
567 \begin_layout Plain Layout
568 What is a Tournament?
577 \begin_layout Itemize
578 \begin_inset Argument item:2
581 \begin_layout Plain Layout
591 \begin_layout Itemize
592 \begin_inset Argument item:2
595 \begin_layout Plain Layout
602 Every pair has a joust.
605 \begin_layout Itemize
606 \begin_inset Argument item:2
609 \begin_layout Plain Layout
616 In every joust one knight wins.
622 \begin_layout Standard
623 \begin_inset Separator plain
630 \begin_inset Argument 4
633 \begin_layout Plain Layout
634 Tournaments are Complete Directed Graphs
643 \begin_layout Columns
652 \begin_layout Standard
656 \begin_layout Plain Layout
660 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
663 \begin_layout Plain Layout
670 \begin_layout Plain Layout
674 pgfsetlinewidth{0.6pt}
677 \begin_layout Plain Layout
686 \begin_layout Plain Layout
695 \begin_layout Plain Layout
704 \begin_layout Plain Layout
713 \begin_layout Plain Layout
720 \begin_layout Plain Layout
728 pgfbox[center,center]{$v_2$}}
731 \begin_layout Plain Layout
739 pgfbox[center,center]{$v_3$}}
742 \begin_layout Plain Layout
750 pgfbox[center,center]{$v_4$}}
753 \begin_layout Plain Layout
761 pgfbox[center,center]{$v_1$}}
764 \begin_layout Plain Layout
771 \begin_layout Plain Layout
780 \begin_layout Plain Layout
784 pgfnodesetsepstart{2pt}
787 \begin_layout Plain Layout
791 pgfnodesetsepend{4pt}
794 \begin_layout Plain Layout
798 pgfnodeconnline{A}{B}
801 \begin_layout Plain Layout
805 pgfnodeconnline{A}{C}
808 \begin_layout Plain Layout
812 pgfnodeconnline{D}{A}
815 \begin_layout Plain Layout
819 pgfnodeconnline{C}{B}
822 \begin_layout Plain Layout
826 pgfnodeconnline{B}{D}
829 \begin_layout Plain Layout
833 pgfnodeconnline{D}{C}
836 \begin_layout Plain Layout
852 \begin_layout Definition
853 \begin_inset Argument 1
856 \begin_layout Plain Layout
875 \begin_layout Enumerate
879 \begin_layout Enumerate
880 with exactly one edge between
881 \begin_inset Newline newline
884 any two different vertices.
890 \begin_layout Standard
891 \begin_inset Separator plain
898 \begin_inset Argument 2
901 \begin_layout Plain Layout
909 \begin_inset Argument 4
912 \begin_layout Plain Layout
913 Tournaments Arise Naturally in Different Situations
922 \begin_layout ExampleBlock
923 \begin_inset Argument 2
926 \begin_layout Plain Layout
927 Applications in Ordering Theory
936 \begin_layout Standard
937 Elements in a set need to be sorted.
939 \begin_inset Newline newline
942 The comparison relation may be cyclic,
947 \begin_layout Standard
948 \begin_inset Separator plain
954 \begin_layout ExampleBlock
955 \begin_inset Argument 2
958 \begin_layout Plain Layout
959 Applications in Sociology
968 \begin_layout Standard
969 Several candidates apply for a position.
970 \begin_inset Newline newline
973 Reviewers decide for any two candidates whom they prefer.
978 \begin_layout Standard
979 \begin_inset Separator plain
985 \begin_layout ExampleBlock
986 \begin_inset Argument 2
989 \begin_layout Plain Layout
990 Applications in Structural Complexity Theory
999 \begin_layout Standard
1001 \begin_inset Formula $L$
1004 is given and a selector function
1005 \begin_inset Formula $f$
1009 \begin_inset Newline newline
1012 It chooses from any two words the one more likely to be in
1013 \begin_inset Formula $f$
1021 \begin_layout Subsection
1022 What Does ``Finding Paths'' Mean?
1026 \begin_inset Argument 4
1029 \begin_layout Plain Layout
1030 ``Finding Paths'' is Ambiguous
1040 \begin_inset Argument 2
1043 \begin_layout Plain Layout
1045 \begin_inset Flex Only
1048 \begin_layout Plain Layout
1049 \begin_inset Argument 1
1052 \begin_layout Plain Layout
1059 Path Finding Problems
1065 \begin_inset Flex Only
1068 \begin_layout Plain Layout
1069 \begin_inset Argument 1
1072 \begin_layout Plain Layout
1080 \begin_inset Formula $\Lang{reach}$
1089 \begin_inset Flex Only
1092 \begin_layout Plain Layout
1093 \begin_inset Argument 1
1096 \begin_layout Plain Layout
1103 the Construction Problem
1109 \begin_inset Flex Only
1112 \begin_layout Plain Layout
1113 \begin_inset Argument 1
1116 \begin_layout Plain Layout
1123 the Optimization Problem
1129 \begin_inset Flex Only
1132 \begin_layout Plain Layout
1133 \begin_inset Argument 1
1136 \begin_layout Plain Layout
1144 \begin_inset Formula $\Lang{distance}$
1153 \begin_inset Flex Only
1156 \begin_layout Plain Layout
1157 \begin_inset Argument 1
1160 \begin_layout Plain Layout
1167 the Approximation Problem
1181 \begin_layout Itemize
1191 \begin_inset Formula $G=(V,E)$
1204 \begin_inset Formula $s\in V$
1216 \begin_inset Formula $t\in V$
1222 \begin_layout Itemize
1223 \begin_inset Argument item:2
1226 \begin_layout Plain Layout
1240 \begin_inset space ~
1244 \begin_inset Formula $d$
1251 \begin_layout Plain Layout
1263 \begin_layout Itemize
1264 \begin_inset Argument item:2
1267 \begin_layout Plain Layout
1283 \begin_inset Formula $r>1$
1290 \begin_layout Standard
1294 \begin_layout Plain Layout
1306 \begin_layout Overprint
1307 \begin_inset Argument item:1
1310 \begin_layout Plain Layout
1321 \begin_layout Columns
1322 \begin_inset Argument 1
1325 \begin_layout Plain Layout
1335 \begin_layout Standard
1336 \begin_inset Flex Alternative
1339 \begin_layout Plain Layout
1340 \begin_inset Argument 1
1343 \begin_layout Plain Layout
1351 \begin_inset Argument 2
1354 \begin_layout Plain Layout
1358 \begin_layout Plain Layout
1378 \begin_layout Plain Layout
1395 \begin_layout ExampleBlock
1396 \begin_inset Argument 2
1399 \begin_layout Plain Layout
1409 \begin_layout Standard
1413 \begin_layout Plain Layout
1417 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1420 \begin_layout Plain Layout
1424 \begin_layout Plain Layout
1428 color{beamerexample}
1431 \begin_layout Plain Layout
1435 \begin_layout Plain Layout
1439 pgfsetlinewidth{0.6pt}
1442 \begin_layout Plain Layout
1446 \begin_layout Plain Layout
1455 \begin_layout Plain Layout
1459 \begin_layout Plain Layout
1468 \begin_layout Plain Layout
1472 \begin_layout Plain Layout
1481 \begin_layout Plain Layout
1485 \begin_layout Plain Layout
1494 \begin_layout Plain Layout
1498 \begin_layout Plain Layout
1502 \begin_layout Plain Layout
1506 \begin_layout Plain Layout
1513 \begin_layout Plain Layout
1517 \begin_layout Plain Layout
1525 pgfbox[center,center]{$t$}}
1528 \begin_layout Plain Layout
1532 \begin_layout Plain Layout
1540 pgfbox[center,center]{$s$}}
1543 \begin_layout Plain Layout
1547 \begin_layout Plain Layout
1551 \begin_layout Plain Layout
1555 \begin_layout Plain Layout
1559 color{beamerexample}
1562 \begin_layout Plain Layout
1566 \begin_layout Plain Layout
1575 \begin_layout Plain Layout
1579 \begin_layout Plain Layout
1583 pgfnodesetsepstart{2pt}
1586 \begin_layout Plain Layout
1590 \begin_layout Plain Layout
1594 pgfnodesetsepend{4pt}
1597 \begin_layout Plain Layout
1601 \begin_layout Plain Layout
1605 pgfnodeconnline{A}{B}
1608 \begin_layout Plain Layout
1612 \begin_layout Plain Layout
1616 pgfnodeconnline{A}{C}
1619 \begin_layout Plain Layout
1623 \begin_layout Plain Layout
1627 pgfnodeconnline{D}{A}
1630 \begin_layout Plain Layout
1634 \begin_layout Plain Layout
1638 pgfnodeconnline{C}{B}
1641 \begin_layout Plain Layout
1645 \begin_layout Plain Layout
1649 pgfnodeconnline{B}{D}
1652 \begin_layout Plain Layout
1656 \begin_layout Plain Layout
1660 pgfnodeconnline{D}{C}
1663 \begin_layout Plain Layout
1667 \begin_layout Plain Layout
1671 \begin_layout Plain Layout
1675 \begin_layout Plain Layout
1685 pgfbox[left,center]{,
1689 \begin_layout Plain Layout
1693 \begin_layout Plain Layout
1703 pgfbox[left,center]{,
1707 \begin_layout Plain Layout
1711 \begin_layout Plain Layout
1721 pgfbox[left,center]{,
1725 \begin_layout Plain Layout
1729 \begin_layout Plain Layout
1742 \begin_layout Standard
1743 \begin_inset Flex Only
1746 \begin_layout Plain Layout
1747 \begin_inset Argument 1
1750 \begin_layout Plain Layout
1761 \begin_layout Plain Layout
1778 \begin_layout ExampleBlock
1779 \begin_inset Argument 1
1782 \begin_layout Plain Layout
1790 \begin_inset Argument 2
1793 \begin_layout Plain Layout
1803 \begin_layout Standard
1807 \begin_layout Plain Layout
1811 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1814 \begin_layout Plain Layout
1821 \begin_layout Plain Layout
1825 color{beamerexample}
1828 \begin_layout Plain Layout
1832 pgfsetlinewidth{0.6pt}
1835 \begin_layout Plain Layout
1844 \begin_layout Plain Layout
1853 \begin_layout Plain Layout
1862 \begin_layout Plain Layout
1871 \begin_layout Plain Layout
1878 \begin_layout Plain Layout
1886 pgfbox[center,center]{$t$}}
1889 \begin_layout Plain Layout
1897 pgfbox[center,center]{$s$}}
1900 \begin_layout Plain Layout
1904 color{beamerexample}
1907 \begin_layout Plain Layout
1916 \begin_layout Plain Layout
1920 pgfnodesetsepstart{2pt}
1923 \begin_layout Plain Layout
1927 pgfnodesetsepend{4pt}
1930 \begin_layout Plain Layout
1936 pgfnodeconnline{A}{B}}
1939 \begin_layout Plain Layout
1945 pgfnodeconnline{A}{C}}
1948 \begin_layout Plain Layout
1954 pgfnodeconnline{D}{A}}
1957 \begin_layout Plain Layout
1963 pgfnodeconnline{C}{B}}
1966 \begin_layout Plain Layout
1970 pgfnodeconnline{B}{D}
1973 \begin_layout Plain Layout
1977 pgfnodeconnline{D}{C}
1980 \begin_layout Plain Layout
1985 \begin_layout Plain Layout
1995 pgfbox[left,center]{
2000 \begin_layout Plain Layout
2015 \begin_layout Overprint
2016 \begin_inset Argument item:1
2019 \begin_layout Plain Layout
2031 \begin_inset Argument 2
2034 \begin_layout Plain Layout
2035 Variants of Path Finding Problems
2044 \begin_layout Description
2045 \begin_inset Argument item:1
2048 \begin_layout Plain Layout
2056 \begin_inset space ~
2060 Is there a path from
2061 \begin_inset Formula $s$
2065 \begin_inset space ~
2069 \begin_inset Formula $t$
2073 \begin_inset Argument 2
2076 \begin_layout Plain Layout
2077 Approximation Problem:
2085 \begin_layout Description
2086 \begin_inset Argument item:1
2089 \begin_layout Plain Layout
2097 \begin_inset space ~
2101 Construct a path from
2102 \begin_inset Formula $s$
2106 \begin_inset space ~
2110 \begin_inset Formula $t$
2117 \begin_layout Description
2118 \begin_inset Argument item:1
2121 \begin_layout Plain Layout
2129 \begin_inset space ~
2133 Construct a shortest path from
2134 \begin_inset Formula $s$
2138 \begin_inset space ~
2142 \begin_inset Formula $t$
2148 \begin_layout Description
2149 \begin_inset Argument item:1
2152 \begin_layout Plain Layout
2160 \begin_inset space ~
2165 \begin_inset Formula $s$
2169 \begin_inset space ~
2173 \begin_inset Formula $t$
2177 \begin_inset space ~
2181 \begin_inset Formula $d$
2187 \begin_layout Description
2188 \begin_inset Argument item:1
2191 \begin_layout Plain Layout
2199 \begin_inset space ~
2203 Construct a path from
2204 \begin_inset Formula $s$
2208 \begin_inset space ~
2212 \begin_inset Formula $t$
2216 \begin_inset Newline newline
2219 approximately their distance.
2225 \begin_layout Section
2229 \begin_layout Subsection
2230 Standard Complexity Classes
2233 \begin_layout Standard
2237 \begin_layout Plain Layout
2241 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2243 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer-g4}
2252 \begin_inset Argument 4
2255 \begin_layout Plain Layout
2256 The Classes L and NL are Defined via
2257 \begin_inset Newline newline
2260 Logspace Turing Machines
2269 \begin_layout Standard
2273 \begin_layout Plain Layout
2277 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2280 \begin_layout Plain Layout
2289 \begin_layout Plain Layout
2293 tape{input tape (read only),
2294 $n$ symbols}{}{3401234*3143223=}}
2297 \begin_layout Plain Layout
2304 \begin_layout Plain Layout
2313 \begin_layout Plain Layout
2317 tape{}{output tape (write only)}{10690836937182}}
2320 \begin_layout Plain Layout
2325 \begin_layout Plain Layout
2332 \begin_layout Plain Layout
2341 \begin_layout Plain Layout
2345 shorttape{work tape (read/write),
2348 log n)$ symbols}{}{42}}
2351 \begin_layout Plain Layout
2360 \begin_layout Plain Layout
2364 pgfbox[center,center]{
2366 pgfuseimage{computer}}}
2369 \begin_layout Plain Layout
2374 \begin_layout Plain Layout
2378 pgfsetlinewidth{0.6pt}
2381 \begin_layout Plain Layout
2388 \begin_layout Plain Layout
2397 \begin_layout Plain Layout
2401 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2404 \begin_layout Plain Layout
2410 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2413 \begin_layout Plain Layout
2419 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2422 \begin_layout Plain Layout
2435 \begin_layout Standard
2436 \begin_inset Separator plain
2443 \begin_inset Argument 4
2446 \begin_layout Plain Layout
2447 Logspace Turing Machines Are Quite Powerful
2457 \begin_inset Argument 2
2460 \begin_layout Plain Layout
2461 Deterministic logspace machines can compute
2470 \begin_layout Itemize
2476 \begin_layout Itemize
2477 reductions used in completeness proofs,
2480 \begin_layout Itemize
2481 reachability in forests.
2490 \begin_inset Argument 2
2493 \begin_layout Plain Layout
2494 Non-deterministic logspace machines can compute
2503 \begin_layout Itemize
2504 reachability in graphs,
2507 \begin_layout Itemize
2508 non-reachability in graphs,
2511 \begin_layout Itemize
2512 satisfiability with two literals per clause.
2517 \begin_layout Standard
2518 \begin_inset Separator plain
2525 \begin_inset Argument 1
2528 \begin_layout Plain Layout
2536 \begin_inset Argument 3
2539 \begin_layout Plain Layout
2546 \begin_inset Argument 4
2549 \begin_layout Plain Layout
2550 The Complexity Class Hierarchy
2559 \begin_layout Standard
2563 \begin_layout Plain Layout
2567 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2570 \begin_layout Plain Layout
2574 pgfsetlinewidth{0.8pt}
2577 \begin_layout Plain Layout
2586 \begin_layout Plain Layout
2590 pgfsetdash{{2pt}}{0pt}
2593 \begin_layout Plain Layout
2601 Class{NC}^2$}{black!50!structure}{2}}
2604 \begin_layout Plain Layout
2610 Class{NL}$}{black!50!structure}{3}
2613 \begin_layout Plain Layout
2619 Class{L}$}{black!50!structure}{4}
2622 \begin_layout Plain Layout
2633 \begin_layout Plain Layout
2639 Class{NC}^1}$}{black!50!structure}{5}
2642 \begin_layout Plain Layout
2647 \begin_layout Plain Layout
2654 \begin_layout Plain Layout
2665 \begin_layout Plain Layout
2671 Class{AC}^0}$}{black}{6}
2674 \begin_layout Plain Layout
2679 \begin_layout Plain Layout
2683 pgfsetlinewidth{1.0pt}
2686 \begin_layout Plain Layout
2693 \begin_layout Plain Layout
2697 pgfxyline(-5,0)(5,0)
2700 \begin_layout Plain Layout
2711 \begin_layout Plain Layout
2721 operatorname{forest}}$}}
2724 \begin_layout Plain Layout
2735 \begin_layout Plain Layout
2754 \begin_layout Plain Layout
2773 \begin_layout Plain Layout
2786 \begin_layout Plain Layout
2794 operatorname{forest}}$,}
2799 \begin_layout Plain Layout
2807 operatorname{forest}}$,}
2812 \begin_layout Plain Layout
2820 operatorname{path}}$,}
2825 \begin_layout Plain Layout
2833 operatorname{path}}$}}}
2836 \begin_layout Plain Layout
2841 \begin_layout Plain Layout
2851 operatorname{tourn}}$}}
2854 \begin_layout Plain Layout
2867 \begin_layout Plain Layout
2875 operatorname{tourn}}$,}
2880 \begin_layout Plain Layout
2891 \begin_layout Plain Layout
2900 \begin_layout Plain Layout
2905 \begin_layout Plain Layout
2911 pgfsetdash{{1pt}}{0pt}%
2914 \begin_layout Plain Layout
2922 operatorname{tourn}}$''}
2925 \begin_layout Plain Layout
2930 \begin_layout Plain Layout
2943 \begin_layout Standard
2944 \begin_inset Separator plain
2951 \begin_inset Argument 4
2954 \begin_layout Plain Layout
2955 The Circuit Complexity Classes AC
2956 \begin_inset Formula $^{0}$
2961 \begin_inset Formula $^{1}$
2966 \begin_inset Formula $^{2}$
2970 \begin_inset Newline newline
2973 Limit the Circuit Depth
2982 \begin_layout Standard
2986 \begin_layout Plain Layout
2995 \begin_layout Plain Layout
3007 \begin_layout Columns
3008 \begin_inset Argument 1
3011 \begin_layout Plain Layout
3021 \begin_layout Column
3026 \begin_inset Argument 2
3029 \begin_layout Plain Layout
3031 \begin_inset Formula $\Class{AC}^{0}$
3043 \begin_layout Itemize
3044 \begin_inset Formula $O(1)$
3050 \begin_layout Itemize
3055 \begin_layout Examples
3060 \begin_layout Itemize
3061 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3067 \begin_layout Itemize
3068 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3079 \begin_layout Column
3084 \begin_inset Argument 2
3087 \begin_layout Plain Layout
3089 \begin_inset Formula $\Class{NC}^{1}$
3101 \begin_layout Itemize
3102 \begin_inset Formula $O(\log n)$
3108 \begin_layout Itemize
3113 \begin_layout Examples
3118 \begin_layout Itemize
3119 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3125 \begin_layout Itemize
3126 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3132 \begin_layout Itemize
3133 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3144 \begin_layout Column
3149 \begin_inset Argument 2
3152 \begin_layout Plain Layout
3154 \begin_inset Formula $\Class{NC}^{2}$
3166 \begin_layout Itemize
3167 \begin_inset Formula $O(\log^{2}n)$
3173 \begin_layout Itemize
3178 \begin_layout Examples
3183 \begin_layout Itemize
3184 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3193 \begin_layout AgainFrame
3194 \begin_inset Argument 1
3197 \begin_layout Plain Layout
3207 \begin_layout Subsection
3208 Standard Complexity Results on Finding Paths
3212 \begin_inset Argument 4
3215 \begin_layout Plain Layout
3216 All Variants of Finding Paths in Directed Graphs
3217 \begin_inset Newline newline
3220 Are Equally Difficult
3230 \begin_inset Formula $\Lang{reach}$
3234 \begin_inset Formula $\Lang{distance}$
3238 \begin_inset Formula $\Class{NL}$
3249 \begin_layout Corollary
3250 For directed graphs,
3255 \begin_layout Itemize
3256 the reachability problem in logspace iff
3257 \begin_inset Formula $\Class{L}=\Class{NL}$
3263 \begin_layout Itemize
3264 the construction problem in logspace iff
3265 \begin_inset Formula $\Class{L}=\Class{NL}$
3271 \begin_layout Itemize
3272 the optimization problem in logspace iff
3273 \begin_inset Formula $\Class{L}=\Class{NL}$
3279 \begin_layout Itemize
3280 the approximation problem in logspace iff
3281 \begin_inset Formula $\Class{L}=\Class{NL}$
3289 \begin_layout AgainFrame
3290 \begin_inset Argument 1
3293 \begin_layout Plain Layout
3304 \begin_inset Argument 4
3307 \begin_layout Plain Layout
3308 Finding Paths in Forests and Directed Paths is Easy,
3309 \begin_inset Newline newline
3322 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3326 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3330 \begin_inset Formula $\Class{L}$
3336 \begin_layout Standard
3337 \begin_inset Separator plain
3344 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3348 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3352 \begin_inset Formula $\Class{L}$
3359 \begin_layout AgainFrame
3360 \begin_inset Argument 1
3363 \begin_layout Plain Layout
3373 \begin_layout Section
3374 Finding Paths in Tournaments
3377 \begin_layout Subsection
3383 \begin_inset Argument 4
3386 \begin_layout Plain Layout
3387 Definition of the Tournament Reachability Problem
3396 \begin_layout Definition
3402 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3410 \begin_inset Formula $(T,s,t)$
3417 \begin_layout Enumerate
3418 \begin_inset Formula $T=(V,E)$
3424 \begin_layout Enumerate
3425 there exists a path from
3426 \begin_inset space ~
3430 \begin_inset Formula $s$
3434 \begin_inset space ~
3438 \begin_inset Formula $t$
3446 \begin_layout Standard
3447 \begin_inset Separator plain
3454 \begin_inset Argument 4
3457 \begin_layout Plain Layout
3458 The Tournament Reachability Problem is Very Easy
3467 \begin_layout Theorem
3468 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3478 \begin_layout AlertBlock
3479 \begin_inset Argument 2
3482 \begin_layout Plain Layout
3492 \begin_layout Itemize
3494 \begin_inset Quotes eld
3498 \begin_inset Quotes erd
3502 \begin_inset Formula $\Lang{reach}$
3506 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3512 \begin_layout Itemize
3513 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3521 \begin_layout AgainFrame
3522 \begin_inset Argument 1
3525 \begin_layout Plain Layout
3535 \begin_layout Subsection
3537 Construct a Shortest Path
3541 \begin_inset Argument 4
3544 \begin_layout Plain Layout
3545 Finding a Shortest Path Is as Difficult as
3546 \begin_inset Newline newline
3549 the Distance Problem
3558 \begin_layout Definition
3564 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3572 \begin_inset Formula $(T,s,t,d)$
3579 \begin_layout Enumerate
3580 \begin_inset Formula $T=(V,E)$
3583 is a tournament in which
3586 \begin_layout Enumerate
3588 \begin_inset Formula $s$
3592 \begin_inset space ~
3596 \begin_inset Formula $t$
3600 \begin_inset space ~
3604 \begin_inset Formula $d$
3612 \begin_layout Standard
3613 \begin_inset Separator plain
3620 \begin_inset Argument 4
3623 \begin_layout Plain Layout
3624 The Tournament Distance Problem is Hard
3633 \begin_layout Theorem
3634 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3638 \begin_inset Formula $\Class{NL}$
3644 \begin_layout Standard
3645 \begin_inset space \hfill{}
3652 \begin_layout Plain Layout
3656 hyperlink{hierarchy<6>}{
3658 beamerskipbutton{Skip Proof}}
3670 \begin_layout Corollary
3671 Shortest path in tournaments can be constructed
3672 \begin_inset Newline newline
3675 in logarithmic space,
3677 \begin_inset Formula $\Class{L}=\Class{NL}$
3687 \begin_layout Corollary
3688 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3695 \begin_layout Standard
3696 \begin_inset Separator plain
3703 \begin_inset Argument 4
3706 \begin_layout Plain Layout
3708 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3720 \begin_layout Standard
3724 \begin_layout Plain Layout
3736 \begin_layout Columns
3737 \begin_inset Argument 1
3740 \begin_layout Plain Layout
3750 \begin_layout Column
3754 \begin_layout Standard
3758 \begin_layout Plain Layout
3773 \begin_inset Argument 2
3776 \begin_layout Plain Layout
3778 \begin_inset Formula $\Lang{reach}$
3782 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3794 \begin_layout Enumerate
3795 \begin_inset Argument item:2
3798 \begin_layout Plain Layout
3806 \begin_inset Formula $(G,s,t)$
3810 \begin_inset Formula $\Lang{reach}$
3816 \begin_layout Enumerate
3817 \begin_inset Argument item:2
3820 \begin_layout Plain Layout
3828 \begin_inset Formula $G$
3832 \begin_inset Formula $G'$
3838 \begin_layout Enumerate
3839 \begin_inset Argument item:2
3842 \begin_layout Plain Layout
3850 \begin_inset Newline newline
3854 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3861 \begin_layout Standard
3862 \begin_inset Separator plain
3869 \begin_inset Argument 2
3872 \begin_layout Plain Layout
3879 \begin_inset Argument 1
3882 \begin_layout Plain Layout
3893 \begin_layout Enumerate
3894 \begin_inset Argument item:2
3897 \begin_layout Plain Layout
3905 \begin_inset space ~
3909 \begin_inset Formula $G$
3913 \begin_inset Newline newline
3917 \begin_inset space ~
3921 \begin_inset Formula $G'$
3927 \begin_layout Enumerate
3928 \begin_inset Argument item:2
3931 \begin_layout Plain Layout
3939 \begin_inset space ~
3943 \begin_inset Formula $G'$
3947 \begin_inset Newline newline
3951 \begin_inset space ~
3955 \begin_inset Formula $G'$
3962 \begin_layout Column
3966 \begin_layout Example
3970 \begin_layout Plain Layout
3974 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3977 \begin_layout Plain Layout
3981 color{beamerexample}
3984 \begin_layout Plain Layout
3988 pgfsetlinewidth{0.6pt}
3991 \begin_layout Plain Layout
4000 \begin_layout Plain Layout
4009 \begin_layout Plain Layout
4018 \begin_layout Plain Layout
4027 \begin_layout Plain Layout
4034 \begin_layout Plain Layout
4042 pgfbox[center,center]{$s$}}
4045 \begin_layout Plain Layout
4053 pgfbox[center,center]{$t$}}
4056 \begin_layout Plain Layout
4060 color{beamerexample}
4063 \begin_layout Plain Layout
4072 \begin_layout Plain Layout
4076 pgfnodesetsepstart{2pt}
4079 \begin_layout Plain Layout
4083 pgfnodesetsepend{2pt}
4086 \begin_layout Plain Layout
4092 pgfnodeconnline{B}{A}}
4095 \begin_layout Plain Layout
4101 pgfnodeconnline{B}{C}}
4104 \begin_layout Plain Layout
4110 pgfnodeconnline{C}{D}}
4113 \begin_layout Plain Layout
4119 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4122 \begin_layout Plain Layout
4130 pgfbox[left,center]{$G
4135 \begin_layout Plain Layout
4142 \begin_layout Plain Layout
4150 pgfbox[left,center]{$G'
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
4200 \begin_layout Plain Layout
4209 \begin_layout Plain Layout
4218 \begin_layout Plain Layout
4227 \begin_layout Plain Layout
4236 \begin_layout Plain Layout
4245 \begin_layout Plain Layout
4254 \begin_layout Plain Layout
4263 \begin_layout Plain Layout
4272 \begin_layout Plain Layout
4281 \begin_layout Plain Layout
4290 \begin_layout Plain Layout
4299 \begin_layout Plain Layout
4306 \begin_layout Plain Layout
4314 pgfbox[center,center]{$s'$}}
4317 \begin_layout Plain Layout
4325 pgfbox[center,center]{$t'$}}
4328 \begin_layout Plain Layout
4333 \begin_layout Plain Layout
4338 \begin_layout Plain Layout
4345 \begin_layout Plain Layout
4349 pgfsetlinewidth{0.4pt}
4352 \begin_layout Plain Layout
4356 color{beamerexample!25!averagebackgroundcolor}
4359 \begin_layout Plain Layout
4363 pgfnodeconnline{A2}{C1}
4366 \begin_layout Plain Layout
4370 pgfnodeconnline{A2}{D1}
4373 \begin_layout Plain Layout
4377 pgfnodeconnline{B2}{A1}
4380 \begin_layout Plain Layout
4384 pgfnodeconnline{B2}{C1}
4387 \begin_layout Plain Layout
4391 pgfnodeconnline{B2}{D1}
4394 \begin_layout Plain Layout
4398 pgfnodeconnline{C2}{D1}
4401 \begin_layout Plain Layout
4405 pgfnodeconnline{D2}{A1}
4408 \begin_layout Plain Layout
4412 pgfnodeconnline{D2}{B1}
4415 \begin_layout Plain Layout
4419 pgfnodeconnline{A3}{C2}
4422 \begin_layout Plain Layout
4426 pgfnodeconnline{A3}{D2}
4429 \begin_layout Plain Layout
4433 pgfnodeconnline{B3}{A2}
4436 \begin_layout Plain Layout
4440 pgfnodeconnline{B3}{C2}
4443 \begin_layout Plain Layout
4447 pgfnodeconnline{B3}{D2}
4450 \begin_layout Plain Layout
4454 pgfnodeconnline{C3}{D2}
4457 \begin_layout Plain Layout
4461 pgfnodeconnline{D3}{A2}
4464 \begin_layout Plain Layout
4468 pgfnodeconnline{D3}{B2}
4471 \begin_layout Plain Layout
4475 pgfnodeconnline{A4}{C3}
4478 \begin_layout Plain Layout
4482 pgfnodeconnline{A4}{D3}
4485 \begin_layout Plain Layout
4489 pgfnodeconnline{B4}{A3}
4492 \begin_layout Plain Layout
4496 pgfnodeconnline{B4}{C3}
4499 \begin_layout Plain Layout
4503 pgfnodeconnline{B4}{D3}
4506 \begin_layout Plain Layout
4510 pgfnodeconnline{C4}{D3}
4513 \begin_layout Plain Layout
4517 pgfnodeconnline{D4}{A3}
4520 \begin_layout Plain Layout
4524 pgfnodeconnline{D4}{B3}
4527 \begin_layout Plain Layout
4536 \begin_layout Plain Layout
4540 pgfnodeconnline{A1}{B1}
4543 \begin_layout Plain Layout
4547 pgfnodeconnline{B1}{C1}
4550 \begin_layout Plain Layout
4554 pgfnodeconnline{C1}{D1}
4557 \begin_layout Plain Layout
4561 pgfnodeconnline{A2}{B2}
4564 \begin_layout Plain Layout
4568 pgfnodeconnline{B2}{C2}
4571 \begin_layout Plain Layout
4575 pgfnodeconnline{C2}{D2}
4578 \begin_layout Plain Layout
4582 pgfnodeconnline{A3}{B3}
4585 \begin_layout Plain Layout
4589 pgfnodeconnline{B3}{C3}
4592 \begin_layout Plain Layout
4596 pgfnodeconnline{C3}{D3}
4599 \begin_layout Plain Layout
4603 pgfnodeconnline{A4}{B4}
4606 \begin_layout Plain Layout
4610 pgfnodeconnline{B4}{C4}
4613 \begin_layout Plain Layout
4617 pgfnodeconnline{C4}{D4}
4620 \begin_layout Plain Layout
4627 \begin_layout Plain Layout
4631 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4634 \begin_layout Plain Layout
4638 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4641 \begin_layout Plain Layout
4645 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4648 \begin_layout Plain Layout
4652 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4655 \begin_layout Plain Layout
4659 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4662 \begin_layout Plain Layout
4666 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4669 \begin_layout Plain Layout
4673 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4676 \begin_layout Plain Layout
4680 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4683 \begin_layout Plain Layout
4687 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4690 \begin_layout Plain Layout
4694 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4697 \begin_layout Plain Layout
4701 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4704 \begin_layout Plain Layout
4708 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4711 \begin_layout Plain Layout
4715 color{beamerexample}
4718 \begin_layout Plain Layout
4722 pgfsetlinewidth{0.6pt}
4725 \begin_layout Plain Layout
4730 \begin_layout Plain Layout
4737 \begin_layout Plain Layout
4744 \begin_layout Plain Layout
4748 pgfnodeconnline{B1}{A2}
4751 \begin_layout Plain Layout
4755 pgfnodeconnline{B2}{A3}
4758 \begin_layout Plain Layout
4762 pgfnodeconnline{B3}{A4}
4765 \begin_layout Plain Layout
4770 \begin_layout Plain Layout
4777 \begin_layout Plain Layout
4784 \begin_layout Plain Layout
4788 pgfnodeconnline{B1}{C2}
4791 \begin_layout Plain Layout
4795 pgfnodeconnline{B2}{C3}
4798 \begin_layout Plain Layout
4802 pgfnodeconnline{B3}{C4}
4805 \begin_layout Plain Layout
4810 \begin_layout Plain Layout
4817 \begin_layout Plain Layout
4824 \begin_layout Plain Layout
4828 pgfnodeconnline{C1}{D2}
4831 \begin_layout Plain Layout
4837 pgfnodeconnline{C2}{D3}}
4840 \begin_layout Plain Layout
4846 pgfnodeconnline{C3}{D4}}
4849 \begin_layout Plain Layout
4854 \begin_layout Plain Layout
4861 \begin_layout Plain Layout
4868 \begin_layout Plain Layout
4874 pgfnodeconnline{A1}{C2}}
4877 \begin_layout Plain Layout
4883 pgfnodeconnline{A2}{C3}}
4886 \begin_layout Plain Layout
4890 pgfnodeconnline{A3}{C4}
4893 \begin_layout Plain Layout
4898 \begin_layout Plain Layout
4905 \begin_layout Plain Layout
4912 \begin_layout Plain Layout
4918 pgfnodeconnline{A1}{A2}}
4921 \begin_layout Plain Layout
4925 pgfnodeconnline{A2}{A3}
4928 \begin_layout Plain Layout
4932 pgfnodeconnline{A3}{A4}
4935 \begin_layout Plain Layout
4939 pgfnodeconnline{B1}{B2}
4942 \begin_layout Plain Layout
4946 pgfnodeconnline{B2}{B3}
4949 \begin_layout Plain Layout
4953 pgfnodeconnline{B3}{B4}
4956 \begin_layout Plain Layout
4960 pgfnodeconnline{C1}{C2}
4963 \begin_layout Plain Layout
4967 pgfnodeconnline{C2}{C3}
4970 \begin_layout Plain Layout
4974 pgfnodeconnline{C3}{C4}
4977 \begin_layout Plain Layout
4981 pgfnodeconnline{D1}{D2}
4984 \begin_layout Plain Layout
4988 pgfnodeconnline{D2}{D3}
4991 \begin_layout Plain Layout
4997 pgfnodeconnline{D3}{D4}}
5000 \begin_layout Plain Layout
5005 \begin_layout Plain Layout
5019 \begin_layout AgainFrame
5020 \begin_inset Argument 1
5023 \begin_layout Plain Layout
5033 \begin_layout Subsection
5035 Approximating the Shortest Path
5039 \begin_inset Argument 4
5042 \begin_layout Plain Layout
5043 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5052 \begin_layout Definition
5057 approximation scheme for
5058 \begin_inset Formula $\Lang{tournament-shortest-path}$
5069 \begin_layout Enumerate
5071 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5077 \begin_layout Enumerate
5079 \begin_inset Formula $r>1$
5085 \begin_layout Standard
5089 \begin_layout Itemize
5091 \begin_inset Formula $s$
5095 \begin_inset space ~
5099 \begin_inset Formula $t$
5103 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5111 \begin_layout Standard
5112 \begin_inset Separator plain
5119 \begin_inset Argument 4
5122 \begin_layout Plain Layout
5123 There Exists a Logspace Approximation Scheme for
5124 \begin_inset Newline newline
5127 the Tournament Shortest Path Problem
5136 \begin_layout Theorem
5137 There exists an approximation scheme for
5138 \begin_inset Formula $\Lang{tournament-shortest-path}$
5142 \begin_inset Formula $1<r<2$
5146 \begin_inset Formula
5148 O\left(\log|V|\log\frac{1}{r-1}\right).
5160 \begin_layout Corollary
5162 paths can be constructed in logarithmic space.
5165 \begin_layout Standard
5166 \begin_inset space \hfill{}
5173 \begin_layout Plain Layout
5177 hyperlink{optimality}{
5179 beamergotobutton{More Details}}
5188 \begin_layout AgainFrame
5189 \begin_inset Argument 1
5192 \begin_layout Plain Layout
5202 \begin_layout Standard
5203 \begin_inset Note Note
5206 \begin_layout Plain Layout
5207 If a frame includes a program listing,
5208 the frame needs to be marked as
5209 \begin_inset Quotes eld
5213 \begin_inset Quotes erd
5218 has the FragileFrame layout for this.
5226 \begin_layout FragileFrame
5227 \begin_inset Argument 4
5230 \begin_layout Plain Layout
5231 Just a frame with a program code listing
5239 \begin_layout FragileFrame
5240 This is some program code:
5244 \begin_layout Standard
5245 \begin_inset listings
5246 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5250 \begin_layout Plain Layout
5255 \begin_layout Plain Layout
5257 'this is a python function'
5260 \begin_layout Plain Layout
5265 \begin_layout Plain Layout
5270 \begin_layout Plain Layout
5272 'This is a German word:
5276 \begin_layout Plain Layout
5281 \begin_layout Plain Layout
5286 \begin_layout Plain Layout
5288 'this is a python function'
5291 \begin_layout Plain Layout
5302 \begin_layout Section*
5306 \begin_layout Subsection*
5311 \begin_inset Argument 4
5314 \begin_layout Plain Layout
5325 \begin_inset Argument 2
5328 \begin_layout Plain Layout
5338 \begin_layout Itemize
5352 \begin_inset Formula $\Class{AC}^{0}$
5361 \begin_layout Itemize
5366 logspace approximation scheme
5378 shortest paths in tournaments.
5381 \begin_layout Itemize
5395 \begin_inset Formula $\Class{NL}$
5404 \begin_layout Standard
5405 \begin_inset Separator plain
5412 \begin_inset Argument 2
5415 \begin_layout Plain Layout
5425 \begin_layout Itemize
5426 The same results apply to graphs with
5427 \begin_inset Newline newline
5430 bounded independence number.
5431 \begin_inset space \hfill{}
5438 \begin_layout Plain Layout
5442 hyperlink{independence}{
5444 beamergotobutton{More Details}}
5452 \begin_layout Itemize
5453 The complexity of finding paths in undirected graphs
5454 \begin_inset Newline newline
5458 \begin_inset space \hfill{}
5465 \begin_layout Plain Layout
5469 hyperlink{undirected}{
5471 beamergotobutton{More Details}}
5481 \begin_layout Subsection*
5486 \begin_inset Argument 4
5489 \begin_layout Plain Layout
5499 \begin_layout Standard
5503 \begin_layout Plain Layout
5507 beamertemplatebookbibitems
5515 \begin_layout Bibliography
5516 \begin_inset CommandInset bibitem
5517 LatexCommand bibitem
5524 \begin_inset space ~
5532 \begin_layout Plain Layout
5543 Topics on Tournaments.
5550 \begin_layout Plain Layout
5567 \begin_layout Plain Layout
5571 beamertemplatearticlebibitems
5579 \begin_layout Bibliography
5580 \begin_inset CommandInset bibitem
5581 LatexCommand bibitem
5582 key "NickelsenT2002"
5588 \begin_inset space ~
5591 Arfst Nickelsen and Till Tantau.
5596 \begin_layout Plain Layout
5605 On reachability in graphs with bounded independence number.
5609 \begin_layout Plain Layout
5628 \begin_layout Bibliography
5629 \begin_inset CommandInset bibitem
5630 LatexCommand bibitem
5637 \begin_inset space ~
5644 \begin_layout Plain Layout
5653 A logspace approximation scheme for the shortest path problem for graphs with bounded independence number.
5657 \begin_layout Plain Layout
5678 \begin_layout Plain Layout
5691 \begin_layout Standard
5696 \begin_layout Plain Layout
5700 AtBeginSubsection[]{}
5708 \begin_layout Section
5712 \begin_layout Subsection
5713 Graphs With Bounded Independence Number
5717 \begin_inset Argument 3
5720 \begin_layout Plain Layout
5727 \begin_inset Argument 4
5730 \begin_layout Plain Layout
5731 Definition of Independence Number of a Graph
5740 \begin_layout Definition
5750 \begin_inset Formula $\alpha(G)$
5754 \begin_inset Newline newline
5757 is the maximum number of vertices we can pick,
5758 \begin_inset Newline newline
5761 such that there is no edge between them.
5764 \begin_layout Example
5765 Tournaments have independence number 1.
5770 \begin_layout Standard
5771 \begin_inset Separator plain
5778 \begin_inset Argument 4
5781 \begin_layout Plain Layout
5782 The Results for Tournaments also Apply to
5783 \begin_inset Newline newline
5786 Graphs With Bounded Independence Number
5795 \begin_layout Theorem
5797 \begin_inset space ~
5801 \begin_inset Formula $k$
5813 in graphs with independence number
5814 \begin_inset Newline newline
5818 \begin_inset space ~
5822 \begin_inset Formula $k$
5826 \begin_inset Formula $\Class{AC}^{0}$
5832 \begin_layout Standard
5833 \begin_inset Separator plain
5839 \begin_layout Theorem
5841 \begin_inset space ~
5845 \begin_inset Formula $k$
5853 logspace approximation scheme
5857 for approximating the shortest path in graphs with independence number at most
5858 \begin_inset space ~
5862 \begin_inset Formula $k$
5868 \begin_layout Standard
5869 \begin_inset Separator plain
5875 \begin_layout Theorem
5877 \begin_inset space ~
5881 \begin_inset Formula $k$
5893 in graphs with independence number at most
5894 \begin_inset space ~
5898 \begin_inset Formula $k$
5906 \begin_inset Formula $\Class{NL}$
5915 \begin_layout Subsection
5916 Finding Paths in Undirected Graphs
5920 \begin_inset Argument 1
5923 \begin_layout Plain Layout
5931 \begin_inset Argument 3
5934 \begin_layout Plain Layout
5941 \begin_inset Argument 4
5944 \begin_layout Plain Layout
5945 The Complexity of Finding Paths in Undirected Graphs
5946 \begin_inset Newline newline
5959 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5963 \begin_inset Formula $\Class{SL}$
5969 \begin_layout Corollary
5970 For undirected graphs,
5975 \begin_layout Itemize
5976 the reachability problem in logspace iff
5977 \begin_inset Formula $\Class L=\Class{SL}$
5983 \begin_layout Itemize
5984 the construction problem in logspace iff
5985 \begin_inset Flex Alternative
5988 \begin_layout Plain Layout
5989 \begin_inset Argument 1
5992 \begin_layout Plain Layout
6000 \begin_inset Argument 2
6003 \begin_layout Plain Layout
6010 \begin_inset Flex Alert
6013 \begin_layout Plain Layout
6014 \begin_inset Formula $\Class L=\Class{SL}$
6031 \begin_layout Itemize
6032 the optimization problem in logspace iff
6033 \begin_inset Flex Alternative
6036 \begin_layout Plain Layout
6037 \begin_inset Argument 1
6040 \begin_layout Plain Layout
6048 \begin_inset Argument 2
6051 \begin_layout Plain Layout
6058 \begin_inset Flex Alert
6061 \begin_layout Plain Layout
6062 \begin_inset Formula $\Class L=\Class{NL}$
6079 \begin_layout Itemize
6080 the approximation problem in logspace iff ?.
6086 \begin_layout Subsection
6087 The Approximation Scheme is Optimal
6091 \begin_inset Argument 3
6094 \begin_layout Plain Layout
6101 \begin_inset Argument 4
6104 \begin_layout Plain Layout
6105 The Approximation Scheme is Optimal
6114 \begin_layout Theorem
6115 Suppose there exists an approximation scheme for
6116 \begin_inset Formula $\Lang{tournament-shortest-path}$
6120 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6125 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6136 \begin_layout Enumerate
6137 Suppose the approximation scheme exists.
6138 \begin_inset Newline newline
6142 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6149 \begin_layout Enumerate
6151 \begin_inset Formula $(T,s,t)$
6156 \begin_inset Formula $n$
6159 be the number of vertices.
6162 \begin_layout Enumerate
6163 Run the approximation scheme for
6164 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6168 \begin_inset Newline newline
6172 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6178 \begin_layout Enumerate
6179 The resulting path has optimal length.
6184 \begin_layout Plain Layout