1 #LyX 1.5.0svn 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 \font_typewriter default
157 \font_default_family default
163 \paperfontsize default
171 \paperorientation portrait
174 \paragraph_separation indent
176 \quotes_language english
179 \paperpagestyle default
180 \tracking_changes false
181 \output_changes false
189 Finding Paths in Tournaments
196 \begin_layout Institute
197 International Computer Schience Institute
203 \begin_layout Standard
216 \begin_layout BeginFrame
220 \begin_layout Standard
221 \begin_inset LatexCommand tableofcontents
228 \begin_layout Standard
238 \begin_layout EndFrame
242 \begin_layout Standard
246 \begin_layout Standard
248 % Show the table of contents at the beginning
251 \begin_layout Standard
255 \begin_layout Standard
257 % of every subsection.
260 \begin_layout Standard
264 \begin_layout Standard
271 \begin_layout Standard
275 \begin_layout Standard
282 \begin_layout Standard
286 \begin_layout Standard
293 \begin_layout Standard
297 \begin_layout Standard
301 tableofcontents[current,currentsubsection]
304 \begin_layout Standard
308 \begin_layout Standard
313 \begin_layout Standard
317 \begin_layout Standard
327 \begin_layout Section
331 \begin_layout Subsection
332 What are Tournaments?
335 \begin_layout BeginFrame
336 Tournaments Consist of Jousts Between Knights
339 \begin_layout Columns
348 \begin_layout Standard
352 \begin_layout Standard
356 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
359 \begin_layout Standard
363 \begin_layout Standard
367 pgfnodebox{A}[virtual]{
371 pgfuseimage{knight1}}{2pt}{2pt}
374 \begin_layout Standard
378 \begin_layout Standard
382 pgfnodebox{B}[virtual]{
386 pgfuseimage{knight2}}{2pt}{2pt}
389 \begin_layout Standard
393 \begin_layout Standard
397 pgfnodebox{C}[virtual]{
401 pgfuseimage{knight3}}{2pt}{2pt}
404 \begin_layout Standard
408 \begin_layout Standard
412 pgfnodebox{D}[virtual]{
416 pgfuseimage{knight4}}{2pt}{2pt}
419 \begin_layout Standard
423 \begin_layout Standard
427 \begin_layout Standard
431 \begin_layout Standard
438 \begin_layout Standard
442 \begin_layout Standard
453 \begin_layout Standard
457 \begin_layout Standard
464 \begin_layout Standard
468 \begin_layout Standard
472 pgfsetlinewidth{0.6pt}
475 \begin_layout Standard
479 \begin_layout Standard
483 pgfnodeconnline{A}{B}
486 \begin_layout Standard
490 \begin_layout Standard
494 pgfnodeconnline{A}{C}
497 \begin_layout Standard
501 \begin_layout Standard
505 pgfnodeconnline{D}{A}
508 \begin_layout Standard
512 \begin_layout Standard
516 pgfnodeconnline{C}{B}
519 \begin_layout Standard
523 \begin_layout Standard
527 pgfnodeconnline{B}{D}
530 \begin_layout Standard
534 \begin_layout Standard
538 pgfnodeconnline{C}{D}}
541 \begin_layout Standard
545 \begin_layout Standard
565 \begin_layout Standard
567 {What is a Tournament?}
576 \begin_layout Itemize
580 \begin_layout Standard
590 \begin_layout Itemize
594 \begin_layout Standard
601 Every pair has a joust.
604 \begin_layout Itemize
608 \begin_layout Standard
615 In every joust one knight wins.
620 \begin_layout BeginFrame
621 Tournaments are Complete Directed Graphs
624 \begin_layout Columns
633 \begin_layout Standard
637 \begin_layout Standard
641 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
644 \begin_layout Standard
648 \begin_layout Standard
655 \begin_layout Standard
659 \begin_layout Standard
663 pgfsetlinewidth{0.6pt}
666 \begin_layout Standard
670 \begin_layout Standard
679 \begin_layout Standard
683 \begin_layout Standard
692 \begin_layout Standard
696 \begin_layout Standard
705 \begin_layout Standard
709 \begin_layout Standard
718 \begin_layout Standard
722 \begin_layout Standard
726 \begin_layout Standard
730 \begin_layout Standard
737 \begin_layout Standard
741 \begin_layout Standard
749 pgfbox[center,center]{$v_2$}}
752 \begin_layout Standard
756 \begin_layout Standard
764 pgfbox[center,center]{$v_3$}}
767 \begin_layout Standard
771 \begin_layout Standard
779 pgfbox[center,center]{$v_4$}}
782 \begin_layout Standard
786 \begin_layout Standard
794 pgfbox[center,center]{$v_1$}}
797 \begin_layout Standard
801 \begin_layout Standard
805 \begin_layout Standard
809 \begin_layout Standard
816 \begin_layout Standard
820 \begin_layout Standard
829 \begin_layout Standard
833 \begin_layout Standard
837 pgfnodesetsepstart{2pt}
840 \begin_layout Standard
844 \begin_layout Standard
848 pgfnodesetsepend{4pt}
851 \begin_layout Standard
855 \begin_layout Standard
859 pgfnodeconnline{A}{B}
862 \begin_layout Standard
866 \begin_layout Standard
870 pgfnodeconnline{A}{C}
873 \begin_layout Standard
877 \begin_layout Standard
881 pgfnodeconnline{D}{A}
884 \begin_layout Standard
888 \begin_layout Standard
892 pgfnodeconnline{C}{B}
895 \begin_layout Standard
899 \begin_layout Standard
903 pgfnodeconnline{B}{D}
906 \begin_layout Standard
910 \begin_layout Standard
914 pgfnodeconnline{D}{C}
917 \begin_layout Standard
921 \begin_layout Standard
937 \begin_layout Definition
941 \begin_layout Standard
960 \begin_layout Enumerate
964 \begin_layout Enumerate
965 with exactly one edge between
967 any two different vertices.
972 \begin_layout BeginFrame
976 \begin_layout Standard
983 Tournaments Arise Naturally in Different Situations
986 \begin_layout ExampleBlock
990 \begin_layout Standard
992 {Applicatins in Ordering Theory}
1001 \begin_layout Standard
1002 Elements in a set need to be sorted.
1005 The comparison relation may be cyclic, however.
1009 \begin_layout Separator
1013 \begin_layout ExampleBlock
1017 \begin_layout Standard
1019 {Applications in Sociology}
1028 \begin_layout Standard
1029 Several candidates apply for a position.
1031 Reviewers decide for any two candidates
1037 \begin_layout Separator
1041 \begin_layout ExampleBlock
1045 \begin_layout Standard
1047 {Applications in Structural Complexity Theory}
1056 \begin_layout Standard
1058 \begin_inset Formula $L$
1061 is given and a selector function
1062 \begin_inset Formula $f$
1067 It chooses from any two words the one more likely to be in
1068 \begin_inset Formula $f$
1075 \begin_layout Subsection
1076 What Does ``Finding Paths'' Mean?
1079 \begin_layout BeginFrame
1080 ``Finding Paths'' is Ambiguous
1087 \begin_layout Standard
1097 par{}% because LyX inserts superfluous paragraphs
1100 \begin_layout Standard
1104 \begin_layout Standard
1108 only<1>{Path Finding Problems}
1113 \begin_layout Standard
1117 \begin_layout Standard
1128 \begin_layout Standard
1132 \begin_layout Standard
1136 only<4-5>{the Construction Problem}
1141 \begin_layout Standard
1145 \begin_layout Standard
1149 only<6-7>{the Optimization Problem}
1154 \begin_layout Standard
1158 \begin_layout Standard
1169 \begin_layout Standard
1173 \begin_layout Standard
1177 only<10->{the Approximation Problem}}
1186 \begin_layout Itemize
1196 \begin_inset Formula $G=(V,E)$
1208 \begin_inset Formula $s\in V$
1220 \begin_inset Formula $t\in V$
1226 \begin_layout Itemize
1230 \begin_layout Standard
1232 <only@-9| visible@8->
1245 \begin_inset Formula $d$
1252 \begin_layout Standard
1264 \begin_layout Itemize
1268 \begin_layout Standard
1284 \begin_inset Formula $r>1$
1291 \begin_layout Standard
1295 \begin_layout Standard
1307 \begin_layout Overprint
1312 \begin_layout Standard
1316 \begin_layout Standard
1320 onslide<1,3,5,7,9,11-12>
1328 \begin_layout Columns
1332 \begin_layout Standard
1343 \begin_layout Standard
1347 \begin_layout Standard
1365 \begin_layout ExampleBlock
1369 \begin_layout Standard
1380 \begin_layout Standard
1384 \begin_layout Standard
1388 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1391 \begin_layout Standard
1395 \begin_layout Standard
1399 color{beamerexample}
1402 \begin_layout Standard
1406 \begin_layout Standard
1410 pgfsetlinewidth{0.6pt}
1413 \begin_layout Standard
1417 \begin_layout Standard
1426 \begin_layout Standard
1430 \begin_layout Standard
1439 \begin_layout Standard
1443 \begin_layout Standard
1452 \begin_layout Standard
1456 \begin_layout Standard
1465 \begin_layout Standard
1469 \begin_layout Standard
1473 \begin_layout Standard
1477 \begin_layout Standard
1484 \begin_layout Standard
1488 \begin_layout Standard
1496 pgfbox[center,center]{$t$}}
1499 \begin_layout Standard
1503 \begin_layout Standard
1511 pgfbox[center,center]{$s$}}
1514 \begin_layout Standard
1518 \begin_layout Standard
1522 \begin_layout Standard
1526 \begin_layout Standard
1530 color{beamerexample}
1533 \begin_layout Standard
1537 \begin_layout Standard
1546 \begin_layout Standard
1550 \begin_layout Standard
1554 pgfnodesetsepstart{2pt}
1557 \begin_layout Standard
1561 \begin_layout Standard
1565 pgfnodesetsepend{4pt}
1568 \begin_layout Standard
1572 \begin_layout Standard
1576 pgfnodeconnline{A}{B}
1579 \begin_layout Standard
1583 \begin_layout Standard
1587 pgfnodeconnline{A}{C}
1590 \begin_layout Standard
1594 \begin_layout Standard
1598 pgfnodeconnline{D}{A}
1601 \begin_layout Standard
1605 \begin_layout Standard
1609 pgfnodeconnline{C}{B}
1612 \begin_layout Standard
1616 \begin_layout Standard
1620 pgfnodeconnline{B}{D}
1623 \begin_layout Standard
1627 \begin_layout Standard
1631 pgfnodeconnline{D}{C}
1634 \begin_layout Standard
1638 \begin_layout Standard
1642 \begin_layout Standard
1646 \begin_layout Standard
1656 pgfbox[left,center]{, $d=2$}}}
1659 \begin_layout Standard
1663 \begin_layout Standard
1673 pgfbox[left,center]{, $r=1.5$}}}
1676 \begin_layout Standard
1680 \begin_layout Standard
1690 pgfbox[left,center]{, $r=1.25$}}}
1693 \begin_layout Standard
1697 \begin_layout Standard
1710 \begin_layout Standard
1714 \begin_layout Standard
1728 \begin_layout ExampleBlock
1732 \begin_layout Standard
1734 <only@3->{Example Output}
1743 \begin_layout Standard
1747 \begin_layout Standard
1751 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1754 \begin_layout Standard
1758 \begin_layout Standard
1765 \begin_layout Standard
1769 \begin_layout Standard
1773 color{beamerexample}
1776 \begin_layout Standard
1780 \begin_layout Standard
1784 pgfsetlinewidth{0.6pt}
1787 \begin_layout Standard
1791 \begin_layout Standard
1800 \begin_layout Standard
1804 \begin_layout Standard
1813 \begin_layout Standard
1817 \begin_layout Standard
1826 \begin_layout Standard
1830 \begin_layout Standard
1839 \begin_layout Standard
1843 \begin_layout Standard
1847 \begin_layout Standard
1851 \begin_layout Standard
1858 \begin_layout Standard
1862 \begin_layout Standard
1870 pgfbox[center,center]{$t$}}
1873 \begin_layout Standard
1877 \begin_layout Standard
1885 pgfbox[center,center]{$s$}}
1888 \begin_layout Standard
1892 \begin_layout Standard
1896 \begin_layout Standard
1900 \begin_layout Standard
1904 color{beamerexample}
1907 \begin_layout Standard
1911 \begin_layout Standard
1920 \begin_layout Standard
1924 \begin_layout Standard
1928 pgfnodesetsepstart{2pt}
1931 \begin_layout Standard
1935 \begin_layout Standard
1939 pgfnodesetsepend{4pt}
1942 \begin_layout Standard
1946 \begin_layout Standard
1951 \begin_layout Standard
1955 \begin_layout Standard
1961 pgfnodeconnline{A}{B}}
1964 \begin_layout Standard
1968 \begin_layout Standard
1974 pgfnodeconnline{A}{C}}
1977 \begin_layout Standard
1981 \begin_layout Standard
1987 pgfnodeconnline{D}{A}}
1990 \begin_layout Standard
1994 \begin_layout Standard
2000 pgfnodeconnline{C}{B}}
2003 \begin_layout Standard
2007 \begin_layout Standard
2011 pgfnodeconnline{B}{D}
2014 \begin_layout Standard
2018 \begin_layout Standard
2022 pgfnodeconnline{D}{C}
2025 \begin_layout Standard
2029 \begin_layout Standard
2034 \begin_layout Standard
2038 \begin_layout Standard
2048 pgfbox[left,center]{
2053 \begin_layout Standard
2057 \begin_layout Standard
2071 \begin_layout Standard
2075 \begin_layout Standard
2091 \begin_layout Standard
2093 {Variants of Path Finding Problems}
2102 \begin_layout Standard
2106 \begin_layout Standard
2110 usedescriptionitemofwidthas{Approximation Problem:}
2118 \begin_layout Description
2119 Reachability\InsetSpace ~
2124 \begin_layout Standard
2131 Is there a path from
2132 \begin_inset Formula $s$
2137 \begin_inset Formula $t$
2143 \begin_layout Description
2144 Construction\InsetSpace ~
2149 \begin_layout Standard
2156 Construct a path from
2157 \begin_inset Formula $s$
2162 \begin_inset Formula $t$
2168 \begin_layout Description
2169 Optimization\InsetSpace ~
2174 \begin_layout Standard
2181 Construct a shortest path from
2182 \begin_inset Formula $s$
2187 \begin_inset Formula $t$
2193 \begin_layout Description
2194 Distance\InsetSpace ~
2199 \begin_layout Standard
2207 \begin_inset Formula $s$
2212 \begin_inset Formula $t$
2215 at most\InsetSpace ~
2217 \begin_inset Formula $d$
2223 \begin_layout Description
2224 Approximation\InsetSpace ~
2229 \begin_layout Standard
2236 Construct a path from
2237 \begin_inset Formula $s$
2242 \begin_inset Formula $t$
2247 approximately their distance.
2252 \begin_layout Section
2256 \begin_layout Subsection
2257 Standard Complexity Classes
2260 \begin_layout Standard
2264 \begin_layout Standard
2268 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2270 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2279 \begin_layout BeginFrame
2280 The Classes L and NL are Defined via
2282 Logspace Turing Machines
2285 \begin_layout Standard
2289 \begin_layout Standard
2293 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2296 \begin_layout Standard
2300 \begin_layout Standard
2308 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2311 \begin_layout Standard
2315 \begin_layout Standard
2322 \begin_layout Standard
2326 \begin_layout Standard
2334 tape{}{output tape (write only)}{10690836937182}}}
2337 \begin_layout Standard
2341 \begin_layout Standard
2348 \begin_layout Standard
2352 \begin_layout Standard
2360 shorttape{work tape (read/write), $O(
2362 log n)$ symbols}{}{42}}
2365 \begin_layout Standard
2369 \begin_layout Standard
2377 pgfbox[center,center]{
2379 pgfuseimage{computer}}}
2382 \begin_layout Standard
2386 \begin_layout Standard
2391 \begin_layout Standard
2395 \begin_layout Standard
2399 pgfsetlinewidth{0.6pt}
2402 \begin_layout Standard
2406 \begin_layout Standard
2410 \begin_layout Standard
2414 \begin_layout Standard
2421 \begin_layout Standard
2425 \begin_layout Standard
2434 \begin_layout Standard
2438 \begin_layout Standard
2442 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2445 \begin_layout Standard
2449 \begin_layout Standard
2455 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2458 \begin_layout Standard
2462 \begin_layout Standard
2468 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2471 \begin_layout Standard
2475 \begin_layout Standard
2487 \begin_layout BeginFrame
2488 Logspace Turing Machines Are Quite Powerful
2495 \begin_layout Standard
2497 {Deterministic logspace machines can compute}
2506 \begin_layout Itemize
2507 addition, multiplication, and even division
2510 \begin_layout Itemize
2511 reductions used in completeness proofs,
2514 \begin_layout Itemize
2515 reachability in forests.
2527 \begin_layout Standard
2529 {Non-deterministic logspace machines can compute}
2538 \begin_layout Itemize
2539 reachability in graphs,
2542 \begin_layout Itemize
2543 non-reachability in graphs,
2546 \begin_layout Itemize
2547 satisfiability with two literals per clause.
2551 \begin_layout BeginFrame
2555 \begin_layout Standard
2557 <1>[label=hierarchy]
2562 The Complexity Class Hierarchy
2565 \begin_layout Standard
2569 \begin_layout Standard
2573 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2576 \begin_layout Standard
2580 \begin_layout Standard
2584 pgfsetlinewidth{0.8pt}
2587 \begin_layout Standard
2591 \begin_layout Standard
2600 \begin_layout Standard
2604 \begin_layout Standard
2608 pgfsetdash{{2pt}}{0pt}
2611 \begin_layout Standard
2615 \begin_layout Standard
2623 Class{NC}^2$}{black!50!structure}{2}}
2626 \begin_layout Standard
2630 \begin_layout Standard
2636 Class{NL}$}{black!50!structure}{3}
2639 \begin_layout Standard
2643 \begin_layout Standard
2649 Class{L}$}{black!50!structure}{4}
2652 \begin_layout Standard
2656 \begin_layout Standard
2668 Class{NC}^1}$}{black!50!structure}{5}}
2671 \begin_layout Standard
2675 \begin_layout Standard
2682 \begin_layout Standard
2686 \begin_layout Standard
2698 Class{AC}^0}$}{black}{6}}
2701 \begin_layout Standard
2705 \begin_layout Standard
2709 \begin_layout Standard
2713 \begin_layout Standard
2717 pgfsetlinewidth{1.0pt}
2720 \begin_layout Standard
2724 \begin_layout Standard
2731 \begin_layout Standard
2735 \begin_layout Standard
2739 pgfxyline(-5,0)(5,0)
2742 \begin_layout Standard
2746 \begin_layout Standard
2750 \begin_layout Standard
2754 \begin_layout Standard
2765 \begin_layout Standard
2769 \begin_layout Standard
2779 operatorname{forest}}$}}
2782 \begin_layout Standard
2786 \begin_layout Standard
2790 \begin_layout Standard
2794 \begin_layout Standard
2805 \begin_layout Standard
2809 \begin_layout Standard
2828 \begin_layout Standard
2832 \begin_layout Standard
2851 \begin_layout Standard
2855 \begin_layout Standard
2868 \begin_layout Standard
2872 \begin_layout Standard
2880 operatorname{forest}}$,}
2885 \begin_layout Standard
2889 \begin_layout Standard
2897 operatorname{forest}}$,}
2902 \begin_layout Standard
2906 \begin_layout Standard
2914 operatorname{path}}$,}
2919 \begin_layout Standard
2923 \begin_layout Standard
2931 operatorname{path}}$}}}}
2934 \begin_layout Standard
2938 \begin_layout Standard
2948 operatorname{tourn}}$}}
2951 \begin_layout Standard
2955 \begin_layout Standard
2968 \begin_layout Standard
2972 \begin_layout Standard
2980 operatorname{tourn}}$,}
2985 \begin_layout Standard
2989 \begin_layout Standard
3000 \begin_layout Standard
3004 \begin_layout Standard
3013 \begin_layout Standard
3017 \begin_layout Standard
3023 pgfsetdash{{1pt}}{0pt}
3029 operatorname{tourn}}$''}}
3032 \begin_layout Standard
3036 \begin_layout Standard
3048 \begin_layout BeginFrame
3049 The Circuit Complexity Classes AC
3050 \begin_inset Formula $^{0}$
3054 \begin_inset Formula $^{1}$
3058 \begin_inset Formula $^{2}$
3063 Limit the Circuit Depth
3066 \begin_layout Standard
3070 \begin_layout Standard
3079 \begin_layout Standard
3083 \begin_layout Standard
3095 \begin_layout Columns
3099 \begin_layout Standard
3110 \begin_layout Column
3118 \begin_layout Standard
3126 \begin_inset Formula $\Class{AC}^{0}$
3133 \begin_layout Standard
3144 \begin_layout Itemize
3145 \begin_inset Formula $O(1)$
3151 \begin_layout Itemize
3156 \begin_layout Examples
3161 \begin_layout Itemize
3162 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3168 \begin_layout Itemize
3169 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3180 \begin_layout Column
3188 \begin_layout Standard
3196 \begin_inset Formula $\Class{NC}^{1}$
3203 \begin_layout Standard
3214 \begin_layout Itemize
3215 \begin_inset Formula $O(\log n)$
3221 \begin_layout Itemize
3226 \begin_layout Examples
3231 \begin_layout Itemize
3232 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3238 \begin_layout Itemize
3239 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3245 \begin_layout Itemize
3246 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3257 \begin_layout Column
3265 \begin_layout Standard
3273 \begin_inset Formula $\Class{NC}^{2}$
3280 \begin_layout Standard
3291 \begin_layout Itemize
3292 \begin_inset Formula $O(\log^{2}n)$
3298 \begin_layout Itemize
3303 \begin_layout Examples
3308 \begin_layout Itemize
3309 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3317 \begin_layout AgainFrame
3321 \begin_layout Standard
3331 \begin_layout Subsection
3332 Standard Complexity Results on Finding Paths
3335 \begin_layout BeginFrame
3336 All Variants of Finding Paths in Directed Graphs
3338 Are Equally Difficult
3342 \begin_inset Formula $\Lang{reach}$
3346 \begin_inset Formula $\Lang{distance}$
3350 \begin_inset Formula $\Class{NL}$
3361 \begin_layout Corollary
3362 For directed graphs, we can solve
3366 \begin_layout Itemize
3367 the reachability problem in logspace iff
3368 \begin_inset Formula $\Class{L}=\Class{NL}$
3374 \begin_layout Itemize
3375 the construction problem in logspace iff
3376 \begin_inset Formula $\Class{L}=\Class{NL}$
3382 \begin_layout Itemize
3383 the optimization problem in logspace iff
3384 \begin_inset Formula $\Class{L}=\Class{NL}$
3390 \begin_layout Itemize
3391 the approximation problem in logspace iff
3392 \begin_inset Formula $\Class{L}=\Class{NL}$
3399 \begin_layout AgainFrame
3403 \begin_layout Standard
3413 \begin_layout BeginFrame
3414 FindingPaths in Forests and Directed Paths is Easy,
3420 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3424 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3428 \begin_inset Formula $\Class{L}$
3434 \begin_layout Separator
3439 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3443 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3447 \begin_inset Formula $\Class{L}$
3453 \begin_layout AgainFrame
3457 \begin_layout Standard
3467 \begin_layout Section
3468 Finding Paths in Tournaments
3471 \begin_layout Subsection
3472 Complexity of: Does a Path Exist?
3475 \begin_layout BeginFrame
3476 Definition of the Tournament Reachability Problem
3479 \begin_layout Definition
3485 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3493 \begin_inset Formula $(T,s,t)$
3500 \begin_layout Enumerate
3501 \begin_inset Formula $T=(V,E)$
3507 \begin_layout Enumerate
3508 there exists a path from\InsetSpace ~
3510 \begin_inset Formula $s$
3515 \begin_inset Formula $t$
3522 \begin_layout BeginFrame
3523 The Tournament Reachability Problem is Very Easy
3526 \begin_layout Theorem
3527 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3537 \begin_layout AlertBlock
3541 \begin_layout Standard
3552 \begin_layout Itemize
3554 \begin_inset Quotes eld
3558 \begin_inset Quotes erd
3562 \begin_inset Formula $\Lang{reach}$
3566 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3572 \begin_layout Itemize
3573 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3580 \begin_layout AgainFrame
3584 \begin_layout Standard
3594 \begin_layout Subsection
3595 Complexity of: Construct a Shortest Path
3598 \begin_layout BeginFrame
3599 Finding a Shortest Path Is as Difficult as
3601 the Distance Problem
3604 \begin_layout Definition
3610 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3618 \begin_inset Formula $(T,s,t,d)$
3625 \begin_layout Enumerate
3626 \begin_inset Formula $T=(V,E)$
3629 is a tournament in which
3632 \begin_layout Enumerate
3634 \begin_inset Formula $s$
3639 \begin_inset Formula $t$
3642 is at most\InsetSpace ~
3644 \begin_inset Formula $d$
3651 \begin_layout BeginFrame
3652 The Tournament Distance Problem is Hard
3655 \begin_layout Theorem
3656 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3660 \begin_inset Formula $\Class{NL}$
3666 \begin_layout Standard
3673 \begin_layout Standard
3677 hyperlink{hierarchy<6>}{
3679 beamerskipbutton{Skip Proof}}
3691 \begin_layout Corollary
3692 Shortest path in tournaments can be constructed
3694 in logarithmic space, iff
3696 \begin_inset Formula $\Class{L}=\Class{NL}$
3706 \begin_layout Corollary
3707 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3713 \begin_layout BeginFrame
3715 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3721 \begin_layout Standard
3725 \begin_layout Standard
3737 \begin_layout Columns
3741 \begin_layout Standard
3752 \begin_layout Column
3756 \begin_layout Standard
3760 \begin_layout Standard
3778 \begin_layout Standard
3786 \begin_inset Formula $\Lang{reach}$
3790 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3797 \begin_layout Standard
3808 \begin_layout Enumerate
3812 \begin_layout Standard
3820 \begin_inset Formula $(G,s,t)$
3824 \begin_inset Formula $\Lang{reach}$
3830 \begin_layout Enumerate
3834 \begin_layout Standard
3842 \begin_inset Formula $G$
3846 \begin_inset Formula $G'$
3852 \begin_layout Enumerate
3856 \begin_layout Standard
3866 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3873 \begin_layout Separator
3881 \begin_layout Standard
3892 \begin_layout Standard
3903 \begin_layout Standard
3914 \begin_layout Enumerate
3918 \begin_layout Standard
3925 A path in\InsetSpace ~
3927 \begin_inset Formula $G$
3932 a length-3 path in\InsetSpace ~
3934 \begin_inset Formula $G'$
3940 \begin_layout Enumerate
3944 \begin_layout Standard
3951 A length-3 path in\InsetSpace ~
3953 \begin_inset Formula $G'$
3958 a path in\InsetSpace ~
3960 \begin_inset Formula $G'$
3967 \begin_layout Column
3971 \begin_layout Example
3975 \begin_layout Standard
3979 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
3982 \begin_layout Standard
3986 \begin_layout Standard
3990 color{beamerexample}
3993 \begin_layout Standard
3997 \begin_layout Standard
4001 pgfsetlinewidth{0.6pt}
4004 \begin_layout Standard
4008 \begin_layout Standard
4017 \begin_layout Standard
4021 \begin_layout Standard
4030 \begin_layout Standard
4034 \begin_layout Standard
4043 \begin_layout Standard
4047 \begin_layout Standard
4056 \begin_layout Standard
4060 \begin_layout Standard
4064 \begin_layout Standard
4068 \begin_layout Standard
4075 \begin_layout Standard
4079 \begin_layout Standard
4087 pgfbox[center,center]{$s$}}
4090 \begin_layout Standard
4094 \begin_layout Standard
4102 pgfbox[center,center]{$t$}}
4105 \begin_layout Standard
4109 \begin_layout Standard
4113 \begin_layout Standard
4117 \begin_layout Standard
4121 color{beamerexample}
4124 \begin_layout Standard
4128 \begin_layout Standard
4137 \begin_layout Standard
4141 \begin_layout Standard
4145 pgfnodesetsepstart{2pt}
4148 \begin_layout Standard
4152 \begin_layout Standard
4156 pgfnodesetsepend{2pt}
4159 \begin_layout Standard
4163 \begin_layout Standard
4169 pgfnodeconnline{B}{A}}
4172 \begin_layout Standard
4176 \begin_layout Standard
4182 pgfnodeconnline{B}{C}}
4185 \begin_layout Standard
4189 \begin_layout Standard
4195 pgfnodeconnline{C}{D}}
4198 \begin_layout Standard
4202 \begin_layout Standard
4208 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4211 \begin_layout Standard
4215 \begin_layout Standard
4220 \begin_layout Standard
4224 \begin_layout Standard
4232 pgfbox[left,center]{$G
4237 \begin_layout Standard
4241 \begin_layout Standard
4245 \begin_layout Standard
4249 \begin_layout Standard
4256 \begin_layout Standard
4260 \begin_layout Standard
4268 pgfbox[left,center]{$G'
4273 \begin_layout Standard
4277 \begin_layout Standard
4286 \begin_layout Standard
4290 \begin_layout Standard
4299 \begin_layout Standard
4303 \begin_layout Standard
4312 \begin_layout Standard
4316 \begin_layout Standard
4325 \begin_layout Standard
4329 \begin_layout Standard
4333 \begin_layout Standard
4337 \begin_layout Standard
4346 \begin_layout Standard
4350 \begin_layout Standard
4359 \begin_layout Standard
4363 \begin_layout Standard
4372 \begin_layout Standard
4376 \begin_layout Standard
4385 \begin_layout Standard
4389 \begin_layout Standard
4398 \begin_layout Standard
4402 \begin_layout Standard
4411 \begin_layout Standard
4415 \begin_layout Standard
4424 \begin_layout Standard
4428 \begin_layout Standard
4437 \begin_layout Standard
4441 \begin_layout Standard
4450 \begin_layout Standard
4454 \begin_layout Standard
4463 \begin_layout Standard
4467 \begin_layout Standard
4476 \begin_layout Standard
4480 \begin_layout Standard
4489 \begin_layout Standard
4493 \begin_layout Standard
4500 \begin_layout Standard
4504 \begin_layout Standard
4512 pgfbox[center,center]{$s'$}}
4515 \begin_layout Standard
4519 \begin_layout Standard
4527 pgfbox[center,center]{$t'$}}
4530 \begin_layout Standard
4534 \begin_layout Standard
4539 \begin_layout Standard
4543 \begin_layout Standard
4548 \begin_layout Standard
4552 \begin_layout Standard
4559 \begin_layout Standard
4563 \begin_layout Standard
4567 pgfsetlinewidth{0.4pt}
4570 \begin_layout Standard
4574 \begin_layout Standard
4578 color{beamerexample!25!averagebackgroundcolor}
4581 \begin_layout Standard
4585 \begin_layout Standard
4589 pgfnodeconnline{A2}{C1}
4592 \begin_layout Standard
4596 \begin_layout Standard
4600 pgfnodeconnline{A2}{D1}
4603 \begin_layout Standard
4607 \begin_layout Standard
4611 pgfnodeconnline{B2}{A1}
4614 \begin_layout Standard
4618 \begin_layout Standard
4622 pgfnodeconnline{B2}{C1}
4625 \begin_layout Standard
4629 \begin_layout Standard
4633 pgfnodeconnline{B2}{D1}
4636 \begin_layout Standard
4640 \begin_layout Standard
4644 pgfnodeconnline{C2}{D1}
4647 \begin_layout Standard
4651 \begin_layout Standard
4655 pgfnodeconnline{D2}{A1}
4658 \begin_layout Standard
4662 \begin_layout Standard
4666 pgfnodeconnline{D2}{B1}
4669 \begin_layout Standard
4673 \begin_layout Standard
4677 pgfnodeconnline{A3}{C2}
4680 \begin_layout Standard
4684 \begin_layout Standard
4688 pgfnodeconnline{A3}{D2}
4691 \begin_layout Standard
4695 \begin_layout Standard
4699 pgfnodeconnline{B3}{A2}
4702 \begin_layout Standard
4706 \begin_layout Standard
4710 pgfnodeconnline{B3}{C2}
4713 \begin_layout Standard
4717 \begin_layout Standard
4721 pgfnodeconnline{B3}{D2}
4724 \begin_layout Standard
4728 \begin_layout Standard
4732 pgfnodeconnline{C3}{D2}
4735 \begin_layout Standard
4739 \begin_layout Standard
4743 pgfnodeconnline{D3}{A2}
4746 \begin_layout Standard
4750 \begin_layout Standard
4754 pgfnodeconnline{D3}{B2}
4757 \begin_layout Standard
4761 \begin_layout Standard
4765 pgfnodeconnline{A4}{C3}
4768 \begin_layout Standard
4772 \begin_layout Standard
4776 pgfnodeconnline{A4}{D3}
4779 \begin_layout Standard
4783 \begin_layout Standard
4787 pgfnodeconnline{B4}{A3}
4790 \begin_layout Standard
4794 \begin_layout Standard
4798 pgfnodeconnline{B4}{C3}
4801 \begin_layout Standard
4805 \begin_layout Standard
4809 pgfnodeconnline{B4}{D3}
4812 \begin_layout Standard
4816 \begin_layout Standard
4820 pgfnodeconnline{C4}{D3}
4823 \begin_layout Standard
4827 \begin_layout Standard
4831 pgfnodeconnline{D4}{A3}
4834 \begin_layout Standard
4838 \begin_layout Standard
4842 pgfnodeconnline{D4}{B3}
4845 \begin_layout Standard
4849 \begin_layout Standard
4853 \begin_layout Standard
4857 \begin_layout Standard
4866 \begin_layout Standard
4870 \begin_layout Standard
4874 pgfnodeconnline{A1}{B1}
4877 \begin_layout Standard
4881 \begin_layout Standard
4885 pgfnodeconnline{B1}{C1}
4888 \begin_layout Standard
4892 \begin_layout Standard
4896 pgfnodeconnline{C1}{D1}
4899 \begin_layout Standard
4903 \begin_layout Standard
4907 pgfnodeconnline{A2}{B2}
4910 \begin_layout Standard
4914 \begin_layout Standard
4918 pgfnodeconnline{B2}{C2}
4921 \begin_layout Standard
4925 \begin_layout Standard
4929 pgfnodeconnline{C2}{D2}
4932 \begin_layout Standard
4936 \begin_layout Standard
4940 pgfnodeconnline{A3}{B3}
4943 \begin_layout Standard
4947 \begin_layout Standard
4951 pgfnodeconnline{B3}{C3}
4954 \begin_layout Standard
4958 \begin_layout Standard
4962 pgfnodeconnline{C3}{D3}
4965 \begin_layout Standard
4969 \begin_layout Standard
4973 pgfnodeconnline{A4}{B4}
4976 \begin_layout Standard
4980 \begin_layout Standard
4984 pgfnodeconnline{B4}{C4}
4987 \begin_layout Standard
4991 \begin_layout Standard
4995 pgfnodeconnline{C4}{D4}
4998 \begin_layout Standard
5002 \begin_layout Standard
5006 \begin_layout Standard
5010 \begin_layout Standard
5017 \begin_layout Standard
5021 \begin_layout Standard
5025 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
5028 \begin_layout Standard
5032 \begin_layout Standard
5036 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
5039 \begin_layout Standard
5043 \begin_layout Standard
5047 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
5050 \begin_layout Standard
5054 \begin_layout Standard
5058 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
5061 \begin_layout Standard
5065 \begin_layout Standard
5069 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
5072 \begin_layout Standard
5076 \begin_layout Standard
5080 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
5083 \begin_layout Standard
5087 \begin_layout Standard
5091 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
5094 \begin_layout Standard
5098 \begin_layout Standard
5102 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
5105 \begin_layout Standard
5109 \begin_layout Standard
5113 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
5116 \begin_layout Standard
5120 \begin_layout Standard
5124 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
5127 \begin_layout Standard
5131 \begin_layout Standard
5135 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
5138 \begin_layout Standard
5142 \begin_layout Standard
5146 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
5149 \begin_layout Standard
5153 \begin_layout Standard
5157 color{beamerexample}
5160 \begin_layout Standard
5164 \begin_layout Standard
5168 pgfsetlinewidth{0.6pt}
5171 \begin_layout Standard
5175 \begin_layout Standard
5180 \begin_layout Standard
5184 \begin_layout Standard
5188 \begin_layout Standard
5192 \begin_layout Standard
5199 \begin_layout Standard
5203 \begin_layout Standard
5210 \begin_layout Standard
5214 \begin_layout Standard
5218 pgfnodeconnline{B1}{A2}
5221 \begin_layout Standard
5225 \begin_layout Standard
5229 pgfnodeconnline{B2}{A3}
5232 \begin_layout Standard
5236 \begin_layout Standard
5240 pgfnodeconnline{B3}{A4}
5243 \begin_layout Standard
5247 \begin_layout Standard
5252 \begin_layout Standard
5256 \begin_layout Standard
5260 \begin_layout Standard
5264 \begin_layout Standard
5271 \begin_layout Standard
5275 \begin_layout Standard
5282 \begin_layout Standard
5286 \begin_layout Standard
5290 pgfnodeconnline{B1}{C2}
5293 \begin_layout Standard
5297 \begin_layout Standard
5301 pgfnodeconnline{B2}{C3}
5304 \begin_layout Standard
5308 \begin_layout Standard
5312 pgfnodeconnline{B3}{C4}
5315 \begin_layout Standard
5319 \begin_layout Standard
5324 \begin_layout Standard
5328 \begin_layout Standard
5333 \begin_layout Standard
5337 \begin_layout Standard
5344 \begin_layout Standard
5348 \begin_layout Standard
5355 \begin_layout Standard
5359 \begin_layout Standard
5363 pgfnodeconnline{C1}{D2}
5366 \begin_layout Standard
5370 \begin_layout Standard
5376 pgfnodeconnline{C2}{D3}}
5379 \begin_layout Standard
5383 \begin_layout Standard
5389 pgfnodeconnline{C3}{D4}}
5392 \begin_layout Standard
5396 \begin_layout Standard
5401 \begin_layout Standard
5405 \begin_layout Standard
5410 \begin_layout Standard
5414 \begin_layout Standard
5421 \begin_layout Standard
5425 \begin_layout Standard
5432 \begin_layout Standard
5436 \begin_layout Standard
5442 pgfnodeconnline{A1}{C2}}
5445 \begin_layout Standard
5449 \begin_layout Standard
5455 pgfnodeconnline{A2}{C3}}
5458 \begin_layout Standard
5462 \begin_layout Standard
5466 pgfnodeconnline{A3}{C4}
5469 \begin_layout Standard
5473 \begin_layout Standard
5478 \begin_layout Standard
5482 \begin_layout Standard
5486 \begin_layout Standard
5490 \begin_layout Standard
5497 \begin_layout Standard
5501 \begin_layout Standard
5508 \begin_layout Standard
5512 \begin_layout Standard
5518 pgfnodeconnline{A1}{A2}}
5521 \begin_layout Standard
5525 \begin_layout Standard
5529 pgfnodeconnline{A2}{A3}
5532 \begin_layout Standard
5536 \begin_layout Standard
5540 pgfnodeconnline{A3}{A4}
5543 \begin_layout Standard
5547 \begin_layout Standard
5551 pgfnodeconnline{B1}{B2}
5554 \begin_layout Standard
5558 \begin_layout Standard
5562 pgfnodeconnline{B2}{B3}
5565 \begin_layout Standard
5569 \begin_layout Standard
5573 pgfnodeconnline{B3}{B4}
5576 \begin_layout Standard
5580 \begin_layout Standard
5584 pgfnodeconnline{C1}{C2}
5587 \begin_layout Standard
5591 \begin_layout Standard
5595 pgfnodeconnline{C2}{C3}
5598 \begin_layout Standard
5602 \begin_layout Standard
5606 pgfnodeconnline{C3}{C4}
5609 \begin_layout Standard
5613 \begin_layout Standard
5617 pgfnodeconnline{D1}{D2}
5620 \begin_layout Standard
5624 \begin_layout Standard
5628 pgfnodeconnline{D2}{D3}
5631 \begin_layout Standard
5635 \begin_layout Standard
5641 pgfnodeconnline{D3}{D4}}
5644 \begin_layout Standard
5648 \begin_layout Standard
5653 \begin_layout Standard
5657 \begin_layout Standard
5670 \begin_layout AgainFrame
5674 \begin_layout Standard
5684 \begin_layout Subsection
5685 Complexity of: Approximating the Shortest Path
5688 \begin_layout BeginFrame
5689 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5692 \begin_layout Definition
5697 approximation scheme for
5698 \begin_inset Formula $\Lang{tournament-shortest-path}$
5709 \begin_layout Enumerate
5711 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5717 \begin_layout Enumerate
5719 \begin_inset Formula $r>1$
5725 \begin_layout Standard
5729 \begin_layout Itemize
5731 \begin_inset Formula $s$
5736 \begin_inset Formula $t$
5740 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5747 \begin_layout BeginFrame
5748 There Exists a Logspace Approximation Scheme for
5750 the Tournament Shortest
5754 \begin_layout Theorem
5755 There exists an approximation scheme for
5756 \begin_inset Formula $\Lang{tournament-shortest-path}$
5760 \begin_inset Formula $1<r<2$
5764 \begin_inset Formula \[
5765 O\left(\log|V|\log\frac{1}{r-1}\right).\]
5776 \begin_layout Corollary
5777 In tournaments, paths can be constructed in logarithmic space.
5780 \begin_layout Standard
5787 \begin_layout Standard
5791 hyperlink{optimality}{
5793 beamergotobutton{More Details}}
5801 \begin_layout AgainFrame
5805 \begin_layout Standard
5815 \begin_layout Section*
5819 \begin_layout Subsection*
5823 \begin_layout BeginFrame
5831 \begin_layout Standard
5842 \begin_layout Itemize
5856 \begin_inset Formula $\Class{AC}^{0}$
5865 \begin_layout Itemize
5870 logspace approximation scheme
5882 shortest paths in tournaments.
5885 \begin_layout Itemize
5899 \begin_inset Formula $\Class{NL}$
5908 \begin_layout Separator
5916 \begin_layout Standard
5927 \begin_layout Itemize
5928 The same results apply to graphs with
5930 bounded independence number.
5936 \begin_layout Standard
5940 hyperlink{independence}{
5942 beamergotobutton{More Details}}
5950 \begin_layout Itemize
5951 The complexity of finding paths in undirected graphs
5959 \begin_layout Standard
5963 hyperlink{undirected}{
5965 beamergotobutton{More Details}}
5974 \begin_layout Subsection*
5978 \begin_layout BeginFrame
5982 \begin_layout Standard
5986 \begin_layout Standard
5990 beamertemplatebookbibitems
5998 \begin_layout Bibliography
6000 \begin_inset LatexCommand bibitem
6010 \begin_layout Standard
6023 Topics on Tournaments.
6030 \begin_layout Standard
6039 Holt, Rinehart, and Winston, 1968.
6044 \begin_layout Standard
6048 beamertemplatearticlebibitems
6056 \begin_layout Bibliography
6058 \begin_inset LatexCommand bibitem
6059 key "NickelsenT2002"
6063 Arfst Nickelsen and Till Tantau.
6068 \begin_layout Standard
6077 On reachability in graphs with bounded independence number.
6081 \begin_layout Standard
6097 , Springer-Verlag, 2002.
6100 \begin_layout Bibliography
6102 \begin_inset LatexCommand bibitem
6111 \begin_layout Standard
6120 A logspace approximation scheme for the shortest path problem for graphs
6121 with bounded independence number.
6125 \begin_layout Standard
6141 , Springer-Verlag, 2004.
6146 \begin_layout Standard
6158 \begin_layout EndFrame
6162 \begin_layout Standard
6167 \begin_layout Standard
6171 AtBeginSubsection[]{}
6179 \begin_layout Section
6183 \begin_layout Subsection
6184 Graphs With Bounded Independence Number
6187 \begin_layout BeginFrame
6191 \begin_layout Standard
6193 [label=independence]
6198 Definition of Independence Number of a Graph
6201 \begin_layout Definition
6211 \begin_inset Formula $\alpha(G)$
6216 is the maximum number of vertices we can pick,
6219 there is no edge between them.
6222 \begin_layout Example
6223 Tournaments have independence number 1.
6227 \begin_layout BeginFrame
6228 The Results for Tournaments also Apply to
6230 Graphs With Bounded Independence
6234 \begin_layout Theorem
6235 For each\InsetSpace ~
6237 \begin_inset Formula $k$
6248 in graphs with independence number
6250 at most\InsetSpace ~
6252 \begin_inset Formula $k$
6256 \begin_inset Formula $\Class{AC}^{0}$
6262 \begin_layout Separator
6266 \begin_layout Theorem
6267 For each\InsetSpace ~
6269 \begin_inset Formula $k$
6276 logspace approximation scheme
6280 for approximating the shortest path in graphs with independence number
6281 at most\InsetSpace ~
6283 \begin_inset Formula $k$
6289 \begin_layout Separator
6293 \begin_layout Theorem
6294 For each\InsetSpace ~
6296 \begin_inset Formula $k$
6307 in graphs with independence number at most\InsetSpace ~
6309 \begin_inset Formula $k$
6317 \begin_inset Formula $\Class{NL}$
6325 \begin_layout Subsection
6326 Finding Paths in Undirected Graphs
6329 \begin_layout BeginFrame
6333 \begin_layout Standard
6335 <1-2>[label=undirected]
6340 The Complexity of Finding Paths in Undirected Graphs
6346 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6350 \begin_inset Formula $\Class{SL}$
6356 \begin_layout Corollary
6357 For undirected graphs, we can solve
6361 \begin_layout Itemize
6362 the reachability problem in logspace iff
6363 \begin_inset Formula $\Class L=\Class{SL}$
6369 \begin_layout Itemize
6370 the construction problem in logspace iff
6374 \begin_layout Standard
6392 \begin_layout Itemize
6393 the optimization problem in logspace iff
6397 \begin_layout Standard
6415 \begin_layout Itemize
6416 the approximation problem in logspace iff ?.
6421 \begin_layout Subsection
6422 The Approximation Scheme is Optimal
6425 \begin_layout BeginFrame
6429 \begin_layout Standard
6436 The Approximation Scheme is Optimal
6439 \begin_layout Theorem
6440 Suppose there exists an approximation scheme for
6441 \begin_inset Formula $\Lang{tournament-shortest-path}$
6445 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6450 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6461 \begin_layout Enumerate
6462 Suppose the approximation scheme exists.
6465 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6472 \begin_layout Enumerate
6474 \begin_inset Formula $(T,s,t)$
6479 \begin_inset Formula $n$
6482 be the number of vertices.
6485 \begin_layout Enumerate
6486 Run the approximation scheme for
6487 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6493 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6499 \begin_layout Enumerate
6500 The resulting path has optimal length.
6505 \begin_layout Standard
6518 \begin_layout EndFrame