1 #LyX 1.6.0 created this file. For more info see http://www.lyx.org/
5 \use_default_options false
8 \beamertemplateshadingbackground{red!5}{structure!5}
10 \usepackage{beamerthemeshadow}
11 \usepackage{pgfnodes,pgfarrows,pgfheaps}
13 \beamertemplatetransparentcovereddynamicmedium
16 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
17 \logo{\pgfuseimage{icsi-logo}}
22 \newcommand{\Class}[1]{\operatorname{\mathchoice
28 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
30 % This gets defined by beamerbasecolor.sty, but only at the beginning of
32 \colorlet{averagebackgroundcolor}{normal text.bg}
34 \newcommand{\tape}[3]{%
35 \color{structure!30!averagebackgroundcolor}
36 \pgfmoveto{\pgfxy(-0.5,0)}
37 \pgflineto{\pgfxy(-0.6,0.1)}
38 \pgflineto{\pgfxy(-0.4,0.2)}
39 \pgflineto{\pgfxy(-0.6,0.3)}
40 \pgflineto{\pgfxy(-0.4,0.4)}
41 \pgflineto{\pgfxy(-0.5,0.5)}
42 \pgflineto{\pgfxy(4,0.5)}
43 \pgflineto{\pgfxy(4.1,0.4)}
44 \pgflineto{\pgfxy(3.9,0.3)}
45 \pgflineto{\pgfxy(4.1,0.2)}
46 \pgflineto{\pgfxy(3.9,0.1)}
47 \pgflineto{\pgfxy(4,0)}
52 \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
53 \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
56 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
59 \newcommand{\shorttape}[3]{%
60 \color{structure!30!averagebackgroundcolor}
61 \pgfmoveto{\pgfxy(-0.5,0)}
62 \pgflineto{\pgfxy(-0.6,0.1)}
63 \pgflineto{\pgfxy(-0.4,0.2)}
64 \pgflineto{\pgfxy(-0.6,0.3)}
65 \pgflineto{\pgfxy(-0.4,0.4)}
66 \pgflineto{\pgfxy(-0.5,0.5)}
67 \pgflineto{\pgfxy(1,0.5)}
68 \pgflineto{\pgfxy(1.1,0.4)}
69 \pgflineto{\pgfxy(0.9,0.3)}
70 \pgflineto{\pgfxy(1.1,0.2)}
71 \pgflineto{\pgfxy(0.9,0.1)}
72 \pgflineto{\pgfxy(1,0)}
77 \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
78 \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
81 \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
84 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
85 {color(0pt)=(black); color(1cm)=(structure!65!white)}
86 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
87 {color(0pt)=(black); color(1cm)=(structure!55!white)}
88 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
89 {color(0pt)=(black); color(1cm)=(structure!45!white)}
90 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
91 {color(0pt)=(black); color(1cm)=(structure!35!white)}
92 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
93 {color(0pt)=(black); color(1cm)=(structure!25!white)}
94 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
95 {color(0pt)=(black); color(1cm)=(red!35!white)}
97 \newcommand{\heap}[5]{%
100 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
102 \begin{pgfmagnify}{1}{#1}
103 \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
109 \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
113 \pgfheaplabel{\pgfxy(0,#1)}{#3}%
117 \newcommand{\langat}[2]{%
118 \color{black!30!beamerexample}
119 \pgfsetlinewidth{0.6pt}
120 \pgfsetendarrow{\pgfarrowdot}
121 \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
122 \color{beamerexample}
123 \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
126 \newcommand{\langatother}[2]{%
127 \color{black!30!beamerexample}
128 \pgfsetlinewidth{0.6pt}
129 \pgfsetendarrow{\pgfarrowdot}
130 \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
131 \color{beamerexample}
132 \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
136 \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}
139 \pgfdeclareradialshading{graphnode}
140 {\pgfpoint{-3pt}{3.6pt}}%
141 {color(0cm)=(beamerexample!15);
142 color(2.63pt)=(beamerexample!75);
143 color(5.26pt)=(beamerexample!70!black);
144 color(7.6pt)=(beamerexample!50!black);
145 color(8pt)=(beamerexample!10!averagebackgroundcolor)}
147 \newcommand{\graphnode}[2]{
148 \pgfnodecircle{#1}[virtual]{#2}{8pt}
149 \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
157 \font_typewriter default
158 \font_default_family default
164 \paperfontsize default
173 \paperorientation portrait
176 \paragraph_separation indent
178 \quotes_language english
181 \paperpagestyle default
182 \tracking_changes false
183 \output_changes false
191 \begin_inset Newline newline
194 Finding Paths in Tournaments
201 \begin_layout Institute
202 International Computer Schience Institute
203 \begin_inset Newline newline
210 \begin_layout Plain Layout
223 \begin_layout BeginFrame
227 \begin_layout Standard
228 \begin_inset CommandInset toc
229 LatexCommand tableofcontents
237 \begin_layout Plain Layout
247 \begin_layout EndFrame
251 \begin_layout Standard
255 \begin_layout Plain Layout
257 % Show the table of contents at the beginning
260 \begin_layout Plain Layout
264 \begin_layout Plain Layout
266 % of every subsection.
269 \begin_layout Plain Layout
273 \begin_layout Plain Layout
280 \begin_layout Plain Layout
284 \begin_layout Plain Layout
291 \begin_layout Plain Layout
295 \begin_layout Plain Layout
302 \begin_layout Plain Layout
306 \begin_layout Plain Layout
310 tableofcontents[current,currentsubsection]
313 \begin_layout Plain Layout
317 \begin_layout Plain Layout
322 \begin_layout Plain Layout
326 \begin_layout Plain Layout
336 \begin_layout Section
340 \begin_layout Subsection
341 What are Tournaments?
344 \begin_layout BeginFrame
345 Tournaments Consist of Jousts Between Knights
348 \begin_layout Columns
357 \begin_layout Standard
361 \begin_layout Plain Layout
365 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
368 \begin_layout Plain Layout
372 \begin_layout Plain Layout
376 pgfnodebox{A}[virtual]{
380 pgfuseimage{knight1}}{2pt}{2pt}
383 \begin_layout Plain Layout
387 \begin_layout Plain Layout
391 pgfnodebox{B}[virtual]{
395 pgfuseimage{knight2}}{2pt}{2pt}
398 \begin_layout Plain Layout
402 \begin_layout Plain Layout
406 pgfnodebox{C}[virtual]{
410 pgfuseimage{knight3}}{2pt}{2pt}
413 \begin_layout Plain Layout
417 \begin_layout Plain Layout
421 pgfnodebox{D}[virtual]{
425 pgfuseimage{knight4}}{2pt}{2pt}
428 \begin_layout Plain Layout
432 \begin_layout Plain Layout
436 \begin_layout Plain Layout
440 \begin_layout Plain Layout
447 \begin_layout Plain Layout
451 \begin_layout Plain Layout
462 \begin_layout Plain Layout
466 \begin_layout Plain Layout
473 \begin_layout Plain Layout
477 \begin_layout Plain Layout
481 pgfsetlinewidth{0.6pt}
484 \begin_layout Plain Layout
488 \begin_layout Plain Layout
492 pgfnodeconnline{A}{B}
495 \begin_layout Plain Layout
499 \begin_layout Plain Layout
503 pgfnodeconnline{A}{C}
506 \begin_layout Plain Layout
510 \begin_layout Plain Layout
514 pgfnodeconnline{D}{A}
517 \begin_layout Plain Layout
521 \begin_layout Plain Layout
525 pgfnodeconnline{C}{B}
528 \begin_layout Plain Layout
532 \begin_layout Plain Layout
536 pgfnodeconnline{B}{D}
539 \begin_layout Plain Layout
543 \begin_layout Plain Layout
547 pgfnodeconnline{C}{D}}
550 \begin_layout Plain Layout
554 \begin_layout Plain Layout
574 \begin_layout Plain Layout
576 {What is a Tournament?}
585 \begin_layout Itemize
589 \begin_layout Plain Layout
599 \begin_layout Itemize
603 \begin_layout Plain Layout
610 Every pair has a joust.
613 \begin_layout Itemize
617 \begin_layout Plain Layout
624 In every joust one knight wins.
629 \begin_layout BeginFrame
630 Tournaments are Complete Directed Graphs
633 \begin_layout Columns
642 \begin_layout Standard
646 \begin_layout Plain Layout
650 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
653 \begin_layout Plain Layout
657 \begin_layout Plain Layout
664 \begin_layout Plain Layout
668 \begin_layout Plain Layout
672 pgfsetlinewidth{0.6pt}
675 \begin_layout Plain Layout
679 \begin_layout Plain Layout
688 \begin_layout Plain Layout
692 \begin_layout Plain Layout
701 \begin_layout Plain Layout
705 \begin_layout Plain Layout
714 \begin_layout Plain Layout
718 \begin_layout Plain Layout
727 \begin_layout Plain Layout
731 \begin_layout Plain Layout
735 \begin_layout Plain Layout
739 \begin_layout Plain Layout
746 \begin_layout Plain Layout
750 \begin_layout Plain Layout
758 pgfbox[center,center]{$v_2$}}
761 \begin_layout Plain Layout
765 \begin_layout Plain Layout
773 pgfbox[center,center]{$v_3$}}
776 \begin_layout Plain Layout
780 \begin_layout Plain Layout
788 pgfbox[center,center]{$v_4$}}
791 \begin_layout Plain Layout
795 \begin_layout Plain Layout
803 pgfbox[center,center]{$v_1$}}
806 \begin_layout Plain Layout
810 \begin_layout Plain Layout
814 \begin_layout Plain Layout
818 \begin_layout Plain Layout
825 \begin_layout Plain Layout
829 \begin_layout Plain Layout
838 \begin_layout Plain Layout
842 \begin_layout Plain Layout
846 pgfnodesetsepstart{2pt}
849 \begin_layout Plain Layout
853 \begin_layout Plain Layout
857 pgfnodesetsepend{4pt}
860 \begin_layout Plain Layout
864 \begin_layout Plain Layout
868 pgfnodeconnline{A}{B}
871 \begin_layout Plain Layout
875 \begin_layout Plain Layout
879 pgfnodeconnline{A}{C}
882 \begin_layout Plain Layout
886 \begin_layout Plain Layout
890 pgfnodeconnline{D}{A}
893 \begin_layout Plain Layout
897 \begin_layout Plain Layout
901 pgfnodeconnline{C}{B}
904 \begin_layout Plain Layout
908 \begin_layout Plain Layout
912 pgfnodeconnline{B}{D}
915 \begin_layout Plain Layout
919 \begin_layout Plain Layout
923 pgfnodeconnline{D}{C}
926 \begin_layout Plain Layout
930 \begin_layout Plain Layout
946 \begin_layout Definition
950 \begin_layout Plain Layout
969 \begin_layout Enumerate
973 \begin_layout Enumerate
974 with exactly one edge between
975 \begin_inset Newline newline
978 any two different vertices.
983 \begin_layout BeginFrame
987 \begin_layout Plain Layout
994 Tournaments Arise Naturally in Different Situations
997 \begin_layout ExampleBlock
1001 \begin_layout Plain Layout
1003 {Applicatins in Ordering Theory}
1012 \begin_layout Standard
1013 Elements in a set need to be sorted.
1015 \begin_inset Newline newline
1018 The comparison relation may be cyclic, however.
1022 \begin_layout Separator
1026 \begin_layout ExampleBlock
1030 \begin_layout Plain Layout
1032 {Applications in Sociology}
1041 \begin_layout Standard
1042 Several candidates apply for a position.
1043 \begin_inset Newline newline
1046 Reviewers decide for any two candidates whom they prefer.
1051 \begin_layout Separator
1055 \begin_layout ExampleBlock
1059 \begin_layout Plain Layout
1061 {Applications in Structural Complexity Theory}
1070 \begin_layout Standard
1072 \begin_inset Formula $L$
1075 is given and a selector function
1076 \begin_inset Formula $f$
1080 \begin_inset Newline newline
1083 It chooses from any two words the one more likely to be in
1084 \begin_inset Formula $f$
1091 \begin_layout Subsection
1092 What Does ``Finding Paths'' Mean?
1095 \begin_layout BeginFrame
1096 ``Finding Paths'' is Ambiguous
1103 \begin_layout Plain Layout
1113 par{}% because LyX inserts superfluous paragraphs
1116 \begin_layout Plain Layout
1120 \begin_layout Plain Layout
1124 only<1>{Path Finding Problems}
1129 \begin_layout Plain Layout
1133 \begin_layout Plain Layout
1144 \begin_layout Plain Layout
1148 \begin_layout Plain Layout
1152 only<4-5>{the Construction Problem}
1157 \begin_layout Plain Layout
1161 \begin_layout Plain Layout
1165 only<6-7>{the Optimization Problem}
1170 \begin_layout Plain Layout
1174 \begin_layout Plain Layout
1185 \begin_layout Plain Layout
1189 \begin_layout Plain Layout
1193 only<10->{the Approximation Problem}}
1202 \begin_layout Itemize
1212 \begin_inset Formula $G=(V,E)$
1224 \begin_inset Formula $s\in V$
1236 \begin_inset Formula $t\in V$
1242 \begin_layout Itemize
1246 \begin_layout Plain Layout
1248 <only@-9| visible@8->
1260 \begin_inset space ~
1264 \begin_inset Formula $d$
1271 \begin_layout Plain Layout
1283 \begin_layout Itemize
1287 \begin_layout Plain Layout
1303 \begin_inset Formula $r>1$
1310 \begin_layout Standard
1314 \begin_layout Plain Layout
1326 \begin_layout Overprint
1331 \begin_layout Standard
1335 \begin_layout Plain Layout
1339 onslide<1,3,5,7,9,11-12>
1347 \begin_layout Columns
1351 \begin_layout Plain Layout
1362 \begin_layout Standard
1366 \begin_layout Plain Layout
1384 \begin_layout ExampleBlock
1388 \begin_layout Plain Layout
1399 \begin_layout Standard
1403 \begin_layout Plain Layout
1407 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1410 \begin_layout Plain Layout
1414 \begin_layout Plain Layout
1418 color{beamerexample}
1421 \begin_layout Plain Layout
1425 \begin_layout Plain Layout
1429 pgfsetlinewidth{0.6pt}
1432 \begin_layout Plain Layout
1436 \begin_layout Plain Layout
1445 \begin_layout Plain Layout
1449 \begin_layout Plain Layout
1458 \begin_layout Plain Layout
1462 \begin_layout Plain Layout
1471 \begin_layout Plain Layout
1475 \begin_layout Plain Layout
1484 \begin_layout Plain Layout
1488 \begin_layout Plain Layout
1492 \begin_layout Plain Layout
1496 \begin_layout Plain Layout
1503 \begin_layout Plain Layout
1507 \begin_layout Plain Layout
1515 pgfbox[center,center]{$t$}}
1518 \begin_layout Plain Layout
1522 \begin_layout Plain Layout
1530 pgfbox[center,center]{$s$}}
1533 \begin_layout Plain Layout
1537 \begin_layout Plain Layout
1541 \begin_layout Plain Layout
1545 \begin_layout Plain Layout
1549 color{beamerexample}
1552 \begin_layout Plain Layout
1556 \begin_layout Plain Layout
1565 \begin_layout Plain Layout
1569 \begin_layout Plain Layout
1573 pgfnodesetsepstart{2pt}
1576 \begin_layout Plain Layout
1580 \begin_layout Plain Layout
1584 pgfnodesetsepend{4pt}
1587 \begin_layout Plain Layout
1591 \begin_layout Plain Layout
1595 pgfnodeconnline{A}{B}
1598 \begin_layout Plain Layout
1602 \begin_layout Plain Layout
1606 pgfnodeconnline{A}{C}
1609 \begin_layout Plain Layout
1613 \begin_layout Plain Layout
1617 pgfnodeconnline{D}{A}
1620 \begin_layout Plain Layout
1624 \begin_layout Plain Layout
1628 pgfnodeconnline{C}{B}
1631 \begin_layout Plain Layout
1635 \begin_layout Plain Layout
1639 pgfnodeconnline{B}{D}
1642 \begin_layout Plain Layout
1646 \begin_layout Plain Layout
1650 pgfnodeconnline{D}{C}
1653 \begin_layout Plain Layout
1657 \begin_layout Plain Layout
1661 \begin_layout Plain Layout
1665 \begin_layout Plain Layout
1675 pgfbox[left,center]{, $d=2$}}}
1678 \begin_layout Plain Layout
1682 \begin_layout Plain Layout
1692 pgfbox[left,center]{, $r=1.5$}}}
1695 \begin_layout Plain Layout
1699 \begin_layout Plain Layout
1709 pgfbox[left,center]{, $r=1.25$}}}
1712 \begin_layout Plain Layout
1716 \begin_layout Plain Layout
1729 \begin_layout Standard
1733 \begin_layout Plain Layout
1747 \begin_layout ExampleBlock
1751 \begin_layout Plain Layout
1753 <only@3->{Example Output}
1762 \begin_layout Standard
1766 \begin_layout Plain Layout
1770 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1773 \begin_layout Plain Layout
1777 \begin_layout Plain Layout
1784 \begin_layout Plain Layout
1788 \begin_layout Plain Layout
1792 color{beamerexample}
1795 \begin_layout Plain Layout
1799 \begin_layout Plain Layout
1803 pgfsetlinewidth{0.6pt}
1806 \begin_layout Plain Layout
1810 \begin_layout Plain Layout
1819 \begin_layout Plain Layout
1823 \begin_layout Plain Layout
1832 \begin_layout Plain Layout
1836 \begin_layout Plain Layout
1845 \begin_layout Plain Layout
1849 \begin_layout Plain Layout
1858 \begin_layout Plain Layout
1862 \begin_layout Plain Layout
1866 \begin_layout Plain Layout
1870 \begin_layout Plain Layout
1877 \begin_layout Plain Layout
1881 \begin_layout Plain Layout
1889 pgfbox[center,center]{$t$}}
1892 \begin_layout Plain Layout
1896 \begin_layout Plain Layout
1904 pgfbox[center,center]{$s$}}
1907 \begin_layout Plain Layout
1911 \begin_layout Plain Layout
1915 \begin_layout Plain Layout
1919 \begin_layout Plain Layout
1923 color{beamerexample}
1926 \begin_layout Plain Layout
1930 \begin_layout Plain Layout
1939 \begin_layout Plain Layout
1943 \begin_layout Plain Layout
1947 pgfnodesetsepstart{2pt}
1950 \begin_layout Plain Layout
1954 \begin_layout Plain Layout
1958 pgfnodesetsepend{4pt}
1961 \begin_layout Plain Layout
1965 \begin_layout Plain Layout
1970 \begin_layout Plain Layout
1974 \begin_layout Plain Layout
1980 pgfnodeconnline{A}{B}}
1983 \begin_layout Plain Layout
1987 \begin_layout Plain Layout
1993 pgfnodeconnline{A}{C}}
1996 \begin_layout Plain Layout
2000 \begin_layout Plain Layout
2006 pgfnodeconnline{D}{A}}
2009 \begin_layout Plain Layout
2013 \begin_layout Plain Layout
2019 pgfnodeconnline{C}{B}}
2022 \begin_layout Plain Layout
2026 \begin_layout Plain Layout
2030 pgfnodeconnline{B}{D}
2033 \begin_layout Plain Layout
2037 \begin_layout Plain Layout
2041 pgfnodeconnline{D}{C}
2044 \begin_layout Plain Layout
2048 \begin_layout Plain Layout
2053 \begin_layout Plain Layout
2057 \begin_layout Plain Layout
2067 pgfbox[left,center]{
2072 \begin_layout Plain Layout
2076 \begin_layout Plain Layout
2090 \begin_layout Standard
2094 \begin_layout Plain Layout
2110 \begin_layout Plain Layout
2112 {Variants of Path Finding Problems}
2121 \begin_layout Standard
2125 \begin_layout Plain Layout
2129 usedescriptionitemofwidthas{Approximation Problem:}
2137 \begin_layout Description
2139 \begin_inset space ~
2146 \begin_layout Plain Layout
2153 Is there a path from
2154 \begin_inset Formula $s$
2158 \begin_inset space ~
2162 \begin_inset Formula $t$
2168 \begin_layout Description
2170 \begin_inset space ~
2177 \begin_layout Plain Layout
2184 Construct a path from
2185 \begin_inset Formula $s$
2189 \begin_inset space ~
2193 \begin_inset Formula $t$
2199 \begin_layout Description
2201 \begin_inset space ~
2208 \begin_layout Plain Layout
2215 Construct a shortest path from
2216 \begin_inset Formula $s$
2220 \begin_inset space ~
2224 \begin_inset Formula $t$
2230 \begin_layout Description
2232 \begin_inset space ~
2239 \begin_layout Plain Layout
2247 \begin_inset Formula $s$
2251 \begin_inset space ~
2255 \begin_inset Formula $t$
2259 \begin_inset space ~
2263 \begin_inset Formula $d$
2269 \begin_layout Description
2271 \begin_inset space ~
2278 \begin_layout Plain Layout
2285 Construct a path from
2286 \begin_inset Formula $s$
2290 \begin_inset space ~
2294 \begin_inset Formula $t$
2298 \begin_inset Newline newline
2301 approximately their distance.
2306 \begin_layout Section
2310 \begin_layout Subsection
2311 Standard Complexity Classes
2314 \begin_layout Standard
2318 \begin_layout Plain Layout
2322 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2324 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2333 \begin_layout BeginFrame
2334 The Classes L and NL are Defined via
2335 \begin_inset Newline newline
2338 Logspace Turing Machines
2341 \begin_layout Standard
2345 \begin_layout Plain Layout
2349 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2352 \begin_layout Plain Layout
2356 \begin_layout Plain Layout
2364 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2367 \begin_layout Plain Layout
2371 \begin_layout Plain Layout
2378 \begin_layout Plain Layout
2382 \begin_layout Plain Layout
2390 tape{}{output tape (write only)}{10690836937182}}}
2393 \begin_layout Plain Layout
2397 \begin_layout Plain Layout
2404 \begin_layout Plain Layout
2408 \begin_layout Plain Layout
2416 shorttape{work tape (read/write), $O(
2418 log n)$ symbols}{}{42}}
2421 \begin_layout Plain Layout
2425 \begin_layout Plain Layout
2433 pgfbox[center,center]{
2435 pgfuseimage{computer}}}
2438 \begin_layout Plain Layout
2442 \begin_layout Plain Layout
2447 \begin_layout Plain Layout
2451 \begin_layout Plain Layout
2455 pgfsetlinewidth{0.6pt}
2458 \begin_layout Plain Layout
2462 \begin_layout Plain Layout
2466 \begin_layout Plain Layout
2470 \begin_layout Plain Layout
2477 \begin_layout Plain Layout
2481 \begin_layout Plain Layout
2490 \begin_layout Plain Layout
2494 \begin_layout Plain Layout
2498 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2501 \begin_layout Plain Layout
2505 \begin_layout Plain Layout
2511 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2514 \begin_layout Plain Layout
2518 \begin_layout Plain Layout
2524 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2527 \begin_layout Plain Layout
2531 \begin_layout Plain Layout
2543 \begin_layout BeginFrame
2544 Logspace Turing Machines Are Quite Powerful
2551 \begin_layout Plain Layout
2553 {Deterministic logspace machines can compute}
2562 \begin_layout Itemize
2563 addition, multiplication, and even division
2566 \begin_layout Itemize
2567 reductions used in completeness proofs,
2570 \begin_layout Itemize
2571 reachability in forests.
2583 \begin_layout Plain Layout
2585 {Non-deterministic logspace machines can compute}
2594 \begin_layout Itemize
2595 reachability in graphs,
2598 \begin_layout Itemize
2599 non-reachability in graphs,
2602 \begin_layout Itemize
2603 satisfiability with two literals per clause.
2607 \begin_layout BeginFrame
2611 \begin_layout Plain Layout
2613 <1>[label=hierarchy]
2618 The Complexity Class Hierarchy
2621 \begin_layout Standard
2625 \begin_layout Plain Layout
2629 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2632 \begin_layout Plain Layout
2636 \begin_layout Plain Layout
2640 pgfsetlinewidth{0.8pt}
2643 \begin_layout Plain Layout
2647 \begin_layout Plain Layout
2656 \begin_layout Plain Layout
2660 \begin_layout Plain Layout
2664 pgfsetdash{{2pt}}{0pt}
2667 \begin_layout Plain Layout
2671 \begin_layout Plain Layout
2679 Class{NC}^2$}{black!50!structure}{2}}
2682 \begin_layout Plain Layout
2686 \begin_layout Plain Layout
2692 Class{NL}$}{black!50!structure}{3}
2695 \begin_layout Plain Layout
2699 \begin_layout Plain Layout
2705 Class{L}$}{black!50!structure}{4}
2708 \begin_layout Plain Layout
2712 \begin_layout Plain Layout
2724 Class{NC}^1}$}{black!50!structure}{5}}
2727 \begin_layout Plain Layout
2731 \begin_layout Plain Layout
2738 \begin_layout Plain Layout
2742 \begin_layout Plain Layout
2754 Class{AC}^0}$}{black}{6}}
2757 \begin_layout Plain Layout
2761 \begin_layout Plain Layout
2765 \begin_layout Plain Layout
2769 \begin_layout Plain Layout
2773 pgfsetlinewidth{1.0pt}
2776 \begin_layout Plain Layout
2780 \begin_layout Plain Layout
2787 \begin_layout Plain Layout
2791 \begin_layout Plain Layout
2795 pgfxyline(-5,0)(5,0)
2798 \begin_layout Plain Layout
2802 \begin_layout Plain Layout
2806 \begin_layout Plain Layout
2810 \begin_layout Plain Layout
2821 \begin_layout Plain Layout
2825 \begin_layout Plain Layout
2835 operatorname{forest}}$}}
2838 \begin_layout Plain Layout
2842 \begin_layout Plain Layout
2846 \begin_layout Plain Layout
2850 \begin_layout Plain Layout
2861 \begin_layout Plain Layout
2865 \begin_layout Plain Layout
2884 \begin_layout Plain Layout
2888 \begin_layout Plain Layout
2907 \begin_layout Plain Layout
2911 \begin_layout Plain Layout
2924 \begin_layout Plain Layout
2928 \begin_layout Plain Layout
2936 operatorname{forest}}$,}
2941 \begin_layout Plain Layout
2945 \begin_layout Plain Layout
2953 operatorname{forest}}$,}
2958 \begin_layout Plain Layout
2962 \begin_layout Plain Layout
2970 operatorname{path}}$,}
2975 \begin_layout Plain Layout
2979 \begin_layout Plain Layout
2987 operatorname{path}}$}}}}
2990 \begin_layout Plain Layout
2994 \begin_layout Plain Layout
3004 operatorname{tourn}}$}}
3007 \begin_layout Plain Layout
3011 \begin_layout Plain Layout
3024 \begin_layout Plain Layout
3028 \begin_layout Plain Layout
3036 operatorname{tourn}}$,}
3041 \begin_layout Plain Layout
3045 \begin_layout Plain Layout
3056 \begin_layout Plain Layout
3060 \begin_layout Plain Layout
3069 \begin_layout Plain Layout
3073 \begin_layout Plain Layout
3079 pgfsetdash{{1pt}}{0pt}
3085 operatorname{tourn}}$''}}
3088 \begin_layout Plain Layout
3092 \begin_layout Plain Layout
3104 \begin_layout BeginFrame
3105 The Circuit Complexity Classes AC
3106 \begin_inset Formula $^{0}$
3110 \begin_inset Formula $^{1}$
3114 \begin_inset Formula $^{2}$
3118 \begin_inset Newline newline
3121 Limit the Circuit Depth
3124 \begin_layout Standard
3128 \begin_layout Plain Layout
3137 \begin_layout Plain Layout
3141 \begin_layout Plain Layout
3153 \begin_layout Columns
3157 \begin_layout Plain Layout
3168 \begin_layout Column
3176 \begin_layout Plain Layout
3184 \begin_inset Formula $\Class{AC}^{0}$
3191 \begin_layout Plain Layout
3202 \begin_layout Itemize
3203 \begin_inset Formula $O(1)$
3209 \begin_layout Itemize
3214 \begin_layout Examples
3219 \begin_layout Itemize
3220 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3226 \begin_layout Itemize
3227 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3238 \begin_layout Column
3246 \begin_layout Plain Layout
3254 \begin_inset Formula $\Class{NC}^{1}$
3261 \begin_layout Plain Layout
3272 \begin_layout Itemize
3273 \begin_inset Formula $O(\log n)$
3279 \begin_layout Itemize
3284 \begin_layout Examples
3289 \begin_layout Itemize
3290 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3296 \begin_layout Itemize
3297 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3303 \begin_layout Itemize
3304 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3315 \begin_layout Column
3323 \begin_layout Plain Layout
3331 \begin_inset Formula $\Class{NC}^{2}$
3338 \begin_layout Plain Layout
3349 \begin_layout Itemize
3350 \begin_inset Formula $O(\log^{2}n)$
3356 \begin_layout Itemize
3361 \begin_layout Examples
3366 \begin_layout Itemize
3367 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3375 \begin_layout AgainFrame
3379 \begin_layout Plain Layout
3389 \begin_layout Subsection
3390 Standard Complexity Results on Finding Paths
3393 \begin_layout BeginFrame
3394 All Variants of Finding Paths in Directed Graphs
3395 \begin_inset Newline newline
3398 Are Equally Difficult
3402 \begin_inset Formula $\Lang{reach}$
3406 \begin_inset Formula $\Lang{distance}$
3410 \begin_inset Formula $\Class{NL}$
3421 \begin_layout Corollary
3422 For directed graphs, we can solve
3426 \begin_layout Itemize
3427 the reachability problem in logspace iff
3428 \begin_inset Formula $\Class{L}=\Class{NL}$
3434 \begin_layout Itemize
3435 the construction problem in logspace iff
3436 \begin_inset Formula $\Class{L}=\Class{NL}$
3442 \begin_layout Itemize
3443 the optimization problem in logspace iff
3444 \begin_inset Formula $\Class{L}=\Class{NL}$
3450 \begin_layout Itemize
3451 the approximation problem in logspace iff
3452 \begin_inset Formula $\Class{L}=\Class{NL}$
3459 \begin_layout AgainFrame
3463 \begin_layout Plain Layout
3473 \begin_layout BeginFrame
3474 FindingPaths in Forests and Directed Paths is Easy,
3475 \begin_inset Newline newline
3482 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3486 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3490 \begin_inset Formula $\Class{L}$
3496 \begin_layout Separator
3501 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3505 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3509 \begin_inset Formula $\Class{L}$
3515 \begin_layout AgainFrame
3519 \begin_layout Plain Layout
3529 \begin_layout Section
3530 Finding Paths in Tournaments
3533 \begin_layout Subsection
3534 Complexity of: Does a Path Exist?
3537 \begin_layout BeginFrame
3538 Definition of the Tournament Reachability Problem
3541 \begin_layout Definition
3547 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3555 \begin_inset Formula $(T,s,t)$
3562 \begin_layout Enumerate
3563 \begin_inset Formula $T=(V,E)$
3569 \begin_layout Enumerate
3570 there exists a path from
3571 \begin_inset space ~
3575 \begin_inset Formula $s$
3579 \begin_inset space ~
3583 \begin_inset Formula $t$
3590 \begin_layout BeginFrame
3591 The Tournament Reachability Problem is Very Easy
3594 \begin_layout Theorem
3595 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3605 \begin_layout AlertBlock
3609 \begin_layout Plain Layout
3620 \begin_layout Itemize
3622 \begin_inset Quotes eld
3626 \begin_inset Quotes erd
3630 \begin_inset Formula $\Lang{reach}$
3634 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3640 \begin_layout Itemize
3641 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3648 \begin_layout AgainFrame
3652 \begin_layout Plain Layout
3662 \begin_layout Subsection
3663 Complexity of: Construct a Shortest Path
3666 \begin_layout BeginFrame
3667 Finding a Shortest Path Is as Difficult as
3668 \begin_inset Newline newline
3671 the Distance Problem
3674 \begin_layout Definition
3680 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3688 \begin_inset Formula $(T,s,t,d)$
3695 \begin_layout Enumerate
3696 \begin_inset Formula $T=(V,E)$
3699 is a tournament in which
3702 \begin_layout Enumerate
3704 \begin_inset Formula $s$
3708 \begin_inset space ~
3712 \begin_inset Formula $t$
3716 \begin_inset space ~
3720 \begin_inset Formula $d$
3727 \begin_layout BeginFrame
3728 The Tournament Distance Problem is Hard
3731 \begin_layout Theorem
3732 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3736 \begin_inset Formula $\Class{NL}$
3742 \begin_layout Standard
3743 \begin_inset space \hfill{}
3750 \begin_layout Plain Layout
3754 hyperlink{hierarchy<6>}{
3756 beamerskipbutton{Skip Proof}}
3768 \begin_layout Corollary
3769 Shortest path in tournaments can be constructed
3770 \begin_inset Newline newline
3773 in logarithmic space, iff
3774 \begin_inset Formula $\Class{L}=\Class{NL}$
3784 \begin_layout Corollary
3785 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3791 \begin_layout BeginFrame
3793 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3799 \begin_layout Standard
3803 \begin_layout Plain Layout
3815 \begin_layout Columns
3819 \begin_layout Plain Layout
3830 \begin_layout Column
3834 \begin_layout Standard
3838 \begin_layout Plain Layout
3856 \begin_layout Plain Layout
3864 \begin_inset Formula $\Lang{reach}$
3868 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3875 \begin_layout Plain Layout
3886 \begin_layout Enumerate
3890 \begin_layout Plain Layout
3898 \begin_inset Formula $(G,s,t)$
3902 \begin_inset Formula $\Lang{reach}$
3908 \begin_layout Enumerate
3912 \begin_layout Plain Layout
3920 \begin_inset Formula $G$
3924 \begin_inset Formula $G'$
3930 \begin_layout Enumerate
3934 \begin_layout Plain Layout
3942 \begin_inset Newline newline
3946 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3953 \begin_layout Separator
3961 \begin_layout Plain Layout
3972 \begin_layout Plain Layout
3983 \begin_layout Plain Layout
3994 \begin_layout Enumerate
3998 \begin_layout Plain Layout
4006 \begin_inset space ~
4010 \begin_inset Formula $G$
4014 \begin_inset Newline newline
4018 \begin_inset space ~
4022 \begin_inset Formula $G'$
4028 \begin_layout Enumerate
4032 \begin_layout Plain Layout
4040 \begin_inset space ~
4044 \begin_inset Formula $G'$
4048 \begin_inset Newline newline
4052 \begin_inset space ~
4056 \begin_inset Formula $G'$
4063 \begin_layout Column
4067 \begin_layout Example
4071 \begin_layout Plain Layout
4075 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
4078 \begin_layout Plain Layout
4082 \begin_layout Plain Layout
4086 color{beamerexample}
4089 \begin_layout Plain Layout
4093 \begin_layout Plain Layout
4097 pgfsetlinewidth{0.6pt}
4100 \begin_layout Plain Layout
4104 \begin_layout Plain Layout
4113 \begin_layout Plain Layout
4117 \begin_layout Plain Layout
4126 \begin_layout Plain Layout
4130 \begin_layout Plain Layout
4139 \begin_layout Plain Layout
4143 \begin_layout Plain Layout
4152 \begin_layout Plain Layout
4156 \begin_layout Plain Layout
4160 \begin_layout Plain Layout
4164 \begin_layout Plain Layout
4171 \begin_layout Plain Layout
4175 \begin_layout Plain Layout
4183 pgfbox[center,center]{$s$}}
4186 \begin_layout Plain Layout
4190 \begin_layout Plain Layout
4198 pgfbox[center,center]{$t$}}
4201 \begin_layout Plain Layout
4205 \begin_layout Plain Layout
4209 \begin_layout Plain Layout
4213 \begin_layout Plain Layout
4217 color{beamerexample}
4220 \begin_layout Plain Layout
4224 \begin_layout Plain Layout
4233 \begin_layout Plain Layout
4237 \begin_layout Plain Layout
4241 pgfnodesetsepstart{2pt}
4244 \begin_layout Plain Layout
4248 \begin_layout Plain Layout
4252 pgfnodesetsepend{2pt}
4255 \begin_layout Plain Layout
4259 \begin_layout Plain Layout
4265 pgfnodeconnline{B}{A}}
4268 \begin_layout Plain Layout
4272 \begin_layout Plain Layout
4278 pgfnodeconnline{B}{C}}
4281 \begin_layout Plain Layout
4285 \begin_layout Plain Layout
4291 pgfnodeconnline{C}{D}}
4294 \begin_layout Plain Layout
4298 \begin_layout Plain Layout
4304 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4307 \begin_layout Plain Layout
4311 \begin_layout Plain Layout
4316 \begin_layout Plain Layout
4320 \begin_layout Plain Layout
4328 pgfbox[left,center]{$G
4333 \begin_layout Plain Layout
4337 \begin_layout Plain Layout
4341 \begin_layout Plain Layout
4345 \begin_layout Plain Layout
4352 \begin_layout Plain Layout
4356 \begin_layout Plain Layout
4364 pgfbox[left,center]{$G'
4369 \begin_layout Plain Layout
4373 \begin_layout Plain Layout
4382 \begin_layout Plain Layout
4386 \begin_layout Plain Layout
4395 \begin_layout Plain Layout
4399 \begin_layout Plain Layout
4408 \begin_layout Plain Layout
4412 \begin_layout Plain Layout
4421 \begin_layout Plain Layout
4425 \begin_layout Plain Layout
4429 \begin_layout Plain Layout
4433 \begin_layout Plain Layout
4442 \begin_layout Plain Layout
4446 \begin_layout Plain Layout
4455 \begin_layout Plain Layout
4459 \begin_layout Plain Layout
4468 \begin_layout Plain Layout
4472 \begin_layout Plain Layout
4481 \begin_layout Plain Layout
4485 \begin_layout Plain Layout
4494 \begin_layout Plain Layout
4498 \begin_layout Plain Layout
4507 \begin_layout Plain Layout
4511 \begin_layout Plain Layout
4520 \begin_layout Plain Layout
4524 \begin_layout Plain Layout
4533 \begin_layout Plain Layout
4537 \begin_layout Plain Layout
4546 \begin_layout Plain Layout
4550 \begin_layout Plain Layout
4559 \begin_layout Plain Layout
4563 \begin_layout Plain Layout
4572 \begin_layout Plain Layout
4576 \begin_layout Plain Layout
4585 \begin_layout Plain Layout
4589 \begin_layout Plain Layout
4596 \begin_layout Plain Layout
4600 \begin_layout Plain Layout
4608 pgfbox[center,center]{$s'$}}
4611 \begin_layout Plain Layout
4615 \begin_layout Plain Layout
4623 pgfbox[center,center]{$t'$}}
4626 \begin_layout Plain Layout
4630 \begin_layout Plain Layout
4635 \begin_layout Plain Layout
4639 \begin_layout Plain Layout
4644 \begin_layout Plain Layout
4648 \begin_layout Plain Layout
4655 \begin_layout Plain Layout
4659 \begin_layout Plain Layout
4663 pgfsetlinewidth{0.4pt}
4666 \begin_layout Plain Layout
4670 \begin_layout Plain Layout
4674 color{beamerexample!25!averagebackgroundcolor}
4677 \begin_layout Plain Layout
4681 \begin_layout Plain Layout
4685 pgfnodeconnline{A2}{C1}
4688 \begin_layout Plain Layout
4692 \begin_layout Plain Layout
4696 pgfnodeconnline{A2}{D1}
4699 \begin_layout Plain Layout
4703 \begin_layout Plain Layout
4707 pgfnodeconnline{B2}{A1}
4710 \begin_layout Plain Layout
4714 \begin_layout Plain Layout
4718 pgfnodeconnline{B2}{C1}
4721 \begin_layout Plain Layout
4725 \begin_layout Plain Layout
4729 pgfnodeconnline{B2}{D1}
4732 \begin_layout Plain Layout
4736 \begin_layout Plain Layout
4740 pgfnodeconnline{C2}{D1}
4743 \begin_layout Plain Layout
4747 \begin_layout Plain Layout
4751 pgfnodeconnline{D2}{A1}
4754 \begin_layout Plain Layout
4758 \begin_layout Plain Layout
4762 pgfnodeconnline{D2}{B1}
4765 \begin_layout Plain Layout
4769 \begin_layout Plain Layout
4773 pgfnodeconnline{A3}{C2}
4776 \begin_layout Plain Layout
4780 \begin_layout Plain Layout
4784 pgfnodeconnline{A3}{D2}
4787 \begin_layout Plain Layout
4791 \begin_layout Plain Layout
4795 pgfnodeconnline{B3}{A2}
4798 \begin_layout Plain Layout
4802 \begin_layout Plain Layout
4806 pgfnodeconnline{B3}{C2}
4809 \begin_layout Plain Layout
4813 \begin_layout Plain Layout
4817 pgfnodeconnline{B3}{D2}
4820 \begin_layout Plain Layout
4824 \begin_layout Plain Layout
4828 pgfnodeconnline{C3}{D2}
4831 \begin_layout Plain Layout
4835 \begin_layout Plain Layout
4839 pgfnodeconnline{D3}{A2}
4842 \begin_layout Plain Layout
4846 \begin_layout Plain Layout
4850 pgfnodeconnline{D3}{B2}
4853 \begin_layout Plain Layout
4857 \begin_layout Plain Layout
4861 pgfnodeconnline{A4}{C3}
4864 \begin_layout Plain Layout
4868 \begin_layout Plain Layout
4872 pgfnodeconnline{A4}{D3}
4875 \begin_layout Plain Layout
4879 \begin_layout Plain Layout
4883 pgfnodeconnline{B4}{A3}
4886 \begin_layout Plain Layout
4890 \begin_layout Plain Layout
4894 pgfnodeconnline{B4}{C3}
4897 \begin_layout Plain Layout
4901 \begin_layout Plain Layout
4905 pgfnodeconnline{B4}{D3}
4908 \begin_layout Plain Layout
4912 \begin_layout Plain Layout
4916 pgfnodeconnline{C4}{D3}
4919 \begin_layout Plain Layout
4923 \begin_layout Plain Layout
4927 pgfnodeconnline{D4}{A3}
4930 \begin_layout Plain Layout
4934 \begin_layout Plain Layout
4938 pgfnodeconnline{D4}{B3}
4941 \begin_layout Plain Layout
4945 \begin_layout Plain Layout
4949 \begin_layout Plain Layout
4953 \begin_layout Plain Layout
4962 \begin_layout Plain Layout
4966 \begin_layout Plain Layout
4970 pgfnodeconnline{A1}{B1}
4973 \begin_layout Plain Layout
4977 \begin_layout Plain Layout
4981 pgfnodeconnline{B1}{C1}
4984 \begin_layout Plain Layout
4988 \begin_layout Plain Layout
4992 pgfnodeconnline{C1}{D1}
4995 \begin_layout Plain Layout
4999 \begin_layout Plain Layout
5003 pgfnodeconnline{A2}{B2}
5006 \begin_layout Plain Layout
5010 \begin_layout Plain Layout
5014 pgfnodeconnline{B2}{C2}
5017 \begin_layout Plain Layout
5021 \begin_layout Plain Layout
5025 pgfnodeconnline{C2}{D2}
5028 \begin_layout Plain Layout
5032 \begin_layout Plain Layout
5036 pgfnodeconnline{A3}{B3}
5039 \begin_layout Plain Layout
5043 \begin_layout Plain Layout
5047 pgfnodeconnline{B3}{C3}
5050 \begin_layout Plain Layout
5054 \begin_layout Plain Layout
5058 pgfnodeconnline{C3}{D3}
5061 \begin_layout Plain Layout
5065 \begin_layout Plain Layout
5069 pgfnodeconnline{A4}{B4}
5072 \begin_layout Plain Layout
5076 \begin_layout Plain Layout
5080 pgfnodeconnline{B4}{C4}
5083 \begin_layout Plain Layout
5087 \begin_layout Plain Layout
5091 pgfnodeconnline{C4}{D4}
5094 \begin_layout Plain Layout
5098 \begin_layout Plain Layout
5102 \begin_layout Plain Layout
5106 \begin_layout Plain Layout
5113 \begin_layout Plain Layout
5117 \begin_layout Plain Layout
5121 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
5124 \begin_layout Plain Layout
5128 \begin_layout Plain Layout
5132 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
5135 \begin_layout Plain Layout
5139 \begin_layout Plain Layout
5143 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
5146 \begin_layout Plain Layout
5150 \begin_layout Plain Layout
5154 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
5157 \begin_layout Plain Layout
5161 \begin_layout Plain Layout
5165 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
5168 \begin_layout Plain Layout
5172 \begin_layout Plain Layout
5176 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
5179 \begin_layout Plain Layout
5183 \begin_layout Plain Layout
5187 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
5190 \begin_layout Plain Layout
5194 \begin_layout Plain Layout
5198 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
5201 \begin_layout Plain Layout
5205 \begin_layout Plain Layout
5209 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
5212 \begin_layout Plain Layout
5216 \begin_layout Plain Layout
5220 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
5223 \begin_layout Plain Layout
5227 \begin_layout Plain Layout
5231 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
5234 \begin_layout Plain Layout
5238 \begin_layout Plain Layout
5242 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
5245 \begin_layout Plain Layout
5249 \begin_layout Plain Layout
5253 color{beamerexample}
5256 \begin_layout Plain Layout
5260 \begin_layout Plain Layout
5264 pgfsetlinewidth{0.6pt}
5267 \begin_layout Plain Layout
5271 \begin_layout Plain Layout
5276 \begin_layout Plain Layout
5280 \begin_layout Plain Layout
5284 \begin_layout Plain Layout
5288 \begin_layout Plain Layout
5295 \begin_layout Plain Layout
5299 \begin_layout Plain Layout
5306 \begin_layout Plain Layout
5310 \begin_layout Plain Layout
5314 pgfnodeconnline{B1}{A2}
5317 \begin_layout Plain Layout
5321 \begin_layout Plain Layout
5325 pgfnodeconnline{B2}{A3}
5328 \begin_layout Plain Layout
5332 \begin_layout Plain Layout
5336 pgfnodeconnline{B3}{A4}
5339 \begin_layout Plain Layout
5343 \begin_layout Plain Layout
5348 \begin_layout Plain Layout
5352 \begin_layout Plain Layout
5356 \begin_layout Plain Layout
5360 \begin_layout Plain Layout
5367 \begin_layout Plain Layout
5371 \begin_layout Plain Layout
5378 \begin_layout Plain Layout
5382 \begin_layout Plain Layout
5386 pgfnodeconnline{B1}{C2}
5389 \begin_layout Plain Layout
5393 \begin_layout Plain Layout
5397 pgfnodeconnline{B2}{C3}
5400 \begin_layout Plain Layout
5404 \begin_layout Plain Layout
5408 pgfnodeconnline{B3}{C4}
5411 \begin_layout Plain Layout
5415 \begin_layout Plain Layout
5420 \begin_layout Plain Layout
5424 \begin_layout Plain Layout
5429 \begin_layout Plain Layout
5433 \begin_layout Plain Layout
5440 \begin_layout Plain Layout
5444 \begin_layout Plain Layout
5451 \begin_layout Plain Layout
5455 \begin_layout Plain Layout
5459 pgfnodeconnline{C1}{D2}
5462 \begin_layout Plain Layout
5466 \begin_layout Plain Layout
5472 pgfnodeconnline{C2}{D3}}
5475 \begin_layout Plain Layout
5479 \begin_layout Plain Layout
5485 pgfnodeconnline{C3}{D4}}
5488 \begin_layout Plain Layout
5492 \begin_layout Plain Layout
5497 \begin_layout Plain Layout
5501 \begin_layout Plain Layout
5506 \begin_layout Plain Layout
5510 \begin_layout Plain Layout
5517 \begin_layout Plain Layout
5521 \begin_layout Plain Layout
5528 \begin_layout Plain Layout
5532 \begin_layout Plain Layout
5538 pgfnodeconnline{A1}{C2}}
5541 \begin_layout Plain Layout
5545 \begin_layout Plain Layout
5551 pgfnodeconnline{A2}{C3}}
5554 \begin_layout Plain Layout
5558 \begin_layout Plain Layout
5562 pgfnodeconnline{A3}{C4}
5565 \begin_layout Plain Layout
5569 \begin_layout Plain Layout
5574 \begin_layout Plain Layout
5578 \begin_layout Plain Layout
5582 \begin_layout Plain Layout
5586 \begin_layout Plain Layout
5593 \begin_layout Plain Layout
5597 \begin_layout Plain Layout
5604 \begin_layout Plain Layout
5608 \begin_layout Plain Layout
5614 pgfnodeconnline{A1}{A2}}
5617 \begin_layout Plain Layout
5621 \begin_layout Plain Layout
5625 pgfnodeconnline{A2}{A3}
5628 \begin_layout Plain Layout
5632 \begin_layout Plain Layout
5636 pgfnodeconnline{A3}{A4}
5639 \begin_layout Plain Layout
5643 \begin_layout Plain Layout
5647 pgfnodeconnline{B1}{B2}
5650 \begin_layout Plain Layout
5654 \begin_layout Plain Layout
5658 pgfnodeconnline{B2}{B3}
5661 \begin_layout Plain Layout
5665 \begin_layout Plain Layout
5669 pgfnodeconnline{B3}{B4}
5672 \begin_layout Plain Layout
5676 \begin_layout Plain Layout
5680 pgfnodeconnline{C1}{C2}
5683 \begin_layout Plain Layout
5687 \begin_layout Plain Layout
5691 pgfnodeconnline{C2}{C3}
5694 \begin_layout Plain Layout
5698 \begin_layout Plain Layout
5702 pgfnodeconnline{C3}{C4}
5705 \begin_layout Plain Layout
5709 \begin_layout Plain Layout
5713 pgfnodeconnline{D1}{D2}
5716 \begin_layout Plain Layout
5720 \begin_layout Plain Layout
5724 pgfnodeconnline{D2}{D3}
5727 \begin_layout Plain Layout
5731 \begin_layout Plain Layout
5737 pgfnodeconnline{D3}{D4}}
5740 \begin_layout Plain Layout
5744 \begin_layout Plain Layout
5749 \begin_layout Plain Layout
5753 \begin_layout Plain Layout
5766 \begin_layout AgainFrame
5770 \begin_layout Plain Layout
5780 \begin_layout Subsection
5781 Complexity of: Approximating the Shortest Path
5784 \begin_layout BeginFrame
5785 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5788 \begin_layout Definition
5793 approximation scheme for
5794 \begin_inset Formula $\Lang{tournament-shortest-path}$
5805 \begin_layout Enumerate
5807 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5813 \begin_layout Enumerate
5815 \begin_inset Formula $r>1$
5821 \begin_layout Standard
5825 \begin_layout Itemize
5827 \begin_inset Formula $s$
5831 \begin_inset space ~
5835 \begin_inset Formula $t$
5839 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5846 \begin_layout BeginFrame
5847 There Exists a Logspace Approximation Scheme for
5848 \begin_inset Newline newline
5851 the Tournament Shortest Path Problem
5854 \begin_layout Theorem
5855 There exists an approximation scheme for
5856 \begin_inset Formula $\Lang{tournament-shortest-path}$
5860 \begin_inset Formula $1<r<2$
5864 \begin_inset Formula \[
5865 O\left(\log|V|\log\frac{1}{r-1}\right).\]
5876 \begin_layout Corollary
5877 In tournaments, paths can be constructed in logarithmic space.
5880 \begin_layout Standard
5881 \begin_inset space \hfill{}
5888 \begin_layout Plain Layout
5892 hyperlink{optimality}{
5894 beamergotobutton{More Details}}
5902 \begin_layout AgainFrame
5906 \begin_layout Plain Layout
5916 \begin_layout Section*
5920 \begin_layout Subsection*
5924 \begin_layout BeginFrame
5932 \begin_layout Plain Layout
5943 \begin_layout Itemize
5957 \begin_inset Formula $\Class{AC}^{0}$
5966 \begin_layout Itemize
5971 logspace approximation scheme
5983 shortest paths in tournaments.
5986 \begin_layout Itemize
6000 \begin_inset Formula $\Class{NL}$
6009 \begin_layout Separator
6017 \begin_layout Plain Layout
6028 \begin_layout Itemize
6029 The same results apply to graphs with
6030 \begin_inset Newline newline
6033 bounded independence number.
6034 \begin_inset space \hfill{}
6041 \begin_layout Plain Layout
6045 hyperlink{independence}{
6047 beamergotobutton{More Details}}
6055 \begin_layout Itemize
6056 The complexity of finding paths in undirected graphs
6057 \begin_inset Newline newline
6061 \begin_inset space \hfill{}
6068 \begin_layout Plain Layout
6072 hyperlink{undirected}{
6074 beamergotobutton{More Details}}
6083 \begin_layout Subsection*
6087 \begin_layout BeginFrame
6091 \begin_layout Standard
6095 \begin_layout Plain Layout
6099 beamertemplatebookbibitems
6107 \begin_layout Bibliography
6108 \begin_inset CommandInset bibitem
6109 LatexCommand bibitem
6115 \begin_inset space ~
6123 \begin_layout Plain Layout
6134 Topics on Tournaments.
6141 \begin_layout Plain Layout
6150 Holt, Rinehart, and Winston, 1968.
6155 \begin_layout Plain Layout
6159 beamertemplatearticlebibitems
6167 \begin_layout Bibliography
6168 \begin_inset CommandInset bibitem
6169 LatexCommand bibitem
6170 key "NickelsenT2002"
6175 \begin_inset space ~
6178 Arfst Nickelsen and Till Tantau.
6183 \begin_layout Plain Layout
6192 On reachability in graphs with bounded independence number.
6196 \begin_layout Plain Layout
6210 , Springer-Verlag, 2002.
6213 \begin_layout Bibliography
6214 \begin_inset CommandInset bibitem
6215 LatexCommand bibitem
6221 \begin_inset space ~
6228 \begin_layout Plain Layout
6237 A logspace approximation scheme for the shortest path problem for graphs
6238 with bounded independence number.
6242 \begin_layout Plain Layout
6256 , Springer-Verlag, 2004.
6261 \begin_layout Plain Layout
6273 \begin_layout EndFrame
6277 \begin_layout Standard
6282 \begin_layout Plain Layout
6286 AtBeginSubsection[]{}
6294 \begin_layout Section
6298 \begin_layout Subsection
6299 Graphs With Bounded Independence Number
6302 \begin_layout BeginFrame
6306 \begin_layout Plain Layout
6308 [label=independence]
6313 Definition of Independence Number of a Graph
6316 \begin_layout Definition
6326 \begin_inset Formula $\alpha(G)$
6330 \begin_inset Newline newline
6333 is the maximum number of vertices we can pick,
6334 \begin_inset Newline newline
6337 such that there is no edge between them.
6340 \begin_layout Example
6341 Tournaments have independence number 1.
6345 \begin_layout BeginFrame
6346 The Results for Tournaments also Apply to
6347 \begin_inset Newline newline
6350 Graphs With Bounded Independence Number
6353 \begin_layout Theorem
6355 \begin_inset space ~
6359 \begin_inset Formula $k$
6370 in graphs with independence number
6371 \begin_inset Newline newline
6375 \begin_inset space ~
6379 \begin_inset Formula $k$
6383 \begin_inset Formula $\Class{AC}^{0}$
6389 \begin_layout Separator
6393 \begin_layout Theorem
6395 \begin_inset space ~
6399 \begin_inset Formula $k$
6406 logspace approximation scheme
6410 for approximating the shortest path in graphs with independence number at
6412 \begin_inset space ~
6416 \begin_inset Formula $k$
6422 \begin_layout Separator
6426 \begin_layout Theorem
6428 \begin_inset space ~
6432 \begin_inset Formula $k$
6443 in graphs with independence number at most
6444 \begin_inset space ~
6448 \begin_inset Formula $k$
6456 \begin_inset Formula $\Class{NL}$
6464 \begin_layout Subsection
6465 Finding Paths in Undirected Graphs
6468 \begin_layout BeginFrame
6472 \begin_layout Plain Layout
6474 <1-2>[label=undirected]
6479 The Complexity of Finding Paths in Undirected Graphs
6480 \begin_inset Newline newline
6487 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6491 \begin_inset Formula $\Class{SL}$
6497 \begin_layout Corollary
6498 For undirected graphs, we can solve
6502 \begin_layout Itemize
6503 the reachability problem in logspace iff
6504 \begin_inset Formula $\Class L=\Class{SL}$
6510 \begin_layout Itemize
6511 the construction problem in logspace iff
6515 \begin_layout Plain Layout
6533 \begin_layout Itemize
6534 the optimization problem in logspace iff
6538 \begin_layout Plain Layout
6556 \begin_layout Itemize
6557 the approximation problem in logspace iff ?.
6562 \begin_layout Subsection
6563 The Approximation Scheme is Optimal
6566 \begin_layout BeginFrame
6570 \begin_layout Plain Layout
6577 The Approximation Scheme is Optimal
6580 \begin_layout Theorem
6581 Suppose there exists an approximation scheme for
6582 \begin_inset Formula $\Lang{tournament-shortest-path}$
6586 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6591 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6602 \begin_layout Enumerate
6603 Suppose the approximation scheme exists.
6604 \begin_inset Newline newline
6608 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6615 \begin_layout Enumerate
6617 \begin_inset Formula $(T,s,t)$
6622 \begin_inset Formula $n$
6625 be the number of vertices.
6628 \begin_layout Enumerate
6629 Run the approximation scheme for
6630 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6634 \begin_inset Newline newline
6638 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6644 \begin_layout Enumerate
6645 The resulting path has optimal length.
6650 \begin_layout Plain Layout
6663 \begin_layout EndFrame