#LyX 1.3 created this file. For more info see http://www.lyx.org/ \lyxformat 221 \textclass beamer \begin_preamble \beamertemplateshadingbackground{red!5}{structure!5} \usepackage{beamerthemeshadow} \usepackage{pgfnodes,pgfarrows,pgfheaps} \beamertemplatetransparentcovereddynamicmedium \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo} \logo{\pgfuseimage{icsi-logo}} \newcommand{\Class}[1]{\operatorname{\mathchoice {\text{\small #1}} {\text{\small #1}} {\text{#1}} {\text{#1}}}} \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}} \newcommand{\tape}[3]{% \color{structure!30!averagebackgroundcolor} \pgfmoveto{\pgfxy(-0.5,0)} \pgflineto{\pgfxy(-0.6,0.1)} \pgflineto{\pgfxy(-0.4,0.2)} \pgflineto{\pgfxy(-0.6,0.3)} \pgflineto{\pgfxy(-0.4,0.4)} \pgflineto{\pgfxy(-0.5,0.5)} \pgflineto{\pgfxy(4,0.5)} \pgflineto{\pgfxy(4.1,0.4)} \pgflineto{\pgfxy(3.9,0.3)} \pgflineto{\pgfxy(4.1,0.2)} \pgflineto{\pgfxy(3.9,0.1)} \pgflineto{\pgfxy(4,0)} \pgfclosepath \pgffill \color{structure} \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}} \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}} \color{black} \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}% } \newcommand{\shorttape}[3]{% \color{structure!30!averagebackgroundcolor} \pgfmoveto{\pgfxy(-0.5,0)} \pgflineto{\pgfxy(-0.6,0.1)} \pgflineto{\pgfxy(-0.4,0.2)} \pgflineto{\pgfxy(-0.6,0.3)} \pgflineto{\pgfxy(-0.4,0.4)} \pgflineto{\pgfxy(-0.5,0.5)} \pgflineto{\pgfxy(1,0.5)} \pgflineto{\pgfxy(1.1,0.4)} \pgflineto{\pgfxy(0.9,0.3)} \pgflineto{\pgfxy(1.1,0.2)} \pgflineto{\pgfxy(0.9,0.1)} \pgflineto{\pgfxy(1,0)} \pgfclosepath \pgffill \color{structure} \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}} \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}} \color{black} \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}% } \pgfdeclareverticalshading{heap1}{\the\paperwidth}% {color(0pt)=(black); color(1cm)=(structure!65!white)} \pgfdeclareverticalshading{heap2}{\the\paperwidth}% {color(0pt)=(black); color(1cm)=(structure!55!white)} \pgfdeclareverticalshading{heap3}{\the\paperwidth}% {color(0pt)=(black); color(1cm)=(structure!45!white)} \pgfdeclareverticalshading{heap4}{\the\paperwidth}% {color(0pt)=(black); color(1cm)=(structure!35!white)} \pgfdeclareverticalshading{heap5}{\the\paperwidth}% {color(0pt)=(black); color(1cm)=(structure!25!white)} \pgfdeclareverticalshading{heap6}{\the\paperwidth}% {color(0pt)=(black); color(1cm)=(red!35!white)} \newcommand{\heap}[5]{% \begin{pgfscope} \color{#4} \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)} \pgfclip \begin{pgfmagnify}{1}{#1} \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}} \end{pgfmagnify} \end{pgfscope} %\pgffill \color{#4} \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)} \pgfstroke \color{white} \pgfheaplabel{\pgfxy(0,#1)}{#3}% } \newcommand{\langat}[2]{% \color{black!30!beamerexample} \pgfsetlinewidth{0.6pt} \pgfsetendarrow{\pgfarrowdot} \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)} \color{beamerexample} \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}% } \newcommand{\langatother}[2]{% \color{black!30!beamerexample} \pgfsetlinewidth{0.6pt} \pgfsetendarrow{\pgfarrowdot} \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)} \color{beamerexample} \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}% } \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} \pgfdeclareradialshading{graphnode} {\pgfpoint{-3pt}{3.6pt}}% {color(0cm)=(beamerexample!15); color(2.63pt)=(beamerexample!75); color(5.26pt)=(beamerexample!70!black); color(7.6pt)=(beamerexample!50!black); color(8pt)=(beamerexample!10!averagebackgroundcolor)} \newcommand{\graphnode}[2]{ \pgfnodecircle{#1}[virtual]{#2}{8pt} \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}} } \end_preamble \options notes=show \language english \inputencoding auto \fontscheme times \graphics default \paperfontsize default \spacing single \papersize Default \paperpackage a4 \use_geometry 0 \use_amsmath 1 \use_natbib 0 \use_numerical_citations 0 \paperorientation portrait \secnumdepth 2 \tocdepth 2 \paragraph_separation indent \defskip medskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 1 \paperpagestyle default \layout Title The Complexity of \newline Finding Paths in Tournaments \layout Author Till Tantau \layout Institute International Computer Schience Institute \newline Berkeley, California \begin_inset OptArg collapsed true \layout Standard ICSI \end_inset \layout Date January 30th, 2004 \layout BeginFrame Outline \layout Standard \begin_inset LatexCommand \tableofcontents{} \end_inset \begin_inset ERT status Collapsed \layout Standard [pausesections] \end_inset \layout EndFrame \layout Standard \begin_inset ERT status Collapsed \layout Standard % Show the table of contents at the beginning \layout Standard % of every subsection. \layout Standard \backslash AtBeginSubsection[]{ \layout Standard \backslash frame{ \layout Standard \backslash frametitle{Outline} \layout Standard \backslash tableofcontents[current,currentsubsection] \layout Standard } \layout Standard } \end_inset \layout Section Introduction \layout Subsection What are Tournaments? \layout BeginFrame Tournaments Consist of Jousts Between Knights \layout Columns \begin_deeper \layout Column 5.75cm \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm} \layout Standard \backslash pgfnodebox{A}[virtual]{ \backslash pgfxy(2,1)}{ \backslash pgfuseimage{knight1}}{2pt}{2pt} \layout Standard \backslash pgfnodebox{B}[virtual]{ \backslash pgfxy(6,1)}{ \backslash pgfuseimage{knight2}}{2pt}{2pt} \layout Standard \backslash pgfnodebox{C}[virtual]{ \backslash pgfxy(4,-1)}{ \backslash pgfuseimage{knight3}}{2pt}{2pt} \layout Standard \backslash pgfnodebox{D}[virtual]{ \backslash pgfxy(4,3)}{ \backslash pgfuseimage{knight4}}{2pt}{2pt} \layout Standard \layout Standard \backslash color{beamerexample} \layout Standard \backslash only<3->{ \backslash pgfsetendarrow{ \backslash pgfarrowto}} \layout Standard \backslash only<2->{ \layout Standard \backslash pgfsetlinewidth{0.6pt} \layout Standard \backslash pgfnodeconnline{A}{B} \layout Standard \backslash pgfnodeconnline{A}{C} \layout Standard \backslash pgfnodeconnline{D}{A} \layout Standard \backslash pgfnodeconnline{C}{B} \layout Standard \backslash pgfnodeconnline{B}{D} \layout Standard \backslash pgfnodeconnline{C}{D}} \layout Standard \backslash end{pgfpicture} \end_inset \layout Column 6cm \layout Block \begin_inset ERT status Inlined \layout Standard {What is a Tournament?} \end_inset \begin_deeper \layout Itemize \begin_inset ERT status Collapsed \layout Standard <1-> \end_inset A group of knights. \layout Itemize \begin_inset ERT status Collapsed \layout Standard <2-> \end_inset Every pair has a joust. \layout Itemize \begin_inset ERT status Collapsed \layout Standard <3-> \end_inset In every joust one knight wins. \end_deeper \end_deeper \layout BeginFrame Tournaments are Complete Directed Graphs \layout Columns \begin_deeper \layout Column 5cm \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm} \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetlinewidth{0.6pt} \layout Standard \backslash graphnode{A}{ \backslash pgfxy(2.5,1)} \layout Standard \backslash graphnode{B}{ \backslash pgfxy(5.5,1)} \layout Standard \backslash graphnode{C}{ \backslash pgfxy(4,-0.5)} \layout Standard \backslash graphnode{D}{ \backslash pgfxy(4,2.5)} \layout Standard \layout Standard \backslash color{white} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{A}}{ \backslash pgfbox[center,center]{$v_2$}} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{B}}{ \backslash pgfbox[center,center]{$v_3$}} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{C}}{ \backslash pgfbox[center,center]{$v_4$}} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{D}}{ \backslash pgfbox[center,center]{$v_1$}} \layout Standard \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetendarrow{ \backslash pgfarrowto} \layout Standard \backslash pgfnodesetsepstart{2pt} \layout Standard \backslash pgfnodesetsepend{4pt} \layout Standard \backslash pgfnodeconnline{A}{B} \layout Standard \backslash pgfnodeconnline{A}{C} \layout Standard \backslash pgfnodeconnline{D}{A} \layout Standard \backslash pgfnodeconnline{C}{B} \layout Standard \backslash pgfnodeconnline{B}{D} \layout Standard \backslash pgfnodeconnline{D}{C} \layout Standard \backslash end{pgfpicture} \end_inset \layout Column 6cm \layout Definition \begin_inset ERT status Collapsed \layout Standard <2-> \end_inset A \color red tournament \color default is a \begin_deeper \layout Enumerate directed graphs, \layout Enumerate with exactly one edge between \newline any two different vertices. \end_deeper \end_deeper \layout BeginFrame \begin_inset ERT status Collapsed \layout Standard [<+>] \end_inset Tournaments Arise Naturally in Different Situations \layout ExampleBlock \begin_inset ERT status Inlined \layout Standard {Applicatins in Ordering Theory} \end_inset \begin_deeper \layout Standard Elements in a set need to be sorted. \newline The comparison relation may be cyclic, however. \end_deeper \layout Separator \layout ExampleBlock \begin_inset ERT status Inlined \layout Standard {Applications in Sociology} \end_inset \begin_deeper \layout Standard Several candidates apply for a position. \newline Reviewers decide for any two candidates whom they prefer. \end_deeper \layout Separator \layout ExampleBlock \begin_inset ERT status Inlined \layout Standard {Applications in Structural Complexity Theory} \end_inset \begin_deeper \layout Standard A language \begin_inset Formula $L$ \end_inset is given and a selector function \begin_inset Formula $f$ \end_inset . \newline It chooses from any two words the one more likely to be in \begin_inset Formula $f$ \end_inset . \end_deeper \layout Subsection What Does ``Finding Paths'' Mean? \layout BeginFrame ``Finding Paths'' is Ambiguous \layout Block \begin_inset ERT status Inlined \layout Standard { \backslash strut Input for \backslash ignorespaces \backslash def \backslash par{}% because LyX inserts superfluous paragraphs \layout Standard \backslash only<1>{Path Finding Problems} \backslash ignorespaces \layout Standard \backslash only<2-3>{$ \backslash Lang{reach}$} \backslash ignorespaces \layout Standard \backslash only<4-5>{the Construction Problem} \backslash ignorespaces \layout Standard \backslash only<6-7>{the Optimization Problem} \backslash ignorespaces \layout Standard \backslash only<8-9>{$ \backslash Lang{distance}$} \backslash ignorespaces \layout Standard \backslash only<10->{the Approximation Problem}} \end_inset \begin_deeper \layout Itemize A \color red graph \color default \begin_inset Formula $G=(V,E)$ \end_inset , a \color red source \color default \begin_inset Formula $s\in V$ \end_inset and a \color red target \color default \begin_inset Formula $t\in V$ \end_inset . \layout Itemize \begin_inset ERT status Collapsed \layout Standard \end_inset A \color red maximum distance \color default \SpecialChar ~ \begin_inset Formula $d$ \end_inset . \begin_inset ERT status Collapsed \layout Standard \backslash phantom{p} \end_inset \layout Itemize \begin_inset ERT status Collapsed \layout Standard \end_inset An \color red approximation ratio \color default \begin_inset Formula $r>1$ \end_inset . \end_deeper \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash nointerlineskip \end_inset \layout Overprint \begin_deeper \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash onslide<1,3,5,7,9,11-12> \end_inset \layout Columns \begin_inset ERT status Inlined \layout Standard [t,onlytextwidth] \end_inset \begin_deeper \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash alt<1-2>{ \backslash column{ \backslash textwidth}}{ \backslash column{5cm}} \end_inset \layout ExampleBlock \begin_inset ERT status Inlined \layout Standard {Example Input} \end_inset \begin_deeper \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetlinewidth{0.6pt} \layout Standard \backslash graphnode{A}{ \backslash pgfxy(3,1)} \layout Standard \backslash graphnode{B}{ \backslash pgfxy(5,1)} \layout Standard \backslash graphnode{C}{ \backslash pgfxy(4,0)} \layout Standard \backslash graphnode{D}{ \backslash pgfxy(4,2)} \layout Standard \layout Standard \backslash color{white} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{B}}{ \backslash pgfbox[center,center]{$t$}} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{D}}{ \backslash pgfbox[center,center]{$s$}} \layout Standard \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetendarrow{ \backslash pgfarrowto} \layout Standard \backslash pgfnodesetsepstart{2pt} \layout Standard \backslash pgfnodesetsepend{4pt} \layout Standard \backslash pgfnodeconnline{A}{B} \layout Standard \backslash pgfnodeconnline{A}{C} \layout Standard \backslash pgfnodeconnline{D}{A} \layout Standard \backslash pgfnodeconnline{C}{B} \layout Standard \backslash pgfnodeconnline{B}{D} \layout Standard \backslash pgfnodeconnline{D}{C} \layout Standard \layout Standard \backslash only<9> { \backslash pgfputat{ \backslash pgfxy(5.3,1)}{ \backslash pgfbox[left,center]{, $d=2$}}} \layout Standard \backslash only<11>{ \backslash pgfputat{ \backslash pgfxy(5.3,1)}{ \backslash pgfbox[left,center]{, $r=1.5$}}} \layout Standard \backslash only<12>{ \backslash pgfputat{ \backslash pgfxy(5.3,1)}{ \backslash pgfbox[left,center]{, $r=1.25$}}} \layout Standard \backslash end{pgfpicture} \end_inset \end_deeper \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash only<3->{ \backslash column{5cm}} \end_inset \layout ExampleBlock \begin_inset ERT status Inlined \layout Standard {Example Output} \end_inset \begin_deeper \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} \layout Standard \backslash only<5-8,10->{ \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetlinewidth{0.6pt} \layout Standard \backslash graphnode{A}{ \backslash pgfxy(3,1)} \layout Standard \backslash graphnode{B}{ \backslash pgfxy(5,1)} \layout Standard \backslash graphnode{C}{ \backslash pgfxy(4,0)} \layout Standard \backslash graphnode{D}{ \backslash pgfxy(4,2)} \layout Standard \layout Standard \backslash color{white} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{B}}{ \backslash pgfbox[center,center]{$t$}} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{D}}{ \backslash pgfbox[center,center]{$s$}} \layout Standard \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetendarrow{ \backslash pgfarrowto} \layout Standard \backslash pgfnodesetsepstart{2pt} \layout Standard \backslash pgfnodesetsepend{4pt} \layout Standard \layout Standard \backslash alert<7,12>{ \backslash pgfnodeconnline{A}{B}} \layout Standard \backslash alert<5,11>{ \backslash pgfnodeconnline{A}{C}} \layout Standard \backslash alert<5,7,11-12>{ \backslash pgfnodeconnline{D}{A}} \layout Standard \backslash alert<5,11>{ \backslash pgfnodeconnline{C}{B}} \layout Standard \backslash pgfnodeconnline{B}{D} \layout Standard \backslash pgfnodeconnline{D}{C} \layout Standard } \layout Standard \backslash only<3,9>{ \backslash pgfputat{ \backslash pgfxy(2.75,1)}{ \backslash pgfbox[left,center]{ \backslash alert{``Yes''}}}} \layout Standard \backslash end{pgfpicture} \end_inset \end_deeper \end_deeper \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash onslide<2,4,6,8,10> \end_inset \layout Block \begin_inset ERT status Inlined \layout Standard {Variants of Path Finding Problems} \end_inset \begin_deeper \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash usedescriptionitemofwidthas{Approximation Problem:} \end_inset \layout Description Reachability\SpecialChar ~ Problem: \begin_inset ERT status Collapsed \layout Standard <2-> \end_inset Is there a path from \begin_inset Formula $s$ \end_inset to\SpecialChar ~ \begin_inset Formula $t$ \end_inset ? \layout Description Construction\SpecialChar ~ Problem: \begin_inset ERT status Collapsed \layout Standard <4-> \end_inset Construct a path from \begin_inset Formula $s$ \end_inset to\SpecialChar ~ \begin_inset Formula $t$ \end_inset ? \layout Description Optimization\SpecialChar ~ Problem: \begin_inset ERT status Collapsed \layout Standard <6-> \end_inset Construct a shortest path from \begin_inset Formula $s$ \end_inset to\SpecialChar ~ \begin_inset Formula $t$ \end_inset . \layout Description Distance\SpecialChar ~ Problem: \begin_inset ERT status Collapsed \layout Standard <8-> \end_inset Is the distance of \begin_inset Formula $s$ \end_inset and\SpecialChar ~ \begin_inset Formula $t$ \end_inset at most\SpecialChar ~ \begin_inset Formula $d$ \end_inset ? \layout Description Approximation\SpecialChar ~ Problem: \begin_inset ERT status Collapsed \layout Standard <10-> \end_inset Construct a path from \begin_inset Formula $s$ \end_inset to\SpecialChar ~ \begin_inset Formula $t$ \end_inset of length \newline approximately their distance. \end_deeper \end_deeper \layout Section Review \layout Subsection Standard Complexity Classes \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash pgfdeclaremask{computer-mask}{beamer-g4-mask} \backslash pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer-g4} \end_inset \layout BeginFrame The Classes L and NL are Defined via \newline Logspace Turing Machines \layout Standard \begin_inset ERT status Open \layout Standard \backslash begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} \layout Standard \backslash pgfputat{ \backslash pgfxy(0,4)}{ \backslash tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} \layout Standard \backslash uncover<2->{ \layout Standard \backslash pgfputat{ \backslash pgfxy(0,0.5)}{ \backslash tape{}{output tape (write only)}{10690836937182}}} \layout Standard \backslash uncover<3->{ \layout Standard \backslash pgfputat{ \backslash pgfxy(7,2)}{ \backslash shorttape{work tape (read/write), $O( \backslash log n)$ symbols}{}{42}} \layout Standard \backslash pgfputat{ \backslash pgfxy(1.75,2.5)}{ \backslash pgfbox[center,center]{ \backslash pgfuseimage{computer}}} \layout Standard } \layout Standard \backslash pgfsetlinewidth{0.6pt} \layout Standard \layout Standard \backslash color{structure} \layout Standard \backslash pgfsetendarrow{ \backslash pgfarrowto} \layout Standard \backslash pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85) \layout Standard \backslash uncover<2->{ \backslash pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)} \layout Standard \backslash uncover<3->{ \backslash pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)} \layout Standard \backslash end{pgfpicture} \end_inset \layout BeginFrame Logspace Turing Machines Are Quite Powerful \layout Block \begin_inset ERT status Inlined \layout Standard {Deterministic logspace machines can compute} \end_inset \begin_deeper \layout Itemize addition, multiplication, and even division \layout Itemize reductions used in completeness proofs, \layout Itemize reachability in forests. \end_deeper \layout Pause \layout Block \begin_inset ERT status Inlined \layout Standard {Non-deterministic logspace machines can compute} \end_inset \begin_deeper \layout Itemize reachability in graphs, \layout Itemize non-reachability in graphs, \layout Itemize satisfiability with two literals per clause. \end_deeper \layout BeginFrame \begin_inset ERT status Inlined \layout Standard <1>[label=hierarchy] \end_inset The Complexity Class Hierarchy \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm} \layout Standard \backslash pgfsetlinewidth{0.8pt} \layout Standard \backslash heap{5.5}{3.5}{$ \backslash Class P$}{black}{1} \layout Standard \backslash pgfsetdash{{2pt}}{0pt} \layout Standard \backslash only<2->{ \backslash heap{4.5}{3}{$ \backslash Class{NC}^2$}{black!50!structure}{2}} \layout Standard \backslash heap{3.5}{2.5}{$ \backslash Class{NL}$}{black!50!structure}{3} \layout Standard \backslash heap{2.5}{2}{$ \backslash Class{L}$}{black!50!structure}{4} \layout Standard \backslash only<2->{ \backslash heap{1.75}{1.5}{$ \backslash vphantom{A} \backslash smash{ \backslash Class{NC}^1}$}{black!50!structure}{5}} \layout Standard \backslash pgfsetdash{}{0pt} \layout Standard \backslash only<2->{ \backslash heap{1.1}{1}{$ \backslash vphantom{A} \backslash smash{ \backslash Class{AC}^0}$}{black}{6}} \layout Standard \layout Standard \backslash pgfsetlinewidth{1.0pt} \layout Standard \backslash color{black} \layout Standard \backslash pgfxyline(-5,0)(5,0) \layout Standard \layout Standard \backslash only<1-2>{ \backslash langat{3.375}{$ \backslash Lang{reach}$}} \layout Standard \backslash only<1-2>{ \backslash langat{2.375}{$ \backslash Lang{reach}_{ \backslash operatorname{forest}}$}} \layout Standard \layout Standard \backslash only<2>{ \backslash langat{0.975}{$ \backslash Lang{addition}$}} \layout Standard \backslash only<2>{ \backslash langatother{1.6}{ \backslash vbox{ \backslash hbox{$ \backslash Lang{division}$,} \backslash hbox{$ \backslash Lang{parity}$}}}} \layout Standard \backslash only<3-5>{ \backslash langat{3.375}{ \backslash vbox{ \backslash hbox{$ \backslash Lang{distance}$,} \backslash hbox{$ \backslash Lang{reach}$}}}} \layout Standard \backslash only<4->{ \backslash langatother{2.375}{ \backslash vbox{ \backslash ignorespaces \layout Standard \backslash hbox{$ \backslash Lang{distance}_{ \backslash operatorname{forest}}$,} \backslash ignorespaces \layout Standard \backslash hbox{$ \backslash Lang{reach}_{ \backslash operatorname{forest}}$,} \backslash ignorespaces \layout Standard \backslash hbox{$ \backslash Lang{distance}_{ \backslash operatorname{path}}$,} \backslash ignorespaces \layout Standard \backslash hbox{$ \backslash Lang{reach}_{ \backslash operatorname{path}}$}}}} \layout Standard \backslash only<5->{ \backslash langat{0.975}{$ \backslash Lang{reach}_{ \backslash operatorname{tourn}}$}} \layout Standard \backslash only<6->{ \backslash langat{3.375}{ \backslash vbox{ \backslash ignorespaces \layout Standard \backslash hbox{$ \backslash Lang{distance}_{ \backslash operatorname{tourn}}$,} \backslash ignorespaces \layout Standard \backslash hbox{$ \backslash Lang{distance}$,} \backslash ignorespaces \layout Standard \backslash hbox{$ \backslash Lang{reach}$}}}} \layout Standard \backslash only<7->{ \backslash pgfsetdash{{1pt}}{0pt} \backslash langat{2.375}{``$ \backslash Lang{approx}_{ \backslash operatorname{tourn}}$''}} \layout Standard \backslash end{pgfpicture} \end_inset \layout BeginFrame The Circuit Complexity Classes AC \begin_inset Formula $^{0}$ \end_inset , NC \begin_inset Formula $^{1}$ \end_inset , and NC \begin_inset Formula $^{2}$ \end_inset \newline Limit the Circuit Depth \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash setlength \backslash leftmargini{1em} \layout Standard \backslash nointerlineskip \end_inset \layout Columns \begin_inset ERT status Collapsed \layout Standard [t] \end_inset \begin_deeper \layout Column 3.6cm \layout Block \begin_inset ERT status Collapsed \layout Standard { \end_inset Circuit Class \begin_inset Formula $\Class{AC}^{0}$ \end_inset \begin_inset ERT status Collapsed \layout Standard } \end_inset \begin_deeper \layout Itemize \begin_inset Formula $O(1)$ \end_inset depth \layout Itemize unbounded fan-in \end_deeper \layout Examples \begin_deeper \layout Itemize \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$ \end_inset . \layout Itemize \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$ \end_inset . \end_deeper \layout Pause \layout Column 3.6cm \layout Block \begin_inset ERT status Collapsed \layout Standard { \end_inset Circuit Class \begin_inset Formula $\Class{NC}^{1}$ \end_inset \begin_inset ERT status Collapsed \layout Standard } \end_inset \begin_deeper \layout Itemize \begin_inset Formula $O(\log n)$ \end_inset depth \layout Itemize bounded fan-in \end_deeper \layout Examples \begin_deeper \layout Itemize \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$ \end_inset . \layout Itemize \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$ \end_inset . \layout Itemize \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$ \end_inset . \end_deeper \layout Pause \layout Column 3.6cm \layout Block \begin_inset ERT status Collapsed \layout Standard { \end_inset Circuit Class \begin_inset Formula $\Class{NC}^{2}$ \end_inset \begin_inset ERT status Collapsed \layout Standard } \end_inset \begin_deeper \layout Itemize \begin_inset Formula $O(\log^{2}n)$ \end_inset depth \layout Itemize bounded fan-in \end_deeper \layout Examples \begin_deeper \layout Itemize \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$ \end_inset . \end_deeper \end_deeper \layout AgainFrame \begin_inset ERT status Collapsed \layout Standard <2> \end_inset hierarchy \layout Subsection Standard Complexity Results on Finding Paths \layout BeginFrame All Variants of Finding Paths in Directed Graphs \newline Are Equally Difficult \layout Fact \begin_inset Formula $\Lang{reach}$ \end_inset and \begin_inset Formula $\Lang{distance}$ \end_inset are \begin_inset Formula $\Class{NL}$ \end_inset -complete. \layout Pause \layout Corollary For directed graphs, we can solve \begin_deeper \layout Itemize the reachability problem in logspace iff \begin_inset Formula $\Class{L}=\Class{NL}$ \end_inset . \layout Itemize the construction problem in logspace iff \begin_inset Formula $\Class{L}=\Class{NL}$ \end_inset . \layout Itemize the optimization problem in logspace iff \begin_inset Formula $\Class{L}=\Class{NL}$ \end_inset . \layout Itemize the approximation problem in logspace iff \begin_inset Formula $\Class{L}=\Class{NL}$ \end_inset . \end_deeper \layout AgainFrame \begin_inset ERT status Collapsed \layout Standard <3> \end_inset hierarchy \layout BeginFrame FindingPaths in Forests and Directed Paths is Easy, \newline But Not Trivial \layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$ \end_inset and \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$ \end_inset are \begin_inset Formula $\Class{L}$ \end_inset -complete. \layout Separator \layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$ \end_inset and \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$ \end_inset are \begin_inset Formula $\Class{L}$ \end_inset -complete. \layout AgainFrame \begin_inset ERT status Collapsed \layout Standard <4> \end_inset hierarchy \layout Section Finding Paths in Tournaments \layout Subsection Complexity of: Does a Path Exist? \layout BeginFrame Definition of the Tournament Reachability Problem \layout Definition Let \color red \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$ \end_inset \color default contain all triples \begin_inset Formula $(T,s,t)$ \end_inset such that \begin_deeper \layout Enumerate \begin_inset Formula $T=(V,E)$ \end_inset is a tournament and \layout Enumerate there exists a path from\SpecialChar ~ \begin_inset Formula $s$ \end_inset to\SpecialChar ~ \begin_inset Formula $t$ \end_inset . \end_deeper \layout BeginFrame The Tournament Reachability Problem is Very Easy \layout Theorem \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$ \end_inset . \layout Pause \layout AlertBlock \begin_inset ERT status Inlined \layout Standard {Implications} \end_inset \begin_deeper \layout Itemize The problem is \begin_inset Quotes eld \end_inset easier \begin_inset Quotes erd \end_inset than \begin_inset Formula $\Lang{reach}$ \end_inset and even \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$ \end_inset . \layout Itemize \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$ \end_inset . \end_deeper \layout AgainFrame \begin_inset ERT status Collapsed \layout Standard <5> \end_inset hierarchy \layout Subsection Complexity of: Construct a Shortest Path \layout BeginFrame Finding a Shortest Path Is as Difficult as \newline the Distance Problem \layout Definition Let \color red \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset \color default contain all tuples \begin_inset Formula $(T,s,t,d)$ \end_inset such that \begin_deeper \layout Enumerate \begin_inset Formula $T=(V,E)$ \end_inset is a tournament in which \layout Enumerate the distance of \begin_inset Formula $s$ \end_inset and\SpecialChar ~ \begin_inset Formula $t$ \end_inset is at most\SpecialChar ~ \begin_inset Formula $d$ \end_inset . \end_deeper \layout BeginFrame The Tournament Distance Problem is Hard \layout Theorem \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset is \begin_inset Formula $\Class{NL}$ \end_inset -complete. \layout Standard \hfill \begin_inset ERT status Inlined \layout Standard \backslash hyperlink{hierarchy<6>}{ \backslash beamerskipbutton{Skip Proof}} \end_inset \layout Pause \layout Corollary Shortest path in tournaments can be constructed \newline in logarithmic space, iff \begin_inset Formula $\Class{L}=\Class{NL}$ \end_inset . \layout Pause \layout Corollary \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$ \end_inset . \layout BeginFrame Proof That \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset is NL-complete \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash nointerlineskip \end_inset \layout Columns \begin_inset ERT status Inlined \layout Standard [t,onlytextwidth] \end_inset \begin_deeper \layout Column 5.7cm \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash setlength \backslash leftmargini{1.5em} \end_inset \layout Block \begin_inset ERT status Collapsed \layout Standard { \end_inset Reduce \begin_inset Formula $\Lang{reach}$ \end_inset to \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset \begin_inset ERT status Collapsed \layout Standard } \end_inset \begin_deeper \layout Enumerate \begin_inset ERT status Inlined \layout Standard \end_inset Is input \begin_inset Formula $(G,s,t)$ \end_inset in \begin_inset Formula $\Lang{reach}$ \end_inset ? \layout Enumerate \begin_inset ERT status Inlined \layout Standard <2-| alert@2-8> \end_inset Map \begin_inset Formula $G$ \end_inset to \begin_inset Formula $G'$ \end_inset . \layout Enumerate \begin_inset ERT status Inlined \layout Standard <9-| alert@9> \end_inset Query: \newline \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$ \end_inset ? \end_deeper \layout Separator \layout Block \begin_inset ERT status Collapsed \layout Standard { \end_inset Correctness \begin_inset ERT status Collapsed \layout Standard } \end_inset \begin_inset ERT status Collapsed \layout Standard <10-> \end_inset \begin_deeper \layout Enumerate \begin_inset ERT status Inlined \layout Standard <10-| alert@10-11> \end_inset A path in\SpecialChar ~ \begin_inset Formula $G$ \end_inset induces \newline a length-3 path in\SpecialChar ~ \begin_inset Formula $G'$ \end_inset . \layout Enumerate \begin_inset ERT status Inlined \layout Standard <12-| alert@12-13> \end_inset A length-3 path in\SpecialChar ~ \begin_inset Formula $G'$ \end_inset induces \newline a path in\SpecialChar ~ \begin_inset Formula $G'$ \end_inset . \end_deeper \layout Column 4.5cm \layout Example \begin_inset ERT status Inlined \layout Standard \backslash begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm} \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetlinewidth{0.6pt} \layout Standard \backslash graphnode{A}{ \backslash pgfxy(1,3.3)} \layout Standard \backslash graphnode{B}{ \backslash pgfxy(2,3.3)} \layout Standard \backslash graphnode{C}{ \backslash pgfxy(3,3.3)} \layout Standard \backslash graphnode{D}{ \backslash pgfxy(4,3.3)} \layout Standard \layout Standard \backslash color{white} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{A}}{ \backslash pgfbox[center,center]{$s$}} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{D}}{ \backslash pgfbox[center,center]{$t$}} \layout Standard \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetendarrow{ \backslash pgfarrowto} \layout Standard \backslash pgfnodesetsepstart{2pt} \layout Standard \backslash pgfnodesetsepend{2pt} \layout Standard \backslash alert<3>{ \backslash pgfnodeconnline{B}{A}} \layout Standard \backslash alert<4>{ \backslash pgfnodeconnline{B}{C}} \layout Standard \backslash alert<5,10-11,13>{ \backslash pgfnodeconnline{C}{D}} \layout Standard \backslash alert<6,10-11,13>{ \backslash pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}} \layout Standard \layout Standard \backslash pgfputat{ \backslash pgfxy(0,3.3)}{ \backslash pgfbox[left,center]{$G \backslash colon$}} \layout Standard \layout Standard \backslash only<2->{ \layout Standard \backslash pgfputat{ \backslash pgfxy(0,2.25)}{ \backslash pgfbox[left,center]{$G' \backslash colon$}} \layout Standard \backslash graphnode{A1}{ \backslash pgfxy(1,2.25)} \layout Standard \backslash graphnode{B1}{ \backslash pgfxy(2,2.25)} \layout Standard \backslash graphnode{C1}{ \backslash pgfxy(3,2.25)} \layout Standard \backslash graphnode{D1}{ \backslash pgfxy(4,2.25)} \layout Standard \layout Standard \backslash graphnode{A2}{ \backslash pgfxy(1,1.25)} \layout Standard \backslash graphnode{B2}{ \backslash pgfxy(2,1.25)} \layout Standard \backslash graphnode{C2}{ \backslash pgfxy(3,1.25)} \layout Standard \backslash graphnode{D2}{ \backslash pgfxy(4,1.25)} \layout Standard \backslash graphnode{A3}{ \backslash pgfxy(1,0.25)} \layout Standard \backslash graphnode{B3}{ \backslash pgfxy(2,0.25)} \layout Standard \backslash graphnode{C3}{ \backslash pgfxy(3,0.25)} \layout Standard \backslash graphnode{D3}{ \backslash pgfxy(4,0.25)} \layout Standard \backslash graphnode{A4}{ \backslash pgfxy(1,-.75)} \layout Standard \backslash graphnode{B4}{ \backslash pgfxy(2,-.75)} \layout Standard \backslash graphnode{C4}{ \backslash pgfxy(3,-.75)} \layout Standard \backslash graphnode{D4}{ \backslash pgfxy(4,-.75)} \layout Standard { \backslash color{white} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{A1}}{ \backslash pgfbox[center,center]{$s'$}} \layout Standard \backslash pgfputat{ \backslash pgfnodecenter{D4}}{ \backslash pgfbox[center,center]{$t'$}} \layout Standard }} \layout Standard \layout Standard \backslash only<8->{ \layout Standard \backslash pgfsetlinewidth{0.4pt} \layout Standard \backslash color{beamerexample!25!averagebackgroundcolor} \layout Standard \backslash pgfnodeconnline{A2}{C1} \layout Standard \backslash pgfnodeconnline{A2}{D1} \layout Standard \backslash pgfnodeconnline{B2}{A1} \layout Standard \backslash pgfnodeconnline{B2}{C1} \layout Standard \backslash pgfnodeconnline{B2}{D1} \layout Standard \backslash pgfnodeconnline{C2}{D1} \layout Standard \backslash pgfnodeconnline{D2}{A1} \layout Standard \backslash pgfnodeconnline{D2}{B1} \layout Standard \backslash pgfnodeconnline{A3}{C2} \layout Standard \backslash pgfnodeconnline{A3}{D2} \layout Standard \backslash pgfnodeconnline{B3}{A2} \layout Standard \backslash pgfnodeconnline{B3}{C2} \layout Standard \backslash pgfnodeconnline{B3}{D2} \layout Standard \backslash pgfnodeconnline{C3}{D2} \layout Standard \backslash pgfnodeconnline{D3}{A2} \layout Standard \backslash pgfnodeconnline{D3}{B2} \layout Standard \backslash pgfnodeconnline{A4}{C3} \layout Standard \backslash pgfnodeconnline{A4}{D3} \layout Standard \backslash pgfnodeconnline{B4}{A3} \layout Standard \backslash pgfnodeconnline{B4}{C3} \layout Standard \backslash pgfnodeconnline{B4}{D3} \layout Standard \backslash pgfnodeconnline{C4}{D3} \layout Standard \backslash pgfnodeconnline{D4}{A3} \layout Standard \backslash pgfnodeconnline{D4}{B3} \layout Standard \layout Standard \backslash pgfsetstartarrow{ \backslash pgfarrowto} \layout Standard \backslash pgfnodeconnline{A1}{B1} \layout Standard \backslash pgfnodeconnline{B1}{C1} \layout Standard \backslash pgfnodeconnline{C1}{D1} \layout Standard \backslash pgfnodeconnline{A2}{B2} \layout Standard \backslash pgfnodeconnline{B2}{C2} \layout Standard \backslash pgfnodeconnline{C2}{D2} \layout Standard \backslash pgfnodeconnline{A3}{B3} \layout Standard \backslash pgfnodeconnline{B3}{C3} \layout Standard \backslash pgfnodeconnline{C3}{D3} \layout Standard \backslash pgfnodeconnline{A4}{B4} \layout Standard \backslash pgfnodeconnline{B4}{C4} \layout Standard \backslash pgfnodeconnline{C4}{D4} \layout Standard \layout Standard \backslash pgfclearstartarrow \layout Standard \backslash pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} \layout Standard \backslash pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} \layout Standard \backslash pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} \layout Standard \backslash pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} \layout Standard \backslash pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} \layout Standard \backslash pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} \layout Standard \backslash pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} \layout Standard \backslash pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} \layout Standard \backslash pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} \layout Standard \backslash pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} \layout Standard \backslash pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} \layout Standard \backslash pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} \layout Standard \backslash color{beamerexample} \layout Standard \backslash pgfsetlinewidth{0.6pt} \layout Standard } \layout Standard \layout Standard \backslash only<3->{ \layout Standard \backslash color<3>{red} \layout Standard \backslash pgfnodeconnline{B1}{A2} \layout Standard \backslash pgfnodeconnline{B2}{A3} \layout Standard \backslash pgfnodeconnline{B3}{A4} \layout Standard } \layout Standard \layout Standard \backslash only<4->{ \layout Standard \backslash color<4>{red} \layout Standard \backslash pgfnodeconnline{B1}{C2} \layout Standard \backslash pgfnodeconnline{B2}{C3} \layout Standard \backslash pgfnodeconnline{B3}{C4} \layout Standard } \layout Standard \layout Standard \backslash only<5->{ \layout Standard \backslash color<5>{red} \layout Standard \backslash pgfnodeconnline{C1}{D2} \layout Standard \backslash alert<11>{ \backslash pgfnodeconnline{C2}{D3}} \layout Standard \backslash alert<12-13>{ \backslash pgfnodeconnline{C3}{D4}} \layout Standard } \layout Standard \layout Standard \backslash only<6->{ \layout Standard \backslash color<6>{red} \layout Standard \backslash alert<11>{ \backslash pgfnodeconnline{A1}{C2}} \layout Standard \backslash alert<12-13>{ \backslash pgfnodeconnline{A2}{C3}} \layout Standard \backslash pgfnodeconnline{A3}{C4} \layout Standard } \layout Standard \layout Standard \backslash only<7->{ \layout Standard \backslash color<7>{red} \layout Standard \backslash alert<12-13>{ \backslash pgfnodeconnline{A1}{A2}} \layout Standard \backslash pgfnodeconnline{A2}{A3} \layout Standard \backslash pgfnodeconnline{A3}{A4} \layout Standard \backslash pgfnodeconnline{B1}{B2} \layout Standard \backslash pgfnodeconnline{B2}{B3} \layout Standard \backslash pgfnodeconnline{B3}{B4} \layout Standard \backslash pgfnodeconnline{C1}{C2} \layout Standard \backslash pgfnodeconnline{C2}{C3} \layout Standard \backslash pgfnodeconnline{C3}{C4} \layout Standard \backslash pgfnodeconnline{D1}{D2} \layout Standard \backslash pgfnodeconnline{D2}{D3} \layout Standard \backslash alert<11>{ \backslash pgfnodeconnline{D3}{D4}} \layout Standard } \layout Standard \backslash end{pgfpicture} \end_inset \end_deeper \layout AgainFrame \begin_inset ERT status Collapsed \layout Standard <6> \end_inset hierarchy \layout Subsection Complexity of: Approximating the Shortest Path \layout BeginFrame Approximators Compute Paths that Are Nearly As Short As a Shortest Path \layout Definition An \color red approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ \end_inset \color default gets as input \begin_deeper \layout Enumerate a tuple \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$ \end_inset and \layout Enumerate a number \begin_inset Formula $r>1$ \end_inset . \layout Standard It outputs \layout Itemize a path from \begin_inset Formula $s$ \end_inset to\SpecialChar ~ \begin_inset Formula $t$ \end_inset of length at most \begin_inset Formula $r\operatorname{d_{T}}(s,t)$ \end_inset . \end_deeper \layout BeginFrame There Exists a Logspace Approximation Scheme for \newline the Tournament Shortest Path Problem \layout Theorem There exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ \end_inset that for \begin_inset Formula $1 \end_inset hierarchy \layout Section* Summary \layout Subsection* Summary \layout BeginFrame Summary \layout Block \begin_inset ERT status Inlined \layout Standard {Summary} \end_inset \begin_deeper \layout Itemize Tournament \color red reachability \color default is in \color red \begin_inset Formula $\Class{AC}^{0}$ \end_inset \color default . \layout Itemize There exists a \color red logspace approximation scheme \color default for \color red approximating \color default shortest paths in tournaments. \layout Itemize Finding \color red shortest paths \color default in tournaments is \color red \begin_inset Formula $\Class{NL}$ \end_inset -complete \color default . \end_deeper \layout Separator \layout Block \begin_inset ERT status Inlined \layout Standard {Outlook} \end_inset \begin_deeper \layout Itemize The same results apply to graphs with \newline bounded independence number. \hfill \begin_inset ERT status Inlined \layout Standard \backslash hyperlink{independence}{ \backslash beamergotobutton{More Details}} \end_inset \layout Itemize The complexity of finding paths in undirected graphs \newline is partly open. \hfill \begin_inset ERT status Inlined \layout Standard \backslash hyperlink{undirected}{ \backslash beamergotobutton{More Details}} \end_inset \end_deeper \layout Subsection* For Further Reading \layout BeginFrame For Further Reading \layout Standard \begin_inset ERT status Inlined \layout Standard \backslash beamertemplatebookbibitems \end_inset \layout Bibliography \bibitem {Moon1968} \SpecialChar ~ John Moon. \begin_inset ERT status Collapsed \layout Standard \backslash newblock \end_inset \emph on Topics on Tournaments. \emph default \begin_inset ERT status Collapsed \layout Standard \backslash newblock \end_inset Holt, Rinehart, and Winston, 1968. \begin_inset ERT status Inlined \layout Standard \backslash beamertemplatearticlebibitems \end_inset \layout Bibliography \bibitem {NickelsenT2002} \SpecialChar ~ Arfst Nickelsen and Till Tantau. \begin_inset ERT status Collapsed \layout Standard \backslash newblock \end_inset On reachability in graphs with bounded independence number. \begin_inset ERT status Collapsed \layout Standard \backslash newblock \end_inset In \emph on Proc. of COCOON 2002 \emph default , Springer-Verlag, 2002. \layout Bibliography \bibitem {Tantau2004b} \SpecialChar ~ Till Tantau \begin_inset ERT status Collapsed \layout Standard \backslash newblock \end_inset A logspace approximation scheme for the shortest path problem for graphs with bounded independence number. \begin_inset ERT status Collapsed \layout Standard \backslash newblock \end_inset In \emph on Proc. of STACS 2004 \emph default , Springer-Verlag, 2004. \begin_inset ERT status Collapsed \layout Standard \backslash newblock \end_inset In press. \layout EndFrame \layout Standard \start_of_appendix \begin_inset ERT status Inlined \layout Standard \backslash AtBeginSubsection[]{} \end_inset \layout Section Appendix \layout Subsection Graphs With Bounded Independence Number \layout BeginFrame \begin_inset ERT status Inlined \layout Standard [label=independence] \end_inset Definition of Independence Number of a Graph \layout Definition The \color red independence number \color default \begin_inset Formula $\alpha(G)$ \end_inset of a directed graph \newline is the maximum number of vertices we can pick, \newline such that there is no edge between them. \layout Example Tournaments have independence number 1. \layout BeginFrame The Results for Tournaments also Apply to \newline Graphs With Bounded Independence Number \layout Theorem For each\SpecialChar ~ \begin_inset Formula $k$ \end_inset , \color red reachability \color default in graphs with independence number \newline at most\SpecialChar ~ \begin_inset Formula $k$ \end_inset is in \begin_inset Formula $\Class{AC}^{0}$ \end_inset . \layout Separator \layout Theorem For each\SpecialChar ~ \begin_inset Formula $k$ \end_inset , there exists a \color red logspace approximation scheme \color default for approximating the shortest path in graphs with independence number at most\SpecialChar ~ \begin_inset Formula $k$ \end_inset \layout Separator \layout Theorem For each\SpecialChar ~ \begin_inset Formula $k$ \end_inset , finding the \color red shortest path \color default in graphs with independence number at most\SpecialChar ~ \begin_inset Formula $k$ \end_inset is \color red \begin_inset Formula $\Class{NL}$ \end_inset -complete \color default . \layout Subsection Finding Paths in Undirected Graphs \layout BeginFrame \begin_inset ERT status Inlined \layout Standard <1-2>[label=undirected] \end_inset The Complexity of Finding Paths in Undirected Graphs \newline Is Party Unknown. \layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$ \end_inset is \begin_inset Formula $\Class{SL}$ \end_inset -complete. \layout Corollary For undirected graphs, we can solve \begin_deeper \layout Itemize the reachability problem in logspace iff \begin_inset Formula $\Class L=\Class{SL}$ \end_inset , \layout Itemize the construction problem in logspace iff \begin_inset ERT status Inlined \layout Standard \backslash alt<1>{?}{ \backslash alert{$ \backslash Class L = \backslash Class{SL}$}} \end_inset , \layout Itemize the optimization problem in logspace iff \begin_inset ERT status Inlined \layout Standard \backslash alt<1>{?}{ \backslash alert{$ \backslash Class L = \backslash Class{NL}$}} \end_inset , \layout Itemize the approximation problem in logspace iff ?. \end_deeper \layout Subsection The Approximation Scheme is Optimal \layout BeginFrame \begin_inset ERT status Inlined \layout Standard [label=optimality] \end_inset The Approximation Scheme is Optimal \layout Theorem Suppose there exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ \end_inset that needs space \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$ \end_inset . Then \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$ \end_inset . \layout Proof \begin_deeper \layout Enumerate Suppose the approximation scheme exists. \newline We show \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$ \end_inset . \layout Enumerate Let \begin_inset Formula $(T,s,t)$ \end_inset be an input. Let \begin_inset Formula $n$ \end_inset be the number of vertices. \layout Enumerate Run the approximation scheme for \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$ \end_inset . \newline This needs space \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$ \end_inset . \layout Enumerate The resulting path has optimal length. \begin_inset ERT status Collapsed \layout Standard \backslash qedhere \end_inset \end_deeper \layout EndFrame \the_end