1 #LyX 2.3 created this file. For more info see http://www.lyx.org/
5 \save_transient_properties true
6 \origin /systemlyxdir/examples/
9 \beamertemplateshadingbackground{red!5}{structure!5}
11 \usepackage{beamerthemeshadow}
12 \usepackage{pgfnodes,pgfarrows,pgfheaps}
14 \beamertemplatetransparentcovereddynamicmedium
17 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
18 \logo{\pgfuseimage{icsi-logo}}
23 \newcommand{\Class}[1]{\operatorname{\mathchoice
29 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
31 % This gets defined by beamerbasecolor.sty, but only at the beginning of
33 \colorlet{averagebackgroundcolor}{normal text.bg}
35 \newcommand{\tape}[3]{%
36 \color{structure!30!averagebackgroundcolor}
37 \pgfmoveto{\pgfxy(-0.5,0)}
38 \pgflineto{\pgfxy(-0.6,0.1)}
39 \pgflineto{\pgfxy(-0.4,0.2)}
40 \pgflineto{\pgfxy(-0.6,0.3)}
41 \pgflineto{\pgfxy(-0.4,0.4)}
42 \pgflineto{\pgfxy(-0.5,0.5)}
43 \pgflineto{\pgfxy(4,0.5)}
44 \pgflineto{\pgfxy(4.1,0.4)}
45 \pgflineto{\pgfxy(3.9,0.3)}
46 \pgflineto{\pgfxy(4.1,0.2)}
47 \pgflineto{\pgfxy(3.9,0.1)}
48 \pgflineto{\pgfxy(4,0)}
53 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
54 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
57 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
60 \newcommand{\shorttape}[3]{%
61 \color{structure!30!averagebackgroundcolor}
62 \pgfmoveto{\pgfxy(-0.5,0)}
63 \pgflineto{\pgfxy(-0.6,0.1)}
64 \pgflineto{\pgfxy(-0.4,0.2)}
65 \pgflineto{\pgfxy(-0.6,0.3)}
66 \pgflineto{\pgfxy(-0.4,0.4)}
67 \pgflineto{\pgfxy(-0.5,0.5)}
68 \pgflineto{\pgfxy(1,0.5)}
69 \pgflineto{\pgfxy(1.1,0.4)}
70 \pgflineto{\pgfxy(0.9,0.3)}
71 \pgflineto{\pgfxy(1.1,0.2)}
72 \pgflineto{\pgfxy(0.9,0.1)}
73 \pgflineto{\pgfxy(1,0)}
78 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
79 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
82 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
85 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
86 {color(0pt)=(black); color(1cm)=(structure!65!white)}
87 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
88 {color(0pt)=(black); color(1cm)=(structure!55!white)}
89 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
90 {color(0pt)=(black); color(1cm)=(structure!45!white)}
91 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
92 {color(0pt)=(black); color(1cm)=(structure!35!white)}
93 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
94 {color(0pt)=(black); color(1cm)=(structure!25!white)}
95 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
96 {color(0pt)=(black); color(1cm)=(red!35!white)}
98 \newcommand{\heap}[5]{%
101 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
103 \begin{pgfmagnify}{1}{#1}
104 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
110 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
114 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
118 \newcommand{\langat}[2]{%
119 \color{black!30!beamerexample}
120 \pgfsetlinewidth{0.6pt}
121 \pgfsetendarrow{\pgfarrowdot}
122 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
123 \color{beamerexample}
124 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
127 \newcommand{\langatother}[2]{%
128 \color{black!30!beamerexample}
129 \pgfsetlinewidth{0.6pt}
130 \pgfsetendarrow{\pgfarrowdot}
131 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
132 \color{beamerexample}
133 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
137 \pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
140 \pgfdeclareradialshading{graphnode}
141 {\pgfpoint{-3pt}{3.6pt}}%
142 {color(0cm)=(beamerexample!15);
143 color(2.63pt)=(beamerexample!75);
144 color(5.26pt)=(beamerexample!70!black);
145 color(7.6pt)=(beamerexample!50!black);
146 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
148 \newcommand{\graphnode}[2]{
149 \pgfnodecircle{#1}[virtual]{#2}{8pt}
150 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
154 \use_default_options false
155 \maintain_unincluded_children false
157 \language_package default
160 \font_roman "times" "default"
161 \font_sans "default" "default"
162 \font_typewriter "default" "default"
163 \font_math "auto" "auto"
164 \font_default_family default
165 \use_non_tex_fonts false
168 \font_sf_scale 100 100
169 \font_tt_scale 100 100
171 \use_dash_ligatures false
173 \default_output_format default
175 \bibtex_command default
176 \index_command default
177 \paperfontsize default
182 \use_package amsmath 2
183 \use_package amssymb 2
184 \use_package cancel 0
186 \use_package mathdots 1
187 \use_package mathtools 0
188 \use_package mhchem 1
189 \use_package stackrel 0
190 \use_package stmaryrd 0
191 \use_package undertilde 0
193 \cite_engine_type default
197 \paperorientation portrait
207 \paragraph_separation indent
208 \paragraph_indentation default
210 \quotes_style english
213 \paperpagestyle default
214 \tracking_changes false
215 \output_changes false
218 \html_be_strict false
225 \begin_inset Newline newline
228 Finding Paths in Tournaments
235 \begin_layout Institute
236 International Computer Science Institute
237 \begin_inset Newline newline
241 \begin_inset Argument 1
244 \begin_layout Plain Layout
258 \begin_inset Argument 4
261 \begin_layout Plain Layout
271 \begin_layout Standard
272 \begin_inset CommandInset toc
273 LatexCommand tableofcontents
281 \begin_layout Plain Layout
292 \begin_layout Standard
296 \begin_layout Plain Layout
298 % Show the table of contents at the beginning
301 \begin_layout Plain Layout
303 % of every subsection.
306 \begin_layout Plain Layout
310 AtBeginSubsection[]{%
313 \begin_layout Plain Layout
320 \begin_layout Plain Layout
327 \begin_layout Plain Layout
331 tableofcontents[current,currentsubsection]
334 \begin_layout Plain Layout
339 \begin_layout Plain Layout
349 \begin_layout Section
353 \begin_layout Subsection
354 What are Tournaments?
358 \begin_inset Argument 4
361 \begin_layout Plain Layout
362 Tournaments Consist of Jousts Between Knights
371 \begin_layout Columns
380 \begin_layout Standard
384 \begin_layout Plain Layout
388 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
391 \begin_layout Plain Layout
395 pgfnodebox{A}[virtual]{
400 \begin_layout Plain Layout
404 pgfuseimage{knight1}}{2pt}{2pt}
407 \begin_layout Plain Layout
411 pgfnodebox{B}[virtual]{
416 \begin_layout Plain Layout
420 pgfuseimage{knight2}}{2pt}{2pt}
423 \begin_layout Plain Layout
427 pgfnodebox{C}[virtual]{
432 \begin_layout Plain Layout
436 pgfuseimage{knight3}}{2pt}{2pt}
439 \begin_layout Plain Layout
443 pgfnodebox{D}[virtual]{
448 \begin_layout Plain Layout
452 pgfuseimage{knight4}}{2pt}{2pt}
455 \begin_layout Plain Layout
462 \begin_layout Plain Layout
473 \begin_layout Plain Layout
480 \begin_layout Plain Layout
484 pgfsetlinewidth{0.6pt}
487 \begin_layout Plain Layout
491 pgfnodeconnline{A}{B}
494 \begin_layout Plain Layout
498 pgfnodeconnline{A}{C}
501 \begin_layout Plain Layout
505 pgfnodeconnline{D}{A}
508 \begin_layout Plain Layout
512 pgfnodeconnline{C}{B}
515 \begin_layout Plain Layout
519 pgfnodeconnline{B}{D}
522 \begin_layout Plain Layout
526 pgfnodeconnline{C}{D}
529 \begin_layout Plain Layout
534 \begin_layout Plain Layout
551 \begin_inset Argument 2
554 \begin_layout Plain Layout
555 What is a Tournament?
564 \begin_layout Itemize
565 \begin_inset Argument item:2
568 \begin_layout Plain Layout
577 \begin_layout Itemize
578 \begin_inset Argument item:2
581 \begin_layout Plain Layout
587 Every pair has a joust.
590 \begin_layout Itemize
591 \begin_inset Argument item:2
594 \begin_layout Plain Layout
600 In every joust one knight wins.
606 \begin_layout Standard
607 \begin_inset Separator plain
614 \begin_inset Argument 4
617 \begin_layout Plain Layout
618 Tournaments are Complete Directed Graphs
627 \begin_layout Columns
636 \begin_layout Standard
640 \begin_layout Plain Layout
644 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
647 \begin_layout Plain Layout
654 \begin_layout Plain Layout
658 pgfsetlinewidth{0.6pt}
661 \begin_layout Plain Layout
670 \begin_layout Plain Layout
679 \begin_layout Plain Layout
688 \begin_layout Plain Layout
697 \begin_layout Plain Layout
704 \begin_layout Plain Layout
712 pgfbox[center,center]{$v_2$}}
715 \begin_layout Plain Layout
723 pgfbox[center,center]{$v_3$}}
726 \begin_layout Plain Layout
734 pgfbox[center,center]{$v_4$}}
737 \begin_layout Plain Layout
745 pgfbox[center,center]{$v_1$}}
748 \begin_layout Plain Layout
755 \begin_layout Plain Layout
764 \begin_layout Plain Layout
768 pgfnodesetsepstart{2pt}
771 \begin_layout Plain Layout
775 pgfnodesetsepend{4pt}
778 \begin_layout Plain Layout
782 pgfnodeconnline{A}{B}
785 \begin_layout Plain Layout
789 pgfnodeconnline{A}{C}
792 \begin_layout Plain Layout
796 pgfnodeconnline{D}{A}
799 \begin_layout Plain Layout
803 pgfnodeconnline{C}{B}
806 \begin_layout Plain Layout
810 pgfnodeconnline{B}{D}
813 \begin_layout Plain Layout
817 pgfnodeconnline{D}{C}
820 \begin_layout Plain Layout
836 \begin_layout Definition
837 \begin_inset Argument 1
840 \begin_layout Plain Layout
858 \begin_layout Enumerate
862 \begin_layout Enumerate
863 with exactly one edge between
864 \begin_inset Newline newline
867 any two different vertices.
873 \begin_layout Standard
874 \begin_inset Separator plain
881 \begin_inset Argument 2
884 \begin_layout Plain Layout
891 \begin_inset Argument 4
894 \begin_layout Plain Layout
895 Tournaments Arise Naturally in Different Situations
904 \begin_layout ExampleBlock
905 \begin_inset Argument 2
908 \begin_layout Plain Layout
909 Applications in Ordering Theory
918 \begin_layout Standard
919 Elements in a set need to be sorted.
921 \begin_inset Newline newline
924 The comparison relation may be cyclic, however.
928 \begin_layout Standard
929 \begin_inset Separator plain
935 \begin_layout ExampleBlock
936 \begin_inset Argument 2
939 \begin_layout Plain Layout
940 Applications in Sociology
949 \begin_layout Standard
950 Several candidates apply for a position.
951 \begin_inset Newline newline
954 Reviewers decide for any two candidates whom they prefer.
959 \begin_layout Standard
960 \begin_inset Separator plain
966 \begin_layout ExampleBlock
967 \begin_inset Argument 2
970 \begin_layout Plain Layout
971 Applications in Structural Complexity Theory
980 \begin_layout Standard
982 \begin_inset Formula $L$
985 is given and a selector function
986 \begin_inset Formula $f$
990 \begin_inset Newline newline
993 It chooses from any two words the one more likely to be in
994 \begin_inset Formula $f$
1002 \begin_layout Subsection
1003 What Does ``Finding Paths'' Mean?
1007 \begin_inset Argument 4
1010 \begin_layout Plain Layout
1011 ``Finding Paths'' is Ambiguous
1021 \begin_inset Argument 2
1024 \begin_layout Plain Layout
1026 \begin_inset Flex Only
1029 \begin_layout Plain Layout
1030 \begin_inset Argument 1
1033 \begin_layout Plain Layout
1039 Path Finding Problems
1045 \begin_inset Flex Only
1048 \begin_layout Plain Layout
1049 \begin_inset Argument 1
1052 \begin_layout Plain Layout
1059 \begin_inset Formula $\Lang{reach}$
1068 \begin_inset Flex Only
1071 \begin_layout Plain Layout
1072 \begin_inset Argument 1
1075 \begin_layout Plain Layout
1081 the Construction Problem
1087 \begin_inset Flex Only
1090 \begin_layout Plain Layout
1091 \begin_inset Argument 1
1094 \begin_layout Plain Layout
1100 the Optimization Problem
1106 \begin_inset Flex Only
1109 \begin_layout Plain Layout
1110 \begin_inset Argument 1
1113 \begin_layout Plain Layout
1120 \begin_inset Formula $\Lang{distance}$
1129 \begin_inset Flex Only
1132 \begin_layout Plain Layout
1133 \begin_inset Argument 1
1136 \begin_layout Plain Layout
1142 the Approximation Problem
1156 \begin_layout Itemize
1166 \begin_inset Formula $G=(V,E)$
1178 \begin_inset Formula $s\in V$
1190 \begin_inset Formula $t\in V$
1196 \begin_layout Itemize
1197 \begin_inset Argument item:2
1200 \begin_layout Plain Layout
1213 \begin_inset space ~
1217 \begin_inset Formula $d$
1224 \begin_layout Plain Layout
1236 \begin_layout Itemize
1237 \begin_inset Argument item:2
1240 \begin_layout Plain Layout
1255 \begin_inset Formula $r>1$
1262 \begin_layout Standard
1266 \begin_layout Plain Layout
1278 \begin_layout Overprint
1279 \begin_inset Argument item:1
1282 \begin_layout Plain Layout
1292 \begin_layout Columns
1293 \begin_inset Argument 1
1296 \begin_layout Plain Layout
1306 \begin_layout Standard
1307 \begin_inset Flex Alternative
1310 \begin_layout Plain Layout
1311 \begin_inset Argument 1
1314 \begin_layout Plain Layout
1321 \begin_inset Argument 2
1324 \begin_layout Plain Layout
1328 \begin_layout Plain Layout
1348 \begin_layout Plain Layout
1365 \begin_layout ExampleBlock
1366 \begin_inset Argument 2
1369 \begin_layout Plain Layout
1379 \begin_layout Standard
1383 \begin_layout Plain Layout
1387 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1390 \begin_layout Plain Layout
1394 \begin_layout Plain Layout
1398 color{beamerexample}
1401 \begin_layout Plain Layout
1405 \begin_layout Plain Layout
1409 pgfsetlinewidth{0.6pt}
1412 \begin_layout Plain Layout
1416 \begin_layout Plain Layout
1425 \begin_layout Plain Layout
1429 \begin_layout Plain Layout
1438 \begin_layout Plain Layout
1442 \begin_layout Plain Layout
1451 \begin_layout Plain Layout
1455 \begin_layout Plain Layout
1464 \begin_layout Plain Layout
1468 \begin_layout Plain Layout
1472 \begin_layout Plain Layout
1476 \begin_layout Plain Layout
1483 \begin_layout Plain Layout
1487 \begin_layout Plain Layout
1495 pgfbox[center,center]{$t$}}
1498 \begin_layout Plain Layout
1502 \begin_layout Plain Layout
1510 pgfbox[center,center]{$s$}}
1513 \begin_layout Plain Layout
1517 \begin_layout Plain Layout
1521 \begin_layout Plain Layout
1525 \begin_layout Plain Layout
1529 color{beamerexample}
1532 \begin_layout Plain Layout
1536 \begin_layout Plain Layout
1545 \begin_layout Plain Layout
1549 \begin_layout Plain Layout
1553 pgfnodesetsepstart{2pt}
1556 \begin_layout Plain Layout
1560 \begin_layout Plain Layout
1564 pgfnodesetsepend{4pt}
1567 \begin_layout Plain Layout
1571 \begin_layout Plain Layout
1575 pgfnodeconnline{A}{B}
1578 \begin_layout Plain Layout
1582 \begin_layout Plain Layout
1586 pgfnodeconnline{A}{C}
1589 \begin_layout Plain Layout
1593 \begin_layout Plain Layout
1597 pgfnodeconnline{D}{A}
1600 \begin_layout Plain Layout
1604 \begin_layout Plain Layout
1608 pgfnodeconnline{C}{B}
1611 \begin_layout Plain Layout
1615 \begin_layout Plain Layout
1619 pgfnodeconnline{B}{D}
1622 \begin_layout Plain Layout
1626 \begin_layout Plain Layout
1630 pgfnodeconnline{D}{C}
1633 \begin_layout Plain Layout
1637 \begin_layout Plain Layout
1641 \begin_layout Plain Layout
1645 \begin_layout Plain Layout
1655 pgfbox[left,center]{, $d=2$}}}
1658 \begin_layout Plain Layout
1662 \begin_layout Plain Layout
1672 pgfbox[left,center]{, $r=1.5$}}}
1675 \begin_layout Plain Layout
1679 \begin_layout Plain Layout
1689 pgfbox[left,center]{, $r=1.25$}}}
1692 \begin_layout Plain Layout
1696 \begin_layout Plain Layout
1709 \begin_layout Standard
1710 \begin_inset Flex Only
1713 \begin_layout Plain Layout
1714 \begin_inset Argument 1
1717 \begin_layout Plain Layout
1727 \begin_layout Plain Layout
1744 \begin_layout ExampleBlock
1745 \begin_inset Argument 1
1748 \begin_layout Plain Layout
1755 \begin_inset Argument 2
1758 \begin_layout Plain Layout
1768 \begin_layout Standard
1772 \begin_layout Plain Layout
1776 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1779 \begin_layout Plain Layout
1786 \begin_layout Plain Layout
1790 color{beamerexample}
1793 \begin_layout Plain Layout
1797 pgfsetlinewidth{0.6pt}
1800 \begin_layout Plain Layout
1809 \begin_layout Plain Layout
1818 \begin_layout Plain Layout
1827 \begin_layout Plain Layout
1836 \begin_layout Plain Layout
1843 \begin_layout Plain Layout
1851 pgfbox[center,center]{$t$}}
1854 \begin_layout Plain Layout
1862 pgfbox[center,center]{$s$}}
1865 \begin_layout Plain Layout
1869 color{beamerexample}
1872 \begin_layout Plain Layout
1881 \begin_layout Plain Layout
1885 pgfnodesetsepstart{2pt}
1888 \begin_layout Plain Layout
1892 pgfnodesetsepend{4pt}
1895 \begin_layout Plain Layout
1901 pgfnodeconnline{A}{B}}
1904 \begin_layout Plain Layout
1910 pgfnodeconnline{A}{C}}
1913 \begin_layout Plain Layout
1919 pgfnodeconnline{D}{A}}
1922 \begin_layout Plain Layout
1928 pgfnodeconnline{C}{B}}
1931 \begin_layout Plain Layout
1935 pgfnodeconnline{B}{D}
1938 \begin_layout Plain Layout
1942 pgfnodeconnline{D}{C}
1945 \begin_layout Plain Layout
1950 \begin_layout Plain Layout
1960 pgfbox[left,center]{
1965 \begin_layout Plain Layout
1980 \begin_layout Overprint
1981 \begin_inset Argument item:1
1984 \begin_layout Plain Layout
1995 \begin_inset Argument 2
1998 \begin_layout Plain Layout
1999 Variants of Path Finding Problems
2008 \begin_layout Description
2009 \begin_inset Argument item:1
2012 \begin_layout Plain Layout
2019 \begin_inset space ~
2022 Problem: Is there a path from
2023 \begin_inset Formula $s$
2027 \begin_inset space ~
2031 \begin_inset Formula $t$
2035 \begin_inset Argument 2
2038 \begin_layout Plain Layout
2039 Approximation Problem:
2047 \begin_layout Description
2048 \begin_inset Argument item:1
2051 \begin_layout Plain Layout
2058 \begin_inset space ~
2061 Problem: Construct a path from
2062 \begin_inset Formula $s$
2066 \begin_inset space ~
2070 \begin_inset Formula $t$
2076 \begin_layout Description
2077 \begin_inset Argument item:1
2080 \begin_layout Plain Layout
2087 \begin_inset space ~
2090 Problem: Construct a shortest path from
2091 \begin_inset Formula $s$
2095 \begin_inset space ~
2099 \begin_inset Formula $t$
2105 \begin_layout Description
2106 \begin_inset Argument item:1
2109 \begin_layout Plain Layout
2116 \begin_inset space ~
2119 Problem: Is the distance of
2120 \begin_inset Formula $s$
2124 \begin_inset space ~
2128 \begin_inset Formula $t$
2132 \begin_inset space ~
2136 \begin_inset Formula $d$
2142 \begin_layout Description
2143 \begin_inset Argument item:1
2146 \begin_layout Plain Layout
2153 \begin_inset space ~
2156 Problem: Construct a path from
2157 \begin_inset Formula $s$
2161 \begin_inset space ~
2165 \begin_inset Formula $t$
2169 \begin_inset Newline newline
2172 approximately their distance.
2178 \begin_layout Section
2182 \begin_layout Subsection
2183 Standard Complexity Classes
2186 \begin_layout Standard
2190 \begin_layout Plain Layout
2194 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2196 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2206 \begin_inset Argument 4
2209 \begin_layout Plain Layout
2210 The Classes L and NL are Defined via
2211 \begin_inset Newline newline
2214 Logspace Turing Machines
2223 \begin_layout Standard
2227 \begin_layout Plain Layout
2231 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2234 \begin_layout Plain Layout
2243 \begin_layout Plain Layout
2247 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2250 \begin_layout Plain Layout
2257 \begin_layout Plain Layout
2266 \begin_layout Plain Layout
2270 tape{}{output tape (write only)}{10690836937182}}
2273 \begin_layout Plain Layout
2278 \begin_layout Plain Layout
2285 \begin_layout Plain Layout
2294 \begin_layout Plain Layout
2298 shorttape{work tape (read/write), $O(
2300 log n)$ symbols}{}{42}}
2303 \begin_layout Plain Layout
2312 \begin_layout Plain Layout
2316 pgfbox[center,center]{
2318 pgfuseimage{computer}}}
2321 \begin_layout Plain Layout
2326 \begin_layout Plain Layout
2330 pgfsetlinewidth{0.6pt}
2333 \begin_layout Plain Layout
2340 \begin_layout Plain Layout
2349 \begin_layout Plain Layout
2353 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2356 \begin_layout Plain Layout
2362 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2365 \begin_layout Plain Layout
2371 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2374 \begin_layout Plain Layout
2387 \begin_layout Standard
2388 \begin_inset Separator plain
2395 \begin_inset Argument 4
2398 \begin_layout Plain Layout
2399 Logspace Turing Machines Are Quite Powerful
2409 \begin_inset Argument 2
2412 \begin_layout Plain Layout
2413 Deterministic logspace machines can compute
2422 \begin_layout Itemize
2423 addition, multiplication, and even division
2426 \begin_layout Itemize
2427 reductions used in completeness proofs,
2430 \begin_layout Itemize
2431 reachability in forests.
2440 \begin_inset Argument 2
2443 \begin_layout Plain Layout
2444 Non-deterministic logspace machines can compute
2453 \begin_layout Itemize
2454 reachability in graphs,
2457 \begin_layout Itemize
2458 non-reachability in graphs,
2461 \begin_layout Itemize
2462 satisfiability with two literals per clause.
2467 \begin_layout Standard
2468 \begin_inset Separator plain
2475 \begin_inset Argument 1
2478 \begin_layout Plain Layout
2485 \begin_inset Argument 3
2488 \begin_layout Plain Layout
2495 \begin_inset Argument 4
2498 \begin_layout Plain Layout
2499 The Complexity Class Hierarchy
2508 \begin_layout Standard
2512 \begin_layout Plain Layout
2516 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2519 \begin_layout Plain Layout
2523 pgfsetlinewidth{0.8pt}
2526 \begin_layout Plain Layout
2535 \begin_layout Plain Layout
2539 pgfsetdash{{2pt}}{0pt}
2542 \begin_layout Plain Layout
2550 Class{NC}^2$}{black!50!structure}{2}}
2553 \begin_layout Plain Layout
2559 Class{NL}$}{black!50!structure}{3}
2562 \begin_layout Plain Layout
2568 Class{L}$}{black!50!structure}{4}
2571 \begin_layout Plain Layout
2582 \begin_layout Plain Layout
2588 Class{NC}^1}$}{black!50!structure}{5}
2591 \begin_layout Plain Layout
2596 \begin_layout Plain Layout
2603 \begin_layout Plain Layout
2614 \begin_layout Plain Layout
2620 Class{AC}^0}$}{black}{6}
2623 \begin_layout Plain Layout
2628 \begin_layout Plain Layout
2632 pgfsetlinewidth{1.0pt}
2635 \begin_layout Plain Layout
2642 \begin_layout Plain Layout
2646 pgfxyline(-5,0)(5,0)
2649 \begin_layout Plain Layout
2660 \begin_layout Plain Layout
2670 operatorname{forest}}$}}
2673 \begin_layout Plain Layout
2684 \begin_layout Plain Layout
2703 \begin_layout Plain Layout
2722 \begin_layout Plain Layout
2735 \begin_layout Plain Layout
2743 operatorname{forest}}$,}
2748 \begin_layout Plain Layout
2756 operatorname{forest}}$,}
2761 \begin_layout Plain Layout
2769 operatorname{path}}$,}
2774 \begin_layout Plain Layout
2782 operatorname{path}}$}}}
2785 \begin_layout Plain Layout
2790 \begin_layout Plain Layout
2800 operatorname{tourn}}$}}
2803 \begin_layout Plain Layout
2816 \begin_layout Plain Layout
2824 operatorname{tourn}}$,}
2829 \begin_layout Plain Layout
2840 \begin_layout Plain Layout
2849 \begin_layout Plain Layout
2854 \begin_layout Plain Layout
2860 pgfsetdash{{1pt}}{0pt}%
2863 \begin_layout Plain Layout
2871 operatorname{tourn}}$''}
2874 \begin_layout Plain Layout
2879 \begin_layout Plain Layout
2892 \begin_layout Standard
2893 \begin_inset Separator plain
2900 \begin_inset Argument 4
2903 \begin_layout Plain Layout
2904 The Circuit Complexity Classes AC
2905 \begin_inset Formula $^{0}$
2909 \begin_inset Formula $^{1}$
2913 \begin_inset Formula $^{2}$
2917 \begin_inset Newline newline
2920 Limit the Circuit Depth
2929 \begin_layout Standard
2933 \begin_layout Plain Layout
2942 \begin_layout Plain Layout
2954 \begin_layout Columns
2955 \begin_inset Argument 1
2958 \begin_layout Plain Layout
2968 \begin_layout Column
2973 \begin_inset Argument 2
2976 \begin_layout Plain Layout
2978 \begin_inset Formula $\Class{AC}^{0}$
2990 \begin_layout Itemize
2991 \begin_inset Formula $O(1)$
2997 \begin_layout Itemize
3002 \begin_layout Examples
3007 \begin_layout Itemize
3008 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3014 \begin_layout Itemize
3015 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3026 \begin_layout Column
3031 \begin_inset Argument 2
3034 \begin_layout Plain Layout
3036 \begin_inset Formula $\Class{NC}^{1}$
3048 \begin_layout Itemize
3049 \begin_inset Formula $O(\log n)$
3055 \begin_layout Itemize
3060 \begin_layout Examples
3065 \begin_layout Itemize
3066 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3072 \begin_layout Itemize
3073 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3079 \begin_layout Itemize
3080 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3091 \begin_layout Column
3096 \begin_inset Argument 2
3099 \begin_layout Plain Layout
3101 \begin_inset Formula $\Class{NC}^{2}$
3113 \begin_layout Itemize
3114 \begin_inset Formula $O(\log^{2}n)$
3120 \begin_layout Itemize
3125 \begin_layout Examples
3130 \begin_layout Itemize
3131 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3140 \begin_layout AgainFrame
3141 \begin_inset Argument 1
3144 \begin_layout Plain Layout
3153 \begin_layout Subsection
3154 Standard Complexity Results on Finding Paths
3158 \begin_inset Argument 4
3161 \begin_layout Plain Layout
3162 All Variants of Finding Paths in Directed Graphs
3163 \begin_inset Newline newline
3166 Are Equally Difficult
3176 \begin_inset Formula $\Lang{reach}$
3180 \begin_inset Formula $\Lang{distance}$
3184 \begin_inset Formula $\Class{NL}$
3195 \begin_layout Corollary
3196 For directed graphs, we can solve
3200 \begin_layout Itemize
3201 the reachability problem in logspace iff
3202 \begin_inset Formula $\Class{L}=\Class{NL}$
3208 \begin_layout Itemize
3209 the construction problem in logspace iff
3210 \begin_inset Formula $\Class{L}=\Class{NL}$
3216 \begin_layout Itemize
3217 the optimization problem in logspace iff
3218 \begin_inset Formula $\Class{L}=\Class{NL}$
3224 \begin_layout Itemize
3225 the approximation problem in logspace iff
3226 \begin_inset Formula $\Class{L}=\Class{NL}$
3234 \begin_layout AgainFrame
3235 \begin_inset Argument 1
3238 \begin_layout Plain Layout
3248 \begin_inset Argument 4
3251 \begin_layout Plain Layout
3252 Finding Paths in Forests and Directed Paths is Easy,
3253 \begin_inset Newline newline
3266 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3270 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3274 \begin_inset Formula $\Class{L}$
3280 \begin_layout Standard
3281 \begin_inset Separator plain
3288 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3292 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3296 \begin_inset Formula $\Class{L}$
3303 \begin_layout AgainFrame
3304 \begin_inset Argument 1
3307 \begin_layout Plain Layout
3316 \begin_layout Section
3317 Finding Paths in Tournaments
3320 \begin_layout Subsection
3321 Complexity of: Does a Path Exist?
3325 \begin_inset Argument 4
3328 \begin_layout Plain Layout
3329 Definition of the Tournament Reachability Problem
3338 \begin_layout Definition
3344 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3352 \begin_inset Formula $(T,s,t)$
3359 \begin_layout Enumerate
3360 \begin_inset Formula $T=(V,E)$
3366 \begin_layout Enumerate
3367 there exists a path from
3368 \begin_inset space ~
3372 \begin_inset Formula $s$
3376 \begin_inset space ~
3380 \begin_inset Formula $t$
3388 \begin_layout Standard
3389 \begin_inset Separator plain
3396 \begin_inset Argument 4
3399 \begin_layout Plain Layout
3400 The Tournament Reachability Problem is Very Easy
3409 \begin_layout Theorem
3410 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3420 \begin_layout AlertBlock
3421 \begin_inset Argument 2
3424 \begin_layout Plain Layout
3434 \begin_layout Itemize
3436 \begin_inset Quotes eld
3440 \begin_inset Quotes erd
3444 \begin_inset Formula $\Lang{reach}$
3448 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3454 \begin_layout Itemize
3455 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3463 \begin_layout AgainFrame
3464 \begin_inset Argument 1
3467 \begin_layout Plain Layout
3476 \begin_layout Subsection
3477 Complexity of: Construct a Shortest Path
3481 \begin_inset Argument 4
3484 \begin_layout Plain Layout
3485 Finding a Shortest Path Is as Difficult as
3486 \begin_inset Newline newline
3489 the Distance Problem
3498 \begin_layout Definition
3504 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3512 \begin_inset Formula $(T,s,t,d)$
3519 \begin_layout Enumerate
3520 \begin_inset Formula $T=(V,E)$
3523 is a tournament in which
3526 \begin_layout Enumerate
3528 \begin_inset Formula $s$
3532 \begin_inset space ~
3536 \begin_inset Formula $t$
3540 \begin_inset space ~
3544 \begin_inset Formula $d$
3552 \begin_layout Standard
3553 \begin_inset Separator plain
3560 \begin_inset Argument 4
3563 \begin_layout Plain Layout
3564 The Tournament Distance Problem is Hard
3573 \begin_layout Theorem
3574 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3578 \begin_inset Formula $\Class{NL}$
3584 \begin_layout Standard
3585 \begin_inset space \hfill{}
3592 \begin_layout Plain Layout
3596 hyperlink{hierarchy<6>}{
3598 beamerskipbutton{Skip Proof}}
3610 \begin_layout Corollary
3611 Shortest path in tournaments can be constructed
3612 \begin_inset Newline newline
3615 in logarithmic space, iff
3616 \begin_inset Formula $\Class{L}=\Class{NL}$
3626 \begin_layout Corollary
3627 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3634 \begin_layout Standard
3635 \begin_inset Separator plain
3642 \begin_inset Argument 4
3645 \begin_layout Plain Layout
3647 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3659 \begin_layout Standard
3663 \begin_layout Plain Layout
3675 \begin_layout Columns
3676 \begin_inset Argument 1
3679 \begin_layout Plain Layout
3689 \begin_layout Column
3693 \begin_layout Standard
3697 \begin_layout Plain Layout
3712 \begin_inset Argument 2
3715 \begin_layout Plain Layout
3717 \begin_inset Formula $\Lang{reach}$
3721 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3733 \begin_layout Enumerate
3734 \begin_inset Argument item:2
3737 \begin_layout Plain Layout
3744 \begin_inset Formula $(G,s,t)$
3748 \begin_inset Formula $\Lang{reach}$
3754 \begin_layout Enumerate
3755 \begin_inset Argument item:2
3758 \begin_layout Plain Layout
3765 \begin_inset Formula $G$
3769 \begin_inset Formula $G'$
3775 \begin_layout Enumerate
3776 \begin_inset Argument item:2
3779 \begin_layout Plain Layout
3786 \begin_inset Newline newline
3790 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3797 \begin_layout Standard
3798 \begin_inset Separator plain
3805 \begin_inset Argument 2
3808 \begin_layout Plain Layout
3815 \begin_inset Argument 1
3818 \begin_layout Plain Layout
3828 \begin_layout Enumerate
3829 \begin_inset Argument item:2
3832 \begin_layout Plain Layout
3839 \begin_inset space ~
3843 \begin_inset Formula $G$
3847 \begin_inset Newline newline
3851 \begin_inset space ~
3855 \begin_inset Formula $G'$
3861 \begin_layout Enumerate
3862 \begin_inset Argument item:2
3865 \begin_layout Plain Layout
3872 \begin_inset space ~
3876 \begin_inset Formula $G'$
3880 \begin_inset Newline newline
3884 \begin_inset space ~
3888 \begin_inset Formula $G'$
3895 \begin_layout Column
3899 \begin_layout Example
3903 \begin_layout Plain Layout
3907 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3910 \begin_layout Plain Layout
3914 color{beamerexample}
3917 \begin_layout Plain Layout
3921 pgfsetlinewidth{0.6pt}
3924 \begin_layout Plain Layout
3933 \begin_layout Plain Layout
3942 \begin_layout Plain Layout
3951 \begin_layout Plain Layout
3960 \begin_layout Plain Layout
3967 \begin_layout Plain Layout
3975 pgfbox[center,center]{$s$}}
3978 \begin_layout Plain Layout
3986 pgfbox[center,center]{$t$}}
3989 \begin_layout Plain Layout
3993 color{beamerexample}
3996 \begin_layout Plain Layout
4005 \begin_layout Plain Layout
4009 pgfnodesetsepstart{2pt}
4012 \begin_layout Plain Layout
4016 pgfnodesetsepend{2pt}
4019 \begin_layout Plain Layout
4025 pgfnodeconnline{B}{A}}
4028 \begin_layout Plain Layout
4034 pgfnodeconnline{B}{C}}
4037 \begin_layout Plain Layout
4043 pgfnodeconnline{C}{D}}
4046 \begin_layout Plain Layout
4052 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4055 \begin_layout Plain Layout
4063 pgfbox[left,center]{$G
4068 \begin_layout Plain Layout
4075 \begin_layout Plain Layout
4083 pgfbox[left,center]{$G'
4088 \begin_layout Plain Layout
4097 \begin_layout Plain Layout
4106 \begin_layout Plain Layout
4115 \begin_layout Plain Layout
4124 \begin_layout Plain Layout
4133 \begin_layout Plain Layout
4142 \begin_layout Plain Layout
4151 \begin_layout Plain Layout
4160 \begin_layout Plain Layout
4169 \begin_layout Plain Layout
4178 \begin_layout Plain Layout
4187 \begin_layout Plain Layout
4196 \begin_layout Plain Layout
4205 \begin_layout Plain Layout
4214 \begin_layout Plain Layout
4223 \begin_layout Plain Layout
4232 \begin_layout Plain Layout
4239 \begin_layout Plain Layout
4247 pgfbox[center,center]{$s'$}}
4250 \begin_layout Plain Layout
4258 pgfbox[center,center]{$t'$}}
4261 \begin_layout Plain Layout
4266 \begin_layout Plain Layout
4271 \begin_layout Plain Layout
4278 \begin_layout Plain Layout
4282 pgfsetlinewidth{0.4pt}
4285 \begin_layout Plain Layout
4289 color{beamerexample!25!averagebackgroundcolor}
4292 \begin_layout Plain Layout
4296 pgfnodeconnline{A2}{C1}
4299 \begin_layout Plain Layout
4303 pgfnodeconnline{A2}{D1}
4306 \begin_layout Plain Layout
4310 pgfnodeconnline{B2}{A1}
4313 \begin_layout Plain Layout
4317 pgfnodeconnline{B2}{C1}
4320 \begin_layout Plain Layout
4324 pgfnodeconnline{B2}{D1}
4327 \begin_layout Plain Layout
4331 pgfnodeconnline{C2}{D1}
4334 \begin_layout Plain Layout
4338 pgfnodeconnline{D2}{A1}
4341 \begin_layout Plain Layout
4345 pgfnodeconnline{D2}{B1}
4348 \begin_layout Plain Layout
4352 pgfnodeconnline{A3}{C2}
4355 \begin_layout Plain Layout
4359 pgfnodeconnline{A3}{D2}
4362 \begin_layout Plain Layout
4366 pgfnodeconnline{B3}{A2}
4369 \begin_layout Plain Layout
4373 pgfnodeconnline{B3}{C2}
4376 \begin_layout Plain Layout
4380 pgfnodeconnline{B3}{D2}
4383 \begin_layout Plain Layout
4387 pgfnodeconnline{C3}{D2}
4390 \begin_layout Plain Layout
4394 pgfnodeconnline{D3}{A2}
4397 \begin_layout Plain Layout
4401 pgfnodeconnline{D3}{B2}
4404 \begin_layout Plain Layout
4408 pgfnodeconnline{A4}{C3}
4411 \begin_layout Plain Layout
4415 pgfnodeconnline{A4}{D3}
4418 \begin_layout Plain Layout
4422 pgfnodeconnline{B4}{A3}
4425 \begin_layout Plain Layout
4429 pgfnodeconnline{B4}{C3}
4432 \begin_layout Plain Layout
4436 pgfnodeconnline{B4}{D3}
4439 \begin_layout Plain Layout
4443 pgfnodeconnline{C4}{D3}
4446 \begin_layout Plain Layout
4450 pgfnodeconnline{D4}{A3}
4453 \begin_layout Plain Layout
4457 pgfnodeconnline{D4}{B3}
4460 \begin_layout Plain Layout
4469 \begin_layout Plain Layout
4473 pgfnodeconnline{A1}{B1}
4476 \begin_layout Plain Layout
4480 pgfnodeconnline{B1}{C1}
4483 \begin_layout Plain Layout
4487 pgfnodeconnline{C1}{D1}
4490 \begin_layout Plain Layout
4494 pgfnodeconnline{A2}{B2}
4497 \begin_layout Plain Layout
4501 pgfnodeconnline{B2}{C2}
4504 \begin_layout Plain Layout
4508 pgfnodeconnline{C2}{D2}
4511 \begin_layout Plain Layout
4515 pgfnodeconnline{A3}{B3}
4518 \begin_layout Plain Layout
4522 pgfnodeconnline{B3}{C3}
4525 \begin_layout Plain Layout
4529 pgfnodeconnline{C3}{D3}
4532 \begin_layout Plain Layout
4536 pgfnodeconnline{A4}{B4}
4539 \begin_layout Plain Layout
4543 pgfnodeconnline{B4}{C4}
4546 \begin_layout Plain Layout
4550 pgfnodeconnline{C4}{D4}
4553 \begin_layout Plain Layout
4560 \begin_layout Plain Layout
4564 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4567 \begin_layout Plain Layout
4571 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
4574 \begin_layout Plain Layout
4578 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
4581 \begin_layout Plain Layout
4585 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
4588 \begin_layout Plain Layout
4592 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
4595 \begin_layout Plain Layout
4599 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
4602 \begin_layout Plain Layout
4606 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
4609 \begin_layout Plain Layout
4613 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
4616 \begin_layout Plain Layout
4620 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
4623 \begin_layout Plain Layout
4627 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
4630 \begin_layout Plain Layout
4634 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
4637 \begin_layout Plain Layout
4641 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
4644 \begin_layout Plain Layout
4648 color{beamerexample}
4651 \begin_layout Plain Layout
4655 pgfsetlinewidth{0.6pt}
4658 \begin_layout Plain Layout
4663 \begin_layout Plain Layout
4670 \begin_layout Plain Layout
4677 \begin_layout Plain Layout
4681 pgfnodeconnline{B1}{A2}
4684 \begin_layout Plain Layout
4688 pgfnodeconnline{B2}{A3}
4691 \begin_layout Plain Layout
4695 pgfnodeconnline{B3}{A4}
4698 \begin_layout Plain Layout
4703 \begin_layout Plain Layout
4710 \begin_layout Plain Layout
4717 \begin_layout Plain Layout
4721 pgfnodeconnline{B1}{C2}
4724 \begin_layout Plain Layout
4728 pgfnodeconnline{B2}{C3}
4731 \begin_layout Plain Layout
4735 pgfnodeconnline{B3}{C4}
4738 \begin_layout Plain Layout
4743 \begin_layout Plain Layout
4750 \begin_layout Plain Layout
4757 \begin_layout Plain Layout
4761 pgfnodeconnline{C1}{D2}
4764 \begin_layout Plain Layout
4770 pgfnodeconnline{C2}{D3}}
4773 \begin_layout Plain Layout
4779 pgfnodeconnline{C3}{D4}}
4782 \begin_layout Plain Layout
4787 \begin_layout Plain Layout
4794 \begin_layout Plain Layout
4801 \begin_layout Plain Layout
4807 pgfnodeconnline{A1}{C2}}
4810 \begin_layout Plain Layout
4816 pgfnodeconnline{A2}{C3}}
4819 \begin_layout Plain Layout
4823 pgfnodeconnline{A3}{C4}
4826 \begin_layout Plain Layout
4831 \begin_layout Plain Layout
4838 \begin_layout Plain Layout
4845 \begin_layout Plain Layout
4851 pgfnodeconnline{A1}{A2}}
4854 \begin_layout Plain Layout
4858 pgfnodeconnline{A2}{A3}
4861 \begin_layout Plain Layout
4865 pgfnodeconnline{A3}{A4}
4868 \begin_layout Plain Layout
4872 pgfnodeconnline{B1}{B2}
4875 \begin_layout Plain Layout
4879 pgfnodeconnline{B2}{B3}
4882 \begin_layout Plain Layout
4886 pgfnodeconnline{B3}{B4}
4889 \begin_layout Plain Layout
4893 pgfnodeconnline{C1}{C2}
4896 \begin_layout Plain Layout
4900 pgfnodeconnline{C2}{C3}
4903 \begin_layout Plain Layout
4907 pgfnodeconnline{C3}{C4}
4910 \begin_layout Plain Layout
4914 pgfnodeconnline{D1}{D2}
4917 \begin_layout Plain Layout
4921 pgfnodeconnline{D2}{D3}
4924 \begin_layout Plain Layout
4930 pgfnodeconnline{D3}{D4}}
4933 \begin_layout Plain Layout
4938 \begin_layout Plain Layout
4952 \begin_layout AgainFrame
4953 \begin_inset Argument 1
4956 \begin_layout Plain Layout
4965 \begin_layout Subsection
4966 Complexity of: Approximating the Shortest Path
4970 \begin_inset Argument 4
4973 \begin_layout Plain Layout
4974 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
4983 \begin_layout Definition
4988 approximation scheme for
4989 \begin_inset Formula $\Lang{tournament-shortest-path}$
5000 \begin_layout Enumerate
5002 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5008 \begin_layout Enumerate
5010 \begin_inset Formula $r>1$
5016 \begin_layout Standard
5020 \begin_layout Itemize
5022 \begin_inset Formula $s$
5026 \begin_inset space ~
5030 \begin_inset Formula $t$
5034 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5042 \begin_layout Standard
5043 \begin_inset Separator plain
5050 \begin_inset Argument 4
5053 \begin_layout Plain Layout
5054 There Exists a Logspace Approximation Scheme for
5055 \begin_inset Newline newline
5058 the Tournament Shortest Path Problem
5067 \begin_layout Theorem
5068 There exists an approximation scheme for
5069 \begin_inset Formula $\Lang{tournament-shortest-path}$
5073 \begin_inset Formula $1<r<2$
5077 \begin_inset Formula
5079 O\left(\log|V|\log\frac{1}{r-1}\right).
5091 \begin_layout Corollary
5092 In tournaments, paths can be constructed in logarithmic space.
5095 \begin_layout Standard
5096 \begin_inset space \hfill{}
5103 \begin_layout Plain Layout
5107 hyperlink{optimality}{
5109 beamergotobutton{More Details}}
5118 \begin_layout AgainFrame
5119 \begin_inset Argument 1
5122 \begin_layout Plain Layout
5131 \begin_layout Standard
5132 \begin_inset Note Note
5135 \begin_layout Plain Layout
5136 If a frame includes a program listing, the frame needs to be marked as
5137 \begin_inset Quotes eld
5141 \begin_inset Quotes erd
5146 has the FragileFrame layout for this.
5154 \begin_layout FragileFrame
5155 \begin_inset Argument 4
5158 \begin_layout Plain Layout
5159 Just a frame with a program code listing
5167 \begin_layout FragileFrame
5168 This is some program code:
5172 \begin_layout Standard
5173 \begin_inset listings
5174 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
5178 \begin_layout Plain Layout
5183 \begin_layout Plain Layout
5185 'this is a python function'
5188 \begin_layout Plain Layout
5193 \begin_layout Plain Layout
5198 \begin_layout Plain Layout
5200 'This is a German word: Tschüs'
5203 \begin_layout Plain Layout
5208 \begin_layout Plain Layout
5213 \begin_layout Plain Layout
5215 'this is a python function'
5218 \begin_layout Plain Layout
5229 \begin_layout Section*
5233 \begin_layout Subsection*
5238 \begin_inset Argument 4
5241 \begin_layout Plain Layout
5252 \begin_inset Argument 2
5255 \begin_layout Plain Layout
5265 \begin_layout Itemize
5279 \begin_inset Formula $\Class{AC}^{0}$
5288 \begin_layout Itemize
5293 logspace approximation scheme
5305 shortest paths in tournaments.
5308 \begin_layout Itemize
5322 \begin_inset Formula $\Class{NL}$
5331 \begin_layout Standard
5332 \begin_inset Separator plain
5339 \begin_inset Argument 2
5342 \begin_layout Plain Layout
5352 \begin_layout Itemize
5353 The same results apply to graphs with
5354 \begin_inset Newline newline
5357 bounded independence number.
5358 \begin_inset space \hfill{}
5365 \begin_layout Plain Layout
5369 hyperlink{independence}{
5371 beamergotobutton{More Details}}
5379 \begin_layout Itemize
5380 The complexity of finding paths in undirected graphs
5381 \begin_inset Newline newline
5385 \begin_inset space \hfill{}
5392 \begin_layout Plain Layout
5396 hyperlink{undirected}{
5398 beamergotobutton{More Details}}
5408 \begin_layout Subsection*
5413 \begin_inset Argument 4
5416 \begin_layout Plain Layout
5426 \begin_layout Standard
5430 \begin_layout Plain Layout
5434 beamertemplatebookbibitems
5442 \begin_layout Bibliography
5443 \begin_inset CommandInset bibitem
5444 LatexCommand bibitem
5451 \begin_inset space ~
5459 \begin_layout Plain Layout
5470 Topics on Tournaments.
5477 \begin_layout Plain Layout
5486 Holt, Rinehart, and Winston, 1968.
5491 \begin_layout Plain Layout
5495 beamertemplatearticlebibitems
5503 \begin_layout Bibliography
5504 \begin_inset CommandInset bibitem
5505 LatexCommand bibitem
5506 key "NickelsenT2002"
5512 \begin_inset space ~
5515 Arfst Nickelsen and Till Tantau.
5520 \begin_layout Plain Layout
5529 On reachability in graphs with bounded independence number.
5533 \begin_layout Plain Layout
5547 , Springer-Verlag, 2002.
5550 \begin_layout Bibliography
5551 \begin_inset CommandInset bibitem
5552 LatexCommand bibitem
5559 \begin_inset space ~
5566 \begin_layout Plain Layout
5575 A logspace approximation scheme for the shortest path problem for graphs
5576 with bounded independence number.
5580 \begin_layout Plain Layout
5594 , Springer-Verlag, 2004.
5599 \begin_layout Plain Layout
5612 \begin_layout Standard
5617 \begin_layout Plain Layout
5621 AtBeginSubsection[]{}
5629 \begin_layout Section
5633 \begin_layout Subsection
5634 Graphs With Bounded Independence Number
5638 \begin_inset Argument 3
5641 \begin_layout Plain Layout
5648 \begin_inset Argument 4
5651 \begin_layout Plain Layout
5652 Definition of Independence Number of a Graph
5661 \begin_layout Definition
5671 \begin_inset Formula $\alpha(G)$
5675 \begin_inset Newline newline
5678 is the maximum number of vertices we can pick,
5679 \begin_inset Newline newline
5682 such that there is no edge between them.
5685 \begin_layout Example
5686 Tournaments have independence number 1.
5691 \begin_layout Standard
5692 \begin_inset Separator plain
5699 \begin_inset Argument 4
5702 \begin_layout Plain Layout
5703 The Results for Tournaments also Apply to
5704 \begin_inset Newline newline
5707 Graphs With Bounded Independence Number
5716 \begin_layout Theorem
5718 \begin_inset space ~
5722 \begin_inset Formula $k$
5733 in graphs with independence number
5734 \begin_inset Newline newline
5738 \begin_inset space ~
5742 \begin_inset Formula $k$
5746 \begin_inset Formula $\Class{AC}^{0}$
5752 \begin_layout Standard
5753 \begin_inset Separator plain
5759 \begin_layout Theorem
5761 \begin_inset space ~
5765 \begin_inset Formula $k$
5772 logspace approximation scheme
5776 for approximating the shortest path in graphs with independence number at
5778 \begin_inset space ~
5782 \begin_inset Formula $k$
5788 \begin_layout Standard
5789 \begin_inset Separator plain
5795 \begin_layout Theorem
5797 \begin_inset space ~
5801 \begin_inset Formula $k$
5812 in graphs with independence number at most
5813 \begin_inset space ~
5817 \begin_inset Formula $k$
5825 \begin_inset Formula $\Class{NL}$
5834 \begin_layout Subsection
5835 Finding Paths in Undirected Graphs
5839 \begin_inset Argument 1
5842 \begin_layout Plain Layout
5849 \begin_inset Argument 3
5852 \begin_layout Plain Layout
5859 \begin_inset Argument 4
5862 \begin_layout Plain Layout
5863 The Complexity of Finding Paths in Undirected Graphs
5864 \begin_inset Newline newline
5877 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
5881 \begin_inset Formula $\Class{SL}$
5887 \begin_layout Corollary
5888 For undirected graphs, we can solve
5892 \begin_layout Itemize
5893 the reachability problem in logspace iff
5894 \begin_inset Formula $\Class L=\Class{SL}$
5900 \begin_layout Itemize
5901 the construction problem in logspace iff
5902 \begin_inset Flex Alternative
5905 \begin_layout Plain Layout
5906 \begin_inset Argument 1
5909 \begin_layout Plain Layout
5916 \begin_inset Argument 2
5919 \begin_layout Plain Layout
5926 \begin_inset Flex Alert
5929 \begin_layout Plain Layout
5930 \begin_inset Formula $\Class L=\Class{SL}$
5946 \begin_layout Itemize
5947 the optimization problem in logspace iff
5948 \begin_inset Flex Alternative
5951 \begin_layout Plain Layout
5952 \begin_inset Argument 1
5955 \begin_layout Plain Layout
5962 \begin_inset Argument 2
5965 \begin_layout Plain Layout
5972 \begin_inset Flex Alert
5975 \begin_layout Plain Layout
5976 \begin_inset Formula $\Class L=\Class{NL}$
5992 \begin_layout Itemize
5993 the approximation problem in logspace iff ?.
5999 \begin_layout Subsection
6000 The Approximation Scheme is Optimal
6004 \begin_inset Argument 3
6007 \begin_layout Plain Layout
6014 \begin_inset Argument 4
6017 \begin_layout Plain Layout
6018 The Approximation Scheme is Optimal
6027 \begin_layout Theorem
6028 Suppose there exists an approximation scheme for
6029 \begin_inset Formula $\Lang{tournament-shortest-path}$
6033 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6038 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6049 \begin_layout Enumerate
6050 Suppose the approximation scheme exists.
6051 \begin_inset Newline newline
6055 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6062 \begin_layout Enumerate
6064 \begin_inset Formula $(T,s,t)$
6069 \begin_inset Formula $n$
6072 be the number of vertices.
6075 \begin_layout Enumerate
6076 Run the approximation scheme for
6077 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6081 \begin_inset Newline newline
6085 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6091 \begin_layout Enumerate
6092 The resulting path has optimal length.
6097 \begin_layout Plain Layout