X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=lib%2Fexamples%2Fbeamerlyxexample1.lyx;h=922cee1048d4b2c31b9eb95db34ecd32d451f7c6;hb=2dc84b69d5a040e6343e21606f1c16a7c0957383;hp=0d443181c8b4e746803fae6732985d40dc725fe6;hpb=6af710094efded1434482073675375d0e0a28029;p=lyx.git diff --git a/lib/examples/beamerlyxexample1.lyx b/lib/examples/beamerlyxexample1.lyx index 0d443181c8..922cee1048 100644 --- a/lib/examples/beamerlyxexample1.lyx +++ b/lib/examples/beamerlyxexample1.lyx @@ -1,5 +1,9 @@ -#LyX 1.3 created this file. For more info see http://www.lyx.org/ -\lyxformat 221 +#LyX 2.3 created this file. For more info see http://www.lyx.org/ +\lyxformat 544 +\begin_document +\begin_header +\save_transient_properties true +\origin /systemlyxdir/examples/ \textclass beamer \begin_preamble \beamertemplateshadingbackground{red!5}{structure!5} @@ -24,6 +28,10 @@ \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}} +% This gets defined by beamerbasecolor.sty, but only at the beginning of +% the document +\colorlet{averagebackgroundcolor}{normal text.bg} + \newcommand{\tape}[3]{% \color{structure!30!averagebackgroundcolor} \pgfmoveto{\pgfxy(-0.5,0)} @@ -143,3738 +151,6004 @@ } \end_preamble \options notes=show +\use_default_options false +\maintain_unincluded_children false \language english +\language_package default \inputencoding auto -\fontscheme times +\fontencoding global +\font_roman "lmodern" "default" +\font_sans "lmss" "default" +\font_typewriter "lmtt" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_osf false +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures false \graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default \paperfontsize default -\spacing single -\papersize Default -\paperpackage a4 -\use_geometry 0 -\use_amsmath 1 -\use_natbib 0 -\use_numerical_citations 0 +\spacing single +\use_hyperref false +\papersize default +\use_geometry true +\use_package amsmath 2 +\use_package amssymb 2 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 1 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false \paperorientation portrait +\suppress_date false +\justification true +\use_refstyle 0 +\use_minted 0 +\index Index +\shortcut idx +\color #008000 +\end_index \secnumdepth 2 \tocdepth 2 \paragraph_separation indent -\defskip medskip -\quotes_language english -\quotes_times 2 +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style english +\dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default +\tracking_changes false +\output_changes false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\end_header -\layout Title +\begin_body +\begin_layout Title The Complexity of -\newline +\begin_inset Newline newline +\end_inset + Finding Paths in Tournaments -\layout Author +\end_layout +\begin_layout Author Till Tantau -\layout Institute +\end_layout -International Computer Schience Institute -\newline -Berkeley, California -\begin_inset OptArg -collapsed true +\begin_layout Institute +International Computer Science Institute +\begin_inset Newline newline +\end_inset -\layout Standard +Berkeley, California +\begin_inset Argument 1 +status collapsed +\begin_layout Plain Layout ICSI -\end_inset +\end_layout +\end_inset -\layout Date +\end_layout + +\begin_layout Date January 30th, 2004 -\layout BeginFrame +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open +\begin_layout Plain Layout Outline -\layout Standard +\end_layout + +\end_inset + +\end_layout -\begin_inset LatexCommand \tableofcontents{} +\begin_deeper +\begin_layout Standard +\begin_inset CommandInset toc +LatexCommand tableofcontents -\end_inset +\end_inset \begin_inset ERT -status Collapsed +status collapsed -\layout Standard -[pausesections] -\end_inset +\begin_layout Plain Layout +[pausesections] +\end_layout -\layout EndFrame +\end_inset -\layout Standard +\end_layout +\end_deeper +\begin_layout Standard \begin_inset ERT -status Collapsed +status open + +\begin_layout Plain Layout -\layout Standard % Show the table of contents at the beginning -\layout Standard +\end_layout + +\begin_layout Plain Layout + % of every subsection. -\layout Standard +\end_layout + +\begin_layout Plain Layout + + +\backslash +AtBeginSubsection[]{% +\end_layout + +\begin_layout Plain Layout -\backslash -AtBeginSubsection[]{ -\layout Standard -\backslash +\backslash frame{ -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash frametitle{Outline} -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash tableofcontents[current,currentsubsection] -\layout Standard +\end_layout + +\begin_layout Plain Layout + } -\layout Standard +\end_layout + +\begin_layout Plain Layout + } -\end_inset +\end_layout + +\end_inset -\layout Section +\end_layout +\begin_layout Section Introduction -\layout Subsection +\end_layout +\begin_layout Subsection What are Tournaments? -\layout BeginFrame +\end_layout +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Consist of Jousts Between Knights -\layout Columns +\end_layout -\begin_deeper -\layout Column +\end_inset -5.75cm -\layout Standard +\end_layout + +\begin_deeper +\begin_layout Columns + +\end_layout + +\begin_deeper +\begin_layout Column +5.75cm +\end_layout +\begin_layout Standard \begin_inset ERT -status Inlined +status collapsed -\layout Standard +\begin_layout Plain Layout -\backslash + +\backslash begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodebox{A}[virtual]{ -\backslash -pgfxy(2,1)}{ -\backslash -pgfuseimage{knight1}}{2pt}{2pt} -\layout Standard +\backslash +pgfxy(2,1)}{% +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash +pgfuseimage{knight1}}{2pt}{2pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodebox{B}[virtual]{ -\backslash -pgfxy(6,1)}{ -\backslash -pgfuseimage{knight2}}{2pt}{2pt} -\layout Standard +\backslash +pgfxy(6,1)}{% +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash +pgfuseimage{knight2}}{2pt}{2pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodebox{C}[virtual]{ -\backslash -pgfxy(4,-1)}{ -\backslash -pgfuseimage{knight3}}{2pt}{2pt} -\layout Standard +\backslash +pgfxy(4,-1)}{% +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash +pgfuseimage{knight3}}{2pt}{2pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodebox{D}[virtual]{ -\backslash -pgfxy(4,3)}{ -\backslash -pgfuseimage{knight4}}{2pt}{2pt} -\layout Standard +\backslash +pgfxy(4,3)}{% +\end_layout + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash +pgfuseimage{knight4}}{2pt}{2pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash color{beamerexample} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash only<3->{ -\backslash +\backslash pgfsetendarrow{ -\backslash +\backslash pgfarrowto}} -\layout Standard - -\backslash -only<2->{ -\layout Standard +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<2->{% +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash pgfsetlinewidth{0.6pt} -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash pgfnodeconnline{A}{B} -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash pgfnodeconnline{A}{C} -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash pgfnodeconnline{D}{A} -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash pgfnodeconnline{C}{B} -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash pgfnodeconnline{B}{D} -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\backslash -pgfnodeconnline{C}{D}} -\layout Standard +\backslash +pgfnodeconnline{C}{D} +\end_layout -\backslash +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash end{pgfpicture} -\end_inset +\end_layout + +\end_inset -\layout Column +\end_layout +\begin_layout Column 6cm -\layout Block +\end_layout +\begin_layout Block +\begin_inset Argument 2 +status open -\begin_inset ERT -status Inlined +\begin_layout Plain Layout +What is a Tournament? +\end_layout -\layout Standard -{What is a Tournament?} -\end_inset +\end_inset -\begin_deeper -\layout Itemize +\end_layout +\begin_deeper +\begin_layout Itemize +\begin_inset Argument item:2 +status open -\begin_inset ERT -status Collapsed +\begin_layout Plain Layout -\layout Standard -<1-> -\end_inset +1- +\end_layout + +\end_inset A group of knights. -\layout Itemize +\end_layout +\begin_layout Itemize +\begin_inset Argument item:2 +status open -\begin_inset ERT -status Collapsed +\begin_layout Plain Layout -\layout Standard -<2-> -\end_inset +2- +\end_layout + +\end_inset Every pair has a joust. -\layout Itemize +\end_layout +\begin_layout Itemize +\begin_inset Argument item:2 +status open -\begin_inset ERT -status Collapsed +\begin_layout Plain Layout -\layout Standard -<3-> -\end_inset +3- +\end_layout + +\end_inset In every joust one knight wins. -\end_deeper -\end_deeper -\layout BeginFrame +\end_layout + +\end_deeper +\end_deeper +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments are Complete Directed Graphs -\layout Columns +\end_layout -\begin_deeper -\layout Column +\end_inset -5cm -\layout Standard +\end_layout + +\begin_deeper +\begin_layout Columns + +\end_layout +\begin_deeper +\begin_layout Column +5cm +\end_layout + +\begin_layout Standard \begin_inset ERT -status Inlined +status collapsed -\layout Standard +\begin_layout Plain Layout -\backslash + +\backslash begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash color{beamerexample} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfsetlinewidth{0.6pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{A}{ -\backslash +\backslash pgfxy(2.5,1)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{B}{ -\backslash +\backslash pgfxy(5.5,1)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{C}{ -\backslash +\backslash pgfxy(4,-0.5)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{D}{ -\backslash +\backslash pgfxy(4,2.5)} -\layout Standard +\end_layout -\layout Standard - -\backslash +\begin_layout Plain Layout + + +\backslash color{white} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfputat{ -\backslash +\backslash pgfnodecenter{A}}{ -\backslash +\backslash pgfbox[center,center]{$v_2$}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfputat{ -\backslash +\backslash pgfnodecenter{B}}{ -\backslash +\backslash pgfbox[center,center]{$v_3$}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfputat{ -\backslash +\backslash pgfnodecenter{C}}{ -\backslash +\backslash pgfbox[center,center]{$v_4$}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfputat{ -\backslash +\backslash pgfnodecenter{D}}{ -\backslash +\backslash pgfbox[center,center]{$v_1$}} -\layout Standard +\end_layout -\layout Standard - -\backslash +\begin_layout Plain Layout + + +\backslash color{beamerexample} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfsetendarrow{ -\backslash +\backslash pgfarrowto} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodesetsepstart{2pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodesetsepend{4pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A}{B} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A}{C} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D}{A} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C}{B} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B}{D} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D}{C} -\layout Standard +\end_layout + +\begin_layout Plain Layout -\backslash + +\backslash end{pgfpicture} -\end_inset +\end_layout + +\end_inset -\layout Column +\end_layout +\begin_layout Column 6cm -\layout Definition +\end_layout +\begin_layout Definition +\begin_inset Argument 1 +status collapsed -\begin_inset ERT -status Collapsed +\begin_layout Plain Layout + +2- +\end_layout -\layout Standard -<2-> -\end_inset +\end_inset -A +A +\color none + \color red tournament -\color default - is a -\begin_deeper -\layout Enumerate +\color none + +\color inherit +is a +\end_layout +\begin_deeper +\begin_layout Enumerate directed graphs, -\layout Enumerate +\end_layout +\begin_layout Enumerate with exactly one edge between -\newline +\begin_inset Newline newline +\end_inset + any two different vertices. -\end_deeper -\end_deeper -\layout BeginFrame +\end_layout +\end_deeper +\end_deeper +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout + ++ +\end_layout + +\end_inset -\begin_inset ERT -status Collapsed -\layout Standard -[<+>] -\end_inset +\begin_inset Argument 4 +status open +\begin_layout Plain Layout Tournaments Arise Naturally in Different Situations -\layout ExampleBlock +\end_layout +\end_inset -\begin_inset ERT -status Inlined -\layout Standard -{Applicatins in Ordering Theory} -\end_inset +\end_layout + +\begin_deeper +\begin_layout ExampleBlock +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Applications in Ordering Theory +\end_layout + +\end_inset -\begin_deeper -\layout Standard +\end_layout +\begin_deeper +\begin_layout Standard Elements in a set need to be sorted. -\newline +\begin_inset Newline newline +\end_inset + The comparison relation may be cyclic, however. -\end_deeper -\layout Separator +\end_layout -\layout ExampleBlock +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset -\begin_inset ERT -status Inlined +\end_layout + +\begin_layout ExampleBlock +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Applications in Sociology +\end_layout -\layout Standard -{Applications in Sociology} -\end_inset +\end_inset -\begin_deeper -\layout Standard +\end_layout +\begin_deeper +\begin_layout Standard Several candidates apply for a position. -\newline +\begin_inset Newline newline +\end_inset + Reviewers decide for any two candidates whom they prefer. -\end_deeper -\layout Separator +\end_layout -\layout ExampleBlock +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset -\begin_inset ERT -status Inlined +\end_layout + +\begin_layout ExampleBlock +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Applications in Structural Complexity Theory +\end_layout -\layout Standard -{Applications in Structural Complexity Theory} -\end_inset +\end_inset -\begin_deeper -\layout Standard +\end_layout +\begin_deeper +\begin_layout Standard A language \begin_inset Formula $L$ -\end_inset +\end_inset is given and a selector function \begin_inset Formula $f$ -\end_inset +\end_inset . -\newline +\begin_inset Newline newline +\end_inset + It chooses from any two words the one more likely to be in \begin_inset Formula $f$ -\end_inset +\end_inset . -\end_deeper -\layout Subsection +\end_layout +\end_deeper +\end_deeper +\begin_layout Subsection What Does ``Finding Paths'' Mean? -\layout BeginFrame +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open +\begin_layout Plain Layout ``Finding Paths'' is Ambiguous -\layout Block +\end_layout +\end_inset -\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 +\end_layout -\backslash -only<2-3>{$ -\backslash -Lang{reach}$} -\backslash -ignorespaces -\layout Standard +\begin_deeper +\begin_layout Block +\begin_inset Argument 2 +status open -\backslash -only<4-5>{the Construction Problem} -\backslash -ignorespaces -\layout Standard +\begin_layout Plain Layout +Input for +\begin_inset Flex Only +status open -\backslash -only<6-7>{the Optimization Problem} -\backslash -ignorespaces -\layout Standard +\begin_layout Plain Layout +\begin_inset Argument 1 +status open -\backslash -only<8-9>{$ -\backslash -Lang{distance}$} -\backslash -ignorespaces -\layout Standard +\begin_layout Plain Layout -\backslash -only<10->{the Approximation Problem}} -\end_inset +1 +\end_layout +\end_inset -\begin_deeper -\layout Itemize +Path Finding Problems +\end_layout -A -\color red -graph -\color default - -\begin_inset Formula $G=(V,E)$ -\end_inset +\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 +\begin_inset Flex Only +status open -. -\layout Itemize +\begin_layout Plain Layout +\begin_inset Argument 1 +status open +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed +2-3 +\end_layout -\layout Standard - -\end_inset +\end_inset -A -\color red -maximum distance -\color default -\SpecialChar ~ -\begin_inset Formula $d$ -\end_inset +\begin_inset Formula $\Lang{reach}$ +\end_inset -. -\begin_inset ERT -status Collapsed -\layout Standard +\end_layout -\backslash -phantom{p} -\end_inset +\end_inset -\layout Itemize +\begin_inset Flex Only +status open +\begin_layout Plain Layout +\begin_inset Argument 1 +status open -\begin_inset ERT -status Collapsed +\begin_layout Plain Layout -\layout Standard - -\end_inset +4-5 +\end_layout -An -\color red -approximation ratio -\color default - -\begin_inset Formula $r>1$ -\end_inset +\end_inset -. -\end_deeper -\layout Standard +the Construction Problem +\end_layout +\end_inset -\begin_inset ERT -status Collapsed -\layout Standard +\begin_inset Flex Only +status open -\backslash -nointerlineskip -\end_inset +\begin_layout Plain Layout +\begin_inset Argument 1 +status open +\begin_layout Plain Layout -\layout Overprint +6-7 +\end_layout -\begin_deeper -\layout Standard +\end_inset +the Optimization Problem +\end_layout -\begin_inset ERT -status Inlined +\end_inset -\layout Standard -\backslash -onslide<1,3,5,7,9,11-12> -\end_inset +\begin_inset Flex Only +status open +\begin_layout Plain Layout +\begin_inset Argument 1 +status open -\layout Columns +\begin_layout Plain Layout +8-9 +\end_layout -\begin_inset ERT -status Inlined +\end_inset -\layout Standard -[t,onlytextwidth] -\end_inset +\begin_inset Formula $\Lang{distance}$ +\end_inset -\begin_deeper -\layout Standard +\end_layout -\begin_inset ERT -status Inlined +\end_inset -\layout Standard -\backslash -alt<1-2>{ -\backslash -column{ -\backslash -textwidth}}{ -\backslash -column{5cm}} -\end_inset +\begin_inset Flex Only +status open +\begin_layout Plain Layout +\begin_inset Argument 1 +status open -\layout ExampleBlock +\begin_layout Plain Layout +10- +\end_layout -\begin_inset ERT -status Inlined +\end_inset -\layout Standard -{Example Input} -\end_inset +the Approximation Problem +\end_layout +\end_inset -\begin_deeper -\layout Standard +\end_layout -\begin_inset ERT -status Inlined +\end_inset -\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 +\end_layout -\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 +\begin_deeper +\begin_layout Itemize +A +\color none + +\color red +graph +\color none + +\color inherit -\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 +\begin_inset Formula $G=(V,E)$ +\end_inset -\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 +, a +\color none + +\color red +source +\color none + +\color inherit -\backslash -end{pgfpicture} -\end_inset +\begin_inset Formula $s\in V$ +\end_inset + + and a +\color none + +\color red +target +\color none + +\color inherit +\begin_inset Formula $t\in V$ +\end_inset -\end_deeper -\layout Standard +. +\end_layout +\begin_layout Itemize +\begin_inset Argument item:2 +status open -\begin_inset ERT -status Inlined +\begin_layout Plain Layout -\layout Standard +only@-9| visible@8- +\end_layout -\backslash -only<3->{ -\backslash -column{5cm}} -\end_inset +\end_inset + +A +\color none + +\color red +maximum distance +\color inherit +\begin_inset space ~ +\end_inset -\layout ExampleBlock +\begin_inset Formula $d$ +\end_inset +. \begin_inset ERT -status Inlined +status collapsed -\layout Standard -{Example Output} -\end_inset +\begin_layout Plain Layout -\begin_deeper -\layout Standard +\backslash +phantom{p} +\end_layout +\end_inset -\begin_inset ERT -status Inlined -\layout Standard +\end_layout -\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 +\begin_layout Itemize +\begin_inset Argument item:2 +status open -\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 +\begin_layout Plain Layout -\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 +only@10- +\end_layout -\backslash -end{pgfpicture} -\end_inset +\end_inset +An +\color none + +\color red +approximation ratio +\color none + +\color inherit -\end_deeper -\end_deeper -\layout Standard +\begin_inset Formula $r>1$ +\end_inset +. +\end_layout +\end_deeper +\begin_layout Standard \begin_inset ERT -status Inlined +status collapsed -\layout Standard +\begin_layout Plain Layout -\backslash -onslide<2,4,6,8,10> -\end_inset +\backslash +nointerlineskip +\end_layout -\layout Block +\end_inset -\begin_inset ERT -status Inlined +\end_layout -\layout Standard -{Variants of Path Finding Problems} -\end_inset +\begin_layout Overprint +\begin_inset Argument item:1 +status open +\begin_layout Plain Layout -\begin_deeper -\layout Standard +1,3,5,7,9,11-12 +\end_layout +\end_inset -\begin_inset ERT -status Inlined -\layout Standard +\end_layout -\backslash -usedescriptionitemofwidthas{Approximation Problem:} -\end_inset +\begin_deeper +\begin_layout Columns +\begin_inset Argument 1 +status open +\begin_layout Plain Layout +t,onlytextwidth +\end_layout -\layout Description +\end_inset -Reachability\SpecialChar ~ -Problem: -\begin_inset ERT -status Collapsed -\layout Standard -<2-> -\end_inset +\end_layout -Is there a path from -\begin_inset Formula $s$ -\end_inset +\begin_deeper +\begin_layout Standard +\begin_inset Flex Alternative +status open - to\SpecialChar ~ +\begin_layout Plain Layout +\begin_inset Argument 1 +status open -\begin_inset Formula $t$ -\end_inset +\begin_layout Plain Layout -? -\layout Description +1-2 +\end_layout -Construction\SpecialChar ~ -Problem: -\begin_inset ERT -status Collapsed +\end_inset -\layout Standard -<4-> -\end_inset -Construct a path from -\begin_inset Formula $s$ -\end_inset +\begin_inset Argument 2 +status open - to\SpecialChar ~ +\begin_layout Plain Layout +\begin_inset ERT +status open -\begin_inset Formula $t$ -\end_inset +\begin_layout Plain Layout -? -\layout Description -Optimization\SpecialChar ~ -Problem: -\begin_inset ERT -status Collapsed +\backslash +column{ +\backslash +textwidth} +\end_layout -\layout Standard -<6-> -\end_inset +\end_inset -Construct a shortest path from -\begin_inset Formula $s$ -\end_inset - to\SpecialChar ~ +\end_layout -\begin_inset Formula $t$ -\end_inset +\end_inset -. -\layout Description -Distance\SpecialChar ~ -Problem: \begin_inset ERT -status Collapsed +status open -\layout Standard -<8-> -\end_inset +\begin_layout Plain Layout -Is the distance of -\begin_inset Formula $s$ -\end_inset - and\SpecialChar ~ +\backslash +column{5cm} +\end_layout -\begin_inset Formula $t$ -\end_inset +\end_inset - at most\SpecialChar ~ -\begin_inset Formula $d$ -\end_inset +\end_layout -? -\layout Description +\end_inset -Approximation\SpecialChar ~ -Problem: -\begin_inset ERT -status Collapsed -\layout Standard -<10-> -\end_inset +\end_layout -Construct a path from -\begin_inset Formula $s$ -\end_inset +\begin_layout ExampleBlock +\begin_inset Argument 2 +status collapsed - to\SpecialChar ~ +\begin_layout Plain Layout +Example Input +\end_layout -\begin_inset Formula $t$ -\end_inset +\end_inset - of length -\newline -approximately their distance. -\end_deeper -\end_deeper -\layout Section -Review -\layout Subsection +\end_layout -Standard Complexity Classes -\layout Standard +\begin_deeper +\begin_layout Standard +\begin_inset ERT +status collapsed +\begin_layout Plain Layout -\begin_inset ERT -status Inlined -\layout Standard +\backslash +begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} +\end_layout -\backslash -pgfdeclaremask{computer-mask}{beamer-g4-mask} -\backslash -pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer-g4} -\end_inset +\begin_layout Plain Layout +\end_layout -\layout BeginFrame +\begin_layout Plain Layout -The Classes L and NL are Defined via -\newline -Logspace Turing Machines -\layout Standard + +\backslash +color{beamerexample} +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Open +\end_layout -\layout Standard +\begin_layout Plain Layout -\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 +\backslash pgfsetlinewidth{0.6pt} -\layout Standard +\end_layout -\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 +\begin_layout Plain Layout -\backslash -end{pgfpicture} -\end_inset +\end_layout +\begin_layout Plain Layout -\layout BeginFrame + +\backslash +graphnode{A}{ +\backslash +pgfxy(3,1)} +\end_layout -Logspace Turing Machines Are Quite Powerful -\layout Block +\begin_layout Plain Layout +\end_layout -\begin_inset ERT -status Inlined +\begin_layout Plain Layout -\layout Standard -{Deterministic logspace machines can compute} -\end_inset + +\backslash +graphnode{B}{ +\backslash +pgfxy(5,1)} +\end_layout +\begin_layout Plain Layout -\begin_deeper -\layout Itemize +\end_layout -addition, multiplication, and even division -\layout Itemize +\begin_layout Plain Layout -reductions used in completeness proofs, -\layout Itemize + +\backslash +graphnode{C}{ +\backslash +pgfxy(4,0)} +\end_layout -reachability in forests. -\end_deeper -\layout Pause +\begin_layout Plain Layout -\layout Block +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Inlined + +\backslash +graphnode{D}{ +\backslash +pgfxy(4,2)} +\end_layout -\layout Standard -{Non-deterministic logspace machines can compute} -\end_inset +\begin_layout Plain Layout +\end_layout -\begin_deeper -\layout Itemize +\begin_layout Plain Layout -reachability in graphs, -\layout Itemize +\end_layout -non-reachability in graphs, -\layout Itemize +\begin_layout Plain Layout -satisfiability with two literals per clause. -\end_deeper -\layout BeginFrame +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Inlined + +\backslash +color{white} +\end_layout -\layout Standard -<1>[label=hierarchy] -\end_inset +\begin_layout Plain Layout -The Complexity Class Hierarchy -\layout Standard +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Inlined + +\backslash +pgfputat{ +\backslash +pgfnodecenter{B}}{ +\backslash +pgfbox[center,center]{$t$}} +\end_layout -\layout Standard +\begin_layout Plain Layout -\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 +\end_layout -\layout Standard - -\backslash -pgfsetlinewidth{1.0pt} -\layout Standard - -\backslash -color{black} -\layout Standard - -\backslash -pgfxyline(-5,0)(5,0) -\layout Standard +\begin_layout Plain Layout -\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 +\backslash +pgfputat{ +\backslash +pgfnodecenter{D}}{ +\backslash +pgfbox[center,center]{$s$}} +\end_layout -\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 +\begin_layout Plain Layout -\backslash -end{pgfpicture} -\end_inset +\end_layout +\begin_layout Plain Layout -\layout BeginFrame +\end_layout -The Circuit Complexity Classes AC -\begin_inset Formula $^{0}$ -\end_inset +\begin_layout Plain Layout -, NC -\begin_inset Formula $^{1}$ -\end_inset +\end_layout -, and NC -\begin_inset Formula $^{2}$ -\end_inset +\begin_layout Plain Layout + +\backslash +color{beamerexample} +\end_layout -\newline -Limit the Circuit Depth -\layout Standard +\begin_layout Plain Layout +\end_layout -\begin_inset ERT -status Inlined +\begin_layout Plain Layout -\layout Standard + +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\end_layout -\backslash -setlength -\backslash -leftmargini{1em} -\layout Standard +\begin_layout Plain Layout -\backslash -nointerlineskip -\end_inset +\end_layout +\begin_layout Plain Layout -\layout Columns + +\backslash +pgfnodesetsepstart{2pt} +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed +\end_layout -\layout Standard -[t] -\end_inset +\begin_layout Plain Layout + +\backslash +pgfnodesetsepend{4pt} +\end_layout -\begin_deeper -\layout Column +\begin_layout Plain Layout -3.6cm -\layout Block +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed + +\backslash +pgfnodeconnline{A}{B} +\end_layout -\layout Standard -{ -\end_inset +\begin_layout Plain Layout -Circuit Class -\begin_inset Formula $\Class{AC}^{0}$ -\end_inset +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed + +\backslash +pgfnodeconnline{A}{C} +\end_layout -\layout Standard -} -\end_inset +\begin_layout Plain Layout +\end_layout -\begin_deeper -\layout Itemize +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{D}{A} +\end_layout -\begin_inset Formula $O(1)$ -\end_inset +\begin_layout Plain Layout - depth -\layout Itemize +\end_layout -unbounded fan-in -\end_deeper -\layout Examples +\begin_layout Plain Layout -\begin_deeper -\layout Itemize + +\backslash +pgfnodeconnline{C}{B} +\end_layout +\begin_layout Plain Layout -\begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$ -\end_inset +\end_layout -. -\layout Itemize +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B}{D} +\end_layout -\begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$ -\end_inset +\begin_layout Plain Layout -. -\end_deeper -\layout Pause +\end_layout -\layout Column +\begin_layout Plain Layout -3.6cm -\layout Block + +\backslash +pgfnodeconnline{D}{C} +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed +\end_layout -\layout Standard -{ -\end_inset +\begin_layout Plain Layout -Circuit Class -\begin_inset Formula $\Class{NC}^{1}$ -\end_inset +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed +\end_layout -\layout Standard -} -\end_inset +\begin_layout Plain Layout + +\backslash +only<9> { +\backslash +pgfputat{ +\backslash +pgfxy(5.3,1)}{ +\backslash +pgfbox[left,center]{, $d=2$}}} +\end_layout -\begin_deeper -\layout Itemize +\begin_layout Plain Layout +\end_layout -\begin_inset Formula $O(\log n)$ -\end_inset +\begin_layout Plain Layout - depth -\layout Itemize + +\backslash +only<11>{ +\backslash +pgfputat{ +\backslash +pgfxy(5.3,1)}{ +\backslash +pgfbox[left,center]{, $r=1.5$}}} +\end_layout -bounded fan-in -\end_deeper -\layout Examples +\begin_layout Plain Layout -\begin_deeper -\layout Itemize +\end_layout +\begin_layout Plain Layout -\begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$ -\end_inset + +\backslash +only<12>{ +\backslash +pgfputat{ +\backslash +pgfxy(5.3,1)}{ +\backslash +pgfbox[left,center]{, $r=1.25$}}} +\end_layout -. -\layout Itemize +\begin_layout Plain Layout +\end_layout -\begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$ -\end_inset +\begin_layout Plain Layout -. -\layout Itemize +\backslash +end{pgfpicture} +\end_layout -\begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$ -\end_inset +\end_inset -. -\end_deeper -\layout Pause -\layout Column +\end_layout -3.6cm -\layout Block +\end_deeper +\begin_layout Standard +\begin_inset Flex Only +status open +\begin_layout Plain Layout +\begin_inset Argument 1 +status open -\begin_inset ERT -status Collapsed +\begin_layout Plain Layout -\layout Standard -{ -\end_inset +3- +\end_layout -Circuit Class -\begin_inset Formula $\Class{NC}^{2}$ -\end_inset +\end_inset \begin_inset ERT -status Collapsed +status open -\layout Standard -} -\end_inset +\begin_layout Plain Layout -\begin_deeper -\layout Itemize +\backslash +column{5cm} +\end_layout +\end_inset -\begin_inset Formula $O(\log^{2}n)$ -\end_inset - depth -\layout Itemize +\end_layout -bounded fan-in -\end_deeper -\layout Examples +\end_inset -\begin_deeper -\layout Itemize +\end_layout -\begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$ -\end_inset +\begin_layout ExampleBlock +\begin_inset Argument 1 +status collapsed -. -\end_deeper -\end_deeper -\layout AgainFrame +\begin_layout Plain Layout +only@3- +\end_layout -\begin_inset ERT -status Collapsed +\end_inset -\layout Standard -<2> -\end_inset -hierarchy -\layout Subsection +\begin_inset Argument 2 +status collapsed -Standard Complexity Results on Finding Paths -\layout BeginFrame +\begin_layout Plain Layout +Example Output +\end_layout -All Variants of Finding Paths in Directed Graphs -\newline -Are Equally Difficult -\layout Fact +\end_inset -\begin_inset Formula $\Lang{reach}$ -\end_inset +\end_layout - and -\begin_inset Formula $\Lang{distance}$ -\end_inset +\begin_deeper +\begin_layout Standard +\begin_inset ERT +status collapsed - are -\begin_inset Formula $\Class{NL}$ -\end_inset +\begin_layout Plain Layout --complete. - -\layout Pause -\layout Corollary +\backslash +begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} +\end_layout -For directed graphs, we can solve -\begin_deeper -\layout Itemize +\begin_layout Plain Layout -the reachability problem in logspace iff -\begin_inset Formula $\Class{L}=\Class{NL}$ -\end_inset -. -\layout Itemize +\backslash +only<5-8,10->{% +\end_layout -the construction problem in logspace iff -\begin_inset Formula $\Class{L}=\Class{NL}$ -\end_inset +\begin_layout Plain Layout -. -\layout Itemize + +\backslash +color{beamerexample} +\end_layout -the optimization problem in logspace iff -\begin_inset Formula $\Class{L}=\Class{NL}$ -\end_inset +\begin_layout Plain Layout -. -\layout Itemize + +\backslash +pgfsetlinewidth{0.6pt} +\end_layout -the approximation problem in logspace iff -\begin_inset Formula $\Class{L}=\Class{NL}$ -\end_inset +\begin_layout Plain Layout -. -\end_deeper -\layout AgainFrame + +\backslash +graphnode{A}{ +\backslash +pgfxy(3,1)} +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed + +\backslash +graphnode{B}{ +\backslash +pgfxy(5,1)} +\end_layout -\layout Standard -<3> -\end_inset +\begin_layout Plain Layout -hierarchy -\layout BeginFrame + +\backslash +graphnode{C}{ +\backslash +pgfxy(4,0)} +\end_layout -FindingPaths in Forests and Directed Paths is Easy, -\newline -But Not Trivial -\layout Fact +\begin_layout Plain Layout + +\backslash +graphnode{D}{ +\backslash +pgfxy(4,2)} +\end_layout -\begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$ -\end_inset +\begin_layout Plain Layout - and -\begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$ -\end_inset + +\backslash +color{white} +\end_layout - are -\begin_inset Formula $\Class{L}$ -\end_inset +\begin_layout Plain Layout --complete. -\layout Separator + +\backslash +pgfputat{ +\backslash +pgfnodecenter{B}}{ +\backslash +pgfbox[center,center]{$t$}} +\end_layout -\layout Fact +\begin_layout Plain Layout + +\backslash +pgfputat{ +\backslash +pgfnodecenter{D}}{ +\backslash +pgfbox[center,center]{$s$}} +\end_layout -\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$ -\end_inset +\begin_layout Plain Layout - and -\begin_inset Formula $\Lang{distance}_{\operatorname{path}}$ -\end_inset + +\backslash +color{beamerexample} +\end_layout - are -\begin_inset Formula $\Class{L}$ -\end_inset +\begin_layout Plain Layout --complete. -\layout AgainFrame + +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed + +\backslash +pgfnodesetsepstart{2pt} +\end_layout -\layout Standard -<4> -\end_inset +\begin_layout Plain Layout -hierarchy -\layout Section + +\backslash +pgfnodesetsepend{4pt} +\end_layout -Finding Paths in Tournaments -\layout Subsection +\begin_layout Plain Layout -Complexity of: Does a Path Exist? -\layout BeginFrame + +\backslash +alert<7,12>{ +\backslash +pgfnodeconnline{A}{B}} +\end_layout -Definition of the Tournament Reachability Problem -\layout Definition +\begin_layout Plain Layout -Let -\color red + +\backslash +alert<5,11>{ +\backslash +pgfnodeconnline{A}{C}} +\end_layout -\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$ -\end_inset +\begin_layout Plain Layout + +\backslash +alert<5,7,11-12>{ +\backslash +pgfnodeconnline{D}{A}} +\end_layout -\color default - contain all triples -\begin_inset Formula $(T,s,t)$ -\end_inset +\begin_layout Plain Layout - such that -\begin_deeper -\layout Enumerate + +\backslash +alert<5,11>{ +\backslash +pgfnodeconnline{C}{B}} +\end_layout +\begin_layout Plain Layout -\begin_inset Formula $T=(V,E)$ -\end_inset + +\backslash +pgfnodeconnline{B}{D} +\end_layout - is a tournament and -\layout Enumerate +\begin_layout Plain Layout -there exists a path from\SpecialChar ~ + +\backslash +pgfnodeconnline{D}{C} +\end_layout -\begin_inset Formula $s$ -\end_inset +\begin_layout Plain Layout + +} +\end_layout - to\SpecialChar ~ +\begin_layout Plain Layout -\begin_inset Formula $t$ -\end_inset -. -\end_deeper -\layout BeginFrame +\backslash +only<3,9>{ +\backslash +pgfputat{ +\backslash +pgfxy(2.75,1)}{ +\backslash +pgfbox[left,center]{ +\backslash +alert{``Yes''}}}} +\end_layout -The Tournament Reachability Problem is Very Easy -\layout Theorem +\begin_layout Plain Layout -\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$ -\end_inset +\backslash +end{pgfpicture} +\end_layout -. -\layout Pause +\end_inset -\layout AlertBlock +\end_layout -\begin_inset ERT -status Inlined +\end_deeper +\end_deeper +\end_deeper +\begin_layout Overprint +\begin_inset Argument item:1 +status open -\layout Standard -{Implications} -\end_inset +\begin_layout Plain Layout +2,4,6,8,10 +\end_layout -\begin_deeper -\layout Itemize +\end_inset -The problem is -\begin_inset Quotes eld -\end_inset -easier -\begin_inset Quotes erd -\end_inset +\end_layout - than -\begin_inset Formula $\Lang{reach}$ -\end_inset +\begin_deeper +\begin_layout Block +\begin_inset Argument 2 +status collapsed - and even -\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$ -\end_inset +\begin_layout Plain Layout +Variants of Path Finding Problems +\end_layout -. -\layout Itemize +\end_inset -\begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$ -\end_inset +\end_layout -. -\end_deeper -\layout AgainFrame +\begin_deeper +\begin_layout Description +\begin_inset Argument item:1 +status open +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed +2- +\end_layout -\layout Standard -<5> -\end_inset +\end_inset -hierarchy -\layout Subsection +Reachability +\begin_inset space ~ +\end_inset -Complexity of: Construct a Shortest Path -\layout BeginFrame +Problem: Is there a path from +\begin_inset Formula $s$ +\end_inset -Finding a Shortest Path Is as Difficult as -\newline -the Distance Problem -\layout Definition + to +\begin_inset space ~ +\end_inset -Let -\color red -\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ -\end_inset +\begin_inset Formula $t$ +\end_inset - -\color default -contain all tuples -\begin_inset Formula $(T,s,t,d)$ -\end_inset +? +\begin_inset Argument 2 +status open - such that -\begin_deeper -\layout Enumerate +\begin_layout Plain Layout +Approximation Problem: +\end_layout +\end_inset -\begin_inset Formula $T=(V,E)$ -\end_inset - is a tournament in which -\layout Enumerate +\end_layout -the distance of +\begin_layout Description +\begin_inset Argument item:1 +status open + +\begin_layout Plain Layout + +4- +\end_layout + +\end_inset + +Construction +\begin_inset space ~ +\end_inset + +Problem: Construct a path from \begin_inset Formula $s$ -\end_inset +\end_inset + + to +\begin_inset space ~ +\end_inset - and\SpecialChar ~ \begin_inset Formula $t$ -\end_inset +\end_inset - is at most\SpecialChar ~ +? +\end_layout -\begin_inset Formula $d$ -\end_inset +\begin_layout Description +\begin_inset Argument item:1 +status open -. -\end_deeper -\layout BeginFrame +\begin_layout Plain Layout -The Tournament Distance Problem is Hard -\layout Theorem +6- +\end_layout +\end_inset -\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ -\end_inset +Optimization +\begin_inset space ~ +\end_inset - is -\begin_inset Formula $\Class{NL}$ -\end_inset +Problem: Construct a shortest path from +\begin_inset Formula $s$ +\end_inset --complete. -\layout Standard + to +\begin_inset space ~ +\end_inset -\hfill +\begin_inset Formula $t$ +\end_inset -\begin_inset ERT -status Inlined +. +\end_layout -\layout Standard +\begin_layout Description +\begin_inset Argument item:1 +status open -\backslash -hyperlink{hierarchy<6>}{ -\backslash -beamerskipbutton{Skip Proof}} -\end_inset +\begin_layout Plain Layout +8- +\end_layout -\layout Pause +\end_inset -\layout Corollary +Distance +\begin_inset space ~ +\end_inset -Shortest path in tournaments can be constructed -\newline -in logarithmic space, iff -\begin_inset Formula $\Class{L}=\Class{NL}$ -\end_inset +Problem: Is the distance of +\begin_inset Formula $s$ +\end_inset -. -\layout Pause + and +\begin_inset space ~ +\end_inset -\layout Corollary +\begin_inset Formula $t$ +\end_inset -\begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$ -\end_inset + at most +\begin_inset space ~ +\end_inset -. -\layout BeginFrame -Proof That -\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ -\end_inset +\begin_inset Formula $d$ +\end_inset - is NL-complete -\layout Standard +? +\end_layout +\begin_layout Description +\begin_inset Argument item:1 +status open -\begin_inset ERT -status Collapsed +\begin_layout Plain Layout -\layout Standard +10- +\end_layout -\backslash -nointerlineskip -\end_inset +\end_inset +Approximation +\begin_inset space ~ +\end_inset -\layout Columns +Problem: Construct a path from +\begin_inset Formula $s$ +\end_inset + to +\begin_inset space ~ +\end_inset -\begin_inset ERT -status Inlined -\layout Standard -[t,onlytextwidth] -\end_inset +\begin_inset Formula $t$ +\end_inset + of length +\begin_inset Newline newline +\end_inset -\begin_deeper -\layout Column +approximately their distance. +\end_layout -5.7cm -\layout Standard +\end_deeper +\end_deeper +\end_deeper +\begin_layout Section +Review +\end_layout +\begin_layout Subsection +Standard Complexity Classes +\end_layout +\begin_layout Standard \begin_inset ERT -status Inlined +status collapsed -\layout Standard +\begin_layout Plain Layout -\backslash -setlength -\backslash -leftmargini{1.5em} -\end_inset +\backslash +pgfdeclaremask{computer-mask}{beamer-g4-mask} +\backslash +pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer +-g4} +\end_layout -\layout Block +\end_inset -\begin_inset ERT -status Collapsed +\end_layout -\layout Standard -{ -\end_inset +\begin_layout Frame +\begin_inset Argument 4 +status open -Reduce -\begin_inset Formula $\Lang{reach}$ -\end_inset +\begin_layout Plain Layout +The Classes L and NL are Defined via +\begin_inset Newline newline +\end_inset - to -\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ -\end_inset +Logspace Turing Machines +\end_layout +\end_inset + +\end_layout + +\begin_deeper +\begin_layout Standard \begin_inset ERT -status Collapsed +status collapsed -\layout Standard -} -\end_inset +\begin_layout Plain Layout -\begin_deeper -\layout Enumerate +\backslash +begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Inlined -\layout Standard - -\end_inset +\backslash +pgfputat{ +\backslash +pgfxy(0,4)}{% +\end_layout -Is input -\begin_inset Formula $(G,s,t)$ -\end_inset +\begin_layout Plain Layout - in -\begin_inset Formula $\Lang{reach}$ -\end_inset + +\backslash +tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} +\end_layout -? -\layout Enumerate +\begin_layout Plain Layout -\begin_inset ERT -status Inlined +\backslash +uncover<2->{% +\end_layout -\layout Standard -<2-| alert@2-8> -\end_inset +\begin_layout Plain Layout -Map -\begin_inset Formula $G$ -\end_inset + +\backslash +pgfputat{ +\backslash +pgfxy(0,0.5)}{% +\end_layout - to -\begin_inset Formula $G'$ -\end_inset +\begin_layout Plain Layout -. -\layout Enumerate + +\backslash +tape{}{output tape (write only)}{10690836937182}} +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Inlined +} +\end_layout -\layout Standard -<9-| alert@9> -\end_inset +\begin_layout Plain Layout -Query: -\newline -\begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$ -\end_inset +\backslash +uncover<3->{% +\end_layout -? -\end_deeper -\layout Separator +\begin_layout Plain Layout -\layout Block + +\backslash +pgfputat{ +\backslash +pgfxy(7,2)}{% +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed + +\backslash +shorttape{work tape (read/write), $O( +\backslash +log n)$ symbols}{}{42}} +\end_layout -\layout Standard -{ -\end_inset +\begin_layout Plain Layout -Correctness -\begin_inset ERT -status Collapsed + +\backslash +pgfputat{ +\backslash +pgfxy(1.75,2.5)}{% +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfbox[center,center]{ +\backslash +pgfuseimage{computer}}} +\end_layout + +\begin_layout Plain Layout -\layout Standard } -\end_inset +\end_layout +\begin_layout Plain Layout -\begin_inset ERT -status Collapsed -\layout Standard -<10-> -\end_inset +\backslash +pgfsetlinewidth{0.6pt} +\end_layout +\begin_layout Plain Layout -\begin_deeper -\layout Enumerate +\backslash +color{structure} +\end_layout -\begin_inset ERT -status Inlined +\begin_layout Plain Layout -\layout Standard -<10-| alert@10-11> -\end_inset -A path in\SpecialChar ~ +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\end_layout -\begin_inset Formula $G$ -\end_inset +\begin_layout Plain Layout - induces -\newline -a length-3 path in\SpecialChar ~ -\begin_inset Formula $G'$ -\end_inset +\backslash +pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85) +\end_layout -. -\layout Enumerate +\begin_layout Plain Layout -\begin_inset ERT -status Inlined +\backslash +uncover<2->{ +\backslash +pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)} +\end_layout -\layout Standard -<12-| alert@12-13> -\end_inset +\begin_layout Plain Layout -A length-3 path in\SpecialChar ~ -\begin_inset Formula $G'$ -\end_inset +\backslash +uncover<3->{ +\backslash +pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)} +\end_layout - induces -\newline -a path in\SpecialChar ~ +\begin_layout Plain Layout -\begin_inset Formula $G'$ -\end_inset -. -\end_deeper -\layout Column +\backslash +end{pgfpicture} +\end_layout -4.5cm -\layout Example +\end_inset -\begin_inset ERT -status Inlined +\end_layout -\layout Standard +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset -\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 +\end_layout -\layout Standard - -\backslash -color{beamerexample} -\layout Standard - -\backslash -pgfsetendarrow{ -\backslash -pgfarrowto} -\layout Standard - -\backslash +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +Logspace Turing Machines Are Quite Powerful +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Block +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Deterministic logspace machines can compute +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Itemize +addition, multiplication, and even division +\end_layout + +\begin_layout Itemize +reductions used in completeness proofs, +\end_layout + +\begin_layout Itemize +reachability in forests. +\end_layout + +\end_deeper +\begin_layout Pause + +\end_layout + +\begin_layout Block +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Non-deterministic logspace machines can compute +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Itemize +reachability in graphs, +\end_layout + +\begin_layout Itemize +non-reachability in graphs, +\end_layout + +\begin_layout Itemize +satisfiability with two literals per clause. +\end_layout + +\end_deeper +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 1 +status collapsed + +\begin_layout Plain Layout + +1 +\end_layout + +\end_inset + + +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=hierarchy +\end_layout + +\end_inset + + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +The Complexity Class Hierarchy +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Standard +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + + +\backslash +begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfsetlinewidth{0.8pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash +heap{5.5}{3.5}{$ +\backslash +Class P$}{black}{1} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfsetdash{{2pt}}{0pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<2->{ +\backslash +heap{4.5}{3}{$ +\backslash +Class{NC}^2$}{black!50!structure}{2}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +heap{3.5}{2.5}{$ +\backslash +Class{NL}$}{black!50!structure}{3} +\end_layout + +\begin_layout Plain Layout + + +\backslash +heap{2.5}{2}{$ +\backslash +Class{L}$}{black!50!structure}{4} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<2->{ +\backslash +heap{1.75}{1.5}{$ +\backslash +vphantom{A}% +\end_layout + +\begin_layout Plain Layout + + +\backslash +smash{ +\backslash +Class{NC}^1}$}{black!50!structure}{5} +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfsetdash{}{0pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<2->{ +\backslash +heap{1.1}{1}{$ +\backslash +vphantom{A}% +\end_layout + +\begin_layout Plain Layout + + +\backslash +smash{ +\backslash +Class{AC}^0}$}{black}{6} +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfsetlinewidth{1.0pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash +color{black} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfxyline(-5,0)(5,0) +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<1-2>{ +\backslash +langat{3.375}{$ +\backslash +Lang{reach}$}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<1-2>{ +\backslash +langat{2.375}{$ +\backslash +Lang{reach}_{ +\backslash +operatorname{forest}}$}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<2>{ +\backslash +langat{0.975}{$ +\backslash +Lang{addition}$}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<2>{ +\backslash +langatother{1.6}{ +\backslash +vbox{ +\backslash +hbox{$ +\backslash +Lang{division}$,} +\backslash +hbox{$ +\backslash +Lang{parity}$}}}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<3-5>{ +\backslash +langat{3.375}{ +\backslash +vbox{ +\backslash +hbox{$ +\backslash +Lang{distance}$,} +\backslash +hbox{$ +\backslash +Lang{reach}$}}}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<4->{ +\backslash +langatother{2.375}{ +\backslash +vbox{ +\backslash +ignorespaces +\end_layout + +\begin_layout Plain Layout + + +\backslash +hbox{$ +\backslash +Lang{distance}_{ +\backslash +operatorname{forest}}$,} +\backslash +ignorespaces +\end_layout + +\begin_layout Plain Layout + + +\backslash +hbox{$ +\backslash +Lang{reach}_{ +\backslash +operatorname{forest}}$,} +\backslash +ignorespaces +\end_layout + +\begin_layout Plain Layout + + +\backslash +hbox{$ +\backslash +Lang{distance}_{ +\backslash +operatorname{path}}$,} +\backslash +ignorespaces +\end_layout + +\begin_layout Plain Layout + + +\backslash +hbox{$ +\backslash +Lang{reach}_{ +\backslash +operatorname{path}}$}}} +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<5->{ +\backslash +langat{0.975}{$ +\backslash +Lang{reach}_{ +\backslash +operatorname{tourn}}$}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<6->{ +\backslash +langat{3.375}{ +\backslash +vbox{ +\backslash +ignorespaces +\end_layout + +\begin_layout Plain Layout + + +\backslash +hbox{$ +\backslash +Lang{distance}_{ +\backslash +operatorname{tourn}}$,} +\backslash +ignorespaces +\end_layout + +\begin_layout Plain Layout + + +\backslash +hbox{$ +\backslash +Lang{distance}$,} +\backslash +ignorespaces +\end_layout + +\begin_layout Plain Layout + + +\backslash +hbox{$ +\backslash +Lang{reach}$}}} +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<7->{ +\backslash +pgfsetdash{{1pt}}{0pt}% +\end_layout + +\begin_layout Plain Layout + + +\backslash +langat{2.375}{``$ +\backslash +Lang{approx}_{ +\backslash +operatorname{tourn}}$''} +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +end{pgfpicture} +\end_layout + +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +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 + + +\begin_inset Newline newline +\end_inset + +Limit the Circuit Depth +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Standard +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + + +\backslash +setlength +\backslash +leftmargini{1em} +\end_layout + +\begin_layout Plain Layout + + +\backslash +nointerlineskip +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Columns +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +t +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Column +3.6cm +\end_layout + +\begin_layout Block +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Circuit Class +\begin_inset Formula $\Class{AC}^{0}$ +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $O(1)$ +\end_inset + + depth +\end_layout + +\begin_layout Itemize +unbounded fan-in +\end_layout + +\end_deeper +\begin_layout Examples + +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Pause + +\end_layout + +\begin_layout Column +3.6cm +\end_layout + +\begin_layout Block +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Circuit Class +\begin_inset Formula $\Class{NC}^{1}$ +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $O(\log n)$ +\end_inset + + depth +\end_layout + +\begin_layout Itemize +bounded fan-in +\end_layout + +\end_deeper +\begin_layout Examples + +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Pause + +\end_layout + +\begin_layout Column +3.6cm +\end_layout + +\begin_layout Block +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Circuit Class +\begin_inset Formula $\Class{NC}^{2}$ +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $O(\log^{2}n)$ +\end_inset + + depth +\end_layout + +\begin_layout Itemize +bounded fan-in +\end_layout + +\end_deeper +\begin_layout Examples + +\end_layout + +\begin_deeper +\begin_layout Itemize +\begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$ +\end_inset + +. +\end_layout + +\end_deeper +\end_deeper +\end_deeper +\begin_layout AgainFrame +\begin_inset Argument 1 +status collapsed + +\begin_layout Plain Layout + +2 +\end_layout + +\end_inset + +hierarchy +\end_layout + +\begin_layout Subsection +Standard Complexity Results on Finding Paths +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +All Variants of Finding Paths in Directed Graphs +\begin_inset Newline newline +\end_inset + +Are Equally Difficult +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_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. + +\end_layout + +\begin_layout Pause + +\end_layout + +\begin_layout Corollary +For directed graphs, we can solve +\end_layout + +\begin_deeper +\begin_layout Itemize +the reachability problem in logspace iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +the construction problem in logspace iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +the optimization problem in logspace iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +the approximation problem in logspace iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\end_layout + +\end_deeper +\end_deeper +\begin_layout AgainFrame +\begin_inset Argument 1 +status collapsed + +\begin_layout Plain Layout + +3 +\end_layout + +\end_inset + +hierarchy +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +Finding Paths in Forests and Directed Paths is Easy, +\begin_inset Newline newline +\end_inset + +But Not Trivial +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_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. +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_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. +\end_layout + +\end_deeper +\begin_layout AgainFrame +\begin_inset Argument 1 +status collapsed + +\begin_layout Plain Layout + +4 +\end_layout + +\end_inset + +hierarchy +\end_layout + +\begin_layout Section +Finding Paths in Tournaments +\end_layout + +\begin_layout Subsection +Complexity of: Does a Path Exist? +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +Definition of the Tournament Reachability Problem +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Definition +Let +\color none + +\color red + +\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$ +\end_inset + + +\color none + +\color inherit +contain all triples +\begin_inset Formula $(T,s,t)$ +\end_inset + + such that +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $T=(V,E)$ +\end_inset + + is a tournament and +\end_layout + +\begin_layout Enumerate +there exists a path from +\begin_inset space ~ +\end_inset + + +\begin_inset Formula $s$ +\end_inset + + to +\begin_inset space ~ +\end_inset + + +\begin_inset Formula $t$ +\end_inset + +. +\end_layout + +\end_deeper +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +The Tournament Reachability Problem is Very Easy +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Theorem +\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$ +\end_inset + +. +\end_layout + +\begin_layout Pause + +\end_layout + +\begin_layout AlertBlock +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Implications +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_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 + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$ +\end_inset + +. +\end_layout + +\end_deeper +\end_deeper +\begin_layout AgainFrame +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout + +5 +\end_layout + +\end_inset + +hierarchy +\end_layout + +\begin_layout Subsection +Complexity of: Construct a Shortest Path +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +Finding a Shortest Path Is as Difficult as +\begin_inset Newline newline +\end_inset + +the Distance Problem +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Definition +Let +\color none + +\color red + +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + + +\color none + +\color inherit +contain all tuples +\begin_inset Formula $(T,s,t,d)$ +\end_inset + + such that +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Formula $T=(V,E)$ +\end_inset + + is a tournament in which +\end_layout + +\begin_layout Enumerate +the distance of +\begin_inset Formula $s$ +\end_inset + + and +\begin_inset space ~ +\end_inset + + +\begin_inset Formula $t$ +\end_inset + + is at most +\begin_inset space ~ +\end_inset + + +\begin_inset Formula $d$ +\end_inset + +. +\end_layout + +\end_deeper +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +The Tournament Distance Problem is Hard +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Theorem +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + + is +\begin_inset Formula $\Class{NL}$ +\end_inset + +-complete. +\end_layout + +\begin_layout Standard +\begin_inset space \hfill{} +\end_inset + + +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + + +\backslash +hyperlink{hierarchy<6>}{ +\backslash +beamerskipbutton{Skip Proof}} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Pause + +\end_layout + +\begin_layout Corollary +Shortest path in tournaments can be constructed +\begin_inset Newline newline +\end_inset + +in logarithmic space, iff +\begin_inset Formula $\Class{L}=\Class{NL}$ +\end_inset + +. +\end_layout + +\begin_layout Pause + +\end_layout + +\begin_layout Corollary +\begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +Proof That +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + + is NL-complete +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Standard +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + + +\backslash +nointerlineskip +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Columns +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +t,onlytextwidth +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Column +5.7cm +\end_layout + +\begin_layout Standard +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + + +\backslash +setlength +\backslash +leftmargini{1.5em} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Block +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Reduce +\begin_inset Formula $\Lang{reach}$ +\end_inset + + to +\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Argument item:2 +status open + +\begin_layout Plain Layout + +alert@1 +\end_layout + +\end_inset + +Is input +\begin_inset Formula $(G,s,t)$ +\end_inset + + in +\begin_inset Formula $\Lang{reach}$ +\end_inset + +? +\end_layout + +\begin_layout Enumerate +\begin_inset Argument item:2 +status open + +\begin_layout Plain Layout + +2-| alert@2-8 +\end_layout + +\end_inset + +Map +\begin_inset Formula $G$ +\end_inset + + to +\begin_inset Formula $G'$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +\begin_inset Argument item:2 +status open + +\begin_layout Plain Layout + +9-| alert@9 +\end_layout + +\end_inset + +Query: +\begin_inset Newline newline +\end_inset + + +\begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$ +\end_inset + +? +\end_layout + +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout + +\begin_layout Block +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Correctness +\end_layout + +\end_inset + + +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout + +10- +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Enumerate +\begin_inset Argument item:2 +status open + +\begin_layout Plain Layout + +10-| alert@10-11 +\end_layout + +\end_inset + +A path in +\begin_inset space ~ +\end_inset + + +\begin_inset Formula $G$ +\end_inset + + induces +\begin_inset Newline newline +\end_inset + +a length-3 path in +\begin_inset space ~ +\end_inset + + +\begin_inset Formula $G'$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +\begin_inset Argument item:2 +status open + +\begin_layout Plain Layout + +12-| alert@12-13 +\end_layout + +\end_inset + +A length-3 path in +\begin_inset space ~ +\end_inset + + +\begin_inset Formula $G'$ +\end_inset + + induces +\begin_inset Newline newline +\end_inset + +a path in +\begin_inset space ~ +\end_inset + + +\begin_inset Formula $G'$ +\end_inset + +. +\end_layout + +\end_deeper +\begin_layout Column +4.5cm +\end_layout + +\begin_layout Example +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + + +\backslash +begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm} +\end_layout + +\begin_layout Plain Layout + + +\backslash +color{beamerexample} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfsetlinewidth{0.6pt} +\end_layout + +\begin_layout Plain Layout + + +\backslash +graphnode{A}{ +\backslash +pgfxy(1,3.3)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +graphnode{B}{ +\backslash +pgfxy(2,3.3)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +graphnode{C}{ +\backslash +pgfxy(3,3.3)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +graphnode{D}{ +\backslash +pgfxy(4,3.3)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +color{white} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfputat{ +\backslash +pgfnodecenter{A}}{ +\backslash +pgfbox[center,center]{$s$}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfputat{ +\backslash +pgfnodecenter{D}}{ +\backslash +pgfbox[center,center]{$t$}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +color{beamerexample} +\end_layout + +\begin_layout Plain Layout + + +\backslash +pgfsetendarrow{ +\backslash +pgfarrowto} +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodesetsepstart{2pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodesetsepend{2pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<3>{ -\backslash +\backslash pgfnodeconnline{B}{A}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<4>{ -\backslash +\backslash pgfnodeconnline{B}{C}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<5,10-11,13>{ -\backslash +\backslash pgfnodeconnline{C}{D}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<6,10-11,13>{ -\backslash +\backslash pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}} -\layout Standard - -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfputat{ -\backslash +\backslash pgfxy(0,3.3)}{ -\backslash +\backslash pgfbox[left,center]{$G -\backslash +\backslash colon$}} -\layout Standard +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<2->{% +\end_layout + +\begin_layout Plain Layout -\layout Standard -\backslash -only<2->{ -\layout Standard - -\backslash +\backslash pgfputat{ -\backslash +\backslash pgfxy(0,2.25)}{ -\backslash +\backslash pgfbox[left,center]{$G' -\backslash +\backslash colon$}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{A1}{ -\backslash +\backslash pgfxy(1,2.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{B1}{ -\backslash +\backslash pgfxy(2,2.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{C1}{ -\backslash +\backslash pgfxy(3,2.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{D1}{ -\backslash +\backslash pgfxy(4,2.25)} -\layout Standard +\end_layout -\layout Standard - -\backslash +\begin_layout Plain Layout + + +\backslash graphnode{A2}{ -\backslash +\backslash pgfxy(1,1.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{B2}{ -\backslash +\backslash pgfxy(2,1.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{C2}{ -\backslash +\backslash pgfxy(3,1.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{D2}{ -\backslash +\backslash pgfxy(4,1.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{A3}{ -\backslash +\backslash pgfxy(1,0.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{B3}{ -\backslash +\backslash pgfxy(2,0.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{C3}{ -\backslash +\backslash pgfxy(3,0.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{D3}{ -\backslash +\backslash pgfxy(4,0.25)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{A4}{ -\backslash +\backslash pgfxy(1,-.75)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{B4}{ -\backslash +\backslash pgfxy(2,-.75)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{C4}{ -\backslash +\backslash pgfxy(3,-.75)} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash graphnode{D4}{ -\backslash +\backslash pgfxy(4,-.75)} -\layout Standard - { -\backslash +\end_layout + +\begin_layout Plain Layout + + { +\backslash color{white} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfputat{ -\backslash +\backslash pgfnodecenter{A1}}{ -\backslash +\backslash pgfbox[center,center]{$s'$}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfputat{ -\backslash +\backslash pgfnodecenter{D4}}{ -\backslash +\backslash pgfbox[center,center]{$t'$}} -\layout Standard - }} -\layout Standard - -\layout Standard - -\backslash -only<8->{ -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<8->{% +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfsetlinewidth{0.4pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash color{beamerexample!25!averagebackgroundcolor} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A2}{C1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A2}{D1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B2}{A1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B2}{C1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B2}{D1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C2}{D1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D2}{A1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D2}{B1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A3}{C2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A3}{D2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B3}{A2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B3}{C2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B3}{D2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C3}{D2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D3}{A2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D3}{B2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A4}{C3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A4}{D3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B4}{A3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B4}{C3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B4}{D3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C4}{D3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D4}{A3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D4}{B3} -\layout Standard +\end_layout -\layout Standard - -\backslash +\begin_layout Plain Layout + + +\backslash pgfsetstartarrow{ -\backslash +\backslash pgfarrowto} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A1}{B1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B1}{C1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C1}{D1} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A2}{B2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B2}{C2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C2}{D2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A3}{B3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B3}{C3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C3}{D3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A4}{B4} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B4}{C4} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C4}{D4} -\layout Standard +\end_layout -\layout Standard - -\backslash +\begin_layout Plain Layout + + +\backslash pgfclearstartarrow -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash color{beamerexample} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfsetlinewidth{0.6pt} -\layout Standard - } -\layout Standard +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<3->{% +\end_layout + +\begin_layout Plain Layout -\layout Standard -\backslash -only<3->{ -\layout Standard - -\backslash +\backslash color<3>{red} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B1}{A2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B2}{A3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B3}{A4} -\layout Standard - } -\layout Standard +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<4->{% +\end_layout + +\begin_layout Plain Layout -\layout Standard -\backslash -only<4->{ -\layout Standard - -\backslash +\backslash color<4>{red} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B1}{C2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B2}{C3} -\layout Standard - -\backslash -pgfnodeconnline{B3}{C4} -\layout Standard - } -\layout Standard +\end_layout + +\begin_layout Plain Layout + -\layout Standard +\backslash +pgfnodeconnline{B3}{C4} +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<5->{% +\end_layout + +\begin_layout Plain Layout + -\backslash -only<5->{ -\layout Standard - -\backslash +\backslash color<5>{red} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C1}{D2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<11>{ -\backslash +\backslash pgfnodeconnline{C2}{D3}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<12-13>{ -\backslash +\backslash pgfnodeconnline{C3}{D4}} -\layout Standard - } -\layout Standard - -\layout Standard +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<6->{% +\end_layout + +\begin_layout Plain Layout + -\backslash -only<6->{ -\layout Standard - -\backslash +\backslash color<6>{red} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<11>{ -\backslash +\backslash pgfnodeconnline{A1}{C2}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<12-13>{ -\backslash +\backslash pgfnodeconnline{A2}{C3}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A3}{C4} -\layout Standard - } -\layout Standard +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +only<7->{% +\end_layout + +\begin_layout Plain Layout -\layout Standard -\backslash -only<7->{ -\layout Standard - -\backslash +\backslash color<7>{red} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<12-13>{ -\backslash +\backslash pgfnodeconnline{A1}{A2}} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A2}{A3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{A3}{A4} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B1}{B2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B2}{B3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{B3}{B4} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C1}{C2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C2}{C3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{C3}{C4} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D1}{D2} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash pgfnodeconnline{D2}{D3} -\layout Standard - -\backslash +\end_layout + +\begin_layout Plain Layout + + +\backslash alert<11>{ -\backslash +\backslash pgfnodeconnline{D3}{D4}} -\layout Standard - } -\layout Standard +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + -\backslash +\backslash end{pgfpicture} -\end_inset +\end_layout +\end_inset -\end_deeper -\layout AgainFrame +\end_layout -\begin_inset ERT -status Collapsed +\end_deeper +\end_deeper +\begin_layout AgainFrame +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout -\layout Standard -<6> -\end_inset +6 +\end_layout + +\end_inset hierarchy -\layout Subsection +\end_layout +\begin_layout Subsection Complexity of: Approximating the Shortest Path -\layout BeginFrame +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open +\begin_layout Plain Layout Approximators Compute Paths that Are Nearly As Short As a Shortest Path -\layout Definition +\end_layout -An +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Definition +An +\color none + \color red approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ -\end_inset +\end_inset -\color default - gets as input -\begin_deeper -\layout Enumerate +\color none + +\color inherit +gets as input +\end_layout +\begin_deeper +\begin_layout Enumerate a tuple \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$ -\end_inset +\end_inset and -\layout Enumerate +\end_layout +\begin_layout Enumerate a number \begin_inset Formula $r>1$ -\end_inset +\end_inset . -\layout Standard +\end_layout +\begin_layout Standard It outputs -\layout Itemize +\end_layout +\begin_layout Itemize a path from \begin_inset Formula $s$ -\end_inset +\end_inset + + to +\begin_inset space ~ +\end_inset - to\SpecialChar ~ \begin_inset Formula $t$ -\end_inset +\end_inset of length at most \begin_inset Formula $r\operatorname{d_{T}}(s,t)$ -\end_inset +\end_inset . -\end_deeper -\layout BeginFrame +\end_layout + +\end_deeper +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout There Exists a Logspace Approximation Scheme for -\newline +\begin_inset Newline newline +\end_inset + the Tournament Shortest Path Problem -\layout Theorem +\end_layout + +\end_inset + +\end_layout + +\begin_deeper +\begin_layout Theorem There exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ -\end_inset +\end_inset that for \begin_inset Formula $1 -\end_inset +7 +\end_layout + +\end_inset hierarchy -\layout Section* +\end_layout + +\begin_layout Standard +\begin_inset Note Note +status open + +\begin_layout Plain Layout +If a frame includes a program listing, the frame needs to be marked as +\begin_inset Quotes eld +\end_inset + +fragile +\begin_inset Quotes erd +\end_inset + +. + \SpecialChar LyX + has the FragileFrame layout for this. +\end_layout + +\end_inset + +\end_layout + +\begin_layout FragileFrame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +Just a frame with a program code listing +\end_layout + +\end_inset + + +\end_layout + +\begin_layout FragileFrame +This is some program code: +\end_layout + +\begin_deeper +\begin_layout Standard +\begin_inset listings +lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4" +inline false +status open + +\begin_layout Plain Layout + +def func(param): +\end_layout + +\begin_layout Plain Layout + + 'this is a python function' +\end_layout + +\begin_layout Plain Layout + + pass +\end_layout + +\begin_layout Plain Layout + +def func(param): +\end_layout + +\begin_layout Plain Layout + +'This is a German word: Tschüs' +\end_layout + +\begin_layout Plain Layout + +pass +\end_layout + +\begin_layout Plain Layout + +def func(param): +\end_layout + +\begin_layout Plain Layout + +'this is a python function' +\end_layout + +\begin_layout Plain Layout + +pass +\end_layout + +\end_inset + + +\end_layout + +\end_deeper +\begin_layout Section* Summary -\layout Subsection* +\end_layout +\begin_layout Subsection* Summary -\layout BeginFrame +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open +\begin_layout Plain Layout Summary -\layout Block +\end_layout +\end_inset -\begin_inset ERT -status Inlined -\layout Standard -{Summary} -\end_inset +\end_layout + +\begin_deeper +\begin_layout Block +\begin_inset Argument 2 +status collapsed +\begin_layout Plain Layout +Summary +\end_layout + +\end_inset -\begin_deeper -\layout Itemize -Tournament +\end_layout + +\begin_deeper +\begin_layout Itemize +Tournament +\color none + \color red reachability -\color default - is in -\color red +\color none + +\color inherit +is in +\color none +\color red + \begin_inset Formula $\Class{AC}^{0}$ -\end_inset +\end_inset -\color default +\color inherit . -\layout Itemize +\end_layout -There exists a +\begin_layout Itemize +There exists a +\color none + \color red logspace approximation scheme -\color default - for +\color none + +\color inherit +for +\color none + \color red approximating -\color default - shortest paths in tournaments. -\layout Itemize +\color none + +\color inherit +shortest paths in tournaments. +\end_layout -Finding +\begin_layout Itemize +Finding +\color none + \color red shortest paths -\color default - in tournaments is -\color red +\color none +\color inherit +in tournaments is +\color none + +\color red + \begin_inset Formula $\Class{NL}$ -\end_inset +\end_inset -complete -\color default +\color inherit . -\end_deeper -\layout Separator +\end_layout -\layout Block +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset -\begin_inset ERT -status Inlined +\end_layout + +\begin_layout Block +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Outlook +\end_layout -\layout Standard -{Outlook} -\end_inset +\end_inset -\begin_deeper -\layout Itemize +\end_layout +\begin_deeper +\begin_layout Itemize The same results apply to graphs with -\newline +\begin_inset Newline newline +\end_inset + bounded independence number. -\hfill +\begin_inset space \hfill{} +\end_inset + \begin_inset ERT -status Inlined +status collapsed -\layout Standard +\begin_layout Plain Layout -\backslash + +\backslash hyperlink{independence}{ -\backslash +\backslash beamergotobutton{More Details}} -\end_inset +\end_layout + +\end_inset -\layout Itemize +\end_layout +\begin_layout Itemize The complexity of finding paths in undirected graphs -\newline +\begin_inset Newline newline +\end_inset + is partly open. -\hfill +\begin_inset space \hfill{} +\end_inset + \begin_inset ERT -status Inlined +status collapsed -\layout Standard +\begin_layout Plain Layout -\backslash + +\backslash hyperlink{undirected}{ -\backslash +\backslash beamergotobutton{More Details}} -\end_inset +\end_layout + +\end_inset -\end_deeper -\layout Subsection* +\end_layout +\end_deeper +\end_deeper +\begin_layout Subsection* For Further Reading -\layout BeginFrame +\end_layout +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout For Further Reading -\layout Standard +\end_layout + +\end_inset +\end_layout + +\begin_deeper +\begin_layout Standard \begin_inset ERT -status Inlined +status open + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash beamertemplatebookbibitems -\end_inset +\end_layout +\end_inset -\layout Bibliography -\bibitem {Moon1968} -\SpecialChar ~ +\end_layout + +\begin_layout Bibliography +\begin_inset CommandInset bibitem +LatexCommand bibitem +key "Moon1968" +literal "true" + +\end_inset + + +\begin_inset space ~ +\end_inset + John Moon. \begin_inset ERT -status Collapsed +status collapsed + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash newblock -\end_inset +\end_layout + +\end_inset -\emph on +\emph on Topics on Tournaments. -\emph default +\emph default \begin_inset ERT -status Collapsed +status collapsed + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash newblock -\end_inset +\end_layout + +\end_inset Holt, Rinehart, and Winston, 1968. \begin_inset ERT -status Inlined +status collapsed + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash beamertemplatearticlebibitems -\end_inset +\end_layout + +\end_inset + +\end_layout -\layout Bibliography -\bibitem {NickelsenT2002} +\begin_layout Bibliography +\begin_inset CommandInset bibitem +LatexCommand bibitem +key "NickelsenT2002" +literal "true" + +\end_inset + + +\begin_inset space ~ +\end_inset -\SpecialChar ~ Arfst Nickelsen and Till Tantau. \begin_inset ERT -status Collapsed +status collapsed + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash newblock -\end_inset +\end_layout + +\end_inset On reachability in graphs with bounded independence number. \begin_inset ERT -status Collapsed +status collapsed + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash newblock -\end_inset +\end_layout + +\end_inset In -\emph on +\emph on Proc. of COCOON 2002 -\emph default +\emph default , Springer-Verlag, 2002. -\layout Bibliography -\bibitem {Tantau2004b} +\end_layout + +\begin_layout Bibliography +\begin_inset CommandInset bibitem +LatexCommand bibitem +key "Tantau2004b" +literal "true" + +\end_inset + + +\begin_inset space ~ +\end_inset -\SpecialChar ~ Till Tantau \begin_inset ERT -status Collapsed +status collapsed + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash newblock -\end_inset +\end_layout + +\end_inset A logspace approximation scheme for the shortest path problem for graphs with bounded independence number. \begin_inset ERT -status Collapsed +status collapsed + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash newblock -\end_inset +\end_layout + +\end_inset In -\emph on +\emph on Proc. of STACS 2004 -\emph default +\emph default , Springer-Verlag, 2004. \begin_inset ERT -status Collapsed +status collapsed + +\begin_layout Plain Layout -\layout Standard -\backslash +\backslash newblock -\end_inset +\end_layout - In press. -\layout EndFrame +\end_inset -\layout Standard -\start_of_appendix + In press. +\end_layout +\end_deeper +\begin_layout Standard +\start_of_appendix \begin_inset ERT -status Inlined +status open + +\begin_layout Plain Layout + -\layout Standard +\backslash +AtBeginSubsection[]{} +\end_layout -\backslash -AtBeginSubsection[]{} -\end_inset +\end_inset -\layout Section +\end_layout +\begin_layout Section Appendix -\layout Subsection +\end_layout +\begin_layout Subsection Graphs With Bounded Independence Number -\layout BeginFrame +\end_layout +\begin_layout Frame +\begin_inset Argument 3 +status collapsed -\begin_inset ERT -status Inlined +\begin_layout Plain Layout +label=independence +\end_layout + +\end_inset -\layout Standard -[label=independence] -\end_inset +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Definition of Independence Number of a Graph -\layout Definition +\end_layout + +\end_inset -The + +\end_layout + +\begin_deeper +\begin_layout Definition +The +\color none + \color red independence number -\color default +\color none +\color inherit + \begin_inset Formula $\alpha(G)$ -\end_inset +\end_inset of a directed graph -\newline +\begin_inset Newline newline +\end_inset + is the maximum number of vertices we can pick, -\newline +\begin_inset Newline newline +\end_inset + such that there is no edge between them. -\layout Example +\end_layout +\begin_layout Example Tournaments have independence number 1. -\layout BeginFrame +\end_layout + +\end_deeper +\begin_layout Standard +\begin_inset Separator plain +\end_inset + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Results for Tournaments also Apply to -\newline +\begin_inset Newline newline +\end_inset + Graphs With Bounded Independence Number -\layout Theorem +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Theorem +For each +\begin_inset space ~ +\end_inset -For each\SpecialChar ~ \begin_inset Formula $k$ -\end_inset +\end_inset -, +, +\color none + \color red reachability -\color default - in graphs with independence number -\newline -at most\SpecialChar ~ +\color none + +\color inherit +in graphs with independence number +\begin_inset Newline newline +\end_inset + +at most +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ -\end_inset +\end_inset is in \begin_inset Formula $\Class{AC}^{0}$ -\end_inset +\end_inset . -\layout Separator +\end_layout + +\begin_layout Standard +\begin_inset Separator plain +\end_inset + + +\end_layout -\layout Theorem +\begin_layout Theorem +For each +\begin_inset space ~ +\end_inset -For each\SpecialChar ~ \begin_inset Formula $k$ -\end_inset +\end_inset -, there exists a +, there exists a +\color none + \color red logspace approximation scheme -\color default - for approximating the shortest path in graphs with independence number - at most\SpecialChar ~ +\color none + +\color inherit +for approximating the shortest path in graphs with independence number at + most +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ -\end_inset +\end_inset + +\end_layout -\layout Separator +\begin_layout Standard +\begin_inset Separator plain +\end_inset -\layout Theorem -For each\SpecialChar ~ +\end_layout + +\begin_layout Theorem +For each +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ -\end_inset +\end_inset -, finding the +, finding the +\color none + \color red shortest path -\color default - in graphs with independence number at most\SpecialChar ~ +\color none + +\color inherit +in graphs with independence number at most +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ -\end_inset +\end_inset - is + is +\color none + \color red \begin_inset Formula $\Class{NL}$ -\end_inset +\end_inset -complete -\color default +\color inherit . -\layout Subsection +\end_layout +\end_deeper +\begin_layout Subsection Finding Paths in Undirected Graphs -\layout BeginFrame +\end_layout +\begin_layout Frame +\begin_inset Argument 1 +status collapsed -\begin_inset ERT -status Inlined +\begin_layout Plain Layout -\layout Standard -<1-2>[label=undirected] -\end_inset +1-2 +\end_layout +\end_inset + + +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=undirected +\end_layout + +\end_inset + + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Complexity of Finding Paths in Undirected Graphs -\newline +\begin_inset Newline newline +\end_inset + Is Party Unknown. -\layout Fact +\end_layout +\end_inset + +\end_layout + +\begin_deeper +\begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$ -\end_inset +\end_inset is \begin_inset Formula $\Class{SL}$ -\end_inset +\end_inset -complete. -\layout Corollary +\end_layout +\begin_layout Corollary For undirected graphs, we can solve -\begin_deeper -\layout Itemize +\end_layout +\begin_deeper +\begin_layout Itemize the reachability problem in logspace iff \begin_inset Formula $\Class L=\Class{SL}$ -\end_inset +\end_inset , -\layout Itemize +\end_layout +\begin_layout Itemize the construction problem in logspace iff -\begin_inset ERT -status Inlined +\begin_inset Flex Alternative +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout + +1 +\end_layout + +\end_inset + + +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +? +\end_layout + +\end_inset + + +\begin_inset Flex Alert +status open + +\begin_layout Plain Layout +\begin_inset Formula $\Class L=\Class{SL}$ +\end_inset -\layout Standard -\backslash -alt<1>{?}{ -\backslash -alert{$ -\backslash -Class L = -\backslash -Class{SL}$}} -\end_inset +\end_layout + +\end_inset + + +\end_layout + +\end_inset , -\layout Itemize +\end_layout +\begin_layout Itemize the optimization problem in logspace iff -\begin_inset ERT -status Inlined +\begin_inset Flex Alternative +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout + +1 +\end_layout + +\end_inset + + +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +? +\end_layout + +\end_inset + + +\begin_inset Flex Alert +status open -\layout Standard +\begin_layout Plain Layout +\begin_inset Formula $\Class L=\Class{NL}$ +\end_inset -\backslash -alt<1>{?}{ -\backslash -alert{$ -\backslash -Class L = -\backslash -Class{NL}$}} -\end_inset + +\end_layout + +\end_inset + + +\end_layout + +\end_inset , -\layout Itemize +\end_layout +\begin_layout Itemize the approximation problem in logspace iff ?. -\end_deeper -\layout Subsection +\end_layout +\end_deeper +\end_deeper +\begin_layout Subsection The Approximation Scheme is Optimal -\layout BeginFrame +\end_layout +\begin_layout Frame +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=optimality +\end_layout + +\end_inset -\begin_inset ERT -status Inlined -\layout Standard -[label=optimality] -\end_inset +\begin_inset Argument 4 +status open +\begin_layout Plain Layout The Approximation Scheme is Optimal -\layout Theorem +\end_layout +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Theorem Suppose there exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ -\end_inset +\end_inset that needs space \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$ -\end_inset +\end_inset . Then \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$ -\end_inset +\end_inset . -\layout Proof +\end_layout + +\begin_layout Proof -\begin_deeper -\layout Enumerate +\end_layout +\begin_deeper +\begin_layout Enumerate Suppose the approximation scheme exists. -\newline +\begin_inset Newline newline +\end_inset + We show \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$ -\end_inset +\end_inset . -\layout Enumerate +\end_layout +\begin_layout Enumerate Let \begin_inset Formula $(T,s,t)$ -\end_inset +\end_inset be an input. Let \begin_inset Formula $n$ -\end_inset +\end_inset be the number of vertices. -\layout Enumerate +\end_layout +\begin_layout Enumerate Run the approximation scheme for \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$ -\end_inset +\end_inset . -\newline +\begin_inset Newline newline +\end_inset + This needs space \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$ -\end_inset +\end_inset . -\layout Enumerate +\end_layout +\begin_layout Enumerate The resulting path has optimal length. \begin_inset ERT -status Collapsed +status collapsed -\layout Standard +\begin_layout Plain Layout -\backslash + +\backslash qedhere -\end_inset +\end_layout + +\end_inset -\end_deeper -\layout EndFrame +\end_layout -\the_end +\end_deeper +\end_deeper +\end_body +\end_document