diff options
Diffstat (limited to 'Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx')
-rw-r--r-- | Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx | 3880 |
1 files changed, 3880 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx new file mode 100644 index 00000000000..0d443181c8b --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer/lyx/examples/beamerlyxexample1.lyx @@ -0,0 +1,3880 @@ +#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<handout:0>{ +\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 +<only@-9| visible@8-> +\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 +<only@10-> +\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 +<only@3->{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 +<alert@1> +\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<r<2$ +\end_inset + + needs space +\begin_inset Formula \[ +O\left(\log|V|\log\frac{1}{r-1}\right).\] + +\end_inset + + +\layout Pause + +\layout Corollary + +In tournaments, paths can be constructed in logarithmic space. +\layout Standard + + +\hfill + +\begin_inset ERT +status Inlined + +\layout Standard + +\backslash +hyperlink{optimality}{ +\backslash +beamergotobutton{More Details}} +\end_inset + + +\layout AgainFrame + + +\begin_inset ERT +status Collapsed + +\layout Standard +<7> +\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 |