X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=lib%2Fexamples%2Fbeamerlyxexample1.lyx;h=b4ee35edf3ae499f0f25da244d8ef1e5351d760b;hb=a1add5e8045905bbeb7747e463f5bb95e221346f;hp=bf172ad5a766596abed1388a72779da11c462094;hpb=0ed05b32be7506ba9b21e1378dec9844e8ff3f23;p=lyx.git diff --git a/lib/examples/beamerlyxexample1.lyx b/lib/examples/beamerlyxexample1.lyx index bf172ad5a7..b4ee35edf3 100644 --- a/lib/examples/beamerlyxexample1.lyx +++ b/lib/examples/beamerlyxexample1.lyx @@ -1,5 +1,5 @@ -#LyX 1.5.0svn created this file. For more info see http://www.lyx.org/ -\lyxformat 276 +#LyX 2.1 created this file. For more info see http://www.lyx.org/ +\lyxformat 474 \begin_document \begin_header \textclass beamer @@ -149,43 +149,77 @@ } \end_preamble \options notes=show +\use_default_options false +\maintain_unincluded_children false \language english +\language_package default \inputencoding auto +\fontencoding global \font_roman times \font_sans default \font_typewriter default +\font_math auto \font_default_family default +\use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 \font_tt_scale 100 \graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default \paperfontsize default \spacing single +\use_hyperref false \papersize default \use_geometry false -\use_amsmath 2 -\use_esint 0 +\use_package amsmath 2 +\use_package amssymb 2 +\use_package cancel 0 +\use_package esint 0 +\use_package mathdots 1 +\use_package mathtools 0 +\use_package mhchem 1 +\use_package stackrel 0 +\use_package stmaryrd 0 +\use_package undertilde 0 \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 +\index Index +\shortcut idx +\color #008000 +\end_index \secnumdepth 2 \tocdepth 2 \paragraph_separation indent -\defskip medskip +\paragraph_indentation default \quotes_language english \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 \begin_body \begin_layout Title The Complexity of -\newline +\begin_inset Newline newline +\end_inset + Finding Paths in Tournaments \end_layout @@ -194,13 +228,15 @@ Till Tantau \end_layout \begin_layout Institute -International Computer Schience Institute -\newline +International Computer Science Institute +\begin_inset Newline newline +\end_inset + Berkeley, California -\begin_inset OptArg +\begin_inset Argument 1 status collapsed -\begin_layout Standard +\begin_layout Plain Layout ICSI \end_layout @@ -213,19 +249,31 @@ ICSI January 30th, 2004 \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Outline \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard -\begin_inset LatexCommand tableofcontents +\begin_inset CommandInset toc +LatexCommand tableofcontents + \end_inset \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout [pausesections] \end_layout @@ -235,86 +283,55 @@ status collapsed \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \begin_inset ERT -status collapsed +status open -\begin_layout Standard +\begin_layout Plain Layout % Show the table of contents at the beginning \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout % of every subsection. \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash -AtBeginSubsection[]{ +AtBeginSubsection[]{% \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash frame{ \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash frametitle{Outline} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash tableofcontents[current,currentsubsection] \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout } \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout } \end_layout @@ -332,10 +349,20 @@ Introduction What are Tournaments? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Consist of Jousts Between Knights \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Columns \end_layout @@ -347,101 +374,89 @@ Tournaments Consist of Jousts Between Knights \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodebox{A}[virtual]{ \backslash -pgfxy(2,1)}{ -\backslash -pgfuseimage{knight1}}{2pt}{2pt} +pgfxy(2,1)}{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfuseimage{knight1}}{2pt}{2pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash pgfnodebox{B}[virtual]{ \backslash -pgfxy(6,1)}{ -\backslash -pgfuseimage{knight2}}{2pt}{2pt} +pgfxy(6,1)}{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfuseimage{knight2}}{2pt}{2pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash pgfnodebox{C}[virtual]{ \backslash -pgfxy(4,-1)}{ -\backslash -pgfuseimage{knight3}}{2pt}{2pt} +pgfxy(4,-1)}{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfuseimage{knight3}}{2pt}{2pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash pgfnodebox{D}[virtual]{ \backslash -pgfxy(4,3)}{ -\backslash -pgfuseimage{knight4}}{2pt}{2pt} -\end_layout - -\begin_layout Standard - +pgfxy(4,3)}{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfuseimage{knight4}}{2pt}{2pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash color{beamerexample} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<3->{ \backslash @@ -450,99 +465,68 @@ pgfsetendarrow{ pgfarrowto}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash -only<2->{ -\end_layout - -\begin_layout Standard - +only<2->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfsetlinewidth{0.6pt} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A}{B} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A}{C} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D}{A} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C}{B} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B}{D} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash -pgfnodeconnline{C}{D}} +pgfnodeconnline{C}{D} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -559,12 +543,11 @@ end{pgfpicture} \end_layout \begin_layout Block -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument 2 +status open -{What is a Tournament?} +\begin_layout Plain Layout +What is a Tournament? \end_layout \end_inset @@ -574,12 +557,11 @@ status inlined \begin_deeper \begin_layout Itemize -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument item:2 +status open -<1-> +\begin_layout Plain Layout +1- \end_layout \end_inset @@ -588,12 +570,11 @@ A group of knights. \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument item:2 +status open -<2-> +\begin_layout Plain Layout +2- \end_layout \end_inset @@ -602,12 +583,11 @@ Every pair has a joust. \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument item:2 +status open -<3-> +\begin_layout Plain Layout +3- \end_layout \end_inset @@ -617,10 +597,25 @@ In every joust one knight wins. \end_deeper \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments are Complete Directed Graphs \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Columns \end_layout @@ -632,115 +627,75 @@ Tournaments are Complete Directed Graphs \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash color{beamerexample} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfsetlinewidth{0.6pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash graphnode{A}{ \backslash pgfxy(2.5,1)} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash graphnode{B}{ \backslash pgfxy(5.5,1)} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash graphnode{C}{ \backslash pgfxy(4,-0.5)} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash graphnode{D}{ \backslash pgfxy(4,2.5)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash color{white} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfputat{ \backslash @@ -749,13 +704,9 @@ pgfnodecenter{A}}{ pgfbox[center,center]{$v_2$}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfputat{ \backslash @@ -764,13 +715,9 @@ pgfnodecenter{B}}{ pgfbox[center,center]{$v_3$}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfputat{ \backslash @@ -779,13 +726,9 @@ pgfnodecenter{C}}{ pgfbox[center,center]{$v_4$}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfputat{ \backslash @@ -794,131 +737,79 @@ pgfnodecenter{D}}{ pgfbox[center,center]{$v_1$}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash color{beamerexample} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfsetendarrow{ \backslash pgfarrowto} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodesetsepstart{2pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodesetsepend{4pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodeconnline{A}{B} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodeconnline{A}{C} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodeconnline{D}{A} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodeconnline{C}{B} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodeconnline{B}{D} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodeconnline{D}{C} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -935,12 +826,11 @@ end{pgfpicture} \end_layout \begin_layout Definition -\begin_inset ERT +\begin_inset Argument 1 status collapsed -\begin_layout Standard - -<2-> +\begin_layout Plain Layout +2- \end_layout \end_inset @@ -963,33 +853,49 @@ directed graphs, \begin_layout Enumerate with exactly one edge between -\newline +\begin_inset Newline newline +\end_inset + any two different vertices. \end_layout \end_deeper \end_deeper -\begin_layout BeginFrame -\begin_inset ERT -status collapsed +\end_deeper +\begin_layout Separator -\begin_layout Standard +\end_layout + +\begin_layout Frame +\begin_inset Argument 2 +status collapsed -[<+>] +\begin_layout Plain Layout ++ \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Arise Naturally in Different Situations \end_layout -\begin_layout ExampleBlock -\begin_inset ERT -status inlined +\end_inset -\begin_layout Standard -{Applicatins in Ordering Theory} +\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 @@ -1001,7 +907,9 @@ status inlined \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_layout @@ -1011,12 +919,11 @@ The comparison relation may be cyclic, however. \end_layout \begin_layout ExampleBlock -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument 2 +status collapsed -{Applications in Sociology} +\begin_layout Plain Layout +Applications in Sociology \end_layout \end_inset @@ -1027,9 +934,10 @@ status inlined \begin_deeper \begin_layout Standard Several candidates apply for a position. -\newline -Reviewers decide for any two candidates - whom they prefer. +\begin_inset Newline newline +\end_inset + +Reviewers decide for any two candidates whom they prefer. \end_layout @@ -1039,12 +947,11 @@ Reviewers decide for any two candidates \end_layout \begin_layout ExampleBlock -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument 2 +status collapsed -{Applications in Structural Complexity Theory} +\begin_layout Plain Layout +Applications in Structural Complexity Theory \end_layout \end_inset @@ -1063,7 +970,9 @@ A language \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 @@ -1071,110 +980,154 @@ It chooses from any two words the one more likely to be in . \end_layout +\end_deeper \end_deeper \begin_layout Subsection What Does ``Finding Paths'' Mean? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout ``Finding Paths'' is Ambiguous \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block -\begin_inset ERT -status inlined +\begin_inset Argument 2 +status open -\begin_layout Standard +\begin_layout Plain Layout +Input for +\begin_inset Flex Only +status open -{ -\backslash -strut Input for -\backslash -ignorespaces -\backslash -def -\backslash -par{}% because LyX inserts superfluous paragraphs +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +1 \end_layout -\begin_layout Standard +\end_inset +Path Finding Problems \end_layout -\begin_layout Standard +\end_inset -\backslash -only<1>{Path Finding Problems} -\backslash -ignorespaces +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +2-3 \end_layout -\begin_layout Standard +\end_inset + + +\begin_inset Formula $\Lang{reach}$ +\end_inset + \end_layout -\begin_layout Standard +\end_inset -\backslash -only<2-3>{$ -\backslash -Lang{reach}$} -\backslash -ignorespaces +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +4-5 \end_layout -\begin_layout Standard +\end_inset +the Construction Problem \end_layout -\begin_layout Standard +\end_inset -\backslash -only<4-5>{the Construction Problem} -\backslash -ignorespaces +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +6-7 \end_layout -\begin_layout Standard +\end_inset +the Optimization Problem \end_layout -\begin_layout Standard +\end_inset -\backslash -only<6-7>{the Optimization Problem} -\backslash -ignorespaces +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +8-9 \end_layout -\begin_layout Standard +\end_inset + + +\begin_inset Formula $\Lang{distance}$ +\end_inset + \end_layout -\begin_layout Standard +\end_inset -\backslash -only<8-9>{$ -\backslash -Lang{distance}$} -\backslash -ignorespaces +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +10- \end_layout -\begin_layout Standard +\end_inset +the Approximation Problem \end_layout -\begin_layout Standard +\end_inset -\backslash -only<10->{the Approximation Problem}} \end_layout \end_inset @@ -1224,12 +1177,11 @@ target \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument item:2 +status open - +\begin_layout Plain Layout +only@-9| visible@8- \end_layout \end_inset @@ -1240,7 +1192,10 @@ A \color red maximum distance \color inherit -\InsetSpace ~ + +\begin_inset space ~ +\end_inset + \begin_inset Formula $d$ \end_inset @@ -1249,7 +1204,7 @@ maximum distance \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1262,12 +1217,11 @@ phantom{p} \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument item:2 +status open - +\begin_layout Plain Layout +only@10- \end_layout \end_inset @@ -1292,7 +1246,7 @@ approximation ratio \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1305,19 +1259,25 @@ nointerlineskip \end_layout \begin_layout Overprint +\begin_inset Argument item:1 +status open +\begin_layout Plain Layout +1,3,5,7,9,11-12 \end_layout -\begin_deeper -\begin_layout Standard -\begin_inset ERT -status inlined +\end_inset -\begin_layout Standard +\end_layout -\backslash -onslide<1,3,5,7,9,11-12> +\begin_deeper +\begin_layout Columns +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +t,onlytextwidth \end_layout \end_inset @@ -1325,36 +1285,36 @@ onslide<1,3,5,7,9,11-12> \end_layout -\begin_layout Columns -\begin_inset ERT -status inlined - +\begin_deeper \begin_layout Standard +\begin_inset Flex Alternative +status open -[t,onlytextwidth] +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +1-2 \end_layout \end_inset -\end_layout +\begin_inset Argument 2 +status open -\begin_deeper -\begin_layout Standard +\begin_layout Plain Layout \begin_inset ERT -status inlined +status open -\begin_layout Standard +\begin_layout Plain Layout -\backslash -alt<1-2>{ \backslash column{ \backslash -textwidth}}{ -\backslash -column{5cm}} +textwidth} \end_layout \end_inset @@ -1362,13 +1322,17 @@ column{5cm}} \end_layout -\begin_layout ExampleBlock +\end_inset + + \begin_inset ERT -status inlined +status open -\begin_layout Standard +\begin_layout Plain Layout -{Example Input} + +\backslash +column{5cm} \end_layout \end_inset @@ -1376,45 +1340,63 @@ status inlined \end_layout -\begin_deeper -\begin_layout Standard -\begin_inset ERT -status inlined +\end_inset -\begin_layout Standard + +\end_layout + +\begin_layout ExampleBlock +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Example Input +\end_layout + +\end_inset + + +\end_layout + +\begin_deeper +\begin_layout Standard +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout \backslash begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color{beamerexample} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfsetlinewidth{0.6pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1423,11 +1405,11 @@ graphnode{A}{ pgfxy(3,1)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1436,11 +1418,11 @@ graphnode{B}{ pgfxy(5,1)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1449,11 +1431,11 @@ graphnode{C}{ pgfxy(4,0)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1462,30 +1444,30 @@ graphnode{D}{ pgfxy(4,2)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color{white} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1496,11 +1478,11 @@ pgfnodecenter{B}}{ pgfbox[center,center]{$t$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1511,30 +1493,30 @@ pgfnodecenter{D}}{ pgfbox[center,center]{$s$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color{beamerexample} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1543,107 +1525,107 @@ pgfsetendarrow{ pgfarrowto} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodesetsepstart{2pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodesetsepend{4pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A}{B} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A}{C} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D}{A} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C}{B} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B}{D} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D}{C} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1656,11 +1638,11 @@ pgfxy(5.3,1)}{ pgfbox[left,center]{, $d=2$}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1673,11 +1655,11 @@ pgfxy(5.3,1)}{ pgfbox[left,center]{, $r=1.5$}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1690,11 +1672,11 @@ pgfxy(5.3,1)}{ pgfbox[left,center]{, $r=1.25$}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1708,16 +1690,33 @@ end{pgfpicture} \end_deeper \begin_layout Standard +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +3- +\end_layout + +\end_inset + + \begin_inset ERT -status inlined +status open -\begin_layout Standard +\begin_layout Plain Layout \backslash -only<3->{ -\backslash -column{5cm}} +column{5cm} +\end_layout + +\end_inset + + \end_layout \end_inset @@ -1726,12 +1725,21 @@ column{5cm}} \end_layout \begin_layout ExampleBlock -\begin_inset ERT -status inlined +\begin_inset Argument 1 +status collapsed -\begin_layout Standard +\begin_layout Plain Layout +only@3- +\end_layout + +\end_inset + + +\begin_inset Argument 2 +status collapsed -{Example Output} +\begin_layout Plain Layout +Example Output \end_layout \end_inset @@ -1742,126 +1750,82 @@ status inlined \begin_deeper \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash -only<5-8,10->{ -\end_layout - -\begin_layout Standard - +only<5-8,10->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash color{beamerexample} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfsetlinewidth{0.6pt} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{A}{ \backslash pgfxy(3,1)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{B}{ \backslash pgfxy(5,1)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{C}{ \backslash pgfxy(4,0)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{D}{ \backslash pgfxy(4,2)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash color{white} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfputat{ \backslash @@ -1870,13 +1834,9 @@ pgfnodecenter{B}}{ pgfbox[center,center]{$t$}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfputat{ \backslash @@ -1885,159 +1845,94 @@ pgfnodecenter{D}}{ pgfbox[center,center]{$s$}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash color{beamerexample} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfsetendarrow{ \backslash pgfarrowto} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfnodesetsepstart{2pt} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfnodesetsepend{4pt} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash alert<7,12>{ \backslash pgfnodeconnline{A}{B}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash alert<5,11>{ \backslash pgfnodeconnline{A}{C}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash alert<5,7,11-12>{ \backslash pgfnodeconnline{D}{A}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash alert<5,11>{ \backslash pgfnodeconnline{C}{B}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B}{D} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B}{D} +pgfnodeconnline{D}{C} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard - - -\backslash -pgfnodeconnline{D}{C} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - } -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<3,9>{ \backslash @@ -2050,11 +1945,7 @@ pgfbox[left,center]{ alert{``Yes''}}}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2068,15 +1959,13 @@ end{pgfpicture} \end_deeper \end_deeper -\begin_layout Standard -\begin_inset ERT -status inlined - -\begin_layout Standard - +\end_deeper +\begin_layout Overprint +\begin_inset Argument item:1 +status open -\backslash -onslide<2,4,6,8,10> +\begin_layout Plain Layout +2,4,6,8,10 \end_layout \end_inset @@ -2084,13 +1973,13 @@ onslide<2,4,6,8,10> \end_layout +\begin_deeper \begin_layout Block -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument 2 +status collapsed -{Variants of Path Finding Problems} +\begin_layout Plain Layout +Variants of Path Finding Problems \end_layout \end_inset @@ -2099,65 +1988,67 @@ status inlined \end_layout \begin_deeper -\begin_layout Standard -\begin_inset ERT -status inlined - -\begin_layout Standard - +\begin_layout Description +\begin_inset Argument item:1 +status open -\backslash -usedescriptionitemofwidthas{Approximation Problem:} +\begin_layout Plain Layout +2- \end_layout \end_inset - -\end_layout - -\begin_layout Description -Reachability\InsetSpace ~ -Problem: -\begin_inset ERT -status collapsed - -\begin_layout Standard - -<2-> -\end_layout - +Reachability +\begin_inset space ~ \end_inset -Is there a path from +Problem: Is there a path from \begin_inset Formula $s$ \end_inset - to\InsetSpace ~ + to +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset ? +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Approximation Problem: \end_layout -\begin_layout Description -Construction\InsetSpace ~ -Problem: -\begin_inset ERT -status collapsed +\end_inset -\begin_layout Standard -<4-> \end_layout +\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 -Construct a path from +Problem: Construct a path from \begin_inset Formula $s$ \end_inset - to\InsetSpace ~ + to +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset @@ -2166,23 +2057,27 @@ Construct a path from \end_layout \begin_layout Description -Optimization\InsetSpace ~ -Problem: -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument item:1 +status open -<6-> +\begin_layout Plain Layout +6- \end_layout \end_inset -Construct a shortest path from +Optimization +\begin_inset space ~ +\end_inset + +Problem: Construct a shortest path from \begin_inset Formula $s$ \end_inset - to\InsetSpace ~ + to +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset @@ -2191,28 +2086,35 @@ Construct a shortest path from \end_layout \begin_layout Description -Distance\InsetSpace ~ -Problem: -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument item:1 +status open -<8-> +\begin_layout Plain Layout +8- \end_layout \end_inset -Is the distance of +Distance +\begin_inset space ~ +\end_inset + +Problem: Is the distance of \begin_inset Formula $s$ \end_inset - and\InsetSpace ~ + and +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset - at most\InsetSpace ~ + at most +\begin_inset space ~ +\end_inset + \begin_inset Formula $d$ \end_inset @@ -2221,32 +2123,39 @@ Is the distance of \end_layout \begin_layout Description -Approximation\InsetSpace ~ -Problem: -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument item:1 +status open -<10-> +\begin_layout Plain Layout +10- \end_layout \end_inset -Construct a path from +Approximation +\begin_inset space ~ +\end_inset + +Problem: Construct a path from \begin_inset Formula $s$ \end_inset - to\InsetSpace ~ + to +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset of length -\newline +\begin_inset Newline newline +\end_inset + approximately their distance. \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout Section @@ -2259,9 +2168,9 @@ Standard Complexity Classes \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2276,203 +2185,176 @@ pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Classes L and NL are Defined via -\newline +\begin_inset Newline newline +\end_inset + Logspace Turing Machines \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT -status open +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfputat{ \backslash -pgfxy(0,4)}{ -\backslash -tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} -\end_layout - -\begin_layout Standard - +pgfxy(0,4)}{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash -uncover<2->{ +tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +uncover<2->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfputat{ \backslash -pgfxy(0,0.5)}{ -\backslash -tape{}{output tape (write only)}{10690836937182}}} +pgfxy(0,0.5)}{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +tape{}{output tape (write only)}{10690836937182}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - -\backslash -uncover<3->{ +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +uncover<3->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfputat{ \backslash -pgfxy(7,2)}{ +pgfxy(7,2)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash shorttape{work tape (read/write), $O( \backslash log n)$ symbols}{}{42}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfputat{ \backslash -pgfxy(1.75,2.5)}{ +pgfxy(1.75,2.5)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash pgfbox[center,center]{ \backslash pgfuseimage{computer}}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - } +} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfsetlinewidth{0.6pt} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash color{structure} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfsetendarrow{ \backslash pgfarrowto} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85) \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash uncover<2->{ \backslash pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash uncover<3->{ \backslash pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2484,17 +2366,31 @@ end{pgfpicture} \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Logspace Turing Machines Are Quite Powerful \end_layout -\begin_layout Block -\begin_inset ERT -status inlined +\end_inset -\begin_layout Standard -{Deterministic logspace machines can compute} +\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 @@ -2521,12 +2417,11 @@ reachability in forests. \end_layout \begin_layout Block -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument 2 +status collapsed -{Non-deterministic logspace machines can compute} +\begin_layout Plain Layout +Non-deterministic logspace machines can compute \end_layout \end_inset @@ -2548,73 +2443,82 @@ satisfiability with two literals per clause. \end_layout \end_deeper -\begin_layout BeginFrame -\begin_inset ERT -status inlined - -\begin_layout Standard +\end_deeper +\begin_layout Separator -<1>[label=hierarchy] \end_layout -\end_inset +\begin_layout Frame +\begin_inset Argument 1 +status collapsed -The Complexity Class Hierarchy +\begin_layout Plain Layout +1 \end_layout -\begin_layout Standard -\begin_inset ERT -status inlined +\end_inset -\begin_layout Standard +\begin_inset Argument 3 +status collapsed -\backslash -begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm} +\begin_layout Plain Layout +label=hierarchy \end_layout -\begin_layout Standard +\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 -pgfsetlinewidth{0.8pt} +begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfsetlinewidth{0.8pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash heap{5.5}{3.5}{$ \backslash Class P$}{black}{1} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfsetdash{{2pt}}{0pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<2->{ \backslash @@ -2623,137 +2527,105 @@ heap{4.5}{3}{$ Class{NC}^2$}{black!50!structure}{2}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash heap{3.5}{2.5}{$ \backslash Class{NL}$}{black!50!structure}{3} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash heap{2.5}{2}{$ \backslash Class{L}$}{black!50!structure}{4} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<2->{ \backslash heap{1.75}{1.5}{$ \backslash -vphantom{A} +vphantom{A}% +\end_layout + +\begin_layout Plain Layout + + \backslash smash{ \backslash -Class{NC}^1}$}{black!50!structure}{5}} +Class{NC}^1}$}{black!50!structure}{5} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash pgfsetdash{}{0pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<2->{ \backslash heap{1.1}{1}{$ \backslash -vphantom{A} -\backslash -smash{ -\backslash -Class{AC}^0}$}{black}{6}} +vphantom{A}% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +smash{ +\backslash +Class{AC}^0}$}{black}{6} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfsetlinewidth{1.0pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash color{black} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfxyline(-5,0)(5,0) \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<1-2>{ \backslash @@ -2762,13 +2634,9 @@ langat{3.375}{$ Lang{reach}$}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<1-2>{ \backslash @@ -2779,21 +2647,9 @@ Lang{reach}_{ operatorname{forest}}$}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<2>{ \backslash @@ -2802,13 +2658,9 @@ langat{0.975}{$ Lang{addition}$}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<2>{ \backslash @@ -2825,13 +2677,9 @@ hbox{$ Lang{parity}$}}}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<3-5>{ \backslash @@ -2848,13 +2696,9 @@ hbox{$ Lang{reach}$}}}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<4->{ \backslash @@ -2865,13 +2709,9 @@ vbox{ ignorespaces \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash hbox{$ \backslash @@ -2882,13 +2722,9 @@ operatorname{forest}}$,} ignorespaces \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash hbox{$ \backslash @@ -2899,13 +2735,9 @@ operatorname{forest}}$,} ignorespaces \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash hbox{$ \backslash @@ -2916,28 +2748,25 @@ operatorname{path}}$,} ignorespaces \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash hbox{$ \backslash Lang{reach}_{ \backslash -operatorname{path}}$}}}} +operatorname{path}}$}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash only<5->{ \backslash @@ -2948,13 +2777,9 @@ Lang{reach}_{ operatorname{tourn}}$}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash only<6->{ \backslash @@ -2965,13 +2790,9 @@ vbox{ ignorespaces \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash hbox{$ \backslash @@ -2982,13 +2803,9 @@ operatorname{tourn}}$,} ignorespaces \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash hbox{$ \backslash @@ -2997,43 +2814,46 @@ Lang{distance}$,} ignorespaces \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash hbox{$ \backslash -Lang{reach}$}}}} +Lang{reach}$}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash only<7->{ \backslash -pgfsetdash{{1pt}}{0pt} +pgfsetdash{{1pt}}{0pt}% +\end_layout + +\begin_layout Plain Layout + + \backslash langat{2.375}{``$ \backslash Lang{approx}_{ \backslash -operatorname{tourn}}$''}} +operatorname{tourn}}$''} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3045,7 +2865,16 @@ end{pgfpicture} \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\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 @@ -3059,15 +2888,23 @@ The Circuit Complexity Classes AC \end_inset -\newline +\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 inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3076,11 +2913,7 @@ setlength leftmargini{1em} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3093,12 +2926,11 @@ nointerlineskip \end_layout \begin_layout Columns -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument 1 +status open -[t] +\begin_layout Plain Layout +t \end_layout \end_inset @@ -3112,27 +2944,15 @@ status collapsed \end_layout \begin_layout Block -\begin_inset ERT -status collapsed - -\begin_layout Standard - -{ -\end_layout - -\end_inset +\begin_inset Argument 2 +status open +\begin_layout Plain Layout Circuit Class \begin_inset Formula $\Class{AC}^{0}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Standard - -} \end_layout \end_inset @@ -3182,27 +3002,15 @@ unbounded fan-in \end_layout \begin_layout Block -\begin_inset ERT -status collapsed - -\begin_layout Standard - -{ -\end_layout - -\end_inset +\begin_inset Argument 2 +status open +\begin_layout Plain Layout Circuit Class \begin_inset Formula $\Class{NC}^{1}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Standard - -} \end_layout \end_inset @@ -3259,27 +3067,15 @@ bounded fan-in \end_layout \begin_layout Block -\begin_inset ERT -status collapsed - -\begin_layout Standard - -{ -\end_layout - -\end_inset +\begin_inset Argument 2 +status open +\begin_layout Plain Layout Circuit Class \begin_inset Formula $\Class{NC}^{2}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Standard - -} \end_layout \end_inset @@ -3312,15 +3108,15 @@ bounded fan-in . \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT +\begin_inset Argument 1 status collapsed -\begin_layout Standard - -<2> +\begin_layout Plain Layout +2 \end_layout \end_inset @@ -3332,12 +3128,24 @@ hierarchy Standard Complexity Results on Finding Paths \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout All Variants of Finding Paths in Directed Graphs -\newline +\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 @@ -3395,14 +3203,14 @@ the approximation problem in logspace iff . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT +\begin_inset Argument 1 status collapsed -\begin_layout Standard - -<3> +\begin_layout Plain Layout +3 \end_layout \end_inset @@ -3410,12 +3218,24 @@ status collapsed hierarchy \end_layout -\begin_layout BeginFrame -FindingPaths in Forests and Directed Paths is Easy, -\newline +\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 @@ -3450,13 +3270,13 @@ But Not Trivial -complete. \end_layout +\end_deeper \begin_layout AgainFrame -\begin_inset ERT +\begin_inset Argument 1 status collapsed -\begin_layout Standard - -<4> +\begin_layout Plain Layout +4 \end_layout \end_inset @@ -3472,10 +3292,20 @@ Finding Paths in Tournaments Complexity of: Does a Path Exist? \end_layout -\begin_layout BeginFrame +\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 @@ -3505,12 +3335,18 @@ contain all triples \end_layout \begin_layout Enumerate -there exists a path from\InsetSpace ~ +there exists a path from +\begin_inset space ~ +\end_inset + \begin_inset Formula $s$ \end_inset - to\InsetSpace ~ + to +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset @@ -3519,10 +3355,25 @@ there exists a path from\InsetSpace ~ \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\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 @@ -3535,12 +3386,11 @@ The Tournament Reachability Problem is Very Easy \end_layout \begin_layout AlertBlock -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument 2 +status collapsed -{Implications} +\begin_layout Plain Layout +Implications \end_layout \end_inset @@ -3576,14 +3426,14 @@ easier . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument 1 +status open -<5> +\begin_layout Plain Layout +5 \end_layout \end_inset @@ -3595,12 +3445,24 @@ hierarchy Complexity of: Construct a Shortest Path \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Finding a Shortest Path Is as Difficult as -\newline +\begin_inset Newline newline +\end_inset + the Distance Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition Let \color none @@ -3634,12 +3496,18 @@ the distance of \begin_inset Formula $s$ \end_inset - and\InsetSpace ~ + and +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset - is at most\InsetSpace ~ + is at most +\begin_inset space ~ +\end_inset + \begin_inset Formula $d$ \end_inset @@ -3648,10 +3516,25 @@ the distance of \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\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 @@ -3664,13 +3547,14 @@ The Tournament Distance Problem is Hard \end_layout \begin_layout Standard +\begin_inset space \hfill{} +\end_inset -\hfill \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3690,9 +3574,10 @@ beamerskipbutton{Skip Proof}} \begin_layout Corollary Shortest path in tournaments can be constructed -\newline -in logarithmic space, iff - +\begin_inset Newline newline +\end_inset + +in logarithmic space, iff \begin_inset Formula $\Class{L}=\Class{NL}$ \end_inset @@ -3710,7 +3595,16 @@ in logarithmic space, iff . \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\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 @@ -3718,11 +3612,17 @@ Proof That is NL-complete \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3735,12 +3635,11 @@ nointerlineskip \end_layout \begin_layout Columns -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument 1 +status open -[t,onlytextwidth] +\begin_layout Plain Layout +t,onlytextwidth \end_layout \end_inset @@ -3755,9 +3654,9 @@ status inlined \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3772,16 +3671,10 @@ leftmargini{1.5em} \end_layout \begin_layout Block -\begin_inset ERT -status collapsed - -\begin_layout Standard - -{ -\end_layout - -\end_inset +\begin_inset Argument 2 +status open +\begin_layout Plain Layout Reduce \begin_inset Formula $\Lang{reach}$ \end_inset @@ -3791,12 +3684,6 @@ Reduce \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Standard - -} \end_layout \end_inset @@ -3806,12 +3693,11 @@ status collapsed \begin_deeper \begin_layout Enumerate -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument item:2 +status open - +\begin_layout Plain Layout +alert@1 \end_layout \end_inset @@ -3828,12 +3714,11 @@ Is input \end_layout \begin_layout Enumerate -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument item:2 +status open -<2-| alert@2-8> +\begin_layout Plain Layout +2-| alert@2-8 \end_layout \end_inset @@ -3850,18 +3735,19 @@ Map \end_layout \begin_layout Enumerate -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument item:2 +status open -<9-| alert@9> +\begin_layout Plain Layout +9-| alert@9 \end_layout \end_inset Query: -\newline +\begin_inset Newline newline +\end_inset + \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$ \end_inset @@ -3875,34 +3761,21 @@ Query: \end_layout \begin_layout Block -\begin_inset ERT -status collapsed - -\begin_layout Standard - -{ -\end_layout - -\end_inset +\begin_inset Argument 2 +status open +\begin_layout Plain Layout Correctness -\begin_inset ERT -status collapsed - -\begin_layout Standard - -} \end_layout \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument 1 +status open -<10-> +\begin_layout Plain Layout +10- \end_layout \end_inset @@ -3912,24 +3785,31 @@ status collapsed \begin_deeper \begin_layout Enumerate -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument item:2 +status open -<10-| alert@10-11> +\begin_layout Plain Layout +10-| alert@10-11 \end_layout \end_inset -A path in\InsetSpace ~ +A path in +\begin_inset space ~ +\end_inset + \begin_inset Formula $G$ \end_inset induces -\newline -a length-3 path in\InsetSpace ~ +\begin_inset Newline newline +\end_inset + +a length-3 path in +\begin_inset space ~ +\end_inset + \begin_inset Formula $G'$ \end_inset @@ -3938,24 +3818,31 @@ a length-3 path in\InsetSpace ~ \end_layout \begin_layout Enumerate -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument item:2 +status open -<12-| alert@12-13> +\begin_layout Plain Layout +12-| alert@12-13 \end_layout \end_inset -A length-3 path in\InsetSpace ~ +A length-3 path in +\begin_inset space ~ +\end_inset + \begin_inset Formula $G'$ \end_inset induces -\newline -a path in\InsetSpace ~ +\begin_inset Newline newline +\end_inset + +a path in +\begin_inset space ~ +\end_inset + \begin_inset Formula $G'$ \end_inset @@ -3970,115 +3857,75 @@ a path in\InsetSpace ~ \begin_layout Example \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash color{beamerexample} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfsetlinewidth{0.6pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash graphnode{A}{ \backslash pgfxy(1,3.3)} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash graphnode{B}{ \backslash pgfxy(2,3.3)} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash graphnode{C}{ \backslash pgfxy(3,3.3)} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash graphnode{D}{ \backslash pgfxy(4,3.3)} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard +\backslash +color{white} \end_layout -\begin_layout Standard +\begin_layout Plain Layout -\end_layout - -\begin_layout Standard - - -\backslash -color{white} -\end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - \backslash pgfputat{ \backslash @@ -4087,13 +3934,9 @@ pgfnodecenter{A}}{ pgfbox[center,center]{$s$}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfputat{ \backslash @@ -4102,128 +3945,75 @@ pgfnodecenter{D}}{ pgfbox[center,center]{$t$}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash color{beamerexample} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfsetendarrow{ \backslash pgfarrowto} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodesetsepstart{2pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfnodesetsepend{2pt} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash alert<3>{ \backslash pgfnodeconnline{B}{A}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash alert<4>{ \backslash pgfnodeconnline{B}{C}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash alert<5,10-11,13>{ \backslash pgfnodeconnline{C}{D}} \end_layout -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash alert<6,10-11,13>{ \backslash pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash pgfputat{ \backslash @@ -4234,32 +4024,16 @@ pgfbox[left,center]{$G colon$}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout +\begin_layout Plain Layout -\begin_layout Standard - \backslash -only<2->{ -\end_layout - -\begin_layout Standard - +only<2->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfputat{ \backslash @@ -4270,240 +4044,160 @@ pgfbox[left,center]{$G' colon$}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{A1}{ \backslash pgfxy(1,2.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{B1}{ \backslash pgfxy(2,2.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{C1}{ \backslash pgfxy(3,2.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{D1}{ \backslash pgfxy(4,2.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{A2}{ \backslash pgfxy(1,1.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{B2}{ \backslash pgfxy(2,1.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{C2}{ \backslash pgfxy(3,1.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{D2}{ \backslash pgfxy(4,1.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{A3}{ \backslash pgfxy(1,0.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{B3}{ \backslash pgfxy(2,0.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{C3}{ \backslash pgfxy(3,0.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{D3}{ \backslash pgfxy(4,0.25)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{A4}{ \backslash pgfxy(1,-.75)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{B4}{ \backslash pgfxy(2,-.75)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{C4}{ \backslash pgfxy(3,-.75)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash graphnode{D4}{ \backslash pgfxy(4,-.75)} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - { + { \backslash color{white} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfputat{ \backslash @@ -4512,13 +4206,9 @@ pgfnodecenter{A1}}{ pgfbox[center,center]{$s'$}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfputat{ \backslash @@ -4527,1134 +4217,684 @@ pgfnodecenter{D4}}{ pgfbox[center,center]{$t'$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + } \end_layout -\begin_layout Standard +\begin_layout Plain Layout - }} +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +only<8->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + +\backslash +pgfsetlinewidth{0.4pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +color{beamerexample!25!averagebackgroundcolor} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash -only<8->{ +pgfnodeconnline{A2}{C1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout -\end_layout - -\begin_layout Standard - - -\backslash -pgfsetlinewidth{0.4pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -color{beamerexample!25!averagebackgroundcolor} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A2}{C1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A2}{D1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B2}{A1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B2}{C1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B2}{D1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{C2}{D1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{D2}{A1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{D2}{B1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A3}{C2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A3}{D2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B3}{A2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B3}{C2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B3}{D2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{C3}{D2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{D3}{A2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{D3}{B2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A4}{C3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A4}{D3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B4}{A3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B4}{C3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B4}{D3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{C4}{D3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{D4}{A3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{D4}{B3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfsetstartarrow{ -\backslash -pgfarrowto} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A1}{B1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B1}{C1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{C1}{D1} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A2}{B2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B2}{C2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{C2}{D2} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A3}{B3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B3}{C3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{C3}{D3} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{A4}{B4} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{B4}{C4} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconnline{C4}{D4} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfclearstartarrow -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - -\backslash -pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - + \backslash -color{beamerexample} +pgfnodeconnline{A2}{D1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{A1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfsetlinewidth{0.6pt} +pgfnodeconnline{B2}{C1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{D1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - } + +\backslash +pgfnodeconnline{C2}{D1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{D2}{A1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{D2}{B1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{A3}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash -only<3->{ +pgfnodeconnline{A3}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{A2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -color<3>{red} +pgfnodeconnline{B3}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B1}{A2} +pgfnodeconnline{C3}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{D3}{A2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B2}{A3} +pgfnodeconnline{D3}{B2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{A4}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B3}{A4} +pgfnodeconnline{A4}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B4}{A3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - } + +\backslash +pgfnodeconnline{B4}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B4}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{C4}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{D4}{A3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash -only<4->{ +pgfnodeconnline{D4}{B3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfsetstartarrow{ +\backslash +pgfarrowto} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -color<4>{red} +pgfnodeconnline{A1}{B1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B1}{C1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B1}{C2} +pgfnodeconnline{C1}{D1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{A2}{B2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B2}{C3} +pgfnodeconnline{B2}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{C2}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B3}{C4} +pgfnodeconnline{A3}{B3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - } + +\backslash +pgfnodeconnline{C3}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{A4}{B4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +\backslash +pgfnodeconnline{B4}{C4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{C4}{D4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash -only<5->{ +pgfclearstartarrow \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -color<5>{red} +pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{C1}{D2} +pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - -\backslash -alert<11>{ + \backslash -pgfnodeconnline{C2}{D3}} +pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - -\backslash -alert<12-13>{ + \backslash -pgfnodeconnline{C3}{D4}} +pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - } + +\backslash +pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + +\backslash +pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +color{beamerexample} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash -only<6->{ +pgfsetlinewidth{0.6pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash -color<6>{red} +only<3->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +color<3>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - -\backslash -alert<11>{ + \backslash -pgfnodeconnline{A1}{C2}} +pgfnodeconnline{B1}{A2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{A3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - -\backslash -alert<12-13>{ + \backslash -pgfnodeconnline{A2}{C3}} +pgfnodeconnline{B3}{A4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash -pgfnodeconnline{A3}{C4} +only<4->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +color<4>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - } + +\backslash +pgfnodeconnline{B1}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{C4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash -only<7->{ +only<5->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +color<5>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -color<7>{red} +pgfnodeconnline{C1}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +alert<11>{ +\backslash +pgfnodeconnline{C2}{D3}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash alert<12-13>{ \backslash -pgfnodeconnline{A1}{A2}} +pgfnodeconnline{C3}{D4}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash -pgfnodeconnline{A2}{A3} +only<6->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +color<6>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{A3}{A4} +alert<11>{ +\backslash +pgfnodeconnline{A1}{C2}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +alert<12-13>{ +\backslash +pgfnodeconnline{A2}{C3}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B1}{B2} +pgfnodeconnline{A3}{C4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + - \backslash -pgfnodeconnline{B2}{B3} +only<7->{% \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +color<7>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{B3}{B4} +alert<12-13>{ +\backslash +pgfnodeconnline{A1}{A2}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{A2}{A3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{C1}{C2} +pgfnodeconnline{A3}{A4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B1}{B2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{C2}{C3} +pgfnodeconnline{B2}{B3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{B4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{C3}{C4} +pgfnodeconnline{C1}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{C2}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash -pgfnodeconnline{D1}{D2} +pgfnodeconnline{C3}{C4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout + +\backslash +pgfnodeconnline{D1}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout - + \backslash pgfnodeconnline{D2}{D3} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout - + \backslash alert<11>{ \backslash pgfnodeconnline{D3}{D4}} \end_layout -\begin_layout Standard - -\end_layout - -\begin_layout Standard - - } -\end_layout - -\begin_layout Standard +\begin_layout Plain Layout +} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5666,14 +4906,14 @@ end{pgfpicture} \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT -status collapsed - -\begin_layout Standard +\begin_inset Argument 1 +status open -<6> +\begin_layout Plain Layout +6 \end_layout \end_inset @@ -5685,10 +4925,20 @@ hierarchy Complexity of: Approximating the Shortest Path \end_layout -\begin_layout BeginFrame +\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 \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition An \color none @@ -5731,7 +4981,10 @@ a path from \begin_inset Formula $s$ \end_inset - to\InsetSpace ~ + to +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset @@ -5744,13 +4997,29 @@ a path from \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout There Exists a Logspace Approximation Scheme for -\newline -the Tournament Shortest - Path Problem +\begin_inset Newline newline +\end_inset + +the Tournament Shortest Path Problem +\end_layout + +\end_inset + + \end_layout +\begin_deeper \begin_layout Theorem There exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ @@ -5761,57 +5030,157 @@ There exists an approximation scheme for \end_inset needs space -\begin_inset Formula \[ -O\left(\log|V|\log\frac{1}{r-1}\right).\] +\begin_inset Formula +\[ +O\left(\log|V|\log\frac{1}{r-1}\right). +\] + +\end_inset + + +\end_layout + +\begin_layout Pause + +\end_layout + +\begin_layout Corollary +In tournaments, paths can be constructed in logarithmic space. +\end_layout + +\begin_layout Standard +\begin_inset space \hfill{} +\end_inset + + +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + + +\backslash +hyperlink{optimality}{ +\backslash +beamergotobutton{More Details}} +\end_layout + +\end_inset + + +\end_layout + +\end_deeper +\begin_layout AgainFrame +\begin_inset Argument 1 +status collapsed + +\begin_layout Plain Layout +7 +\end_layout + +\end_inset + +hierarchy +\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 + +. + 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 -\end_inset +\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 Pause +\begin_layout Plain Layout + 'this is a python function' \end_layout -\begin_layout Corollary -In tournaments, paths can be constructed in logarithmic space. +\begin_layout Plain Layout + + pass \end_layout -\begin_layout Standard +\begin_layout Plain Layout -\hfill +def func(param): +\end_layout -\begin_inset ERT -status inlined +\begin_layout Plain Layout -\begin_layout Standard +'This is a German word: Tschüs' +\end_layout +\begin_layout Plain Layout -\backslash -hyperlink{optimality}{ -\backslash -beamergotobutton{More Details}} +pass \end_layout -\end_inset - +\begin_layout Plain Layout +def func(param): \end_layout -\begin_layout AgainFrame -\begin_inset ERT -status collapsed +\begin_layout Plain Layout -\begin_layout Standard +'this is a python function' +\end_layout -<7> +\begin_layout Plain Layout + +pass \end_layout \end_inset -hierarchy + \end_layout +\end_deeper \begin_layout Section* Summary \end_layout @@ -5820,17 +5189,26 @@ Summary Summary \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Summary \end_layout -\begin_layout Block -\begin_inset ERT -status inlined +\end_inset -\begin_layout Standard -{Summary} +\end_layout + +\begin_deeper +\begin_layout Block +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Summary \end_layout \end_inset @@ -5910,12 +5288,11 @@ in tournaments is \end_layout \begin_layout Block -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_inset Argument 2 +status collapsed -{Outlook} +\begin_layout Plain Layout +Outlook \end_layout \end_inset @@ -5926,14 +5303,18 @@ status inlined \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 -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5949,14 +5330,18 @@ beamergotobutton{More Details}} \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 -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5970,20 +5355,31 @@ beamergotobutton{More Details}} \end_layout +\end_deeper \end_deeper \begin_layout Subsection* For Further Reading \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout For Further Reading \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT -status inlined +status open -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5996,18 +5392,22 @@ beamertemplatebookbibitems \end_layout \begin_layout Bibliography - -\begin_inset LatexCommand bibitem +\begin_inset CommandInset bibitem +LatexCommand bibitem key "Moon1968" \end_inset -\InsetSpace ~ + + +\begin_inset space ~ +\end_inset + John Moon. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6016,8 +5416,6 @@ newblock \end_inset - -\emph default \emph on Topics on Tournaments. @@ -6027,7 +5425,7 @@ Topics on Tournaments. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6039,9 +5437,9 @@ newblock Holt, Rinehart, and Winston, 1968. \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6054,18 +5452,22 @@ beamertemplatearticlebibitems \end_layout \begin_layout Bibliography - -\begin_inset LatexCommand bibitem +\begin_inset CommandInset bibitem +LatexCommand bibitem key "NickelsenT2002" \end_inset -\InsetSpace ~ + + +\begin_inset space ~ +\end_inset + Arfst Nickelsen and Till Tantau. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6078,7 +5480,7 @@ newblock \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6087,9 +5489,7 @@ newblock \end_inset - In -\emph default - + In \emph on Proc. of COCOON 2002 @@ -6098,17 +5498,21 @@ Proc. \end_layout \begin_layout Bibliography - -\begin_inset LatexCommand bibitem +\begin_inset CommandInset bibitem +LatexCommand bibitem key "Tantau2004b" \end_inset -\InsetSpace ~ + + +\begin_inset space ~ +\end_inset + Till Tantau \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6122,7 +5526,7 @@ newblock \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6131,9 +5535,7 @@ newblock \end_inset - In -\emph default - + In \emph on Proc. of STACS 2004 @@ -6143,7 +5545,7 @@ Proc. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6155,20 +5557,17 @@ newblock In press. \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \start_of_appendix \begin_inset ERT -status inlined +status open -\begin_layout Standard +\begin_layout Plain Layout \backslash -AtBeginSubsection[]{} +AtBeginSubsection[]{} \end_layout \end_inset @@ -6184,20 +5583,30 @@ Appendix Graphs With Bounded Independence Number \end_layout -\begin_layout BeginFrame -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_layout Frame +\begin_inset Argument 3 +status collapsed -[label=independence] +\begin_layout Plain Layout +label=independence \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Definition of Independence Number of a Graph \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition The \color none @@ -6212,11 +5621,14 @@ independence number \end_inset of a directed graph -\newline +\begin_inset Newline newline +\end_inset + is the maximum number of vertices we can pick, -\newline -such that - there is no edge between them. +\begin_inset Newline newline +\end_inset + +such that there is no edge between them. \end_layout \begin_layout Example @@ -6224,15 +5636,34 @@ Tournaments have independence number 1. \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Results for Tournaments also Apply to -\newline -Graphs With Bounded Independence - Number +\begin_inset Newline newline +\end_inset + +Graphs With Bounded Independence Number +\end_layout + +\end_inset + + \end_layout +\begin_deeper \begin_layout Theorem -For each\InsetSpace ~ +For each +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset @@ -6246,8 +5677,13 @@ reachability \color inherit in graphs with independence number -\newline -at most\InsetSpace ~ +\begin_inset Newline newline +\end_inset + +at most +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset @@ -6264,7 +5700,10 @@ at most\InsetSpace ~ \end_layout \begin_layout Theorem -For each\InsetSpace ~ +For each +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset @@ -6277,8 +5716,11 @@ logspace approximation scheme \color none \color inherit -for approximating the shortest path in graphs with independence number - at most\InsetSpace ~ +for approximating the shortest path in graphs with independence number at + most +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset @@ -6291,7 +5733,10 @@ for approximating the shortest path in graphs with independence number \end_layout \begin_layout Theorem -For each\InsetSpace ~ +For each +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset @@ -6304,7 +5749,10 @@ shortest path \color none \color inherit -in graphs with independence number at most\InsetSpace ~ +in graphs with independence number at most +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset @@ -6322,26 +5770,49 @@ in graphs with independence number at most\InsetSpace ~ . \end_layout +\end_deeper \begin_layout Subsection Finding Paths in Undirected Graphs \end_layout -\begin_layout BeginFrame -\begin_inset ERT -status inlined +\begin_layout Frame +\begin_inset Argument 1 +status collapsed -\begin_layout Standard +\begin_layout Plain Layout +1-2 +\end_layout + +\end_inset + + +\begin_inset Argument 3 +status collapsed -<1-2>[label=undirected] +\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. \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$ \end_inset @@ -6368,20 +5839,43 @@ the reachability problem in logspace iff \begin_layout Itemize the construction problem in logspace iff -\begin_inset ERT -status inlined +\begin_inset Flex Alternative +status open -\begin_layout Standard +\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 + + +\end_layout + +\end_inset -\backslash -alt<1>{?}{ -\backslash -alert{$ -\backslash -Class L = -\backslash -Class{SL}$}} \end_layout \end_inset @@ -6391,20 +5885,43 @@ Class{SL}$}} \begin_layout Itemize the optimization problem in logspace iff -\begin_inset ERT -status inlined +\begin_inset Flex Alternative +status open -\begin_layout Standard +\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{NL}$ +\end_inset + + +\end_layout + +\end_inset -\backslash -alt<1>{?}{ -\backslash -alert{$ -\backslash -Class L = -\backslash -Class{NL}$}} \end_layout \end_inset @@ -6417,25 +5934,36 @@ the approximation problem in logspace iff ?. \end_layout +\end_deeper \end_deeper \begin_layout Subsection The Approximation Scheme is Optimal \end_layout -\begin_layout BeginFrame -\begin_inset ERT -status inlined - -\begin_layout Standard +\begin_layout Frame +\begin_inset Argument 3 +status collapsed -[label=optimality] +\begin_layout Plain Layout +label=optimality \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Approximation Scheme is Optimal \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}$ @@ -6460,7 +5988,9 @@ Suppose there exists an approximation scheme for \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 @@ -6488,7 +6018,9 @@ Run the approximation scheme for \end_inset . -\newline +\begin_inset Newline newline +\end_inset + This needs space \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$ \end_inset @@ -6502,7 +6034,7 @@ The resulting path has optimal length. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6515,9 +6047,6 @@ qedhere \end_layout \end_deeper -\begin_layout EndFrame - -\end_layout - +\end_deeper \end_body \end_document