1 #LyX 1.6.5svn 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
157 \font_typewriter default
158 \font_default_family default
165 \paperfontsize default
174 \paperorientation portrait
177 \paragraph_separation indent
179 \quotes_language english
182 \paperpagestyle default
183 \tracking_changes false
184 \output_changes false
193 \begin_inset Newline newline
196 Finding Paths in Tournaments
203 \begin_layout Institute
204 International Computer Schience Institute
205 \begin_inset Newline newline
212 \begin_layout Plain Layout
225 \begin_layout BeginFrame
229 \begin_layout Standard
230 \begin_inset CommandInset toc
231 LatexCommand tableofcontents
239 \begin_layout Plain Layout
249 \begin_layout EndFrame
253 \begin_layout Standard
257 \begin_layout Plain Layout
259 % Show the table of contents at the beginning
262 \begin_layout Plain Layout
266 \begin_layout Plain Layout
268 % of every subsection.
271 \begin_layout Plain Layout
275 \begin_layout Plain Layout
282 \begin_layout Plain Layout
286 \begin_layout Plain Layout
293 \begin_layout Plain Layout
297 \begin_layout Plain Layout
304 \begin_layout Plain Layout
308 \begin_layout Plain Layout
312 tableofcontents[current,currentsubsection]
315 \begin_layout Plain Layout
319 \begin_layout Plain Layout
324 \begin_layout Plain Layout
328 \begin_layout Plain Layout
338 \begin_layout Section
342 \begin_layout Subsection
343 What are Tournaments?
346 \begin_layout BeginFrame
347 Tournaments Consist of Jousts Between Knights
350 \begin_layout Columns
359 \begin_layout Standard
363 \begin_layout Plain Layout
367 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
370 \begin_layout Plain Layout
374 \begin_layout Plain Layout
378 pgfnodebox{A}[virtual]{
382 pgfuseimage{knight1}}{2pt}{2pt}
385 \begin_layout Plain Layout
389 \begin_layout Plain Layout
393 pgfnodebox{B}[virtual]{
397 pgfuseimage{knight2}}{2pt}{2pt}
400 \begin_layout Plain Layout
404 \begin_layout Plain Layout
408 pgfnodebox{C}[virtual]{
412 pgfuseimage{knight3}}{2pt}{2pt}
415 \begin_layout Plain Layout
419 \begin_layout Plain Layout
423 pgfnodebox{D}[virtual]{
427 pgfuseimage{knight4}}{2pt}{2pt}
430 \begin_layout Plain Layout
434 \begin_layout Plain Layout
438 \begin_layout Plain Layout
442 \begin_layout Plain Layout
449 \begin_layout Plain Layout
453 \begin_layout Plain Layout
464 \begin_layout Plain Layout
468 \begin_layout Plain Layout
475 \begin_layout Plain Layout
479 \begin_layout Plain Layout
483 pgfsetlinewidth{0.6pt}
486 \begin_layout Plain Layout
490 \begin_layout Plain Layout
494 pgfnodeconnline{A}{B}
497 \begin_layout Plain Layout
501 \begin_layout Plain Layout
505 pgfnodeconnline{A}{C}
508 \begin_layout Plain Layout
512 \begin_layout Plain Layout
516 pgfnodeconnline{D}{A}
519 \begin_layout Plain Layout
523 \begin_layout Plain Layout
527 pgfnodeconnline{C}{B}
530 \begin_layout Plain Layout
534 \begin_layout Plain Layout
538 pgfnodeconnline{B}{D}
541 \begin_layout Plain Layout
545 \begin_layout Plain Layout
549 pgfnodeconnline{C}{D}}
552 \begin_layout Plain Layout
556 \begin_layout Plain Layout
576 \begin_layout Plain Layout
578 {What is a Tournament?}
587 \begin_layout Itemize
591 \begin_layout Plain Layout
601 \begin_layout Itemize
605 \begin_layout Plain Layout
612 Every pair has a joust.
615 \begin_layout Itemize
619 \begin_layout Plain Layout
626 In every joust one knight wins.
631 \begin_layout BeginFrame
632 Tournaments are Complete Directed Graphs
635 \begin_layout Columns
644 \begin_layout Standard
648 \begin_layout Plain Layout
652 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
655 \begin_layout Plain Layout
659 \begin_layout Plain Layout
666 \begin_layout Plain Layout
670 \begin_layout Plain Layout
674 pgfsetlinewidth{0.6pt}
677 \begin_layout Plain Layout
681 \begin_layout Plain Layout
690 \begin_layout Plain Layout
694 \begin_layout Plain Layout
703 \begin_layout Plain Layout
707 \begin_layout Plain Layout
716 \begin_layout Plain Layout
720 \begin_layout Plain Layout
729 \begin_layout Plain Layout
733 \begin_layout Plain Layout
737 \begin_layout Plain Layout
741 \begin_layout Plain Layout
748 \begin_layout Plain Layout
752 \begin_layout Plain Layout
760 pgfbox[center,center]{$v_2$}}
763 \begin_layout Plain Layout
767 \begin_layout Plain Layout
775 pgfbox[center,center]{$v_3$}}
778 \begin_layout Plain Layout
782 \begin_layout Plain Layout
790 pgfbox[center,center]{$v_4$}}
793 \begin_layout Plain Layout
797 \begin_layout Plain Layout
805 pgfbox[center,center]{$v_1$}}
808 \begin_layout Plain Layout
812 \begin_layout Plain Layout
816 \begin_layout Plain Layout
820 \begin_layout Plain Layout
827 \begin_layout Plain Layout
831 \begin_layout Plain Layout
840 \begin_layout Plain Layout
844 \begin_layout Plain Layout
848 pgfnodesetsepstart{2pt}
851 \begin_layout Plain Layout
855 \begin_layout Plain Layout
859 pgfnodesetsepend{4pt}
862 \begin_layout Plain Layout
866 \begin_layout Plain Layout
870 pgfnodeconnline{A}{B}
873 \begin_layout Plain Layout
877 \begin_layout Plain Layout
881 pgfnodeconnline{A}{C}
884 \begin_layout Plain Layout
888 \begin_layout Plain Layout
892 pgfnodeconnline{D}{A}
895 \begin_layout Plain Layout
899 \begin_layout Plain Layout
903 pgfnodeconnline{C}{B}
906 \begin_layout Plain Layout
910 \begin_layout Plain Layout
914 pgfnodeconnline{B}{D}
917 \begin_layout Plain Layout
921 \begin_layout Plain Layout
925 pgfnodeconnline{D}{C}
928 \begin_layout Plain Layout
932 \begin_layout Plain Layout
948 \begin_layout Definition
952 \begin_layout Plain Layout
971 \begin_layout Enumerate
975 \begin_layout Enumerate
976 with exactly one edge between
977 \begin_inset Newline newline
980 any two different vertices.
985 \begin_layout BeginFrame
989 \begin_layout Plain Layout
996 Tournaments Arise Naturally in Different Situations
999 \begin_layout ExampleBlock
1003 \begin_layout Plain Layout
1005 {Applicatins in Ordering Theory}
1014 \begin_layout Standard
1015 Elements in a set need to be sorted.
1017 \begin_inset Newline newline
1020 The comparison relation may be cyclic, however.
1024 \begin_layout Separator
1028 \begin_layout ExampleBlock
1032 \begin_layout Plain Layout
1034 {Applications in Sociology}
1043 \begin_layout Standard
1044 Several candidates apply for a position.
1045 \begin_inset Newline newline
1048 Reviewers decide for any two candidates whom they prefer.
1053 \begin_layout Separator
1057 \begin_layout ExampleBlock
1061 \begin_layout Plain Layout
1063 {Applications in Structural Complexity Theory}
1072 \begin_layout Standard
1074 \begin_inset Formula $L$
1077 is given and a selector function
1078 \begin_inset Formula $f$
1082 \begin_inset Newline newline
1085 It chooses from any two words the one more likely to be in
1086 \begin_inset Formula $f$
1093 \begin_layout Subsection
1094 What Does ``Finding Paths'' Mean?
1097 \begin_layout BeginFrame
1098 ``Finding Paths'' is Ambiguous
1105 \begin_layout Plain Layout
1115 par{}% because LyX inserts superfluous paragraphs
1118 \begin_layout Plain Layout
1122 \begin_layout Plain Layout
1126 only<1>{Path Finding Problems}
1131 \begin_layout Plain Layout
1135 \begin_layout Plain Layout
1146 \begin_layout Plain Layout
1150 \begin_layout Plain Layout
1154 only<4-5>{the Construction Problem}
1159 \begin_layout Plain Layout
1163 \begin_layout Plain Layout
1167 only<6-7>{the Optimization Problem}
1172 \begin_layout Plain Layout
1176 \begin_layout Plain Layout
1187 \begin_layout Plain Layout
1191 \begin_layout Plain Layout
1195 only<10->{the Approximation Problem}}
1204 \begin_layout Itemize
1214 \begin_inset Formula $G=(V,E)$
1226 \begin_inset Formula $s\in V$
1238 \begin_inset Formula $t\in V$
1244 \begin_layout Itemize
1248 \begin_layout Plain Layout
1250 <only@-9| visible@8->
1262 \begin_inset space ~
1266 \begin_inset Formula $d$
1273 \begin_layout Plain Layout
1285 \begin_layout Itemize
1289 \begin_layout Plain Layout
1305 \begin_inset Formula $r>1$
1312 \begin_layout Standard
1316 \begin_layout Plain Layout
1328 \begin_layout Overprint
1333 \begin_layout Standard
1337 \begin_layout Plain Layout
1341 onslide<1,3,5,7,9,11-12>
1349 \begin_layout Columns
1353 \begin_layout Plain Layout
1364 \begin_layout Standard
1368 \begin_layout Plain Layout
1386 \begin_layout ExampleBlock
1390 \begin_layout Plain Layout
1401 \begin_layout Standard
1405 \begin_layout Plain Layout
1409 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1412 \begin_layout Plain Layout
1416 \begin_layout Plain Layout
1420 color{beamerexample}
1423 \begin_layout Plain Layout
1427 \begin_layout Plain Layout
1431 pgfsetlinewidth{0.6pt}
1434 \begin_layout Plain Layout
1438 \begin_layout Plain Layout
1447 \begin_layout Plain Layout
1451 \begin_layout Plain Layout
1460 \begin_layout Plain Layout
1464 \begin_layout Plain Layout
1473 \begin_layout Plain Layout
1477 \begin_layout Plain Layout
1486 \begin_layout Plain Layout
1490 \begin_layout Plain Layout
1494 \begin_layout Plain Layout
1498 \begin_layout Plain Layout
1505 \begin_layout Plain Layout
1509 \begin_layout Plain Layout
1517 pgfbox[center,center]{$t$}}
1520 \begin_layout Plain Layout
1524 \begin_layout Plain Layout
1532 pgfbox[center,center]{$s$}}
1535 \begin_layout Plain Layout
1539 \begin_layout Plain Layout
1543 \begin_layout Plain Layout
1547 \begin_layout Plain Layout
1551 color{beamerexample}
1554 \begin_layout Plain Layout
1558 \begin_layout Plain Layout
1567 \begin_layout Plain Layout
1571 \begin_layout Plain Layout
1575 pgfnodesetsepstart{2pt}
1578 \begin_layout Plain Layout
1582 \begin_layout Plain Layout
1586 pgfnodesetsepend{4pt}
1589 \begin_layout Plain Layout
1593 \begin_layout Plain Layout
1597 pgfnodeconnline{A}{B}
1600 \begin_layout Plain Layout
1604 \begin_layout Plain Layout
1608 pgfnodeconnline{A}{C}
1611 \begin_layout Plain Layout
1615 \begin_layout Plain Layout
1619 pgfnodeconnline{D}{A}
1622 \begin_layout Plain Layout
1626 \begin_layout Plain Layout
1630 pgfnodeconnline{C}{B}
1633 \begin_layout Plain Layout
1637 \begin_layout Plain Layout
1641 pgfnodeconnline{B}{D}
1644 \begin_layout Plain Layout
1648 \begin_layout Plain Layout
1652 pgfnodeconnline{D}{C}
1655 \begin_layout Plain Layout
1659 \begin_layout Plain Layout
1663 \begin_layout Plain Layout
1667 \begin_layout Plain Layout
1677 pgfbox[left,center]{, $d=2$}}}
1680 \begin_layout Plain Layout
1684 \begin_layout Plain Layout
1694 pgfbox[left,center]{, $r=1.5$}}}
1697 \begin_layout Plain Layout
1701 \begin_layout Plain Layout
1711 pgfbox[left,center]{, $r=1.25$}}}
1714 \begin_layout Plain Layout
1718 \begin_layout Plain Layout
1731 \begin_layout Standard
1735 \begin_layout Plain Layout
1749 \begin_layout ExampleBlock
1753 \begin_layout Plain Layout
1755 <only@3->{Example Output}
1764 \begin_layout Standard
1768 \begin_layout Plain Layout
1772 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1775 \begin_layout Plain Layout
1779 \begin_layout Plain Layout
1786 \begin_layout Plain Layout
1790 \begin_layout Plain Layout
1794 color{beamerexample}
1797 \begin_layout Plain Layout
1801 \begin_layout Plain Layout
1805 pgfsetlinewidth{0.6pt}
1808 \begin_layout Plain Layout
1812 \begin_layout Plain Layout
1821 \begin_layout Plain Layout
1825 \begin_layout Plain Layout
1834 \begin_layout Plain Layout
1838 \begin_layout Plain Layout
1847 \begin_layout Plain Layout
1851 \begin_layout Plain Layout
1860 \begin_layout Plain Layout
1864 \begin_layout Plain Layout
1868 \begin_layout Plain Layout
1872 \begin_layout Plain Layout
1879 \begin_layout Plain Layout
1883 \begin_layout Plain Layout
1891 pgfbox[center,center]{$t$}}
1894 \begin_layout Plain Layout
1898 \begin_layout Plain Layout
1906 pgfbox[center,center]{$s$}}
1909 \begin_layout Plain Layout
1913 \begin_layout Plain Layout
1917 \begin_layout Plain Layout
1921 \begin_layout Plain Layout
1925 color{beamerexample}
1928 \begin_layout Plain Layout
1932 \begin_layout Plain Layout
1941 \begin_layout Plain Layout
1945 \begin_layout Plain Layout
1949 pgfnodesetsepstart{2pt}
1952 \begin_layout Plain Layout
1956 \begin_layout Plain Layout
1960 pgfnodesetsepend{4pt}
1963 \begin_layout Plain Layout
1967 \begin_layout Plain Layout
1972 \begin_layout Plain Layout
1976 \begin_layout Plain Layout
1982 pgfnodeconnline{A}{B}}
1985 \begin_layout Plain Layout
1989 \begin_layout Plain Layout
1995 pgfnodeconnline{A}{C}}
1998 \begin_layout Plain Layout
2002 \begin_layout Plain Layout
2008 pgfnodeconnline{D}{A}}
2011 \begin_layout Plain Layout
2015 \begin_layout Plain Layout
2021 pgfnodeconnline{C}{B}}
2024 \begin_layout Plain Layout
2028 \begin_layout Plain Layout
2032 pgfnodeconnline{B}{D}
2035 \begin_layout Plain Layout
2039 \begin_layout Plain Layout
2043 pgfnodeconnline{D}{C}
2046 \begin_layout Plain Layout
2050 \begin_layout Plain Layout
2055 \begin_layout Plain Layout
2059 \begin_layout Plain Layout
2069 pgfbox[left,center]{
2074 \begin_layout Plain Layout
2078 \begin_layout Plain Layout
2092 \begin_layout Standard
2096 \begin_layout Plain Layout
2112 \begin_layout Plain Layout
2114 {Variants of Path Finding Problems}
2123 \begin_layout Standard
2127 \begin_layout Plain Layout
2131 usedescriptionitemofwidthas{Approximation Problem:}
2139 \begin_layout Description
2141 \begin_inset space ~
2148 \begin_layout Plain Layout
2155 Is there a path from
2156 \begin_inset Formula $s$
2160 \begin_inset space ~
2164 \begin_inset Formula $t$
2170 \begin_layout Description
2172 \begin_inset space ~
2179 \begin_layout Plain Layout
2186 Construct a path from
2187 \begin_inset Formula $s$
2191 \begin_inset space ~
2195 \begin_inset Formula $t$
2201 \begin_layout Description
2203 \begin_inset space ~
2210 \begin_layout Plain Layout
2217 Construct a shortest path from
2218 \begin_inset Formula $s$
2222 \begin_inset space ~
2226 \begin_inset Formula $t$
2232 \begin_layout Description
2234 \begin_inset space ~
2241 \begin_layout Plain Layout
2249 \begin_inset Formula $s$
2253 \begin_inset space ~
2257 \begin_inset Formula $t$
2261 \begin_inset space ~
2265 \begin_inset Formula $d$
2271 \begin_layout Description
2273 \begin_inset space ~
2280 \begin_layout Plain Layout
2287 Construct a path from
2288 \begin_inset Formula $s$
2292 \begin_inset space ~
2296 \begin_inset Formula $t$
2300 \begin_inset Newline newline
2303 approximately their distance.
2308 \begin_layout Section
2312 \begin_layout Subsection
2313 Standard Complexity Classes
2316 \begin_layout Standard
2320 \begin_layout Plain Layout
2324 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2326 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2335 \begin_layout BeginFrame
2336 The Classes L and NL are Defined via
2337 \begin_inset Newline newline
2340 Logspace Turing Machines
2343 \begin_layout Standard
2347 \begin_layout Plain Layout
2351 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2354 \begin_layout Plain Layout
2358 \begin_layout Plain Layout
2366 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2369 \begin_layout Plain Layout
2373 \begin_layout Plain Layout
2380 \begin_layout Plain Layout
2384 \begin_layout Plain Layout
2392 tape{}{output tape (write only)}{10690836937182}}}
2395 \begin_layout Plain Layout
2399 \begin_layout Plain Layout
2406 \begin_layout Plain Layout
2410 \begin_layout Plain Layout
2418 shorttape{work tape (read/write), $O(
2420 log n)$ symbols}{}{42}}
2423 \begin_layout Plain Layout
2427 \begin_layout Plain Layout
2435 pgfbox[center,center]{
2437 pgfuseimage{computer}}}
2440 \begin_layout Plain Layout
2444 \begin_layout Plain Layout
2449 \begin_layout Plain Layout
2453 \begin_layout Plain Layout
2457 pgfsetlinewidth{0.6pt}
2460 \begin_layout Plain Layout
2464 \begin_layout Plain Layout
2468 \begin_layout Plain Layout
2472 \begin_layout Plain Layout
2479 \begin_layout Plain Layout
2483 \begin_layout Plain Layout
2492 \begin_layout Plain Layout
2496 \begin_layout Plain Layout
2500 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2503 \begin_layout Plain Layout
2507 \begin_layout Plain Layout
2513 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2516 \begin_layout Plain Layout
2520 \begin_layout Plain Layout
2526 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2529 \begin_layout Plain Layout
2533 \begin_layout Plain Layout
2545 \begin_layout BeginFrame
2546 Logspace Turing Machines Are Quite Powerful
2553 \begin_layout Plain Layout
2555 {Deterministic logspace machines can compute}
2564 \begin_layout Itemize
2565 addition, multiplication, and even division
2568 \begin_layout Itemize
2569 reductions used in completeness proofs,
2572 \begin_layout Itemize
2573 reachability in forests.
2585 \begin_layout Plain Layout
2587 {Non-deterministic logspace machines can compute}
2596 \begin_layout Itemize
2597 reachability in graphs,
2600 \begin_layout Itemize
2601 non-reachability in graphs,
2604 \begin_layout Itemize
2605 satisfiability with two literals per clause.
2609 \begin_layout BeginFrame
2613 \begin_layout Plain Layout
2615 <1>[label=hierarchy]
2620 The Complexity Class Hierarchy
2623 \begin_layout Standard
2627 \begin_layout Plain Layout
2631 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2634 \begin_layout Plain Layout
2638 \begin_layout Plain Layout
2642 pgfsetlinewidth{0.8pt}
2645 \begin_layout Plain Layout
2649 \begin_layout Plain Layout
2658 \begin_layout Plain Layout
2662 \begin_layout Plain Layout
2666 pgfsetdash{{2pt}}{0pt}
2669 \begin_layout Plain Layout
2673 \begin_layout Plain Layout
2681 Class{NC}^2$}{black!50!structure}{2}}
2684 \begin_layout Plain Layout
2688 \begin_layout Plain Layout
2694 Class{NL}$}{black!50!structure}{3}
2697 \begin_layout Plain Layout
2701 \begin_layout Plain Layout
2707 Class{L}$}{black!50!structure}{4}
2710 \begin_layout Plain Layout
2714 \begin_layout Plain Layout
2726 Class{NC}^1}$}{black!50!structure}{5}}
2729 \begin_layout Plain Layout
2733 \begin_layout Plain Layout
2740 \begin_layout Plain Layout
2744 \begin_layout Plain Layout
2756 Class{AC}^0}$}{black}{6}}
2759 \begin_layout Plain Layout
2763 \begin_layout Plain Layout
2767 \begin_layout Plain Layout
2771 \begin_layout Plain Layout
2775 pgfsetlinewidth{1.0pt}
2778 \begin_layout Plain Layout
2782 \begin_layout Plain Layout
2789 \begin_layout Plain Layout
2793 \begin_layout Plain Layout
2797 pgfxyline(-5,0)(5,0)
2800 \begin_layout Plain Layout
2804 \begin_layout Plain Layout
2808 \begin_layout Plain Layout
2812 \begin_layout Plain Layout
2823 \begin_layout Plain Layout
2827 \begin_layout Plain Layout
2837 operatorname{forest}}$}}
2840 \begin_layout Plain Layout
2844 \begin_layout Plain Layout
2848 \begin_layout Plain Layout
2852 \begin_layout Plain Layout
2863 \begin_layout Plain Layout
2867 \begin_layout Plain Layout
2886 \begin_layout Plain Layout
2890 \begin_layout Plain Layout
2909 \begin_layout Plain Layout
2913 \begin_layout Plain Layout
2926 \begin_layout Plain Layout
2930 \begin_layout Plain Layout
2938 operatorname{forest}}$,}
2943 \begin_layout Plain Layout
2947 \begin_layout Plain Layout
2955 operatorname{forest}}$,}
2960 \begin_layout Plain Layout
2964 \begin_layout Plain Layout
2972 operatorname{path}}$,}
2977 \begin_layout Plain Layout
2981 \begin_layout Plain Layout
2989 operatorname{path}}$}}}}
2992 \begin_layout Plain Layout
2996 \begin_layout Plain Layout
3006 operatorname{tourn}}$}}
3009 \begin_layout Plain Layout
3013 \begin_layout Plain Layout
3026 \begin_layout Plain Layout
3030 \begin_layout Plain Layout
3038 operatorname{tourn}}$,}
3043 \begin_layout Plain Layout
3047 \begin_layout Plain Layout
3058 \begin_layout Plain Layout
3062 \begin_layout Plain Layout
3071 \begin_layout Plain Layout
3075 \begin_layout Plain Layout
3081 pgfsetdash{{1pt}}{0pt}
3087 operatorname{tourn}}$''}}
3090 \begin_layout Plain Layout
3094 \begin_layout Plain Layout
3106 \begin_layout BeginFrame
3107 The Circuit Complexity Classes AC
3108 \begin_inset Formula $^{0}$
3112 \begin_inset Formula $^{1}$
3116 \begin_inset Formula $^{2}$
3120 \begin_inset Newline newline
3123 Limit the Circuit Depth
3126 \begin_layout Standard
3130 \begin_layout Plain Layout
3139 \begin_layout Plain Layout
3143 \begin_layout Plain Layout
3155 \begin_layout Columns
3159 \begin_layout Plain Layout
3170 \begin_layout Column
3178 \begin_layout Plain Layout
3186 \begin_inset Formula $\Class{AC}^{0}$
3193 \begin_layout Plain Layout
3204 \begin_layout Itemize
3205 \begin_inset Formula $O(1)$
3211 \begin_layout Itemize
3216 \begin_layout Examples
3221 \begin_layout Itemize
3222 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3228 \begin_layout Itemize
3229 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3240 \begin_layout Column
3248 \begin_layout Plain Layout
3256 \begin_inset Formula $\Class{NC}^{1}$
3263 \begin_layout Plain Layout
3274 \begin_layout Itemize
3275 \begin_inset Formula $O(\log n)$
3281 \begin_layout Itemize
3286 \begin_layout Examples
3291 \begin_layout Itemize
3292 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3298 \begin_layout Itemize
3299 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3305 \begin_layout Itemize
3306 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3317 \begin_layout Column
3325 \begin_layout Plain Layout
3333 \begin_inset Formula $\Class{NC}^{2}$
3340 \begin_layout Plain Layout
3351 \begin_layout Itemize
3352 \begin_inset Formula $O(\log^{2}n)$
3358 \begin_layout Itemize
3363 \begin_layout Examples
3368 \begin_layout Itemize
3369 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3377 \begin_layout AgainFrame
3381 \begin_layout Plain Layout
3391 \begin_layout Subsection
3392 Standard Complexity Results on Finding Paths
3395 \begin_layout BeginFrame
3396 All Variants of Finding Paths in Directed Graphs
3397 \begin_inset Newline newline
3400 Are Equally Difficult
3404 \begin_inset Formula $\Lang{reach}$
3408 \begin_inset Formula $\Lang{distance}$
3412 \begin_inset Formula $\Class{NL}$
3423 \begin_layout Corollary
3424 For directed graphs, we can solve
3428 \begin_layout Itemize
3429 the reachability problem in logspace iff
3430 \begin_inset Formula $\Class{L}=\Class{NL}$
3436 \begin_layout Itemize
3437 the construction problem in logspace iff
3438 \begin_inset Formula $\Class{L}=\Class{NL}$
3444 \begin_layout Itemize
3445 the optimization problem in logspace iff
3446 \begin_inset Formula $\Class{L}=\Class{NL}$
3452 \begin_layout Itemize
3453 the approximation problem in logspace iff
3454 \begin_inset Formula $\Class{L}=\Class{NL}$
3461 \begin_layout AgainFrame
3465 \begin_layout Plain Layout
3475 \begin_layout BeginFrame
3476 FindingPaths in Forests and Directed Paths is Easy,
3477 \begin_inset Newline newline
3484 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3488 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3492 \begin_inset Formula $\Class{L}$
3498 \begin_layout Separator
3503 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3507 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3511 \begin_inset Formula $\Class{L}$
3517 \begin_layout AgainFrame
3521 \begin_layout Plain Layout
3531 \begin_layout Section
3532 Finding Paths in Tournaments
3535 \begin_layout Subsection
3536 Complexity of: Does a Path Exist?
3539 \begin_layout BeginFrame
3540 Definition of the Tournament Reachability Problem
3543 \begin_layout Definition
3549 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3557 \begin_inset Formula $(T,s,t)$
3564 \begin_layout Enumerate
3565 \begin_inset Formula $T=(V,E)$
3571 \begin_layout Enumerate
3572 there exists a path from
3573 \begin_inset space ~
3577 \begin_inset Formula $s$
3581 \begin_inset space ~
3585 \begin_inset Formula $t$
3592 \begin_layout BeginFrame
3593 The Tournament Reachability Problem is Very Easy
3596 \begin_layout Theorem
3597 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3607 \begin_layout AlertBlock
3611 \begin_layout Plain Layout
3622 \begin_layout Itemize
3624 \begin_inset Quotes eld
3628 \begin_inset Quotes erd
3632 \begin_inset Formula $\Lang{reach}$
3636 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3642 \begin_layout Itemize
3643 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3650 \begin_layout AgainFrame
3654 \begin_layout Plain Layout
3664 \begin_layout Subsection
3665 Complexity of: Construct a Shortest Path
3668 \begin_layout BeginFrame
3669 Finding a Shortest Path Is as Difficult as
3670 \begin_inset Newline newline
3673 the Distance Problem
3676 \begin_layout Definition
3682 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3690 \begin_inset Formula $(T,s,t,d)$
3697 \begin_layout Enumerate
3698 \begin_inset Formula $T=(V,E)$
3701 is a tournament in which
3704 \begin_layout Enumerate
3706 \begin_inset Formula $s$
3710 \begin_inset space ~
3714 \begin_inset Formula $t$
3718 \begin_inset space ~
3722 \begin_inset Formula $d$
3729 \begin_layout BeginFrame
3730 The Tournament Distance Problem is Hard
3733 \begin_layout Theorem
3734 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3738 \begin_inset Formula $\Class{NL}$
3744 \begin_layout Standard
3745 \begin_inset space \hfill{}
3752 \begin_layout Plain Layout
3756 hyperlink{hierarchy<6>}{
3758 beamerskipbutton{Skip Proof}}
3770 \begin_layout Corollary
3771 Shortest path in tournaments can be constructed
3772 \begin_inset Newline newline
3775 in logarithmic space, iff
3776 \begin_inset Formula $\Class{L}=\Class{NL}$
3786 \begin_layout Corollary
3787 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3793 \begin_layout BeginFrame
3795 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3801 \begin_layout Standard
3805 \begin_layout Plain Layout
3817 \begin_layout Columns
3821 \begin_layout Plain Layout
3832 \begin_layout Column
3836 \begin_layout Standard
3840 \begin_layout Plain Layout
3858 \begin_layout Plain Layout
3866 \begin_inset Formula $\Lang{reach}$
3870 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3877 \begin_layout Plain Layout
3888 \begin_layout Enumerate
3892 \begin_layout Plain Layout
3900 \begin_inset Formula $(G,s,t)$
3904 \begin_inset Formula $\Lang{reach}$
3910 \begin_layout Enumerate
3914 \begin_layout Plain Layout
3922 \begin_inset Formula $G$
3926 \begin_inset Formula $G'$
3932 \begin_layout Enumerate
3936 \begin_layout Plain Layout
3944 \begin_inset Newline newline
3948 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3955 \begin_layout Separator
3963 \begin_layout Plain Layout
3974 \begin_layout Plain Layout
3985 \begin_layout Plain Layout
3996 \begin_layout Enumerate
4000 \begin_layout Plain Layout
4008 \begin_inset space ~
4012 \begin_inset Formula $G$
4016 \begin_inset Newline newline
4020 \begin_inset space ~
4024 \begin_inset Formula $G'$
4030 \begin_layout Enumerate
4034 \begin_layout Plain Layout
4042 \begin_inset space ~
4046 \begin_inset Formula $G'$
4050 \begin_inset Newline newline
4054 \begin_inset space ~
4058 \begin_inset Formula $G'$
4065 \begin_layout Column
4069 \begin_layout Example
4073 \begin_layout Plain Layout
4077 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
4080 \begin_layout Plain Layout
4084 \begin_layout Plain Layout
4088 color{beamerexample}
4091 \begin_layout Plain Layout
4095 \begin_layout Plain Layout
4099 pgfsetlinewidth{0.6pt}
4102 \begin_layout Plain Layout
4106 \begin_layout Plain Layout
4115 \begin_layout Plain Layout
4119 \begin_layout Plain Layout
4128 \begin_layout Plain Layout
4132 \begin_layout Plain Layout
4141 \begin_layout Plain Layout
4145 \begin_layout Plain Layout
4154 \begin_layout Plain Layout
4158 \begin_layout Plain Layout
4162 \begin_layout Plain Layout
4166 \begin_layout Plain Layout
4173 \begin_layout Plain Layout
4177 \begin_layout Plain Layout
4185 pgfbox[center,center]{$s$}}
4188 \begin_layout Plain Layout
4192 \begin_layout Plain Layout
4200 pgfbox[center,center]{$t$}}
4203 \begin_layout Plain Layout
4207 \begin_layout Plain Layout
4211 \begin_layout Plain Layout
4215 \begin_layout Plain Layout
4219 color{beamerexample}
4222 \begin_layout Plain Layout
4226 \begin_layout Plain Layout
4235 \begin_layout Plain Layout
4239 \begin_layout Plain Layout
4243 pgfnodesetsepstart{2pt}
4246 \begin_layout Plain Layout
4250 \begin_layout Plain Layout
4254 pgfnodesetsepend{2pt}
4257 \begin_layout Plain Layout
4261 \begin_layout Plain Layout
4267 pgfnodeconnline{B}{A}}
4270 \begin_layout Plain Layout
4274 \begin_layout Plain Layout
4280 pgfnodeconnline{B}{C}}
4283 \begin_layout Plain Layout
4287 \begin_layout Plain Layout
4293 pgfnodeconnline{C}{D}}
4296 \begin_layout Plain Layout
4300 \begin_layout Plain Layout
4306 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4309 \begin_layout Plain Layout
4313 \begin_layout Plain Layout
4318 \begin_layout Plain Layout
4322 \begin_layout Plain Layout
4330 pgfbox[left,center]{$G
4335 \begin_layout Plain Layout
4339 \begin_layout Plain Layout
4343 \begin_layout Plain Layout
4347 \begin_layout Plain Layout
4354 \begin_layout Plain Layout
4358 \begin_layout Plain Layout
4366 pgfbox[left,center]{$G'
4371 \begin_layout Plain Layout
4375 \begin_layout Plain Layout
4384 \begin_layout Plain Layout
4388 \begin_layout Plain Layout
4397 \begin_layout Plain Layout
4401 \begin_layout Plain Layout
4410 \begin_layout Plain Layout
4414 \begin_layout Plain Layout
4423 \begin_layout Plain Layout
4427 \begin_layout Plain Layout
4431 \begin_layout Plain Layout
4435 \begin_layout Plain Layout
4444 \begin_layout Plain Layout
4448 \begin_layout Plain Layout
4457 \begin_layout Plain Layout
4461 \begin_layout Plain Layout
4470 \begin_layout Plain Layout
4474 \begin_layout Plain Layout
4483 \begin_layout Plain Layout
4487 \begin_layout Plain Layout
4496 \begin_layout Plain Layout
4500 \begin_layout Plain Layout
4509 \begin_layout Plain Layout
4513 \begin_layout Plain Layout
4522 \begin_layout Plain Layout
4526 \begin_layout Plain Layout
4535 \begin_layout Plain Layout
4539 \begin_layout Plain Layout
4548 \begin_layout Plain Layout
4552 \begin_layout Plain Layout
4561 \begin_layout Plain Layout
4565 \begin_layout Plain Layout
4574 \begin_layout Plain Layout
4578 \begin_layout Plain Layout
4587 \begin_layout Plain Layout
4591 \begin_layout Plain Layout
4598 \begin_layout Plain Layout
4602 \begin_layout Plain Layout
4610 pgfbox[center,center]{$s'$}}
4613 \begin_layout Plain Layout
4617 \begin_layout Plain Layout
4625 pgfbox[center,center]{$t'$}}
4628 \begin_layout Plain Layout
4632 \begin_layout Plain Layout
4637 \begin_layout Plain Layout
4641 \begin_layout Plain Layout
4646 \begin_layout Plain Layout
4650 \begin_layout Plain Layout
4657 \begin_layout Plain Layout
4661 \begin_layout Plain Layout
4665 pgfsetlinewidth{0.4pt}
4668 \begin_layout Plain Layout
4672 \begin_layout Plain Layout
4676 color{beamerexample!25!averagebackgroundcolor}
4679 \begin_layout Plain Layout
4683 \begin_layout Plain Layout
4687 pgfnodeconnline{A2}{C1}
4690 \begin_layout Plain Layout
4694 \begin_layout Plain Layout
4698 pgfnodeconnline{A2}{D1}
4701 \begin_layout Plain Layout
4705 \begin_layout Plain Layout
4709 pgfnodeconnline{B2}{A1}
4712 \begin_layout Plain Layout
4716 \begin_layout Plain Layout
4720 pgfnodeconnline{B2}{C1}
4723 \begin_layout Plain Layout
4727 \begin_layout Plain Layout
4731 pgfnodeconnline{B2}{D1}
4734 \begin_layout Plain Layout
4738 \begin_layout Plain Layout
4742 pgfnodeconnline{C2}{D1}
4745 \begin_layout Plain Layout
4749 \begin_layout Plain Layout
4753 pgfnodeconnline{D2}{A1}
4756 \begin_layout Plain Layout
4760 \begin_layout Plain Layout
4764 pgfnodeconnline{D2}{B1}
4767 \begin_layout Plain Layout
4771 \begin_layout Plain Layout
4775 pgfnodeconnline{A3}{C2}
4778 \begin_layout Plain Layout
4782 \begin_layout Plain Layout
4786 pgfnodeconnline{A3}{D2}
4789 \begin_layout Plain Layout
4793 \begin_layout Plain Layout
4797 pgfnodeconnline{B3}{A2}
4800 \begin_layout Plain Layout
4804 \begin_layout Plain Layout
4808 pgfnodeconnline{B3}{C2}
4811 \begin_layout Plain Layout
4815 \begin_layout Plain Layout
4819 pgfnodeconnline{B3}{D2}
4822 \begin_layout Plain Layout
4826 \begin_layout Plain Layout
4830 pgfnodeconnline{C3}{D2}
4833 \begin_layout Plain Layout
4837 \begin_layout Plain Layout
4841 pgfnodeconnline{D3}{A2}
4844 \begin_layout Plain Layout
4848 \begin_layout Plain Layout
4852 pgfnodeconnline{D3}{B2}
4855 \begin_layout Plain Layout
4859 \begin_layout Plain Layout
4863 pgfnodeconnline{A4}{C3}
4866 \begin_layout Plain Layout
4870 \begin_layout Plain Layout
4874 pgfnodeconnline{A4}{D3}
4877 \begin_layout Plain Layout
4881 \begin_layout Plain Layout
4885 pgfnodeconnline{B4}{A3}
4888 \begin_layout Plain Layout
4892 \begin_layout Plain Layout
4896 pgfnodeconnline{B4}{C3}
4899 \begin_layout Plain Layout
4903 \begin_layout Plain Layout
4907 pgfnodeconnline{B4}{D3}
4910 \begin_layout Plain Layout
4914 \begin_layout Plain Layout
4918 pgfnodeconnline{C4}{D3}
4921 \begin_layout Plain Layout
4925 \begin_layout Plain Layout
4929 pgfnodeconnline{D4}{A3}
4932 \begin_layout Plain Layout
4936 \begin_layout Plain Layout
4940 pgfnodeconnline{D4}{B3}
4943 \begin_layout Plain Layout
4947 \begin_layout Plain Layout
4951 \begin_layout Plain Layout
4955 \begin_layout Plain Layout
4964 \begin_layout Plain Layout
4968 \begin_layout Plain Layout
4972 pgfnodeconnline{A1}{B1}
4975 \begin_layout Plain Layout
4979 \begin_layout Plain Layout
4983 pgfnodeconnline{B1}{C1}
4986 \begin_layout Plain Layout
4990 \begin_layout Plain Layout
4994 pgfnodeconnline{C1}{D1}
4997 \begin_layout Plain Layout
5001 \begin_layout Plain Layout
5005 pgfnodeconnline{A2}{B2}
5008 \begin_layout Plain Layout
5012 \begin_layout Plain Layout
5016 pgfnodeconnline{B2}{C2}
5019 \begin_layout Plain Layout
5023 \begin_layout Plain Layout
5027 pgfnodeconnline{C2}{D2}
5030 \begin_layout Plain Layout
5034 \begin_layout Plain Layout
5038 pgfnodeconnline{A3}{B3}
5041 \begin_layout Plain Layout
5045 \begin_layout Plain Layout
5049 pgfnodeconnline{B3}{C3}
5052 \begin_layout Plain Layout
5056 \begin_layout Plain Layout
5060 pgfnodeconnline{C3}{D3}
5063 \begin_layout Plain Layout
5067 \begin_layout Plain Layout
5071 pgfnodeconnline{A4}{B4}
5074 \begin_layout Plain Layout
5078 \begin_layout Plain Layout
5082 pgfnodeconnline{B4}{C4}
5085 \begin_layout Plain Layout
5089 \begin_layout Plain Layout
5093 pgfnodeconnline{C4}{D4}
5096 \begin_layout Plain Layout
5100 \begin_layout Plain Layout
5104 \begin_layout Plain Layout
5108 \begin_layout Plain Layout
5115 \begin_layout Plain Layout
5119 \begin_layout Plain Layout
5123 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
5126 \begin_layout Plain Layout
5130 \begin_layout Plain Layout
5134 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
5137 \begin_layout Plain Layout
5141 \begin_layout Plain Layout
5145 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
5148 \begin_layout Plain Layout
5152 \begin_layout Plain Layout
5156 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
5159 \begin_layout Plain Layout
5163 \begin_layout Plain Layout
5167 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
5170 \begin_layout Plain Layout
5174 \begin_layout Plain Layout
5178 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
5181 \begin_layout Plain Layout
5185 \begin_layout Plain Layout
5189 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
5192 \begin_layout Plain Layout
5196 \begin_layout Plain Layout
5200 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
5203 \begin_layout Plain Layout
5207 \begin_layout Plain Layout
5211 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
5214 \begin_layout Plain Layout
5218 \begin_layout Plain Layout
5222 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
5225 \begin_layout Plain Layout
5229 \begin_layout Plain Layout
5233 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
5236 \begin_layout Plain Layout
5240 \begin_layout Plain Layout
5244 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
5247 \begin_layout Plain Layout
5251 \begin_layout Plain Layout
5255 color{beamerexample}
5258 \begin_layout Plain Layout
5262 \begin_layout Plain Layout
5266 pgfsetlinewidth{0.6pt}
5269 \begin_layout Plain Layout
5273 \begin_layout Plain Layout
5278 \begin_layout Plain Layout
5282 \begin_layout Plain Layout
5286 \begin_layout Plain Layout
5290 \begin_layout Plain Layout
5297 \begin_layout Plain Layout
5301 \begin_layout Plain Layout
5308 \begin_layout Plain Layout
5312 \begin_layout Plain Layout
5316 pgfnodeconnline{B1}{A2}
5319 \begin_layout Plain Layout
5323 \begin_layout Plain Layout
5327 pgfnodeconnline{B2}{A3}
5330 \begin_layout Plain Layout
5334 \begin_layout Plain Layout
5338 pgfnodeconnline{B3}{A4}
5341 \begin_layout Plain Layout
5345 \begin_layout Plain Layout
5350 \begin_layout Plain Layout
5354 \begin_layout Plain Layout
5358 \begin_layout Plain Layout
5362 \begin_layout Plain Layout
5369 \begin_layout Plain Layout
5373 \begin_layout Plain Layout
5380 \begin_layout Plain Layout
5384 \begin_layout Plain Layout
5388 pgfnodeconnline{B1}{C2}
5391 \begin_layout Plain Layout
5395 \begin_layout Plain Layout
5399 pgfnodeconnline{B2}{C3}
5402 \begin_layout Plain Layout
5406 \begin_layout Plain Layout
5410 pgfnodeconnline{B3}{C4}
5413 \begin_layout Plain Layout
5417 \begin_layout Plain Layout
5422 \begin_layout Plain Layout
5426 \begin_layout Plain Layout
5431 \begin_layout Plain Layout
5435 \begin_layout Plain Layout
5442 \begin_layout Plain Layout
5446 \begin_layout Plain Layout
5453 \begin_layout Plain Layout
5457 \begin_layout Plain Layout
5461 pgfnodeconnline{C1}{D2}
5464 \begin_layout Plain Layout
5468 \begin_layout Plain Layout
5474 pgfnodeconnline{C2}{D3}}
5477 \begin_layout Plain Layout
5481 \begin_layout Plain Layout
5487 pgfnodeconnline{C3}{D4}}
5490 \begin_layout Plain Layout
5494 \begin_layout Plain Layout
5499 \begin_layout Plain Layout
5503 \begin_layout Plain Layout
5508 \begin_layout Plain Layout
5512 \begin_layout Plain Layout
5519 \begin_layout Plain Layout
5523 \begin_layout Plain Layout
5530 \begin_layout Plain Layout
5534 \begin_layout Plain Layout
5540 pgfnodeconnline{A1}{C2}}
5543 \begin_layout Plain Layout
5547 \begin_layout Plain Layout
5553 pgfnodeconnline{A2}{C3}}
5556 \begin_layout Plain Layout
5560 \begin_layout Plain Layout
5564 pgfnodeconnline{A3}{C4}
5567 \begin_layout Plain Layout
5571 \begin_layout Plain Layout
5576 \begin_layout Plain Layout
5580 \begin_layout Plain Layout
5584 \begin_layout Plain Layout
5588 \begin_layout Plain Layout
5595 \begin_layout Plain Layout
5599 \begin_layout Plain Layout
5606 \begin_layout Plain Layout
5610 \begin_layout Plain Layout
5616 pgfnodeconnline{A1}{A2}}
5619 \begin_layout Plain Layout
5623 \begin_layout Plain Layout
5627 pgfnodeconnline{A2}{A3}
5630 \begin_layout Plain Layout
5634 \begin_layout Plain Layout
5638 pgfnodeconnline{A3}{A4}
5641 \begin_layout Plain Layout
5645 \begin_layout Plain Layout
5649 pgfnodeconnline{B1}{B2}
5652 \begin_layout Plain Layout
5656 \begin_layout Plain Layout
5660 pgfnodeconnline{B2}{B3}
5663 \begin_layout Plain Layout
5667 \begin_layout Plain Layout
5671 pgfnodeconnline{B3}{B4}
5674 \begin_layout Plain Layout
5678 \begin_layout Plain Layout
5682 pgfnodeconnline{C1}{C2}
5685 \begin_layout Plain Layout
5689 \begin_layout Plain Layout
5693 pgfnodeconnline{C2}{C3}
5696 \begin_layout Plain Layout
5700 \begin_layout Plain Layout
5704 pgfnodeconnline{C3}{C4}
5707 \begin_layout Plain Layout
5711 \begin_layout Plain Layout
5715 pgfnodeconnline{D1}{D2}
5718 \begin_layout Plain Layout
5722 \begin_layout Plain Layout
5726 pgfnodeconnline{D2}{D3}
5729 \begin_layout Plain Layout
5733 \begin_layout Plain Layout
5739 pgfnodeconnline{D3}{D4}}
5742 \begin_layout Plain Layout
5746 \begin_layout Plain Layout
5751 \begin_layout Plain Layout
5755 \begin_layout Plain Layout
5768 \begin_layout AgainFrame
5772 \begin_layout Plain Layout
5782 \begin_layout Subsection
5783 Complexity of: Approximating the Shortest Path
5786 \begin_layout BeginFrame
5787 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5790 \begin_layout Definition
5795 approximation scheme for
5796 \begin_inset Formula $\Lang{tournament-shortest-path}$
5807 \begin_layout Enumerate
5809 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5815 \begin_layout Enumerate
5817 \begin_inset Formula $r>1$
5823 \begin_layout Standard
5827 \begin_layout Itemize
5829 \begin_inset Formula $s$
5833 \begin_inset space ~
5837 \begin_inset Formula $t$
5841 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5848 \begin_layout BeginFrame
5849 There Exists a Logspace Approximation Scheme for
5850 \begin_inset Newline newline
5853 the Tournament Shortest Path Problem
5856 \begin_layout Theorem
5857 There exists an approximation scheme for
5858 \begin_inset Formula $\Lang{tournament-shortest-path}$
5862 \begin_inset Formula $1<r<2$
5866 \begin_inset Formula \[
5867 O\left(\log|V|\log\frac{1}{r-1}\right).\]
5878 \begin_layout Corollary
5879 In tournaments, paths can be constructed in logarithmic space.
5882 \begin_layout Standard
5883 \begin_inset space \hfill{}
5890 \begin_layout Plain Layout
5894 hyperlink{optimality}{
5896 beamergotobutton{More Details}}
5904 \begin_layout AgainFrame
5908 \begin_layout Plain Layout
5918 \begin_layout EndFrame
5922 \begin_layout Standard
5923 \begin_inset Note Note
5926 \begin_layout Plain Layout
5927 If a frame includes a program listing, the frame needs to be marked as
5928 \begin_inset Quotes eld
5932 \begin_inset Quotes erd
5936 This is not yet supported by LyX, so the frame is created using TeX code.
5939 begin{frame}[fragile] needs to be preceeded by an
5951 \begin_layout Standard
5955 \begin_layout Plain Layout
5959 begin{frame}[fragile]
5967 \begin_layout Standard
5971 \begin_layout Plain Layout
5980 Just a frame with a program code listing
5984 \begin_layout Plain Layout
5994 \begin_layout Standard
5995 This is some program code:
5998 \begin_layout Standard
5999 \begin_inset listings
6000 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
6004 \begin_layout Plain Layout
6009 \begin_layout Plain Layout
6011 'this is a python function'
6014 \begin_layout Plain Layout
6019 \begin_layout Plain Layout
6024 \begin_layout Plain Layout
6026 'This is a German word: Tschüs'
6029 \begin_layout Plain Layout
6034 \begin_layout Plain Layout
6039 \begin_layout Plain Layout
6041 'this is a python function'
6044 \begin_layout Plain Layout
6054 \begin_layout Standard
6058 \begin_layout Plain Layout
6070 \begin_layout Section*
6074 \begin_layout Subsection*
6078 \begin_layout BeginFrame
6086 \begin_layout Plain Layout
6097 \begin_layout Itemize
6111 \begin_inset Formula $\Class{AC}^{0}$
6120 \begin_layout Itemize
6125 logspace approximation scheme
6137 shortest paths in tournaments.
6140 \begin_layout Itemize
6154 \begin_inset Formula $\Class{NL}$
6163 \begin_layout Separator
6171 \begin_layout Plain Layout
6182 \begin_layout Itemize
6183 The same results apply to graphs with
6184 \begin_inset Newline newline
6187 bounded independence number.
6188 \begin_inset space \hfill{}
6195 \begin_layout Plain Layout
6199 hyperlink{independence}{
6201 beamergotobutton{More Details}}
6209 \begin_layout Itemize
6210 The complexity of finding paths in undirected graphs
6211 \begin_inset Newline newline
6215 \begin_inset space \hfill{}
6222 \begin_layout Plain Layout
6226 hyperlink{undirected}{
6228 beamergotobutton{More Details}}
6237 \begin_layout Subsection*
6241 \begin_layout BeginFrame
6245 \begin_layout Standard
6249 \begin_layout Plain Layout
6253 beamertemplatebookbibitems
6261 \begin_layout Bibliography
6262 \begin_inset CommandInset bibitem
6263 LatexCommand bibitem
6269 \begin_inset space ~
6277 \begin_layout Plain Layout
6288 Topics on Tournaments.
6295 \begin_layout Plain Layout
6304 Holt, Rinehart, and Winston, 1968.
6309 \begin_layout Plain Layout
6313 beamertemplatearticlebibitems
6321 \begin_layout Bibliography
6322 \begin_inset CommandInset bibitem
6323 LatexCommand bibitem
6324 key "NickelsenT2002"
6329 \begin_inset space ~
6332 Arfst Nickelsen and Till Tantau.
6337 \begin_layout Plain Layout
6346 On reachability in graphs with bounded independence number.
6350 \begin_layout Plain Layout
6364 , Springer-Verlag, 2002.
6367 \begin_layout Bibliography
6368 \begin_inset CommandInset bibitem
6369 LatexCommand bibitem
6375 \begin_inset space ~
6382 \begin_layout Plain Layout
6391 A logspace approximation scheme for the shortest path problem for graphs
6392 with bounded independence number.
6396 \begin_layout Plain Layout
6410 , Springer-Verlag, 2004.
6415 \begin_layout Plain Layout
6427 \begin_layout EndFrame
6431 \begin_layout Standard
6436 \begin_layout Plain Layout
6440 AtBeginSubsection[]{}
6448 \begin_layout Section
6452 \begin_layout Subsection
6453 Graphs With Bounded Independence Number
6456 \begin_layout BeginFrame
6460 \begin_layout Plain Layout
6462 [label=independence]
6467 Definition of Independence Number of a Graph
6470 \begin_layout Definition
6480 \begin_inset Formula $\alpha(G)$
6484 \begin_inset Newline newline
6487 is the maximum number of vertices we can pick,
6488 \begin_inset Newline newline
6491 such that there is no edge between them.
6494 \begin_layout Example
6495 Tournaments have independence number 1.
6499 \begin_layout BeginFrame
6500 The Results for Tournaments also Apply to
6501 \begin_inset Newline newline
6504 Graphs With Bounded Independence Number
6507 \begin_layout Theorem
6509 \begin_inset space ~
6513 \begin_inset Formula $k$
6524 in graphs with independence number
6525 \begin_inset Newline newline
6529 \begin_inset space ~
6533 \begin_inset Formula $k$
6537 \begin_inset Formula $\Class{AC}^{0}$
6543 \begin_layout Separator
6547 \begin_layout Theorem
6549 \begin_inset space ~
6553 \begin_inset Formula $k$
6560 logspace approximation scheme
6564 for approximating the shortest path in graphs with independence number at
6566 \begin_inset space ~
6570 \begin_inset Formula $k$
6576 \begin_layout Separator
6580 \begin_layout Theorem
6582 \begin_inset space ~
6586 \begin_inset Formula $k$
6597 in graphs with independence number at most
6598 \begin_inset space ~
6602 \begin_inset Formula $k$
6610 \begin_inset Formula $\Class{NL}$
6618 \begin_layout Subsection
6619 Finding Paths in Undirected Graphs
6622 \begin_layout BeginFrame
6626 \begin_layout Plain Layout
6628 <1-2>[label=undirected]
6633 The Complexity of Finding Paths in Undirected Graphs
6634 \begin_inset Newline newline
6641 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6645 \begin_inset Formula $\Class{SL}$
6651 \begin_layout Corollary
6652 For undirected graphs, we can solve
6656 \begin_layout Itemize
6657 the reachability problem in logspace iff
6658 \begin_inset Formula $\Class L=\Class{SL}$
6664 \begin_layout Itemize
6665 the construction problem in logspace iff
6669 \begin_layout Plain Layout
6687 \begin_layout Itemize
6688 the optimization problem in logspace iff
6692 \begin_layout Plain Layout
6710 \begin_layout Itemize
6711 the approximation problem in logspace iff ?.
6716 \begin_layout Subsection
6717 The Approximation Scheme is Optimal
6720 \begin_layout BeginFrame
6724 \begin_layout Plain Layout
6731 The Approximation Scheme is Optimal
6734 \begin_layout Theorem
6735 Suppose there exists an approximation scheme for
6736 \begin_inset Formula $\Lang{tournament-shortest-path}$
6740 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6745 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6756 \begin_layout Enumerate
6757 Suppose the approximation scheme exists.
6758 \begin_inset Newline newline
6762 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6769 \begin_layout Enumerate
6771 \begin_inset Formula $(T,s,t)$
6776 \begin_inset Formula $n$
6779 be the number of vertices.
6782 \begin_layout Enumerate
6783 Run the approximation scheme for
6784 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6788 \begin_inset Newline newline
6792 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6798 \begin_layout Enumerate
6799 The resulting path has optimal length.
6804 \begin_layout Plain Layout
6817 \begin_layout EndFrame