1 #LyX 2.0 created this file. For more info see http://www.lyx.org/
7 \beamertemplateshadingbackground{red!5}{structure!5}
9 \usepackage{beamerthemeshadow}
10 \usepackage{pgfnodes,pgfarrows,pgfheaps}
12 \beamertemplatetransparentcovereddynamicmedium
15 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
16 \logo{\pgfuseimage{icsi-logo}}
21 \newcommand{\Class}[1]{\operatorname{\mathchoice
27 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
29 % This gets defined by beamerbasecolor.sty, but only at the beginning of
31 \colorlet{averagebackgroundcolor}{normal text.bg}
33 \newcommand{\tape}[3]{%
34 \color{structure!30!averagebackgroundcolor}
35 \pgfmoveto{\pgfxy(-0.5,0)}
36 \pgflineto{\pgfxy(-0.6,0.1)}
37 \pgflineto{\pgfxy(-0.4,0.2)}
38 \pgflineto{\pgfxy(-0.6,0.3)}
39 \pgflineto{\pgfxy(-0.4,0.4)}
40 \pgflineto{\pgfxy(-0.5,0.5)}
41 \pgflineto{\pgfxy(4,0.5)}
42 \pgflineto{\pgfxy(4.1,0.4)}
43 \pgflineto{\pgfxy(3.9,0.3)}
44 \pgflineto{\pgfxy(4.1,0.2)}
45 \pgflineto{\pgfxy(3.9,0.1)}
46 \pgflineto{\pgfxy(4,0)}
51 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
52 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
55 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
58 \newcommand{\shorttape}[3]{%
59 \color{structure!30!averagebackgroundcolor}
60 \pgfmoveto{\pgfxy(-0.5,0)}
61 \pgflineto{\pgfxy(-0.6,0.1)}
62 \pgflineto{\pgfxy(-0.4,0.2)}
63 \pgflineto{\pgfxy(-0.6,0.3)}
64 \pgflineto{\pgfxy(-0.4,0.4)}
65 \pgflineto{\pgfxy(-0.5,0.5)}
66 \pgflineto{\pgfxy(1,0.5)}
67 \pgflineto{\pgfxy(1.1,0.4)}
68 \pgflineto{\pgfxy(0.9,0.3)}
69 \pgflineto{\pgfxy(1.1,0.2)}
70 \pgflineto{\pgfxy(0.9,0.1)}
71 \pgflineto{\pgfxy(1,0)}
76 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
77 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
80 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
83 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
84 {color(0pt)=(black); color(1cm)=(structure!65!white)}
85 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
86 {color(0pt)=(black); color(1cm)=(structure!55!white)}
87 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
88 {color(0pt)=(black); color(1cm)=(structure!45!white)}
89 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
90 {color(0pt)=(black); color(1cm)=(structure!35!white)}
91 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
92 {color(0pt)=(black); color(1cm)=(structure!25!white)}
93 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
94 {color(0pt)=(black); color(1cm)=(red!35!white)}
96 \newcommand{\heap}[5]{%
99 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
101 \begin{pgfmagnify}{1}{#1}
102 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
108 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
112 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
116 \newcommand{\langat}[2]{%
117 \color{black!30!beamerexample}
118 \pgfsetlinewidth{0.6pt}
119 \pgfsetendarrow{\pgfarrowdot}
120 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
121 \color{beamerexample}
122 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
125 \newcommand{\langatother}[2]{%
126 \color{black!30!beamerexample}
127 \pgfsetlinewidth{0.6pt}
128 \pgfsetendarrow{\pgfarrowdot}
129 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
130 \color{beamerexample}
131 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
135 \pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
138 \pgfdeclareradialshading{graphnode}
139 {\pgfpoint{-3pt}{3.6pt}}%
140 {color(0cm)=(beamerexample!15);
141 color(2.63pt)=(beamerexample!75);
142 color(5.26pt)=(beamerexample!70!black);
143 color(7.6pt)=(beamerexample!50!black);
144 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
146 \newcommand{\graphnode}[2]{
147 \pgfnodecircle{#1}[virtual]{#2}{8pt}
148 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
152 \use_default_options false
153 \maintain_unincluded_children false
155 \language_package default
160 \font_typewriter default
161 \font_default_family default
162 \use_non_tex_fonts false
169 \default_output_format default
171 \bibtex_command default
172 \index_command default
173 \paperfontsize default
185 \paperorientation portrait
194 \paragraph_separation indent
195 \paragraph_indentation default
196 \quotes_language english
199 \paperpagestyle default
200 \tracking_changes false
201 \output_changes false
204 \html_be_strict false
211 \begin_inset Newline newline
214 Finding Paths in Tournaments
221 \begin_layout Institute
222 International Computer Schience Institute
223 \begin_inset Newline newline
227 \begin_inset Argument
230 \begin_layout Plain Layout
243 \begin_layout BeginFrame
247 \begin_layout Standard
248 \begin_inset CommandInset toc
249 LatexCommand tableofcontents
257 \begin_layout Plain Layout
267 \begin_layout EndFrame
271 \begin_layout Standard
275 \begin_layout Plain Layout
277 % Show the table of contents at the beginning
280 \begin_layout Plain Layout
284 \begin_layout Plain Layout
286 % of every subsection.
289 \begin_layout Plain Layout
293 \begin_layout Plain Layout
300 \begin_layout Plain Layout
304 \begin_layout Plain Layout
311 \begin_layout Plain Layout
315 \begin_layout Plain Layout
322 \begin_layout Plain Layout
326 \begin_layout Plain Layout
330 tableofcontents[current,currentsubsection]
333 \begin_layout Plain Layout
337 \begin_layout Plain Layout
342 \begin_layout Plain Layout
346 \begin_layout Plain Layout
356 \begin_layout Section
360 \begin_layout Subsection
361 What are Tournaments?
364 \begin_layout BeginFrame
365 Tournaments Consist of Jousts Between Knights
368 \begin_layout Columns
377 \begin_layout Standard
381 \begin_layout Plain Layout
385 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
388 \begin_layout Plain Layout
392 \begin_layout Plain Layout
396 pgfnodebox{A}[virtual]{
400 pgfuseimage{knight1}}{2pt}{2pt}
403 \begin_layout Plain Layout
407 \begin_layout Plain Layout
411 pgfnodebox{B}[virtual]{
415 pgfuseimage{knight2}}{2pt}{2pt}
418 \begin_layout Plain Layout
422 \begin_layout Plain Layout
426 pgfnodebox{C}[virtual]{
430 pgfuseimage{knight3}}{2pt}{2pt}
433 \begin_layout Plain Layout
437 \begin_layout Plain Layout
441 pgfnodebox{D}[virtual]{
445 pgfuseimage{knight4}}{2pt}{2pt}
448 \begin_layout Plain Layout
452 \begin_layout Plain Layout
456 \begin_layout Plain Layout
460 \begin_layout Plain Layout
467 \begin_layout Plain Layout
471 \begin_layout Plain Layout
482 \begin_layout Plain Layout
486 \begin_layout Plain Layout
493 \begin_layout Plain Layout
497 \begin_layout Plain Layout
501 pgfsetlinewidth{0.6pt}
504 \begin_layout Plain Layout
508 \begin_layout Plain Layout
512 pgfnodeconnline{A}{B}
515 \begin_layout Plain Layout
519 \begin_layout Plain Layout
523 pgfnodeconnline{A}{C}
526 \begin_layout Plain Layout
530 \begin_layout Plain Layout
534 pgfnodeconnline{D}{A}
537 \begin_layout Plain Layout
541 \begin_layout Plain Layout
545 pgfnodeconnline{C}{B}
548 \begin_layout Plain Layout
552 \begin_layout Plain Layout
556 pgfnodeconnline{B}{D}
559 \begin_layout Plain Layout
563 \begin_layout Plain Layout
567 pgfnodeconnline{C}{D}}
570 \begin_layout Plain Layout
574 \begin_layout Plain Layout
594 \begin_layout Plain Layout
596 {What is a Tournament?}
605 \begin_layout Itemize
609 \begin_layout Plain Layout
619 \begin_layout Itemize
623 \begin_layout Plain Layout
630 Every pair has a joust.
633 \begin_layout Itemize
637 \begin_layout Plain Layout
644 In every joust one knight wins.
649 \begin_layout BeginFrame
650 Tournaments are Complete Directed Graphs
653 \begin_layout Columns
662 \begin_layout Standard
666 \begin_layout Plain Layout
670 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
673 \begin_layout Plain Layout
677 \begin_layout Plain Layout
684 \begin_layout Plain Layout
688 \begin_layout Plain Layout
692 pgfsetlinewidth{0.6pt}
695 \begin_layout Plain Layout
699 \begin_layout Plain Layout
708 \begin_layout Plain Layout
712 \begin_layout Plain Layout
721 \begin_layout Plain Layout
725 \begin_layout Plain Layout
734 \begin_layout Plain Layout
738 \begin_layout Plain Layout
747 \begin_layout Plain Layout
751 \begin_layout Plain Layout
755 \begin_layout Plain Layout
759 \begin_layout Plain Layout
766 \begin_layout Plain Layout
770 \begin_layout Plain Layout
778 pgfbox[center,center]{$v_2$}}
781 \begin_layout Plain Layout
785 \begin_layout Plain Layout
793 pgfbox[center,center]{$v_3$}}
796 \begin_layout Plain Layout
800 \begin_layout Plain Layout
808 pgfbox[center,center]{$v_4$}}
811 \begin_layout Plain Layout
815 \begin_layout Plain Layout
823 pgfbox[center,center]{$v_1$}}
826 \begin_layout Plain Layout
830 \begin_layout Plain Layout
834 \begin_layout Plain Layout
838 \begin_layout Plain Layout
845 \begin_layout Plain Layout
849 \begin_layout Plain Layout
858 \begin_layout Plain Layout
862 \begin_layout Plain Layout
866 pgfnodesetsepstart{2pt}
869 \begin_layout Plain Layout
873 \begin_layout Plain Layout
877 pgfnodesetsepend{4pt}
880 \begin_layout Plain Layout
884 \begin_layout Plain Layout
888 pgfnodeconnline{A}{B}
891 \begin_layout Plain Layout
895 \begin_layout Plain Layout
899 pgfnodeconnline{A}{C}
902 \begin_layout Plain Layout
906 \begin_layout Plain Layout
910 pgfnodeconnline{D}{A}
913 \begin_layout Plain Layout
917 \begin_layout Plain Layout
921 pgfnodeconnline{C}{B}
924 \begin_layout Plain Layout
928 \begin_layout Plain Layout
932 pgfnodeconnline{B}{D}
935 \begin_layout Plain Layout
939 \begin_layout Plain Layout
943 pgfnodeconnline{D}{C}
946 \begin_layout Plain Layout
950 \begin_layout Plain Layout
966 \begin_layout Definition
970 \begin_layout Plain Layout
989 \begin_layout Enumerate
993 \begin_layout Enumerate
994 with exactly one edge between
995 \begin_inset Newline newline
998 any two different vertices.
1003 \begin_layout BeginFrame
1007 \begin_layout Plain Layout
1014 Tournaments Arise Naturally in Different Situations
1017 \begin_layout ExampleBlock
1021 \begin_layout Plain Layout
1023 {Applicatins in Ordering Theory}
1032 \begin_layout Standard
1033 Elements in a set need to be sorted.
1035 \begin_inset Newline newline
1038 The comparison relation may be cyclic, however.
1042 \begin_layout Separator
1046 \begin_layout ExampleBlock
1050 \begin_layout Plain Layout
1052 {Applications in Sociology}
1061 \begin_layout Standard
1062 Several candidates apply for a position.
1063 \begin_inset Newline newline
1066 Reviewers decide for any two candidates whom they prefer.
1071 \begin_layout Separator
1075 \begin_layout ExampleBlock
1079 \begin_layout Plain Layout
1081 {Applications in Structural Complexity Theory}
1090 \begin_layout Standard
1092 \begin_inset Formula $L$
1095 is given and a selector function
1096 \begin_inset Formula $f$
1100 \begin_inset Newline newline
1103 It chooses from any two words the one more likely to be in
1104 \begin_inset Formula $f$
1111 \begin_layout Subsection
1112 What Does ``Finding Paths'' Mean?
1115 \begin_layout BeginFrame
1116 ``Finding Paths'' is Ambiguous
1123 \begin_layout Plain Layout
1133 par{}% because LyX inserts superfluous paragraphs
1136 \begin_layout Plain Layout
1140 \begin_layout Plain Layout
1144 only<1>{Path Finding Problems}
1149 \begin_layout Plain Layout
1153 \begin_layout Plain Layout
1164 \begin_layout Plain Layout
1168 \begin_layout Plain Layout
1172 only<4-5>{the Construction Problem}
1177 \begin_layout Plain Layout
1181 \begin_layout Plain Layout
1185 only<6-7>{the Optimization Problem}
1190 \begin_layout Plain Layout
1194 \begin_layout Plain Layout
1205 \begin_layout Plain Layout
1209 \begin_layout Plain Layout
1213 only<10->{the Approximation Problem}}
1222 \begin_layout Itemize
1232 \begin_inset Formula $G=(V,E)$
1244 \begin_inset Formula $s\in V$
1256 \begin_inset Formula $t\in V$
1262 \begin_layout Itemize
1266 \begin_layout Plain Layout
1268 <only@-9| visible@8->
1280 \begin_inset space ~
1284 \begin_inset Formula $d$
1291 \begin_layout Plain Layout
1303 \begin_layout Itemize
1307 \begin_layout Plain Layout
1323 \begin_inset Formula $r>1$
1330 \begin_layout Standard
1334 \begin_layout Plain Layout
1346 \begin_layout Overprint
1351 \begin_layout Standard
1355 \begin_layout Plain Layout
1359 onslide<1,3,5,7,9,11-12>
1367 \begin_layout Columns
1371 \begin_layout Plain Layout
1382 \begin_layout Standard
1386 \begin_layout Plain Layout
1404 \begin_layout ExampleBlock
1408 \begin_layout Plain Layout
1419 \begin_layout Standard
1423 \begin_layout Plain Layout
1427 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1430 \begin_layout Plain Layout
1434 \begin_layout Plain Layout
1438 color{beamerexample}
1441 \begin_layout Plain Layout
1445 \begin_layout Plain Layout
1449 pgfsetlinewidth{0.6pt}
1452 \begin_layout Plain Layout
1456 \begin_layout Plain Layout
1465 \begin_layout Plain Layout
1469 \begin_layout Plain Layout
1478 \begin_layout Plain Layout
1482 \begin_layout Plain Layout
1491 \begin_layout Plain Layout
1495 \begin_layout Plain Layout
1504 \begin_layout Plain Layout
1508 \begin_layout Plain Layout
1512 \begin_layout Plain Layout
1516 \begin_layout Plain Layout
1523 \begin_layout Plain Layout
1527 \begin_layout Plain Layout
1535 pgfbox[center,center]{$t$}}
1538 \begin_layout Plain Layout
1542 \begin_layout Plain Layout
1550 pgfbox[center,center]{$s$}}
1553 \begin_layout Plain Layout
1557 \begin_layout Plain Layout
1561 \begin_layout Plain Layout
1565 \begin_layout Plain Layout
1569 color{beamerexample}
1572 \begin_layout Plain Layout
1576 \begin_layout Plain Layout
1585 \begin_layout Plain Layout
1589 \begin_layout Plain Layout
1593 pgfnodesetsepstart{2pt}
1596 \begin_layout Plain Layout
1600 \begin_layout Plain Layout
1604 pgfnodesetsepend{4pt}
1607 \begin_layout Plain Layout
1611 \begin_layout Plain Layout
1615 pgfnodeconnline{A}{B}
1618 \begin_layout Plain Layout
1622 \begin_layout Plain Layout
1626 pgfnodeconnline{A}{C}
1629 \begin_layout Plain Layout
1633 \begin_layout Plain Layout
1637 pgfnodeconnline{D}{A}
1640 \begin_layout Plain Layout
1644 \begin_layout Plain Layout
1648 pgfnodeconnline{C}{B}
1651 \begin_layout Plain Layout
1655 \begin_layout Plain Layout
1659 pgfnodeconnline{B}{D}
1662 \begin_layout Plain Layout
1666 \begin_layout Plain Layout
1670 pgfnodeconnline{D}{C}
1673 \begin_layout Plain Layout
1677 \begin_layout Plain Layout
1681 \begin_layout Plain Layout
1685 \begin_layout Plain Layout
1695 pgfbox[left,center]{, $d=2$}}}
1698 \begin_layout Plain Layout
1702 \begin_layout Plain Layout
1712 pgfbox[left,center]{, $r=1.5$}}}
1715 \begin_layout Plain Layout
1719 \begin_layout Plain Layout
1729 pgfbox[left,center]{, $r=1.25$}}}
1732 \begin_layout Plain Layout
1736 \begin_layout Plain Layout
1749 \begin_layout Standard
1753 \begin_layout Plain Layout
1767 \begin_layout ExampleBlock
1771 \begin_layout Plain Layout
1773 <only@3->{Example Output}
1782 \begin_layout Standard
1786 \begin_layout Plain Layout
1790 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1793 \begin_layout Plain Layout
1797 \begin_layout Plain Layout
1804 \begin_layout Plain Layout
1808 \begin_layout Plain Layout
1812 color{beamerexample}
1815 \begin_layout Plain Layout
1819 \begin_layout Plain Layout
1823 pgfsetlinewidth{0.6pt}
1826 \begin_layout Plain Layout
1830 \begin_layout Plain Layout
1839 \begin_layout Plain Layout
1843 \begin_layout Plain Layout
1852 \begin_layout Plain Layout
1856 \begin_layout Plain Layout
1865 \begin_layout Plain Layout
1869 \begin_layout Plain Layout
1878 \begin_layout Plain Layout
1882 \begin_layout Plain Layout
1886 \begin_layout Plain Layout
1890 \begin_layout Plain Layout
1897 \begin_layout Plain Layout
1901 \begin_layout Plain Layout
1909 pgfbox[center,center]{$t$}}
1912 \begin_layout Plain Layout
1916 \begin_layout Plain Layout
1924 pgfbox[center,center]{$s$}}
1927 \begin_layout Plain Layout
1931 \begin_layout Plain Layout
1935 \begin_layout Plain Layout
1939 \begin_layout Plain Layout
1943 color{beamerexample}
1946 \begin_layout Plain Layout
1950 \begin_layout Plain Layout
1959 \begin_layout Plain Layout
1963 \begin_layout Plain Layout
1967 pgfnodesetsepstart{2pt}
1970 \begin_layout Plain Layout
1974 \begin_layout Plain Layout
1978 pgfnodesetsepend{4pt}
1981 \begin_layout Plain Layout
1985 \begin_layout Plain Layout
1990 \begin_layout Plain Layout
1994 \begin_layout Plain Layout
2000 pgfnodeconnline{A}{B}}
2003 \begin_layout Plain Layout
2007 \begin_layout Plain Layout
2013 pgfnodeconnline{A}{C}}
2016 \begin_layout Plain Layout
2020 \begin_layout Plain Layout
2026 pgfnodeconnline{D}{A}}
2029 \begin_layout Plain Layout
2033 \begin_layout Plain Layout
2039 pgfnodeconnline{C}{B}}
2042 \begin_layout Plain Layout
2046 \begin_layout Plain Layout
2050 pgfnodeconnline{B}{D}
2053 \begin_layout Plain Layout
2057 \begin_layout Plain Layout
2061 pgfnodeconnline{D}{C}
2064 \begin_layout Plain Layout
2068 \begin_layout Plain Layout
2073 \begin_layout Plain Layout
2077 \begin_layout Plain Layout
2087 pgfbox[left,center]{
2092 \begin_layout Plain Layout
2096 \begin_layout Plain Layout
2110 \begin_layout Standard
2114 \begin_layout Plain Layout
2130 \begin_layout Plain Layout
2132 {Variants of Path Finding Problems}
2141 \begin_layout Standard
2145 \begin_layout Plain Layout
2149 usedescriptionitemofwidthas{Approximation Problem:}
2157 \begin_layout Description
2159 \begin_inset space ~
2166 \begin_layout Plain Layout
2173 Is there a path from
2174 \begin_inset Formula $s$
2178 \begin_inset space ~
2182 \begin_inset Formula $t$
2188 \begin_layout Description
2190 \begin_inset space ~
2197 \begin_layout Plain Layout
2204 Construct a path from
2205 \begin_inset Formula $s$
2209 \begin_inset space ~
2213 \begin_inset Formula $t$
2219 \begin_layout Description
2221 \begin_inset space ~
2228 \begin_layout Plain Layout
2235 Construct a shortest path from
2236 \begin_inset Formula $s$
2240 \begin_inset space ~
2244 \begin_inset Formula $t$
2250 \begin_layout Description
2252 \begin_inset space ~
2259 \begin_layout Plain Layout
2267 \begin_inset Formula $s$
2271 \begin_inset space ~
2275 \begin_inset Formula $t$
2279 \begin_inset space ~
2283 \begin_inset Formula $d$
2289 \begin_layout Description
2291 \begin_inset space ~
2298 \begin_layout Plain Layout
2305 Construct a path from
2306 \begin_inset Formula $s$
2310 \begin_inset space ~
2314 \begin_inset Formula $t$
2318 \begin_inset Newline newline
2321 approximately their distance.
2326 \begin_layout Section
2330 \begin_layout Subsection
2331 Standard Complexity Classes
2334 \begin_layout Standard
2338 \begin_layout Plain Layout
2342 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2344 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2353 \begin_layout BeginFrame
2354 The Classes L and NL are Defined via
2355 \begin_inset Newline newline
2358 Logspace Turing Machines
2361 \begin_layout Standard
2365 \begin_layout Plain Layout
2369 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2372 \begin_layout Plain Layout
2376 \begin_layout Plain Layout
2384 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2387 \begin_layout Plain Layout
2391 \begin_layout Plain Layout
2398 \begin_layout Plain Layout
2402 \begin_layout Plain Layout
2410 tape{}{output tape (write only)}{10690836937182}}}
2413 \begin_layout Plain Layout
2417 \begin_layout Plain Layout
2424 \begin_layout Plain Layout
2428 \begin_layout Plain Layout
2436 shorttape{work tape (read/write), $O(
2438 log n)$ symbols}{}{42}}
2441 \begin_layout Plain Layout
2445 \begin_layout Plain Layout
2453 pgfbox[center,center]{
2455 pgfuseimage{computer}}}
2458 \begin_layout Plain Layout
2462 \begin_layout Plain Layout
2467 \begin_layout Plain Layout
2471 \begin_layout Plain Layout
2475 pgfsetlinewidth{0.6pt}
2478 \begin_layout Plain Layout
2482 \begin_layout Plain Layout
2486 \begin_layout Plain Layout
2490 \begin_layout Plain Layout
2497 \begin_layout Plain Layout
2501 \begin_layout Plain Layout
2510 \begin_layout Plain Layout
2514 \begin_layout Plain Layout
2518 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2521 \begin_layout Plain Layout
2525 \begin_layout Plain Layout
2531 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2534 \begin_layout Plain Layout
2538 \begin_layout Plain Layout
2544 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2547 \begin_layout Plain Layout
2551 \begin_layout Plain Layout
2563 \begin_layout BeginFrame
2564 Logspace Turing Machines Are Quite Powerful
2571 \begin_layout Plain Layout
2573 {Deterministic logspace machines can compute}
2582 \begin_layout Itemize
2583 addition, multiplication, and even division
2586 \begin_layout Itemize
2587 reductions used in completeness proofs,
2590 \begin_layout Itemize
2591 reachability in forests.
2603 \begin_layout Plain Layout
2605 {Non-deterministic logspace machines can compute}
2614 \begin_layout Itemize
2615 reachability in graphs,
2618 \begin_layout Itemize
2619 non-reachability in graphs,
2622 \begin_layout Itemize
2623 satisfiability with two literals per clause.
2627 \begin_layout BeginFrame
2631 \begin_layout Plain Layout
2633 <1>[label=hierarchy]
2638 The Complexity Class Hierarchy
2641 \begin_layout Standard
2645 \begin_layout Plain Layout
2649 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2652 \begin_layout Plain Layout
2656 \begin_layout Plain Layout
2660 pgfsetlinewidth{0.8pt}
2663 \begin_layout Plain Layout
2667 \begin_layout Plain Layout
2676 \begin_layout Plain Layout
2680 \begin_layout Plain Layout
2684 pgfsetdash{{2pt}}{0pt}
2687 \begin_layout Plain Layout
2691 \begin_layout Plain Layout
2699 Class{NC}^2$}{black!50!structure}{2}}
2702 \begin_layout Plain Layout
2706 \begin_layout Plain Layout
2712 Class{NL}$}{black!50!structure}{3}
2715 \begin_layout Plain Layout
2719 \begin_layout Plain Layout
2725 Class{L}$}{black!50!structure}{4}
2728 \begin_layout Plain Layout
2732 \begin_layout Plain Layout
2744 Class{NC}^1}$}{black!50!structure}{5}}
2747 \begin_layout Plain Layout
2751 \begin_layout Plain Layout
2758 \begin_layout Plain Layout
2762 \begin_layout Plain Layout
2774 Class{AC}^0}$}{black}{6}}
2777 \begin_layout Plain Layout
2781 \begin_layout Plain Layout
2785 \begin_layout Plain Layout
2789 \begin_layout Plain Layout
2793 pgfsetlinewidth{1.0pt}
2796 \begin_layout Plain Layout
2800 \begin_layout Plain Layout
2807 \begin_layout Plain Layout
2811 \begin_layout Plain Layout
2815 pgfxyline(-5,0)(5,0)
2818 \begin_layout Plain Layout
2822 \begin_layout Plain Layout
2826 \begin_layout Plain Layout
2830 \begin_layout Plain Layout
2841 \begin_layout Plain Layout
2845 \begin_layout Plain Layout
2855 operatorname{forest}}$}}
2858 \begin_layout Plain Layout
2862 \begin_layout Plain Layout
2866 \begin_layout Plain Layout
2870 \begin_layout Plain Layout
2881 \begin_layout Plain Layout
2885 \begin_layout Plain Layout
2904 \begin_layout Plain Layout
2908 \begin_layout Plain Layout
2927 \begin_layout Plain Layout
2931 \begin_layout Plain Layout
2944 \begin_layout Plain Layout
2948 \begin_layout Plain Layout
2956 operatorname{forest}}$,}
2961 \begin_layout Plain Layout
2965 \begin_layout Plain Layout
2973 operatorname{forest}}$,}
2978 \begin_layout Plain Layout
2982 \begin_layout Plain Layout
2990 operatorname{path}}$,}
2995 \begin_layout Plain Layout
2999 \begin_layout Plain Layout
3007 operatorname{path}}$}}}}
3010 \begin_layout Plain Layout
3014 \begin_layout Plain Layout
3024 operatorname{tourn}}$}}
3027 \begin_layout Plain Layout
3031 \begin_layout Plain Layout
3044 \begin_layout Plain Layout
3048 \begin_layout Plain Layout
3056 operatorname{tourn}}$,}
3061 \begin_layout Plain Layout
3065 \begin_layout Plain Layout
3076 \begin_layout Plain Layout
3080 \begin_layout Plain Layout
3089 \begin_layout Plain Layout
3093 \begin_layout Plain Layout
3099 pgfsetdash{{1pt}}{0pt}
3105 operatorname{tourn}}$''}}
3108 \begin_layout Plain Layout
3112 \begin_layout Plain Layout
3124 \begin_layout BeginFrame
3125 The Circuit Complexity Classes AC
3126 \begin_inset Formula $^{0}$
3130 \begin_inset Formula $^{1}$
3134 \begin_inset Formula $^{2}$
3138 \begin_inset Newline newline
3141 Limit the Circuit Depth
3144 \begin_layout Standard
3148 \begin_layout Plain Layout
3157 \begin_layout Plain Layout
3161 \begin_layout Plain Layout
3173 \begin_layout Columns
3177 \begin_layout Plain Layout
3188 \begin_layout Column
3196 \begin_layout Plain Layout
3204 \begin_inset Formula $\Class{AC}^{0}$
3211 \begin_layout Plain Layout
3222 \begin_layout Itemize
3223 \begin_inset Formula $O(1)$
3229 \begin_layout Itemize
3234 \begin_layout Examples
3239 \begin_layout Itemize
3240 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3246 \begin_layout Itemize
3247 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3258 \begin_layout Column
3266 \begin_layout Plain Layout
3274 \begin_inset Formula $\Class{NC}^{1}$
3281 \begin_layout Plain Layout
3292 \begin_layout Itemize
3293 \begin_inset Formula $O(\log n)$
3299 \begin_layout Itemize
3304 \begin_layout Examples
3309 \begin_layout Itemize
3310 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3316 \begin_layout Itemize
3317 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3323 \begin_layout Itemize
3324 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3335 \begin_layout Column
3343 \begin_layout Plain Layout
3351 \begin_inset Formula $\Class{NC}^{2}$
3358 \begin_layout Plain Layout
3369 \begin_layout Itemize
3370 \begin_inset Formula $O(\log^{2}n)$
3376 \begin_layout Itemize
3381 \begin_layout Examples
3386 \begin_layout Itemize
3387 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3395 \begin_layout AgainFrame
3399 \begin_layout Plain Layout
3409 \begin_layout Subsection
3410 Standard Complexity Results on Finding Paths
3413 \begin_layout BeginFrame
3414 All Variants of Finding Paths in Directed Graphs
3415 \begin_inset Newline newline
3418 Are Equally Difficult
3422 \begin_inset Formula $\Lang{reach}$
3426 \begin_inset Formula $\Lang{distance}$
3430 \begin_inset Formula $\Class{NL}$
3441 \begin_layout Corollary
3442 For directed graphs, we can solve
3446 \begin_layout Itemize
3447 the reachability problem in logspace iff
3448 \begin_inset Formula $\Class{L}=\Class{NL}$
3454 \begin_layout Itemize
3455 the construction problem in logspace iff
3456 \begin_inset Formula $\Class{L}=\Class{NL}$
3462 \begin_layout Itemize
3463 the optimization problem in logspace iff
3464 \begin_inset Formula $\Class{L}=\Class{NL}$
3470 \begin_layout Itemize
3471 the approximation problem in logspace iff
3472 \begin_inset Formula $\Class{L}=\Class{NL}$
3479 \begin_layout AgainFrame
3483 \begin_layout Plain Layout
3493 \begin_layout BeginFrame
3494 FindingPaths in Forests and Directed Paths is Easy,
3495 \begin_inset Newline newline
3502 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3506 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3510 \begin_inset Formula $\Class{L}$
3516 \begin_layout Separator
3521 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3525 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3529 \begin_inset Formula $\Class{L}$
3535 \begin_layout AgainFrame
3539 \begin_layout Plain Layout
3549 \begin_layout Section
3550 Finding Paths in Tournaments
3553 \begin_layout Subsection
3554 Complexity of: Does a Path Exist?
3557 \begin_layout BeginFrame
3558 Definition of the Tournament Reachability Problem
3561 \begin_layout Definition
3567 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3575 \begin_inset Formula $(T,s,t)$
3582 \begin_layout Enumerate
3583 \begin_inset Formula $T=(V,E)$
3589 \begin_layout Enumerate
3590 there exists a path from
3591 \begin_inset space ~
3595 \begin_inset Formula $s$
3599 \begin_inset space ~
3603 \begin_inset Formula $t$
3610 \begin_layout BeginFrame
3611 The Tournament Reachability Problem is Very Easy
3614 \begin_layout Theorem
3615 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3625 \begin_layout AlertBlock
3629 \begin_layout Plain Layout
3640 \begin_layout Itemize
3642 \begin_inset Quotes eld
3646 \begin_inset Quotes erd
3650 \begin_inset Formula $\Lang{reach}$
3654 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3660 \begin_layout Itemize
3661 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3668 \begin_layout AgainFrame
3672 \begin_layout Plain Layout
3682 \begin_layout Subsection
3683 Complexity of: Construct a Shortest Path
3686 \begin_layout BeginFrame
3687 Finding a Shortest Path Is as Difficult as
3688 \begin_inset Newline newline
3691 the Distance Problem
3694 \begin_layout Definition
3700 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3708 \begin_inset Formula $(T,s,t,d)$
3715 \begin_layout Enumerate
3716 \begin_inset Formula $T=(V,E)$
3719 is a tournament in which
3722 \begin_layout Enumerate
3724 \begin_inset Formula $s$
3728 \begin_inset space ~
3732 \begin_inset Formula $t$
3736 \begin_inset space ~
3740 \begin_inset Formula $d$
3747 \begin_layout BeginFrame
3748 The Tournament Distance Problem is Hard
3751 \begin_layout Theorem
3752 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3756 \begin_inset Formula $\Class{NL}$
3762 \begin_layout Standard
3763 \begin_inset space \hfill{}
3770 \begin_layout Plain Layout
3774 hyperlink{hierarchy<6>}{
3776 beamerskipbutton{Skip Proof}}
3788 \begin_layout Corollary
3789 Shortest path in tournaments can be constructed
3790 \begin_inset Newline newline
3793 in logarithmic space, iff
3794 \begin_inset Formula $\Class{L}=\Class{NL}$
3804 \begin_layout Corollary
3805 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3811 \begin_layout BeginFrame
3813 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3819 \begin_layout Standard
3823 \begin_layout Plain Layout
3835 \begin_layout Columns
3839 \begin_layout Plain Layout
3850 \begin_layout Column
3854 \begin_layout Standard
3858 \begin_layout Plain Layout
3876 \begin_layout Plain Layout
3884 \begin_inset Formula $\Lang{reach}$
3888 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3895 \begin_layout Plain Layout
3906 \begin_layout Enumerate
3910 \begin_layout Plain Layout
3918 \begin_inset Formula $(G,s,t)$
3922 \begin_inset Formula $\Lang{reach}$
3928 \begin_layout Enumerate
3932 \begin_layout Plain Layout
3940 \begin_inset Formula $G$
3944 \begin_inset Formula $G'$
3950 \begin_layout Enumerate
3954 \begin_layout Plain Layout
3962 \begin_inset Newline newline
3966 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3973 \begin_layout Separator
3981 \begin_layout Plain Layout
3992 \begin_layout Plain Layout
4003 \begin_layout Plain Layout
4014 \begin_layout Enumerate
4018 \begin_layout Plain Layout
4026 \begin_inset space ~
4030 \begin_inset Formula $G$
4034 \begin_inset Newline newline
4038 \begin_inset space ~
4042 \begin_inset Formula $G'$
4048 \begin_layout Enumerate
4052 \begin_layout Plain Layout
4060 \begin_inset space ~
4064 \begin_inset Formula $G'$
4068 \begin_inset Newline newline
4072 \begin_inset space ~
4076 \begin_inset Formula $G'$
4083 \begin_layout Column
4087 \begin_layout Example
4091 \begin_layout Plain Layout
4095 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
4098 \begin_layout Plain Layout
4102 \begin_layout Plain Layout
4106 color{beamerexample}
4109 \begin_layout Plain Layout
4113 \begin_layout Plain Layout
4117 pgfsetlinewidth{0.6pt}
4120 \begin_layout Plain Layout
4124 \begin_layout Plain Layout
4133 \begin_layout Plain Layout
4137 \begin_layout Plain Layout
4146 \begin_layout Plain Layout
4150 \begin_layout Plain Layout
4159 \begin_layout Plain Layout
4163 \begin_layout Plain Layout
4172 \begin_layout Plain Layout
4176 \begin_layout Plain Layout
4180 \begin_layout Plain Layout
4184 \begin_layout Plain Layout
4191 \begin_layout Plain Layout
4195 \begin_layout Plain Layout
4203 pgfbox[center,center]{$s$}}
4206 \begin_layout Plain Layout
4210 \begin_layout Plain Layout
4218 pgfbox[center,center]{$t$}}
4221 \begin_layout Plain Layout
4225 \begin_layout Plain Layout
4229 \begin_layout Plain Layout
4233 \begin_layout Plain Layout
4237 color{beamerexample}
4240 \begin_layout Plain Layout
4244 \begin_layout Plain Layout
4253 \begin_layout Plain Layout
4257 \begin_layout Plain Layout
4261 pgfnodesetsepstart{2pt}
4264 \begin_layout Plain Layout
4268 \begin_layout Plain Layout
4272 pgfnodesetsepend{2pt}
4275 \begin_layout Plain Layout
4279 \begin_layout Plain Layout
4285 pgfnodeconnline{B}{A}}
4288 \begin_layout Plain Layout
4292 \begin_layout Plain Layout
4298 pgfnodeconnline{B}{C}}
4301 \begin_layout Plain Layout
4305 \begin_layout Plain Layout
4311 pgfnodeconnline{C}{D}}
4314 \begin_layout Plain Layout
4318 \begin_layout Plain Layout
4324 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4327 \begin_layout Plain Layout
4331 \begin_layout Plain Layout
4336 \begin_layout Plain Layout
4340 \begin_layout Plain Layout
4348 pgfbox[left,center]{$G
4353 \begin_layout Plain Layout
4357 \begin_layout Plain Layout
4361 \begin_layout Plain Layout
4365 \begin_layout Plain Layout
4372 \begin_layout Plain Layout
4376 \begin_layout Plain Layout
4384 pgfbox[left,center]{$G'
4389 \begin_layout Plain Layout
4393 \begin_layout Plain Layout
4402 \begin_layout Plain Layout
4406 \begin_layout Plain Layout
4415 \begin_layout Plain Layout
4419 \begin_layout Plain Layout
4428 \begin_layout Plain Layout
4432 \begin_layout Plain Layout
4441 \begin_layout Plain Layout
4445 \begin_layout Plain Layout
4449 \begin_layout Plain Layout
4453 \begin_layout Plain Layout
4462 \begin_layout Plain Layout
4466 \begin_layout Plain Layout
4475 \begin_layout Plain Layout
4479 \begin_layout Plain Layout
4488 \begin_layout Plain Layout
4492 \begin_layout Plain Layout
4501 \begin_layout Plain Layout
4505 \begin_layout Plain Layout
4514 \begin_layout Plain Layout
4518 \begin_layout Plain Layout
4527 \begin_layout Plain Layout
4531 \begin_layout Plain Layout
4540 \begin_layout Plain Layout
4544 \begin_layout Plain Layout
4553 \begin_layout Plain Layout
4557 \begin_layout Plain Layout
4566 \begin_layout Plain Layout
4570 \begin_layout Plain Layout
4579 \begin_layout Plain Layout
4583 \begin_layout Plain Layout
4592 \begin_layout Plain Layout
4596 \begin_layout Plain Layout
4605 \begin_layout Plain Layout
4609 \begin_layout Plain Layout
4616 \begin_layout Plain Layout
4620 \begin_layout Plain Layout
4628 pgfbox[center,center]{$s'$}}
4631 \begin_layout Plain Layout
4635 \begin_layout Plain Layout
4643 pgfbox[center,center]{$t'$}}
4646 \begin_layout Plain Layout
4650 \begin_layout Plain Layout
4655 \begin_layout Plain Layout
4659 \begin_layout Plain Layout
4664 \begin_layout Plain Layout
4668 \begin_layout Plain Layout
4675 \begin_layout Plain Layout
4679 \begin_layout Plain Layout
4683 pgfsetlinewidth{0.4pt}
4686 \begin_layout Plain Layout
4690 \begin_layout Plain Layout
4694 color{beamerexample!25!averagebackgroundcolor}
4697 \begin_layout Plain Layout
4701 \begin_layout Plain Layout
4705 pgfnodeconnline{A2}{C1}
4708 \begin_layout Plain Layout
4712 \begin_layout Plain Layout
4716 pgfnodeconnline{A2}{D1}
4719 \begin_layout Plain Layout
4723 \begin_layout Plain Layout
4727 pgfnodeconnline{B2}{A1}
4730 \begin_layout Plain Layout
4734 \begin_layout Plain Layout
4738 pgfnodeconnline{B2}{C1}
4741 \begin_layout Plain Layout
4745 \begin_layout Plain Layout
4749 pgfnodeconnline{B2}{D1}
4752 \begin_layout Plain Layout
4756 \begin_layout Plain Layout
4760 pgfnodeconnline{C2}{D1}
4763 \begin_layout Plain Layout
4767 \begin_layout Plain Layout
4771 pgfnodeconnline{D2}{A1}
4774 \begin_layout Plain Layout
4778 \begin_layout Plain Layout
4782 pgfnodeconnline{D2}{B1}
4785 \begin_layout Plain Layout
4789 \begin_layout Plain Layout
4793 pgfnodeconnline{A3}{C2}
4796 \begin_layout Plain Layout
4800 \begin_layout Plain Layout
4804 pgfnodeconnline{A3}{D2}
4807 \begin_layout Plain Layout
4811 \begin_layout Plain Layout
4815 pgfnodeconnline{B3}{A2}
4818 \begin_layout Plain Layout
4822 \begin_layout Plain Layout
4826 pgfnodeconnline{B3}{C2}
4829 \begin_layout Plain Layout
4833 \begin_layout Plain Layout
4837 pgfnodeconnline{B3}{D2}
4840 \begin_layout Plain Layout
4844 \begin_layout Plain Layout
4848 pgfnodeconnline{C3}{D2}
4851 \begin_layout Plain Layout
4855 \begin_layout Plain Layout
4859 pgfnodeconnline{D3}{A2}
4862 \begin_layout Plain Layout
4866 \begin_layout Plain Layout
4870 pgfnodeconnline{D3}{B2}
4873 \begin_layout Plain Layout
4877 \begin_layout Plain Layout
4881 pgfnodeconnline{A4}{C3}
4884 \begin_layout Plain Layout
4888 \begin_layout Plain Layout
4892 pgfnodeconnline{A4}{D3}
4895 \begin_layout Plain Layout
4899 \begin_layout Plain Layout
4903 pgfnodeconnline{B4}{A3}
4906 \begin_layout Plain Layout
4910 \begin_layout Plain Layout
4914 pgfnodeconnline{B4}{C3}
4917 \begin_layout Plain Layout
4921 \begin_layout Plain Layout
4925 pgfnodeconnline{B4}{D3}
4928 \begin_layout Plain Layout
4932 \begin_layout Plain Layout
4936 pgfnodeconnline{C4}{D3}
4939 \begin_layout Plain Layout
4943 \begin_layout Plain Layout
4947 pgfnodeconnline{D4}{A3}
4950 \begin_layout Plain Layout
4954 \begin_layout Plain Layout
4958 pgfnodeconnline{D4}{B3}
4961 \begin_layout Plain Layout
4965 \begin_layout Plain Layout
4969 \begin_layout Plain Layout
4973 \begin_layout Plain Layout
4982 \begin_layout Plain Layout
4986 \begin_layout Plain Layout
4990 pgfnodeconnline{A1}{B1}
4993 \begin_layout Plain Layout
4997 \begin_layout Plain Layout
5001 pgfnodeconnline{B1}{C1}
5004 \begin_layout Plain Layout
5008 \begin_layout Plain Layout
5012 pgfnodeconnline{C1}{D1}
5015 \begin_layout Plain Layout
5019 \begin_layout Plain Layout
5023 pgfnodeconnline{A2}{B2}
5026 \begin_layout Plain Layout
5030 \begin_layout Plain Layout
5034 pgfnodeconnline{B2}{C2}
5037 \begin_layout Plain Layout
5041 \begin_layout Plain Layout
5045 pgfnodeconnline{C2}{D2}
5048 \begin_layout Plain Layout
5052 \begin_layout Plain Layout
5056 pgfnodeconnline{A3}{B3}
5059 \begin_layout Plain Layout
5063 \begin_layout Plain Layout
5067 pgfnodeconnline{B3}{C3}
5070 \begin_layout Plain Layout
5074 \begin_layout Plain Layout
5078 pgfnodeconnline{C3}{D3}
5081 \begin_layout Plain Layout
5085 \begin_layout Plain Layout
5089 pgfnodeconnline{A4}{B4}
5092 \begin_layout Plain Layout
5096 \begin_layout Plain Layout
5100 pgfnodeconnline{B4}{C4}
5103 \begin_layout Plain Layout
5107 \begin_layout Plain Layout
5111 pgfnodeconnline{C4}{D4}
5114 \begin_layout Plain Layout
5118 \begin_layout Plain Layout
5122 \begin_layout Plain Layout
5126 \begin_layout Plain Layout
5133 \begin_layout Plain Layout
5137 \begin_layout Plain Layout
5141 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
5144 \begin_layout Plain Layout
5148 \begin_layout Plain Layout
5152 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
5155 \begin_layout Plain Layout
5159 \begin_layout Plain Layout
5163 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
5166 \begin_layout Plain Layout
5170 \begin_layout Plain Layout
5174 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
5177 \begin_layout Plain Layout
5181 \begin_layout Plain Layout
5185 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
5188 \begin_layout Plain Layout
5192 \begin_layout Plain Layout
5196 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
5199 \begin_layout Plain Layout
5203 \begin_layout Plain Layout
5207 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
5210 \begin_layout Plain Layout
5214 \begin_layout Plain Layout
5218 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
5221 \begin_layout Plain Layout
5225 \begin_layout Plain Layout
5229 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
5232 \begin_layout Plain Layout
5236 \begin_layout Plain Layout
5240 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
5243 \begin_layout Plain Layout
5247 \begin_layout Plain Layout
5251 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
5254 \begin_layout Plain Layout
5258 \begin_layout Plain Layout
5262 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
5265 \begin_layout Plain Layout
5269 \begin_layout Plain Layout
5273 color{beamerexample}
5276 \begin_layout Plain Layout
5280 \begin_layout Plain Layout
5284 pgfsetlinewidth{0.6pt}
5287 \begin_layout Plain Layout
5291 \begin_layout Plain Layout
5296 \begin_layout Plain Layout
5300 \begin_layout Plain Layout
5304 \begin_layout Plain Layout
5308 \begin_layout Plain Layout
5315 \begin_layout Plain Layout
5319 \begin_layout Plain Layout
5326 \begin_layout Plain Layout
5330 \begin_layout Plain Layout
5334 pgfnodeconnline{B1}{A2}
5337 \begin_layout Plain Layout
5341 \begin_layout Plain Layout
5345 pgfnodeconnline{B2}{A3}
5348 \begin_layout Plain Layout
5352 \begin_layout Plain Layout
5356 pgfnodeconnline{B3}{A4}
5359 \begin_layout Plain Layout
5363 \begin_layout Plain Layout
5368 \begin_layout Plain Layout
5372 \begin_layout Plain Layout
5376 \begin_layout Plain Layout
5380 \begin_layout Plain Layout
5387 \begin_layout Plain Layout
5391 \begin_layout Plain Layout
5398 \begin_layout Plain Layout
5402 \begin_layout Plain Layout
5406 pgfnodeconnline{B1}{C2}
5409 \begin_layout Plain Layout
5413 \begin_layout Plain Layout
5417 pgfnodeconnline{B2}{C3}
5420 \begin_layout Plain Layout
5424 \begin_layout Plain Layout
5428 pgfnodeconnline{B3}{C4}
5431 \begin_layout Plain Layout
5435 \begin_layout Plain Layout
5440 \begin_layout Plain Layout
5444 \begin_layout Plain Layout
5449 \begin_layout Plain Layout
5453 \begin_layout Plain Layout
5460 \begin_layout Plain Layout
5464 \begin_layout Plain Layout
5471 \begin_layout Plain Layout
5475 \begin_layout Plain Layout
5479 pgfnodeconnline{C1}{D2}
5482 \begin_layout Plain Layout
5486 \begin_layout Plain Layout
5492 pgfnodeconnline{C2}{D3}}
5495 \begin_layout Plain Layout
5499 \begin_layout Plain Layout
5505 pgfnodeconnline{C3}{D4}}
5508 \begin_layout Plain Layout
5512 \begin_layout Plain Layout
5517 \begin_layout Plain Layout
5521 \begin_layout Plain Layout
5526 \begin_layout Plain Layout
5530 \begin_layout Plain Layout
5537 \begin_layout Plain Layout
5541 \begin_layout Plain Layout
5548 \begin_layout Plain Layout
5552 \begin_layout Plain Layout
5558 pgfnodeconnline{A1}{C2}}
5561 \begin_layout Plain Layout
5565 \begin_layout Plain Layout
5571 pgfnodeconnline{A2}{C3}}
5574 \begin_layout Plain Layout
5578 \begin_layout Plain Layout
5582 pgfnodeconnline{A3}{C4}
5585 \begin_layout Plain Layout
5589 \begin_layout Plain Layout
5594 \begin_layout Plain Layout
5598 \begin_layout Plain Layout
5602 \begin_layout Plain Layout
5606 \begin_layout Plain Layout
5613 \begin_layout Plain Layout
5617 \begin_layout Plain Layout
5624 \begin_layout Plain Layout
5628 \begin_layout Plain Layout
5634 pgfnodeconnline{A1}{A2}}
5637 \begin_layout Plain Layout
5641 \begin_layout Plain Layout
5645 pgfnodeconnline{A2}{A3}
5648 \begin_layout Plain Layout
5652 \begin_layout Plain Layout
5656 pgfnodeconnline{A3}{A4}
5659 \begin_layout Plain Layout
5663 \begin_layout Plain Layout
5667 pgfnodeconnline{B1}{B2}
5670 \begin_layout Plain Layout
5674 \begin_layout Plain Layout
5678 pgfnodeconnline{B2}{B3}
5681 \begin_layout Plain Layout
5685 \begin_layout Plain Layout
5689 pgfnodeconnline{B3}{B4}
5692 \begin_layout Plain Layout
5696 \begin_layout Plain Layout
5700 pgfnodeconnline{C1}{C2}
5703 \begin_layout Plain Layout
5707 \begin_layout Plain Layout
5711 pgfnodeconnline{C2}{C3}
5714 \begin_layout Plain Layout
5718 \begin_layout Plain Layout
5722 pgfnodeconnline{C3}{C4}
5725 \begin_layout Plain Layout
5729 \begin_layout Plain Layout
5733 pgfnodeconnline{D1}{D2}
5736 \begin_layout Plain Layout
5740 \begin_layout Plain Layout
5744 pgfnodeconnline{D2}{D3}
5747 \begin_layout Plain Layout
5751 \begin_layout Plain Layout
5757 pgfnodeconnline{D3}{D4}}
5760 \begin_layout Plain Layout
5764 \begin_layout Plain Layout
5769 \begin_layout Plain Layout
5773 \begin_layout Plain Layout
5786 \begin_layout AgainFrame
5790 \begin_layout Plain Layout
5800 \begin_layout Subsection
5801 Complexity of: Approximating the Shortest Path
5804 \begin_layout BeginFrame
5805 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5808 \begin_layout Definition
5813 approximation scheme for
5814 \begin_inset Formula $\Lang{tournament-shortest-path}$
5825 \begin_layout Enumerate
5827 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5833 \begin_layout Enumerate
5835 \begin_inset Formula $r>1$
5841 \begin_layout Standard
5845 \begin_layout Itemize
5847 \begin_inset Formula $s$
5851 \begin_inset space ~
5855 \begin_inset Formula $t$
5859 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5866 \begin_layout BeginFrame
5867 There Exists a Logspace Approximation Scheme for
5868 \begin_inset Newline newline
5871 the Tournament Shortest Path Problem
5874 \begin_layout Theorem
5875 There exists an approximation scheme for
5876 \begin_inset Formula $\Lang{tournament-shortest-path}$
5880 \begin_inset Formula $1<r<2$
5884 \begin_inset Formula
5886 O\left(\log|V|\log\frac{1}{r-1}\right).
5898 \begin_layout Corollary
5899 In tournaments, paths can be constructed in logarithmic space.
5902 \begin_layout Standard
5903 \begin_inset space \hfill{}
5910 \begin_layout Plain Layout
5914 hyperlink{optimality}{
5916 beamergotobutton{More Details}}
5924 \begin_layout AgainFrame
5928 \begin_layout Plain Layout
5938 \begin_layout EndFrame
5942 \begin_layout Standard
5943 \begin_inset Note Note
5946 \begin_layout Plain Layout
5947 If a frame includes a program listing, the frame needs to be marked as
5948 \begin_inset Quotes eld
5952 \begin_inset Quotes erd
5956 This is not yet supported by LyX, so the frame is created using TeX code.
5959 begin{frame}[fragile] needs to be preceeded by an
5971 \begin_layout Standard
5975 \begin_layout Plain Layout
5979 begin{frame}[fragile]
5987 \begin_layout Standard
5991 \begin_layout Plain Layout
6000 Just a frame with a program code listing
6004 \begin_layout Plain Layout
6014 \begin_layout Standard
6015 This is some program code:
6018 \begin_layout Standard
6019 \begin_inset listings
6020 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
6024 \begin_layout Plain Layout
6029 \begin_layout Plain Layout
6031 'this is a python function'
6034 \begin_layout Plain Layout
6039 \begin_layout Plain Layout
6044 \begin_layout Plain Layout
6046 'This is a German word: Tschüs'
6049 \begin_layout Plain Layout
6054 \begin_layout Plain Layout
6059 \begin_layout Plain Layout
6061 'this is a python function'
6064 \begin_layout Plain Layout
6074 \begin_layout Standard
6078 \begin_layout Plain Layout
6090 \begin_layout Section*
6094 \begin_layout Subsection*
6098 \begin_layout BeginFrame
6106 \begin_layout Plain Layout
6117 \begin_layout Itemize
6131 \begin_inset Formula $\Class{AC}^{0}$
6140 \begin_layout Itemize
6145 logspace approximation scheme
6157 shortest paths in tournaments.
6160 \begin_layout Itemize
6174 \begin_inset Formula $\Class{NL}$
6183 \begin_layout Separator
6191 \begin_layout Plain Layout
6202 \begin_layout Itemize
6203 The same results apply to graphs with
6204 \begin_inset Newline newline
6207 bounded independence number.
6208 \begin_inset space \hfill{}
6215 \begin_layout Plain Layout
6219 hyperlink{independence}{
6221 beamergotobutton{More Details}}
6229 \begin_layout Itemize
6230 The complexity of finding paths in undirected graphs
6231 \begin_inset Newline newline
6235 \begin_inset space \hfill{}
6242 \begin_layout Plain Layout
6246 hyperlink{undirected}{
6248 beamergotobutton{More Details}}
6257 \begin_layout Subsection*
6261 \begin_layout BeginFrame
6265 \begin_layout Standard
6269 \begin_layout Plain Layout
6273 beamertemplatebookbibitems
6281 \begin_layout Bibliography
6282 \labelwidthstring References
6283 \begin_inset CommandInset bibitem
6284 LatexCommand bibitem
6290 \begin_inset space ~
6298 \begin_layout Plain Layout
6309 Topics on Tournaments.
6316 \begin_layout Plain Layout
6325 Holt, Rinehart, and Winston, 1968.
6330 \begin_layout Plain Layout
6334 beamertemplatearticlebibitems
6342 \begin_layout Bibliography
6343 \labelwidthstring References
6344 \begin_inset CommandInset bibitem
6345 LatexCommand bibitem
6346 key "NickelsenT2002"
6351 \begin_inset space ~
6354 Arfst Nickelsen and Till Tantau.
6359 \begin_layout Plain Layout
6368 On reachability in graphs with bounded independence number.
6372 \begin_layout Plain Layout
6386 , Springer-Verlag, 2002.
6389 \begin_layout Bibliography
6390 \labelwidthstring References
6391 \begin_inset CommandInset bibitem
6392 LatexCommand bibitem
6398 \begin_inset space ~
6405 \begin_layout Plain Layout
6414 A logspace approximation scheme for the shortest path problem for graphs
6415 with bounded independence number.
6419 \begin_layout Plain Layout
6433 , Springer-Verlag, 2004.
6438 \begin_layout Plain Layout
6450 \begin_layout EndFrame
6454 \begin_layout Standard
6459 \begin_layout Plain Layout
6463 AtBeginSubsection[]{}
6471 \begin_layout Section
6475 \begin_layout Subsection
6476 Graphs With Bounded Independence Number
6479 \begin_layout BeginFrame
6483 \begin_layout Plain Layout
6485 [label=independence]
6490 Definition of Independence Number of a Graph
6493 \begin_layout Definition
6503 \begin_inset Formula $\alpha(G)$
6507 \begin_inset Newline newline
6510 is the maximum number of vertices we can pick,
6511 \begin_inset Newline newline
6514 such that there is no edge between them.
6517 \begin_layout Example
6518 Tournaments have independence number 1.
6522 \begin_layout BeginFrame
6523 The Results for Tournaments also Apply to
6524 \begin_inset Newline newline
6527 Graphs With Bounded Independence Number
6530 \begin_layout Theorem
6532 \begin_inset space ~
6536 \begin_inset Formula $k$
6547 in graphs with independence number
6548 \begin_inset Newline newline
6552 \begin_inset space ~
6556 \begin_inset Formula $k$
6560 \begin_inset Formula $\Class{AC}^{0}$
6566 \begin_layout Separator
6570 \begin_layout Theorem
6572 \begin_inset space ~
6576 \begin_inset Formula $k$
6583 logspace approximation scheme
6587 for approximating the shortest path in graphs with independence number at
6589 \begin_inset space ~
6593 \begin_inset Formula $k$
6599 \begin_layout Separator
6603 \begin_layout Theorem
6605 \begin_inset space ~
6609 \begin_inset Formula $k$
6620 in graphs with independence number at most
6621 \begin_inset space ~
6625 \begin_inset Formula $k$
6633 \begin_inset Formula $\Class{NL}$
6641 \begin_layout Subsection
6642 Finding Paths in Undirected Graphs
6645 \begin_layout BeginFrame
6649 \begin_layout Plain Layout
6651 <1-2>[label=undirected]
6656 The Complexity of Finding Paths in Undirected Graphs
6657 \begin_inset Newline newline
6664 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6668 \begin_inset Formula $\Class{SL}$
6674 \begin_layout Corollary
6675 For undirected graphs, we can solve
6679 \begin_layout Itemize
6680 the reachability problem in logspace iff
6681 \begin_inset Formula $\Class L=\Class{SL}$
6687 \begin_layout Itemize
6688 the construction problem in logspace iff
6692 \begin_layout Plain Layout
6710 \begin_layout Itemize
6711 the optimization problem in logspace iff
6715 \begin_layout Plain Layout
6733 \begin_layout Itemize
6734 the approximation problem in logspace iff ?.
6739 \begin_layout Subsection
6740 The Approximation Scheme is Optimal
6743 \begin_layout BeginFrame
6747 \begin_layout Plain Layout
6754 The Approximation Scheme is Optimal
6757 \begin_layout Theorem
6758 Suppose there exists an approximation scheme for
6759 \begin_inset Formula $\Lang{tournament-shortest-path}$
6763 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6768 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6779 \begin_layout Enumerate
6780 Suppose the approximation scheme exists.
6781 \begin_inset Newline newline
6785 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6792 \begin_layout Enumerate
6794 \begin_inset Formula $(T,s,t)$
6799 \begin_inset Formula $n$
6802 be the number of vertices.
6805 \begin_layout Enumerate
6806 Run the approximation scheme for
6807 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6811 \begin_inset Newline newline
6815 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6821 \begin_layout Enumerate
6822 The resulting path has optimal length.
6827 \begin_layout Plain Layout
6840 \begin_layout EndFrame