1 #LyX 1.4.3 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}}}
156 \paperfontsize default
163 \paperorientation portrait
166 \paragraph_separation indent
168 \quotes_language english
171 \paperpagestyle default
172 \tracking_changes false
181 Finding Paths in Tournaments
188 \begin_layout Institute
189 International Computer Schience Institute
195 \begin_layout Standard
208 \begin_layout BeginFrame
212 \begin_layout Standard
213 \begin_inset LatexCommand \tableofcontents{}
221 \begin_layout Standard
231 \begin_layout EndFrame
235 \begin_layout Standard
239 \begin_layout Standard
241 % Show the table of contents at the beginning
244 \begin_layout Standard
248 \begin_layout Standard
250 % of every subsection.
253 \begin_layout Standard
257 \begin_layout Standard
264 \begin_layout Standard
268 \begin_layout Standard
275 \begin_layout Standard
279 \begin_layout Standard
286 \begin_layout Standard
290 \begin_layout Standard
294 tableofcontents[current,currentsubsection]
297 \begin_layout Standard
301 \begin_layout Standard
306 \begin_layout Standard
310 \begin_layout Standard
320 \begin_layout Section
324 \begin_layout Subsection
325 What are Tournaments?
328 \begin_layout BeginFrame
329 Tournaments Consist of Jousts Between Knights
332 \begin_layout Columns
341 \begin_layout Standard
345 \begin_layout Standard
349 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
352 \begin_layout Standard
356 \begin_layout Standard
360 pgfnodebox{A}[virtual]{
364 pgfuseimage{knight1}}{2pt}{2pt}
367 \begin_layout Standard
371 \begin_layout Standard
375 pgfnodebox{B}[virtual]{
379 pgfuseimage{knight2}}{2pt}{2pt}
382 \begin_layout Standard
386 \begin_layout Standard
390 pgfnodebox{C}[virtual]{
394 pgfuseimage{knight3}}{2pt}{2pt}
397 \begin_layout Standard
401 \begin_layout Standard
405 pgfnodebox{D}[virtual]{
409 pgfuseimage{knight4}}{2pt}{2pt}
412 \begin_layout Standard
416 \begin_layout Standard
420 \begin_layout Standard
424 \begin_layout Standard
431 \begin_layout Standard
435 \begin_layout Standard
446 \begin_layout Standard
450 \begin_layout Standard
457 \begin_layout Standard
461 \begin_layout Standard
465 pgfsetlinewidth{0.6pt}
468 \begin_layout Standard
472 \begin_layout Standard
476 pgfnodeconnline{A}{B}
479 \begin_layout Standard
483 \begin_layout Standard
487 pgfnodeconnline{A}{C}
490 \begin_layout Standard
494 \begin_layout Standard
498 pgfnodeconnline{D}{A}
501 \begin_layout Standard
505 \begin_layout Standard
509 pgfnodeconnline{C}{B}
512 \begin_layout Standard
516 \begin_layout Standard
520 pgfnodeconnline{B}{D}
523 \begin_layout Standard
527 \begin_layout Standard
531 pgfnodeconnline{C}{D}}
534 \begin_layout Standard
538 \begin_layout Standard
558 \begin_layout Standard
560 {What is a Tournament?}
569 \begin_layout Itemize
573 \begin_layout Standard
583 \begin_layout Itemize
587 \begin_layout Standard
594 Every pair has a joust.
597 \begin_layout Itemize
601 \begin_layout Standard
608 In every joust one knight wins.
613 \begin_layout BeginFrame
614 Tournaments are Complete Directed Graphs
617 \begin_layout Columns
626 \begin_layout Standard
630 \begin_layout Standard
634 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
637 \begin_layout Standard
641 \begin_layout Standard
648 \begin_layout Standard
652 \begin_layout Standard
656 pgfsetlinewidth{0.6pt}
659 \begin_layout Standard
663 \begin_layout Standard
672 \begin_layout Standard
676 \begin_layout Standard
685 \begin_layout Standard
689 \begin_layout Standard
698 \begin_layout Standard
702 \begin_layout Standard
711 \begin_layout Standard
715 \begin_layout Standard
719 \begin_layout Standard
723 \begin_layout Standard
730 \begin_layout Standard
734 \begin_layout Standard
742 pgfbox[center,center]{$v_2$}}
745 \begin_layout Standard
749 \begin_layout Standard
757 pgfbox[center,center]{$v_3$}}
760 \begin_layout Standard
764 \begin_layout Standard
772 pgfbox[center,center]{$v_4$}}
775 \begin_layout Standard
779 \begin_layout Standard
787 pgfbox[center,center]{$v_1$}}
790 \begin_layout Standard
794 \begin_layout Standard
798 \begin_layout Standard
802 \begin_layout Standard
809 \begin_layout Standard
813 \begin_layout Standard
822 \begin_layout Standard
826 \begin_layout Standard
830 pgfnodesetsepstart{2pt}
833 \begin_layout Standard
837 \begin_layout Standard
841 pgfnodesetsepend{4pt}
844 \begin_layout Standard
848 \begin_layout Standard
852 pgfnodeconnline{A}{B}
855 \begin_layout Standard
859 \begin_layout Standard
863 pgfnodeconnline{A}{C}
866 \begin_layout Standard
870 \begin_layout Standard
874 pgfnodeconnline{D}{A}
877 \begin_layout Standard
881 \begin_layout Standard
885 pgfnodeconnline{C}{B}
888 \begin_layout Standard
892 \begin_layout Standard
896 pgfnodeconnline{B}{D}
899 \begin_layout Standard
903 \begin_layout Standard
907 pgfnodeconnline{D}{C}
910 \begin_layout Standard
914 \begin_layout Standard
930 \begin_layout Definition
934 \begin_layout Standard
949 \begin_layout Enumerate
953 \begin_layout Enumerate
954 with exactly one edge between
956 any two different vertices.
961 \begin_layout BeginFrame
965 \begin_layout Standard
972 Tournaments Arise Naturally in Different Situations
975 \begin_layout ExampleBlock
979 \begin_layout Standard
981 {Applicatins in Ordering Theory}
990 \begin_layout Standard
991 Elements in a set need to be sorted.
994 The comparison relation may be cyclic, however.
998 \begin_layout Separator
1002 \begin_layout ExampleBlock
1006 \begin_layout Standard
1008 {Applications in Sociology}
1017 \begin_layout Standard
1018 Several candidates apply for a position.
1020 Reviewers decide for any two candidates
1026 \begin_layout Separator
1030 \begin_layout ExampleBlock
1034 \begin_layout Standard
1036 {Applications in Structural Complexity Theory}
1045 \begin_layout Standard
1047 \begin_inset Formula $L$
1050 is given and a selector function
1051 \begin_inset Formula $f$
1056 It chooses from any two words the one more likely to be in
1057 \begin_inset Formula $f$
1064 \begin_layout Subsection
1065 What Does ``Finding Paths'' Mean?
1068 \begin_layout BeginFrame
1069 ``Finding Paths'' is Ambiguous
1076 \begin_layout Standard
1086 par{}% because LyX inserts superfluous paragraphs
1089 \begin_layout Standard
1093 \begin_layout Standard
1097 only<1>{Path Finding Problems}
1102 \begin_layout Standard
1106 \begin_layout Standard
1117 \begin_layout Standard
1121 \begin_layout Standard
1125 only<4-5>{the Construction Problem}
1130 \begin_layout Standard
1134 \begin_layout Standard
1138 only<6-7>{the Optimization Problem}
1143 \begin_layout Standard
1147 \begin_layout Standard
1158 \begin_layout Standard
1162 \begin_layout Standard
1166 only<10->{the Approximation Problem}}
1175 \begin_layout Itemize
1181 \begin_inset Formula $G=(V,E)$
1189 \begin_inset Formula $s\in V$
1197 \begin_inset Formula $t\in V$
1203 \begin_layout Itemize
1207 \begin_layout Standard
1209 <only@-9| visible@8->
1220 \begin_inset Formula $d$
1227 \begin_layout Standard
1239 \begin_layout Itemize
1243 \begin_layout Standard
1255 \begin_inset Formula $r>1$
1262 \begin_layout Standard
1266 \begin_layout Standard
1278 \begin_layout Overprint
1283 \begin_layout Standard
1287 \begin_layout Standard
1291 onslide<1,3,5,7,9,11-12>
1299 \begin_layout Columns
1303 \begin_layout Standard
1314 \begin_layout Standard
1318 \begin_layout Standard
1336 \begin_layout ExampleBlock
1340 \begin_layout Standard
1351 \begin_layout Standard
1355 \begin_layout Standard
1359 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1362 \begin_layout Standard
1366 \begin_layout Standard
1370 color{beamerexample}
1373 \begin_layout Standard
1377 \begin_layout Standard
1381 pgfsetlinewidth{0.6pt}
1384 \begin_layout Standard
1388 \begin_layout Standard
1397 \begin_layout Standard
1401 \begin_layout Standard
1410 \begin_layout Standard
1414 \begin_layout Standard
1423 \begin_layout Standard
1427 \begin_layout Standard
1436 \begin_layout Standard
1440 \begin_layout Standard
1444 \begin_layout Standard
1448 \begin_layout Standard
1455 \begin_layout Standard
1459 \begin_layout Standard
1467 pgfbox[center,center]{$t$}}
1470 \begin_layout Standard
1474 \begin_layout Standard
1482 pgfbox[center,center]{$s$}}
1485 \begin_layout Standard
1489 \begin_layout Standard
1493 \begin_layout Standard
1497 \begin_layout Standard
1501 color{beamerexample}
1504 \begin_layout Standard
1508 \begin_layout Standard
1517 \begin_layout Standard
1521 \begin_layout Standard
1525 pgfnodesetsepstart{2pt}
1528 \begin_layout Standard
1532 \begin_layout Standard
1536 pgfnodesetsepend{4pt}
1539 \begin_layout Standard
1543 \begin_layout Standard
1547 pgfnodeconnline{A}{B}
1550 \begin_layout Standard
1554 \begin_layout Standard
1558 pgfnodeconnline{A}{C}
1561 \begin_layout Standard
1565 \begin_layout Standard
1569 pgfnodeconnline{D}{A}
1572 \begin_layout Standard
1576 \begin_layout Standard
1580 pgfnodeconnline{C}{B}
1583 \begin_layout Standard
1587 \begin_layout Standard
1591 pgfnodeconnline{B}{D}
1594 \begin_layout Standard
1598 \begin_layout Standard
1602 pgfnodeconnline{D}{C}
1605 \begin_layout Standard
1609 \begin_layout Standard
1613 \begin_layout Standard
1617 \begin_layout Standard
1627 pgfbox[left,center]{, $d=2$}}}
1630 \begin_layout Standard
1634 \begin_layout Standard
1644 pgfbox[left,center]{, $r=1.5$}}}
1647 \begin_layout Standard
1651 \begin_layout Standard
1661 pgfbox[left,center]{, $r=1.25$}}}
1664 \begin_layout Standard
1668 \begin_layout Standard
1681 \begin_layout Standard
1685 \begin_layout Standard
1699 \begin_layout ExampleBlock
1703 \begin_layout Standard
1705 <only@3->{Example Output}
1714 \begin_layout Standard
1718 \begin_layout Standard
1722 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1725 \begin_layout Standard
1729 \begin_layout Standard
1736 \begin_layout Standard
1740 \begin_layout Standard
1744 color{beamerexample}
1747 \begin_layout Standard
1751 \begin_layout Standard
1755 pgfsetlinewidth{0.6pt}
1758 \begin_layout Standard
1762 \begin_layout Standard
1771 \begin_layout Standard
1775 \begin_layout Standard
1784 \begin_layout Standard
1788 \begin_layout Standard
1797 \begin_layout Standard
1801 \begin_layout Standard
1810 \begin_layout Standard
1814 \begin_layout Standard
1818 \begin_layout Standard
1822 \begin_layout Standard
1829 \begin_layout Standard
1833 \begin_layout Standard
1841 pgfbox[center,center]{$t$}}
1844 \begin_layout Standard
1848 \begin_layout Standard
1856 pgfbox[center,center]{$s$}}
1859 \begin_layout Standard
1863 \begin_layout Standard
1867 \begin_layout Standard
1871 \begin_layout Standard
1875 color{beamerexample}
1878 \begin_layout Standard
1882 \begin_layout Standard
1891 \begin_layout Standard
1895 \begin_layout Standard
1899 pgfnodesetsepstart{2pt}
1902 \begin_layout Standard
1906 \begin_layout Standard
1910 pgfnodesetsepend{4pt}
1913 \begin_layout Standard
1917 \begin_layout Standard
1922 \begin_layout Standard
1926 \begin_layout Standard
1932 pgfnodeconnline{A}{B}}
1935 \begin_layout Standard
1939 \begin_layout Standard
1945 pgfnodeconnline{A}{C}}
1948 \begin_layout Standard
1952 \begin_layout Standard
1958 pgfnodeconnline{D}{A}}
1961 \begin_layout Standard
1965 \begin_layout Standard
1971 pgfnodeconnline{C}{B}}
1974 \begin_layout Standard
1978 \begin_layout Standard
1982 pgfnodeconnline{B}{D}
1985 \begin_layout Standard
1989 \begin_layout Standard
1993 pgfnodeconnline{D}{C}
1996 \begin_layout Standard
2000 \begin_layout Standard
2005 \begin_layout Standard
2009 \begin_layout Standard
2019 pgfbox[left,center]{
2024 \begin_layout Standard
2028 \begin_layout Standard
2042 \begin_layout Standard
2046 \begin_layout Standard
2062 \begin_layout Standard
2064 {Variants of Path Finding Problems}
2073 \begin_layout Standard
2077 \begin_layout Standard
2081 usedescriptionitemofwidthas{Approximation Problem:}
2089 \begin_layout Description
2090 Reachability\InsetSpace ~
2095 \begin_layout Standard
2102 Is there a path from
2103 \begin_inset Formula $s$
2108 \begin_inset Formula $t$
2114 \begin_layout Description
2115 Construction\InsetSpace ~
2120 \begin_layout Standard
2127 Construct a path from
2128 \begin_inset Formula $s$
2133 \begin_inset Formula $t$
2139 \begin_layout Description
2140 Optimization\InsetSpace ~
2145 \begin_layout Standard
2152 Construct a shortest path from
2153 \begin_inset Formula $s$
2158 \begin_inset Formula $t$
2164 \begin_layout Description
2165 Distance\InsetSpace ~
2170 \begin_layout Standard
2178 \begin_inset Formula $s$
2183 \begin_inset Formula $t$
2186 at most\InsetSpace ~
2188 \begin_inset Formula $d$
2194 \begin_layout Description
2195 Approximation\InsetSpace ~
2200 \begin_layout Standard
2207 Construct a path from
2208 \begin_inset Formula $s$
2213 \begin_inset Formula $t$
2218 approximately their distance.
2223 \begin_layout Section
2227 \begin_layout Subsection
2228 Standard Complexity Classes
2231 \begin_layout Standard
2235 \begin_layout Standard
2239 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2241 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2250 \begin_layout BeginFrame
2251 The Classes L and NL are Defined via
2253 Logspace Turing Machines
2256 \begin_layout Standard
2260 \begin_layout Standard
2264 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2267 \begin_layout Standard
2271 \begin_layout Standard
2279 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2282 \begin_layout Standard
2286 \begin_layout Standard
2293 \begin_layout Standard
2297 \begin_layout Standard
2305 tape{}{output tape (write only)}{10690836937182}}}
2308 \begin_layout Standard
2312 \begin_layout Standard
2319 \begin_layout Standard
2323 \begin_layout Standard
2331 shorttape{work tape (read/write), $O(
2333 log n)$ symbols}{}{42}}
2336 \begin_layout Standard
2340 \begin_layout Standard
2348 pgfbox[center,center]{
2350 pgfuseimage{computer}}}
2353 \begin_layout Standard
2357 \begin_layout Standard
2362 \begin_layout Standard
2366 \begin_layout Standard
2370 pgfsetlinewidth{0.6pt}
2373 \begin_layout Standard
2377 \begin_layout Standard
2381 \begin_layout Standard
2385 \begin_layout Standard
2392 \begin_layout Standard
2396 \begin_layout Standard
2405 \begin_layout Standard
2409 \begin_layout Standard
2413 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2416 \begin_layout Standard
2420 \begin_layout Standard
2426 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2429 \begin_layout Standard
2433 \begin_layout Standard
2439 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2442 \begin_layout Standard
2446 \begin_layout Standard
2458 \begin_layout BeginFrame
2459 Logspace Turing Machines Are Quite Powerful
2466 \begin_layout Standard
2468 {Deterministic logspace machines can compute}
2477 \begin_layout Itemize
2478 addition, multiplication, and even division
2481 \begin_layout Itemize
2482 reductions used in completeness proofs,
2485 \begin_layout Itemize
2486 reachability in forests.
2498 \begin_layout Standard
2500 {Non-deterministic logspace machines can compute}
2509 \begin_layout Itemize
2510 reachability in graphs,
2513 \begin_layout Itemize
2514 non-reachability in graphs,
2517 \begin_layout Itemize
2518 satisfiability with two literals per clause.
2522 \begin_layout BeginFrame
2526 \begin_layout Standard
2528 <1>[label=hierarchy]
2533 The Complexity Class Hierarchy
2536 \begin_layout Standard
2540 \begin_layout Standard
2544 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2547 \begin_layout Standard
2551 \begin_layout Standard
2555 pgfsetlinewidth{0.8pt}
2558 \begin_layout Standard
2562 \begin_layout Standard
2571 \begin_layout Standard
2575 \begin_layout Standard
2579 pgfsetdash{{2pt}}{0pt}
2582 \begin_layout Standard
2586 \begin_layout Standard
2594 Class{NC}^2$}{black!50!structure}{2}}
2597 \begin_layout Standard
2601 \begin_layout Standard
2607 Class{NL}$}{black!50!structure}{3}
2610 \begin_layout Standard
2614 \begin_layout Standard
2620 Class{L}$}{black!50!structure}{4}
2623 \begin_layout Standard
2627 \begin_layout Standard
2639 Class{NC}^1}$}{black!50!structure}{5}}
2642 \begin_layout Standard
2646 \begin_layout Standard
2653 \begin_layout Standard
2657 \begin_layout Standard
2669 Class{AC}^0}$}{black}{6}}
2672 \begin_layout Standard
2676 \begin_layout Standard
2680 \begin_layout Standard
2684 \begin_layout Standard
2688 pgfsetlinewidth{1.0pt}
2691 \begin_layout Standard
2695 \begin_layout Standard
2702 \begin_layout Standard
2706 \begin_layout Standard
2710 pgfxyline(-5,0)(5,0)
2713 \begin_layout Standard
2717 \begin_layout Standard
2721 \begin_layout Standard
2725 \begin_layout Standard
2736 \begin_layout Standard
2740 \begin_layout Standard
2750 operatorname{forest}}$}}
2753 \begin_layout Standard
2757 \begin_layout Standard
2761 \begin_layout Standard
2765 \begin_layout Standard
2776 \begin_layout Standard
2780 \begin_layout Standard
2799 \begin_layout Standard
2803 \begin_layout Standard
2822 \begin_layout Standard
2826 \begin_layout Standard
2839 \begin_layout Standard
2843 \begin_layout Standard
2851 operatorname{forest}}$,}
2856 \begin_layout Standard
2860 \begin_layout Standard
2868 operatorname{forest}}$,}
2873 \begin_layout Standard
2877 \begin_layout Standard
2885 operatorname{path}}$,}
2890 \begin_layout Standard
2894 \begin_layout Standard
2902 operatorname{path}}$}}}}
2905 \begin_layout Standard
2909 \begin_layout Standard
2919 operatorname{tourn}}$}}
2922 \begin_layout Standard
2926 \begin_layout Standard
2939 \begin_layout Standard
2943 \begin_layout Standard
2951 operatorname{tourn}}$,}
2956 \begin_layout Standard
2960 \begin_layout Standard
2971 \begin_layout Standard
2975 \begin_layout Standard
2984 \begin_layout Standard
2988 \begin_layout Standard
2994 pgfsetdash{{1pt}}{0pt}
3000 operatorname{tourn}}$''}}
3003 \begin_layout Standard
3007 \begin_layout Standard
3019 \begin_layout BeginFrame
3020 The Circuit Complexity Classes AC
3021 \begin_inset Formula $^{0}$
3025 \begin_inset Formula $^{1}$
3029 \begin_inset Formula $^{2}$
3034 Limit the Circuit Depth
3037 \begin_layout Standard
3041 \begin_layout Standard
3050 \begin_layout Standard
3054 \begin_layout Standard
3066 \begin_layout Columns
3070 \begin_layout Standard
3081 \begin_layout Column
3089 \begin_layout Standard
3097 \begin_inset Formula $\Class{AC}^{0}$
3104 \begin_layout Standard
3115 \begin_layout Itemize
3116 \begin_inset Formula $O(1)$
3122 \begin_layout Itemize
3127 \begin_layout Examples
3132 \begin_layout Itemize
3133 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3139 \begin_layout Itemize
3140 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3151 \begin_layout Column
3159 \begin_layout Standard
3167 \begin_inset Formula $\Class{NC}^{1}$
3174 \begin_layout Standard
3185 \begin_layout Itemize
3186 \begin_inset Formula $O(\log n)$
3192 \begin_layout Itemize
3197 \begin_layout Examples
3202 \begin_layout Itemize
3203 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3209 \begin_layout Itemize
3210 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3216 \begin_layout Itemize
3217 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3228 \begin_layout Column
3236 \begin_layout Standard
3244 \begin_inset Formula $\Class{NC}^{2}$
3251 \begin_layout Standard
3262 \begin_layout Itemize
3263 \begin_inset Formula $O(\log^{2}n)$
3269 \begin_layout Itemize
3274 \begin_layout Examples
3279 \begin_layout Itemize
3280 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3288 \begin_layout AgainFrame
3292 \begin_layout Standard
3302 \begin_layout Subsection
3303 Standard Complexity Results on Finding Paths
3306 \begin_layout BeginFrame
3307 All Variants of Finding Paths in Directed Graphs
3309 Are Equally Difficult
3313 \begin_inset Formula $\Lang{reach}$
3317 \begin_inset Formula $\Lang{distance}$
3321 \begin_inset Formula $\Class{NL}$
3332 \begin_layout Corollary
3333 For directed graphs, we can solve
3337 \begin_layout Itemize
3338 the reachability problem in logspace iff
3339 \begin_inset Formula $\Class{L}=\Class{NL}$
3345 \begin_layout Itemize
3346 the construction problem in logspace iff
3347 \begin_inset Formula $\Class{L}=\Class{NL}$
3353 \begin_layout Itemize
3354 the optimization problem in logspace iff
3355 \begin_inset Formula $\Class{L}=\Class{NL}$
3361 \begin_layout Itemize
3362 the approximation problem in logspace iff
3363 \begin_inset Formula $\Class{L}=\Class{NL}$
3370 \begin_layout AgainFrame
3374 \begin_layout Standard
3384 \begin_layout BeginFrame
3385 FindingPaths in Forests and Directed Paths is Easy,
3391 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3395 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3399 \begin_inset Formula $\Class{L}$
3405 \begin_layout Separator
3410 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3414 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3418 \begin_inset Formula $\Class{L}$
3424 \begin_layout AgainFrame
3428 \begin_layout Standard
3438 \begin_layout Section
3439 Finding Paths in Tournaments
3442 \begin_layout Subsection
3443 Complexity of: Does a Path Exist?
3446 \begin_layout BeginFrame
3447 Definition of the Tournament Reachability Problem
3450 \begin_layout Definition
3454 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3460 \begin_inset Formula $(T,s,t)$
3467 \begin_layout Enumerate
3468 \begin_inset Formula $T=(V,E)$
3474 \begin_layout Enumerate
3475 there exists a path from\InsetSpace ~
3477 \begin_inset Formula $s$
3482 \begin_inset Formula $t$
3489 \begin_layout BeginFrame
3490 The Tournament Reachability Problem is Very Easy
3493 \begin_layout Theorem
3494 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3504 \begin_layout AlertBlock
3508 \begin_layout Standard
3519 \begin_layout Itemize
3521 \begin_inset Quotes eld
3525 \begin_inset Quotes erd
3529 \begin_inset Formula $\Lang{reach}$
3533 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3539 \begin_layout Itemize
3540 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3547 \begin_layout AgainFrame
3551 \begin_layout Standard
3561 \begin_layout Subsection
3562 Complexity of: Construct a Shortest Path
3565 \begin_layout BeginFrame
3566 Finding a Shortest Path Is as Difficult as
3568 the Distance Problem
3571 \begin_layout Definition
3575 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3581 \begin_inset Formula $(T,s,t,d)$
3588 \begin_layout Enumerate
3589 \begin_inset Formula $T=(V,E)$
3592 is a tournament in which
3595 \begin_layout Enumerate
3597 \begin_inset Formula $s$
3602 \begin_inset Formula $t$
3605 is at most\InsetSpace ~
3607 \begin_inset Formula $d$
3614 \begin_layout BeginFrame
3615 The Tournament Distance Problem is Hard
3618 \begin_layout Theorem
3619 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3623 \begin_inset Formula $\Class{NL}$
3629 \begin_layout Standard
3636 \begin_layout Standard
3640 hyperlink{hierarchy<6>}{
3642 beamerskipbutton{Skip Proof}}
3654 \begin_layout Corollary
3655 Shortest path in tournaments can be constructed
3657 in logarithmic space, iff
3659 \begin_inset Formula $\Class{L}=\Class{NL}$
3669 \begin_layout Corollary
3670 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3676 \begin_layout BeginFrame
3678 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3684 \begin_layout Standard
3688 \begin_layout Standard
3700 \begin_layout Columns
3704 \begin_layout Standard
3715 \begin_layout Column
3719 \begin_layout Standard
3723 \begin_layout Standard
3741 \begin_layout Standard
3749 \begin_inset Formula $\Lang{reach}$
3753 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3760 \begin_layout Standard
3771 \begin_layout Enumerate
3775 \begin_layout Standard
3783 \begin_inset Formula $(G,s,t)$
3787 \begin_inset Formula $\Lang{reach}$
3793 \begin_layout Enumerate
3797 \begin_layout Standard
3805 \begin_inset Formula $G$
3809 \begin_inset Formula $G'$
3815 \begin_layout Enumerate
3819 \begin_layout Standard
3829 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3836 \begin_layout Separator
3844 \begin_layout Standard
3855 \begin_layout Standard
3866 \begin_layout Standard
3877 \begin_layout Enumerate
3881 \begin_layout Standard
3888 A path in\InsetSpace ~
3890 \begin_inset Formula $G$
3895 a length-3 path in\InsetSpace ~
3897 \begin_inset Formula $G'$
3903 \begin_layout Enumerate
3907 \begin_layout Standard
3914 A length-3 path in\InsetSpace ~
3916 \begin_inset Formula $G'$
3921 a path in\InsetSpace ~
3923 \begin_inset Formula $G'$
3930 \begin_layout Column
3934 \begin_layout Example
3938 \begin_layout Standard
3942 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3945 \begin_layout Standard
3949 \begin_layout Standard
3953 color{beamerexample}
3956 \begin_layout Standard
3960 \begin_layout Standard
3964 pgfsetlinewidth{0.6pt}
3967 \begin_layout Standard
3971 \begin_layout Standard
3980 \begin_layout Standard
3984 \begin_layout Standard
3993 \begin_layout Standard
3997 \begin_layout Standard
4006 \begin_layout Standard
4010 \begin_layout Standard
4019 \begin_layout Standard
4023 \begin_layout Standard
4027 \begin_layout Standard
4031 \begin_layout Standard
4038 \begin_layout Standard
4042 \begin_layout Standard
4050 pgfbox[center,center]{$s$}}
4053 \begin_layout Standard
4057 \begin_layout Standard
4065 pgfbox[center,center]{$t$}}
4068 \begin_layout Standard
4072 \begin_layout Standard
4076 \begin_layout Standard
4080 \begin_layout Standard
4084 color{beamerexample}
4087 \begin_layout Standard
4091 \begin_layout Standard
4100 \begin_layout Standard
4104 \begin_layout Standard
4108 pgfnodesetsepstart{2pt}
4111 \begin_layout Standard
4115 \begin_layout Standard
4119 pgfnodesetsepend{2pt}
4122 \begin_layout Standard
4126 \begin_layout Standard
4132 pgfnodeconnline{B}{A}}
4135 \begin_layout Standard
4139 \begin_layout Standard
4145 pgfnodeconnline{B}{C}}
4148 \begin_layout Standard
4152 \begin_layout Standard
4158 pgfnodeconnline{C}{D}}
4161 \begin_layout Standard
4165 \begin_layout Standard
4171 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4174 \begin_layout Standard
4178 \begin_layout Standard
4183 \begin_layout Standard
4187 \begin_layout Standard
4195 pgfbox[left,center]{$G
4200 \begin_layout Standard
4204 \begin_layout Standard
4208 \begin_layout Standard
4212 \begin_layout Standard
4219 \begin_layout Standard
4223 \begin_layout Standard
4231 pgfbox[left,center]{$G'
4236 \begin_layout Standard
4240 \begin_layout Standard
4249 \begin_layout Standard
4253 \begin_layout Standard
4262 \begin_layout Standard
4266 \begin_layout Standard
4275 \begin_layout Standard
4279 \begin_layout Standard
4288 \begin_layout Standard
4292 \begin_layout Standard
4296 \begin_layout Standard
4300 \begin_layout Standard
4309 \begin_layout Standard
4313 \begin_layout Standard
4322 \begin_layout Standard
4326 \begin_layout Standard
4335 \begin_layout Standard
4339 \begin_layout Standard
4348 \begin_layout Standard
4352 \begin_layout Standard
4361 \begin_layout Standard
4365 \begin_layout Standard
4374 \begin_layout Standard
4378 \begin_layout Standard
4387 \begin_layout Standard
4391 \begin_layout Standard
4400 \begin_layout Standard
4404 \begin_layout Standard
4413 \begin_layout Standard
4417 \begin_layout Standard
4426 \begin_layout Standard
4430 \begin_layout Standard
4439 \begin_layout Standard
4443 \begin_layout Standard
4452 \begin_layout Standard
4456 \begin_layout Standard
4463 \begin_layout Standard
4467 \begin_layout Standard
4475 pgfbox[center,center]{$s'$}}
4478 \begin_layout Standard
4482 \begin_layout Standard
4490 pgfbox[center,center]{$t'$}}
4493 \begin_layout Standard
4497 \begin_layout Standard
4502 \begin_layout Standard
4506 \begin_layout Standard
4511 \begin_layout Standard
4515 \begin_layout Standard
4522 \begin_layout Standard
4526 \begin_layout Standard
4530 pgfsetlinewidth{0.4pt}
4533 \begin_layout Standard
4537 \begin_layout Standard
4541 color{beamerexample!25!averagebackgroundcolor}
4544 \begin_layout Standard
4548 \begin_layout Standard
4552 pgfnodeconnline{A2}{C1}
4555 \begin_layout Standard
4559 \begin_layout Standard
4563 pgfnodeconnline{A2}{D1}
4566 \begin_layout Standard
4570 \begin_layout Standard
4574 pgfnodeconnline{B2}{A1}
4577 \begin_layout Standard
4581 \begin_layout Standard
4585 pgfnodeconnline{B2}{C1}
4588 \begin_layout Standard
4592 \begin_layout Standard
4596 pgfnodeconnline{B2}{D1}
4599 \begin_layout Standard
4603 \begin_layout Standard
4607 pgfnodeconnline{C2}{D1}
4610 \begin_layout Standard
4614 \begin_layout Standard
4618 pgfnodeconnline{D2}{A1}
4621 \begin_layout Standard
4625 \begin_layout Standard
4629 pgfnodeconnline{D2}{B1}
4632 \begin_layout Standard
4636 \begin_layout Standard
4640 pgfnodeconnline{A3}{C2}
4643 \begin_layout Standard
4647 \begin_layout Standard
4651 pgfnodeconnline{A3}{D2}
4654 \begin_layout Standard
4658 \begin_layout Standard
4662 pgfnodeconnline{B3}{A2}
4665 \begin_layout Standard
4669 \begin_layout Standard
4673 pgfnodeconnline{B3}{C2}
4676 \begin_layout Standard
4680 \begin_layout Standard
4684 pgfnodeconnline{B3}{D2}
4687 \begin_layout Standard
4691 \begin_layout Standard
4695 pgfnodeconnline{C3}{D2}
4698 \begin_layout Standard
4702 \begin_layout Standard
4706 pgfnodeconnline{D3}{A2}
4709 \begin_layout Standard
4713 \begin_layout Standard
4717 pgfnodeconnline{D3}{B2}
4720 \begin_layout Standard
4724 \begin_layout Standard
4728 pgfnodeconnline{A4}{C3}
4731 \begin_layout Standard
4735 \begin_layout Standard
4739 pgfnodeconnline{A4}{D3}
4742 \begin_layout Standard
4746 \begin_layout Standard
4750 pgfnodeconnline{B4}{A3}
4753 \begin_layout Standard
4757 \begin_layout Standard
4761 pgfnodeconnline{B4}{C3}
4764 \begin_layout Standard
4768 \begin_layout Standard
4772 pgfnodeconnline{B4}{D3}
4775 \begin_layout Standard
4779 \begin_layout Standard
4783 pgfnodeconnline{C4}{D3}
4786 \begin_layout Standard
4790 \begin_layout Standard
4794 pgfnodeconnline{D4}{A3}
4797 \begin_layout Standard
4801 \begin_layout Standard
4805 pgfnodeconnline{D4}{B3}
4808 \begin_layout Standard
4812 \begin_layout Standard
4816 \begin_layout Standard
4820 \begin_layout Standard
4829 \begin_layout Standard
4833 \begin_layout Standard
4837 pgfnodeconnline{A1}{B1}
4840 \begin_layout Standard
4844 \begin_layout Standard
4848 pgfnodeconnline{B1}{C1}
4851 \begin_layout Standard
4855 \begin_layout Standard
4859 pgfnodeconnline{C1}{D1}
4862 \begin_layout Standard
4866 \begin_layout Standard
4870 pgfnodeconnline{A2}{B2}
4873 \begin_layout Standard
4877 \begin_layout Standard
4881 pgfnodeconnline{B2}{C2}
4884 \begin_layout Standard
4888 \begin_layout Standard
4892 pgfnodeconnline{C2}{D2}
4895 \begin_layout Standard
4899 \begin_layout Standard
4903 pgfnodeconnline{A3}{B3}
4906 \begin_layout Standard
4910 \begin_layout Standard
4914 pgfnodeconnline{B3}{C3}
4917 \begin_layout Standard
4921 \begin_layout Standard
4925 pgfnodeconnline{C3}{D3}
4928 \begin_layout Standard
4932 \begin_layout Standard
4936 pgfnodeconnline{A4}{B4}
4939 \begin_layout Standard
4943 \begin_layout Standard
4947 pgfnodeconnline{B4}{C4}
4950 \begin_layout Standard
4954 \begin_layout Standard
4958 pgfnodeconnline{C4}{D4}
4961 \begin_layout Standard
4965 \begin_layout Standard
4969 \begin_layout Standard
4973 \begin_layout Standard
4980 \begin_layout Standard
4984 \begin_layout Standard
4988 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
4991 \begin_layout Standard
4995 \begin_layout Standard
4999 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
5002 \begin_layout Standard
5006 \begin_layout Standard
5010 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
5013 \begin_layout Standard
5017 \begin_layout Standard
5021 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
5024 \begin_layout Standard
5028 \begin_layout Standard
5032 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
5035 \begin_layout Standard
5039 \begin_layout Standard
5043 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
5046 \begin_layout Standard
5050 \begin_layout Standard
5054 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
5057 \begin_layout Standard
5061 \begin_layout Standard
5065 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
5068 \begin_layout Standard
5072 \begin_layout Standard
5076 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
5079 \begin_layout Standard
5083 \begin_layout Standard
5087 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
5090 \begin_layout Standard
5094 \begin_layout Standard
5098 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
5101 \begin_layout Standard
5105 \begin_layout Standard
5109 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
5112 \begin_layout Standard
5116 \begin_layout Standard
5120 color{beamerexample}
5123 \begin_layout Standard
5127 \begin_layout Standard
5131 pgfsetlinewidth{0.6pt}
5134 \begin_layout Standard
5138 \begin_layout Standard
5143 \begin_layout Standard
5147 \begin_layout Standard
5151 \begin_layout Standard
5155 \begin_layout Standard
5162 \begin_layout Standard
5166 \begin_layout Standard
5173 \begin_layout Standard
5177 \begin_layout Standard
5181 pgfnodeconnline{B1}{A2}
5184 \begin_layout Standard
5188 \begin_layout Standard
5192 pgfnodeconnline{B2}{A3}
5195 \begin_layout Standard
5199 \begin_layout Standard
5203 pgfnodeconnline{B3}{A4}
5206 \begin_layout Standard
5210 \begin_layout Standard
5215 \begin_layout Standard
5219 \begin_layout Standard
5223 \begin_layout Standard
5227 \begin_layout Standard
5234 \begin_layout Standard
5238 \begin_layout Standard
5245 \begin_layout Standard
5249 \begin_layout Standard
5253 pgfnodeconnline{B1}{C2}
5256 \begin_layout Standard
5260 \begin_layout Standard
5264 pgfnodeconnline{B2}{C3}
5267 \begin_layout Standard
5271 \begin_layout Standard
5275 pgfnodeconnline{B3}{C4}
5278 \begin_layout Standard
5282 \begin_layout Standard
5287 \begin_layout Standard
5291 \begin_layout Standard
5296 \begin_layout Standard
5300 \begin_layout Standard
5307 \begin_layout Standard
5311 \begin_layout Standard
5318 \begin_layout Standard
5322 \begin_layout Standard
5326 pgfnodeconnline{C1}{D2}
5329 \begin_layout Standard
5333 \begin_layout Standard
5339 pgfnodeconnline{C2}{D3}}
5342 \begin_layout Standard
5346 \begin_layout Standard
5352 pgfnodeconnline{C3}{D4}}
5355 \begin_layout Standard
5359 \begin_layout Standard
5364 \begin_layout Standard
5368 \begin_layout Standard
5373 \begin_layout Standard
5377 \begin_layout Standard
5384 \begin_layout Standard
5388 \begin_layout Standard
5395 \begin_layout Standard
5399 \begin_layout Standard
5405 pgfnodeconnline{A1}{C2}}
5408 \begin_layout Standard
5412 \begin_layout Standard
5418 pgfnodeconnline{A2}{C3}}
5421 \begin_layout Standard
5425 \begin_layout Standard
5429 pgfnodeconnline{A3}{C4}
5432 \begin_layout Standard
5436 \begin_layout Standard
5441 \begin_layout Standard
5445 \begin_layout Standard
5449 \begin_layout Standard
5453 \begin_layout Standard
5460 \begin_layout Standard
5464 \begin_layout Standard
5471 \begin_layout Standard
5475 \begin_layout Standard
5481 pgfnodeconnline{A1}{A2}}
5484 \begin_layout Standard
5488 \begin_layout Standard
5492 pgfnodeconnline{A2}{A3}
5495 \begin_layout Standard
5499 \begin_layout Standard
5503 pgfnodeconnline{A3}{A4}
5506 \begin_layout Standard
5510 \begin_layout Standard
5514 pgfnodeconnline{B1}{B2}
5517 \begin_layout Standard
5521 \begin_layout Standard
5525 pgfnodeconnline{B2}{B3}
5528 \begin_layout Standard
5532 \begin_layout Standard
5536 pgfnodeconnline{B3}{B4}
5539 \begin_layout Standard
5543 \begin_layout Standard
5547 pgfnodeconnline{C1}{C2}
5550 \begin_layout Standard
5554 \begin_layout Standard
5558 pgfnodeconnline{C2}{C3}
5561 \begin_layout Standard
5565 \begin_layout Standard
5569 pgfnodeconnline{C3}{C4}
5572 \begin_layout Standard
5576 \begin_layout Standard
5580 pgfnodeconnline{D1}{D2}
5583 \begin_layout Standard
5587 \begin_layout Standard
5591 pgfnodeconnline{D2}{D3}
5594 \begin_layout Standard
5598 \begin_layout Standard
5604 pgfnodeconnline{D3}{D4}}
5607 \begin_layout Standard
5611 \begin_layout Standard
5616 \begin_layout Standard
5620 \begin_layout Standard
5633 \begin_layout AgainFrame
5637 \begin_layout Standard
5647 \begin_layout Subsection
5648 Complexity of: Approximating the Shortest Path
5651 \begin_layout BeginFrame
5652 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5655 \begin_layout Definition
5658 approximation scheme for
5659 \begin_inset Formula $\Lang{tournament-shortest-path}$
5668 \begin_layout Enumerate
5670 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5676 \begin_layout Enumerate
5678 \begin_inset Formula $r>1$
5684 \begin_layout Standard
5688 \begin_layout Itemize
5690 \begin_inset Formula $s$
5695 \begin_inset Formula $t$
5699 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5706 \begin_layout BeginFrame
5707 There Exists a Logspace Approximation Scheme for
5709 the Tournament Shortest
5713 \begin_layout Theorem
5714 There exists an approximation scheme for
5715 \begin_inset Formula $\Lang{tournament-shortest-path}$
5719 \begin_inset Formula $1<r<2$
5723 \begin_inset Formula \[
5724 O\left(\log|V|\log\frac{1}{r-1}\right).\]
5735 \begin_layout Corollary
5736 In tournaments, paths can be constructed in logarithmic space.
5739 \begin_layout Standard
5746 \begin_layout Standard
5750 hyperlink{optimality}{
5752 beamergotobutton{More Details}}
5760 \begin_layout AgainFrame
5764 \begin_layout Standard
5774 \begin_layout Section*
5778 \begin_layout Subsection*
5782 \begin_layout BeginFrame
5790 \begin_layout Standard
5801 \begin_layout Itemize
5809 \begin_inset Formula $\Class{AC}^{0}$
5818 \begin_layout Itemize
5821 logspace approximation scheme
5827 shortest paths in tournaments.
5830 \begin_layout Itemize
5838 \begin_inset Formula $\Class{NL}$
5847 \begin_layout Separator
5855 \begin_layout Standard
5866 \begin_layout Itemize
5867 The same results apply to graphs with
5869 bounded independence number.
5875 \begin_layout Standard
5879 hyperlink{independence}{
5881 beamergotobutton{More Details}}
5889 \begin_layout Itemize
5890 The complexity of finding paths in undirected graphs
5898 \begin_layout Standard
5902 hyperlink{undirected}{
5904 beamergotobutton{More Details}}
5913 \begin_layout Subsection*
5917 \begin_layout BeginFrame
5921 \begin_layout Standard
5925 \begin_layout Standard
5929 beamertemplatebookbibitems
5937 \begin_layout Bibliography
5946 \begin_layout Standard
5957 Topics on Tournaments.
5964 \begin_layout Standard
5973 Holt, Rinehart, and Winston, 1968.
5978 \begin_layout Standard
5982 beamertemplatearticlebibitems
5990 \begin_layout Bibliography
5992 \bibitem {NickelsenT2002}
5994 Arfst Nickelsen and Till Tantau.
5999 \begin_layout Standard
6008 On reachability in graphs with bounded independence number.
6012 \begin_layout Standard
6026 , Springer-Verlag, 2002.
6029 \begin_layout Bibliography
6031 \bibitem {Tantau2004b}
6037 \begin_layout Standard
6046 A logspace approximation scheme for the shortest path problem for graphs
6047 with bounded independence number.
6051 \begin_layout Standard
6065 , Springer-Verlag, 2004.
6070 \begin_layout Standard
6082 \begin_layout EndFrame
6086 \begin_layout Standard
6091 \begin_layout Standard
6095 AtBeginSubsection[]{}
6103 \begin_layout Section
6107 \begin_layout Subsection
6108 Graphs With Bounded Independence Number
6111 \begin_layout BeginFrame
6115 \begin_layout Standard
6117 [label=independence]
6122 Definition of Independence Number of a Graph
6125 \begin_layout Definition
6131 \begin_inset Formula $\alpha(G)$
6136 is the maximum number of vertices we can pick,
6139 there is no edge between them.
6142 \begin_layout Example
6143 Tournaments have independence number 1.
6147 \begin_layout BeginFrame
6148 The Results for Tournaments also Apply to
6150 Graphs With Bounded Independence
6154 \begin_layout Theorem
6155 For each\InsetSpace ~
6157 \begin_inset Formula $k$
6164 in graphs with independence number
6166 at most\InsetSpace ~
6168 \begin_inset Formula $k$
6172 \begin_inset Formula $\Class{AC}^{0}$
6178 \begin_layout Separator
6182 \begin_layout Theorem
6183 For each\InsetSpace ~
6185 \begin_inset Formula $k$
6190 logspace approximation scheme
6192 for approximating the shortest path in graphs with independence number
6193 at most\InsetSpace ~
6195 \begin_inset Formula $k$
6201 \begin_layout Separator
6205 \begin_layout Theorem
6206 For each\InsetSpace ~
6208 \begin_inset Formula $k$
6215 in graphs with independence number at most\InsetSpace ~
6217 \begin_inset Formula $k$
6223 \begin_inset Formula $\Class{NL}$
6231 \begin_layout Subsection
6232 Finding Paths in Undirected Graphs
6235 \begin_layout BeginFrame
6239 \begin_layout Standard
6241 <1-2>[label=undirected]
6246 The Complexity of Finding Paths in Undirected Graphs
6252 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6256 \begin_inset Formula $\Class{SL}$
6262 \begin_layout Corollary
6263 For undirected graphs, we can solve
6267 \begin_layout Itemize
6268 the reachability problem in logspace iff
6269 \begin_inset Formula $\Class L=\Class{SL}$
6275 \begin_layout Itemize
6276 the construction problem in logspace iff
6280 \begin_layout Standard
6298 \begin_layout Itemize
6299 the optimization problem in logspace iff
6303 \begin_layout Standard
6321 \begin_layout Itemize
6322 the approximation problem in logspace iff ?.
6327 \begin_layout Subsection
6328 The Approximation Scheme is Optimal
6331 \begin_layout BeginFrame
6335 \begin_layout Standard
6342 The Approximation Scheme is Optimal
6345 \begin_layout Theorem
6346 Suppose there exists an approximation scheme for
6347 \begin_inset Formula $\Lang{tournament-shortest-path}$
6351 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6356 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6367 \begin_layout Enumerate
6368 Suppose the approximation scheme exists.
6371 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6378 \begin_layout Enumerate
6380 \begin_inset Formula $(T,s,t)$
6385 \begin_inset Formula $n$
6388 be the number of vertices.
6391 \begin_layout Enumerate
6392 Run the approximation scheme for
6393 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6399 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6405 \begin_layout Enumerate
6406 The resulting path has optimal length.
6411 \begin_layout Standard
6424 \begin_layout EndFrame