X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=lib%2Fexamples%2Fbeamerlyxexample1.lyx;h=b4ee35edf3ae499f0f25da244d8ef1e5351d760b;hb=a1add5e8045905bbeb7747e463f5bb95e221346f;hp=5ec80b8cfa2770714cabeb744a32def14bbad52a;hpb=25aef8a80135e4742e6513c7cf0f54b56af128d7;p=lyx.git diff --git a/lib/examples/beamerlyxexample1.lyx b/lib/examples/beamerlyxexample1.lyx index 5ec80b8cfa..b4ee35edf3 100644 --- a/lib/examples/beamerlyxexample1.lyx +++ b/lib/examples/beamerlyxexample1.lyx @@ -1,8 +1,7 @@ -#LyX 1.6.0 created this file. For more info see http://www.lyx.org/ -\lyxformat 345 +#LyX 2.1 created this file. For more info see http://www.lyx.org/ +\lyxformat 474 \begin_document \begin_header -\use_default_options false \textclass beamer \begin_preamble \beamertemplateshadingbackground{red!5}{structure!5} @@ -150,38 +149,68 @@ } \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 -\author "" +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false \end_header \begin_body @@ -199,12 +228,12 @@ Till Tantau \end_layout \begin_layout Institute -International Computer Schience Institute +International Computer Science Institute \begin_inset Newline newline \end_inset Berkeley, California -\begin_inset OptArg +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout @@ -220,10 +249,20 @@ 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 CommandInset toc LatexCommand tableofcontents @@ -244,13 +283,10 @@ status collapsed \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \begin_inset ERT -status collapsed +status open \begin_layout Plain Layout @@ -259,26 +295,14 @@ status collapsed \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - % of every subsection. \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash -AtBeginSubsection[]{ -\end_layout - -\begin_layout Plain Layout - +AtBeginSubsection[]{% \end_layout \begin_layout Plain Layout @@ -290,10 +314,6 @@ frame{ \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash frametitle{Outline} @@ -301,19 +321,11 @@ frametitle{Outline} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash tableofcontents[current,currentsubsection] \end_layout -\begin_layout Plain Layout - -\end_layout - \begin_layout Plain Layout } @@ -321,10 +333,6 @@ tableofcontents[current,currentsubsection] \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - } \end_layout @@ -341,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 @@ -367,90 +385,78 @@ begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodebox{A}[virtual]{ \backslash -pgfxy(2,1)}{ -\backslash -pgfuseimage{knight1}}{2pt}{2pt} +pgfxy(2,1)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfuseimage{knight1}}{2pt}{2pt} \end_layout \begin_layout Plain Layout - + \backslash pgfnodebox{B}[virtual]{ \backslash -pgfxy(6,1)}{ -\backslash -pgfuseimage{knight2}}{2pt}{2pt} +pgfxy(6,1)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfuseimage{knight2}}{2pt}{2pt} \end_layout \begin_layout Plain Layout - + \backslash pgfnodebox{C}[virtual]{ \backslash -pgfxy(4,-1)}{ -\backslash -pgfuseimage{knight3}}{2pt}{2pt} +pgfxy(4,-1)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfuseimage{knight3}}{2pt}{2pt} \end_layout \begin_layout Plain Layout - + \backslash pgfnodebox{D}[virtual]{ \backslash -pgfxy(4,3)}{ -\backslash -pgfuseimage{knight4}}{2pt}{2pt} -\end_layout - -\begin_layout Plain Layout - +pgfxy(4,3)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfuseimage{knight4}}{2pt}{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<3->{ \backslash @@ -461,17 +467,9 @@ pgfarrowto}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash -only<2->{ -\end_layout - -\begin_layout Plain Layout - +only<2->{% \end_layout \begin_layout Plain Layout @@ -483,10 +481,6 @@ pgfsetlinewidth{0.6pt} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{A}{B} @@ -494,10 +488,6 @@ pgfnodeconnline{A}{B} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{A}{C} @@ -505,10 +495,6 @@ pgfnodeconnline{A}{C} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{D}{A} @@ -516,10 +502,6 @@ pgfnodeconnline{D}{A} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{C}{B} @@ -527,10 +509,6 @@ pgfnodeconnline{C}{B} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{B}{D} @@ -538,17 +516,14 @@ pgfnodeconnline{B}{D} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash -pgfnodeconnline{C}{D}} +pgfnodeconnline{C}{D} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout @@ -568,12 +543,11 @@ end{pgfpicture} \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{What is a Tournament?} +What is a Tournament? \end_layout \end_inset @@ -583,12 +557,11 @@ status collapsed \begin_deeper \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<1-> +1- \end_layout \end_inset @@ -597,12 +570,11 @@ A group of knights. \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<2-> +2- \end_layout \end_inset @@ -611,12 +583,11 @@ Every pair has a joust. \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<3-> +3- \end_layout \end_inset @@ -626,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 @@ -652,33 +638,21 @@ begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{A}{ \backslash @@ -687,11 +661,7 @@ pgfxy(2.5,1)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{B}{ \backslash @@ -700,11 +670,7 @@ pgfxy(5.5,1)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{C}{ \backslash @@ -713,11 +679,7 @@ pgfxy(4,-0.5)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{D}{ \backslash @@ -726,30 +688,14 @@ pgfxy(4,2.5)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{white} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -760,11 +706,7 @@ pgfbox[center,center]{$v_2$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -775,11 +717,7 @@ pgfbox[center,center]{$v_3$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -790,11 +728,7 @@ pgfbox[center,center]{$v_4$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -805,30 +739,14 @@ pgfbox[center,center]{$v_1$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetendarrow{ \backslash @@ -837,98 +755,62 @@ pgfarrowto} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodesetsepstart{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodesetsepend{4pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{A}{B} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{A}{C} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{D}{A} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{C}{B} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B}{D} \end_layout \begin_layout Plain Layout - -\backslash -pgfnodeconnline{B}{D} -\end_layout - -\begin_layout Plain Layout - -\end_layout -\begin_layout Plain Layout - - \backslash pgfnodeconnline{D}{C} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash end{pgfpicture} @@ -944,12 +826,11 @@ end{pgfpicture} \end_layout \begin_layout Definition -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout - -<2-> +2- \end_layout \end_inset @@ -980,27 +861,41 @@ any two different vertices. \end_deeper \end_deeper -\begin_layout BeginFrame -\begin_inset ERT +\end_deeper +\begin_layout Separator + +\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 +\end_inset + + +\end_layout + +\begin_deeper \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Applicatins in Ordering Theory} +Applications in Ordering Theory \end_layout \end_inset @@ -1024,12 +919,11 @@ The comparison relation may be cyclic, however. \end_layout \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Applications in Sociology} +Applications in Sociology \end_layout \end_inset @@ -1053,12 +947,11 @@ Reviewers decide for any two candidates whom they prefer. \end_layout \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Applications in Structural Complexity Theory} +Applications in Structural Complexity Theory \end_layout \end_inset @@ -1087,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 -\begin_layout Block -\begin_inset ERT -status collapsed +\end_inset -\begin_layout Plain Layout -{ -\backslash -strut Input for -\backslash -ignorespaces -\backslash -def -\backslash -par{}% because LyX inserts superfluous paragraphs \end_layout +\begin_deeper +\begin_layout Block +\begin_inset Argument 2 +status open + \begin_layout Plain Layout +Input for +\begin_inset Flex Only +status open -\end_layout +\begin_layout Plain Layout +\begin_inset Argument 1 +status open \begin_layout Plain Layout +1 +\end_layout +\end_inset -\backslash -only<1>{Path Finding Problems} -\backslash -ignorespaces +Path Finding Problems \end_layout +\end_inset + + +\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 Plain Layout +\end_inset -\backslash -only<2-3>{$ -\backslash -Lang{reach}$} -\backslash -ignorespaces -\end_layout +\begin_inset Formula $\Lang{reach}$ +\end_inset -\begin_layout Plain Layout \end_layout -\begin_layout Plain Layout +\end_inset -\backslash -only<4-5>{the Construction Problem} -\backslash -ignorespaces -\end_layout +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open \begin_layout Plain Layout +4-5 +\end_layout + +\end_inset +the Construction Problem \end_layout +\end_inset + + +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + \begin_layout Plain Layout +6-7 +\end_layout +\end_inset -\backslash -only<6-7>{the Optimization Problem} -\backslash -ignorespaces +the Optimization Problem \end_layout +\end_inset + + +\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 Plain Layout +\end_inset + + +\begin_inset Formula $\Lang{distance}$ +\end_inset -\backslash -only<8-9>{$ -\backslash -Lang{distance}$} -\backslash -ignorespaces \end_layout +\end_inset + + +\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 Plain Layout +\end_inset + +the Approximation Problem +\end_layout + +\end_inset -\backslash -only<10->{the Approximation Problem}} \end_layout \end_inset @@ -1240,12 +1177,11 @@ target \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - - +only@-9| visible@8- \end_layout \end_inset @@ -1281,12 +1217,11 @@ phantom{p} \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - - +only@10- \end_layout \end_inset @@ -1324,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 collapsed +\end_inset -\begin_layout Plain Layout +\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 @@ -1344,36 +1285,59 @@ onslide<1,3,5,7,9,11-12> \end_layout -\begin_layout Columns -\begin_inset ERT -status collapsed +\begin_deeper +\begin_layout Standard +\begin_inset Flex Alternative +status open \begin_layout Plain Layout +\begin_inset Argument 1 +status open -[t,onlytextwidth] +\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 collapsed +status open \begin_layout Plain Layout -\backslash -alt<1-2>{ \backslash column{ \backslash -textwidth}}{ +textwidth} +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset ERT +status open + +\begin_layout Plain Layout + + \backslash -column{5cm}} +column{5cm} +\end_layout + +\end_inset + + \end_layout \end_inset @@ -1382,12 +1346,11 @@ column{5cm}} \end_layout \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Example Input} +Example Input \end_layout \end_inset @@ -1727,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 collapsed +status open \begin_layout Plain Layout \backslash -only<3->{ -\backslash -column{5cm}} +column{5cm} +\end_layout + +\end_inset + + \end_layout \end_inset @@ -1745,12 +1725,21 @@ column{5cm}} \end_layout \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout +only@3- +\end_layout + +\end_inset + -{Example Output} +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Example Output \end_layout \end_inset @@ -1772,83 +1761,55 @@ begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} \begin_layout Plain Layout + +\backslash +only<5-8,10->{% \end_layout \begin_layout Plain Layout \backslash -only<5-8,10->{ +color{beamerexample} \end_layout \begin_layout Plain Layout + +\backslash +pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout - + \backslash -color{beamerexample} +graphnode{A}{ +\backslash +pgfxy(3,1)} \end_layout \begin_layout Plain Layout + +\backslash +graphnode{B}{ +\backslash +pgfxy(5,1)} \end_layout \begin_layout Plain Layout - + \backslash -pgfsetlinewidth{0.6pt} +graphnode{C}{ +\backslash +pgfxy(4,0)} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - -\backslash -graphnode{A}{ -\backslash -pgfxy(3,1)} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -graphnode{B}{ -\backslash -pgfxy(5,1)} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -graphnode{C}{ -\backslash -pgfxy(4,0)} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D}{ \backslash @@ -1857,30 +1818,14 @@ pgfxy(4,2)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash color{white} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash @@ -1891,11 +1836,7 @@ pgfbox[center,center]{$t$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash @@ -1906,30 +1847,14 @@ pgfbox[center,center]{$s$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfsetendarrow{ \backslash @@ -1938,42 +1863,21 @@ pgfarrowto} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodesetsepstart{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodesetsepend{4pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<7,12>{ \backslash @@ -1982,11 +1886,7 @@ pgfnodeconnline{A}{B}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<5,11>{ \backslash @@ -1995,11 +1895,7 @@ pgfnodeconnline{A}{C}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<5,7,11-12>{ \backslash @@ -2008,11 +1904,7 @@ pgfnodeconnline{D}{A}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<5,11>{ \backslash @@ -2021,42 +1913,26 @@ pgfnodeconnline{C}{B}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B}{D} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{D}{C} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - } -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash only<3,9>{ \backslash @@ -2071,10 +1947,6 @@ alert{``Yes''}}}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash end{pgfpicture} @@ -2087,15 +1959,13 @@ end{pgfpicture} \end_deeper \end_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\end_deeper +\begin_layout Overprint +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - - -\backslash -onslide<2,4,6,8,10> +2,4,6,8,10 \end_layout \end_inset @@ -2103,13 +1973,13 @@ onslide<2,4,6,8,10> \end_layout +\begin_deeper \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Variants of Path Finding Problems} +Variants of Path Finding Problems \end_layout \end_inset @@ -2118,39 +1988,21 @@ status collapsed \end_layout \begin_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\begin_layout Description +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - - -\backslash -usedescriptionitemofwidthas{Approximation Problem:} +2- \end_layout \end_inset - -\end_layout - -\begin_layout Description Reachability \begin_inset space ~ \end_inset -Problem: -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -<2-> -\end_layout - -\end_inset - -Is there a path from +Problem: Is there a path from \begin_inset Formula $s$ \end_inset @@ -2163,25 +2015,33 @@ Is there a path from \end_inset ? +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Approximation Problem: \end_layout -\begin_layout Description -Construction -\begin_inset space ~ \end_inset -Problem: -\begin_inset ERT -status collapsed -\begin_layout Plain Layout +\end_layout + +\begin_layout Description +\begin_inset Argument item:1 +status open -<4-> +\begin_layout Plain Layout +4- \end_layout \end_inset -Construct a path from +Construction +\begin_inset space ~ +\end_inset + +Problem: Construct a path from \begin_inset Formula $s$ \end_inset @@ -2197,22 +2057,20 @@ Construct a path from \end_layout \begin_layout Description -Optimization -\begin_inset space ~ -\end_inset - -Problem: -\begin_inset ERT -status collapsed +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - -<6-> +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 @@ -2228,22 +2086,20 @@ Construct a shortest path from \end_layout \begin_layout Description -Distance -\begin_inset space ~ -\end_inset - -Problem: -\begin_inset ERT -status collapsed +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - -<8-> +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 @@ -2267,22 +2123,20 @@ Is the distance of \end_layout \begin_layout Description -Approximation -\begin_inset space ~ -\end_inset - -Problem: -\begin_inset ERT -status collapsed +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - -<10-> +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 @@ -2301,6 +2155,7 @@ Construct a path from approximately their distance. \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout Section @@ -2330,7 +2185,11 @@ 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 \begin_inset Newline newline \end_inset @@ -2338,80 +2197,86 @@ The Classes L and NL are Defined via Logspace Turing Machines \end_layout -\begin_layout Standard -\begin_inset ERT -status open +\end_inset -\begin_layout Plain Layout +\end_layout -\backslash -begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} -\end_layout +\begin_deeper +\begin_layout Standard +\begin_inset ERT +status collapsed \begin_layout Plain Layout + +\backslash +begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} \end_layout \begin_layout Plain Layout - + \backslash pgfputat{ \backslash -pgfxy(0,4)}{ -\backslash -tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} -\end_layout - -\begin_layout Plain Layout - +pgfxy(0,4)}{% \end_layout \begin_layout Plain Layout \backslash -uncover<2->{ +tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} \end_layout \begin_layout Plain Layout + +\backslash +uncover<2->{% \end_layout \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 Plain Layout + +\backslash +tape{}{output tape (write only)}{10690836937182}} \end_layout \begin_layout Plain Layout - -\backslash -uncover<3->{ +} \end_layout \begin_layout Plain Layout + +\backslash +uncover<3->{% \end_layout \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 @@ -2420,15 +2285,16 @@ log n)$ symbols}{}{42}} \begin_layout Plain Layout + +\backslash +pgfputat{ +\backslash +pgfxy(1.75,2.5)}{% \end_layout \begin_layout Plain Layout - -\backslash -pgfputat{ -\backslash -pgfxy(1.75,2.5)}{ + \backslash pgfbox[center,center]{ \backslash @@ -2437,50 +2303,26 @@ pgfuseimage{computer}}} \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - } -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{structure} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetendarrow{ \backslash @@ -2489,22 +2331,14 @@ pgfarrowto} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85) \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash uncover<2->{ \backslash @@ -2513,11 +2347,7 @@ pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash uncover<3->{ \backslash @@ -2526,10 +2356,6 @@ pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash end{pgfpicture} @@ -2540,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 +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Deterministic logspace machines can compute} +Deterministic logspace machines can compute \end_layout \end_inset @@ -2577,12 +2417,11 @@ reachability in forests. \end_layout \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Non-deterministic logspace machines can compute} +Non-deterministic logspace machines can compute \end_layout \end_inset @@ -2604,20 +2443,45 @@ satisfiability with two literals per clause. \end_layout \end_deeper -\begin_layout BeginFrame -\begin_inset ERT +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout +1 +\end_layout + +\end_inset + -<1>[label=hierarchy] +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=hierarchy \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Complexity Class Hierarchy \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -2631,22 +2495,14 @@ begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{0.8pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash heap{5.5}{3.5}{$ \backslash @@ -2655,22 +2511,14 @@ Class P$}{black}{1} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetdash{{2pt}}{0pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<2->{ \backslash @@ -2681,11 +2529,7 @@ Class{NC}^2$}{black!50!structure}{2}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash heap{3.5}{2.5}{$ \backslash @@ -2694,11 +2538,7 @@ Class{NL}$}{black!50!structure}{3} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash heap{2.5}{2}{$ \backslash @@ -2707,109 +2547,85 @@ Class{L}$}{black!50!structure}{4} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \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 Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash pgfsetdash{}{0pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \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 Plain Layout + +\backslash +smash{ +\backslash +Class{AC}^0}$}{black}{6} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{1.0pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash color{black} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfxyline(-5,0)(5,0) \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash only<1-2>{ \backslash @@ -2820,11 +2636,7 @@ Lang{reach}$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<1-2>{ \backslash @@ -2837,19 +2649,7 @@ operatorname{forest}}$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash only<2>{ \backslash @@ -2860,11 +2660,7 @@ Lang{addition}$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<2>{ \backslash @@ -2883,11 +2679,7 @@ Lang{parity}$}}}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<3-5>{ \backslash @@ -2906,11 +2698,7 @@ Lang{reach}$}}}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<4->{ \backslash @@ -2923,11 +2711,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -2940,11 +2724,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -2957,11 +2737,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -2974,26 +2750,23 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash Lang{reach}_{ \backslash -operatorname{path}}$}}}} +operatorname{path}}$}}} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash only<5->{ \backslash @@ -3006,11 +2779,7 @@ operatorname{tourn}}$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<6->{ \backslash @@ -3023,11 +2792,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -3040,11 +2805,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -3055,38 +2816,41 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash -Lang{reach}$}}}} +Lang{reach}$}}} \end_layout \begin_layout Plain Layout +} \end_layout \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 Plain Layout +} \end_layout \begin_layout Plain Layout @@ -3101,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 @@ -3121,6 +2894,12 @@ The Circuit Complexity Classes AC Limit the Circuit Depth \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -3136,10 +2915,6 @@ leftmargini{1em} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash nointerlineskip @@ -3151,12 +2926,11 @@ nointerlineskip \end_layout \begin_layout Columns -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -[t] +t \end_layout \end_inset @@ -3170,27 +2944,15 @@ status collapsed \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Circuit Class \begin_inset Formula $\Class{AC}^{0}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -3240,27 +3002,15 @@ unbounded fan-in \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Circuit Class \begin_inset Formula $\Class{NC}^{1}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -3317,27 +3067,15 @@ bounded fan-in \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Circuit Class \begin_inset Formula $\Class{NC}^{2}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -3370,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 Plain Layout - -<2> +2 \end_layout \end_inset @@ -3390,7 +3128,11 @@ 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 \begin_inset Newline newline \end_inset @@ -3398,6 +3140,12 @@ All Variants of Finding Paths in Directed Graphs Are Equally Difficult \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}$ \end_inset @@ -3455,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 Plain Layout - -<3> +3 \end_layout \end_inset @@ -3470,14 +3218,24 @@ status collapsed hierarchy \end_layout -\begin_layout BeginFrame -FindingPaths in Forests and Directed Paths is Easy, +\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 @@ -3512,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 Plain Layout - -<4> +4 \end_layout \end_inset @@ -3534,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 @@ -3587,10 +3355,25 @@ there exists 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 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 @@ -3603,12 +3386,11 @@ The Tournament Reachability Problem is Very Easy \end_layout \begin_layout AlertBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Implications} +Implications \end_layout \end_inset @@ -3644,14 +3426,14 @@ easier . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -<5> +5 \end_layout \end_inset @@ -3663,7 +3445,11 @@ 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 \begin_inset Newline newline \end_inset @@ -3671,6 +3457,12 @@ Finding a Shortest Path Is as Difficult as the Distance Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition Let \color none @@ -3724,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 @@ -3788,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 @@ -3796,6 +3612,12 @@ Proof That is NL-complete \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -3813,12 +3635,11 @@ nointerlineskip \end_layout \begin_layout Columns -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -[t,onlytextwidth] +t,onlytextwidth \end_layout \end_inset @@ -3850,16 +3671,10 @@ leftmargini{1.5em} \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Reduce \begin_inset Formula $\Lang{reach}$ \end_inset @@ -3869,12 +3684,6 @@ Reduce \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -3884,12 +3693,11 @@ status collapsed \begin_deeper \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - - +alert@1 \end_layout \end_inset @@ -3906,12 +3714,11 @@ Is input \end_layout \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<2-| alert@2-8> +2-| alert@2-8 \end_layout \end_inset @@ -3928,12 +3735,11 @@ Map \end_layout \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<9-| alert@9> +9-| alert@9 \end_layout \end_inset @@ -3955,34 +3761,21 @@ Query: \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Correctness -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -<10-> +10- \end_layout \end_inset @@ -3992,12 +3785,11 @@ status collapsed \begin_deeper \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<10-| alert@10-11> +10-| alert@10-11 \end_layout \end_inset @@ -4026,12 +3818,11 @@ a length-3 path in \end_layout \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<12-| alert@12-13> +12-| alert@12-13 \end_layout \end_inset @@ -4077,33 +3868,21 @@ begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout -\end_layout -\begin_layout Plain Layout - - \backslash graphnode{A}{ \backslash @@ -4112,11 +3891,7 @@ pgfxy(1,3.3)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{B}{ \backslash @@ -4125,11 +3900,7 @@ pgfxy(2,3.3)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{C}{ \backslash @@ -4138,11 +3909,7 @@ pgfxy(3,3.3)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{D}{ \backslash @@ -4151,30 +3918,14 @@ pgfxy(4,3.3)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{white} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -4185,11 +3936,7 @@ pgfbox[center,center]{$s$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -4200,30 +3947,14 @@ pgfbox[center,center]{$t$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetendarrow{ \backslash @@ -4232,33 +3963,21 @@ pgfarrowto} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodesetsepstart{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodesetsepend{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash alert<3>{ \backslash @@ -4267,11 +3986,7 @@ pgfnodeconnline{B}{A}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash alert<4>{ \backslash @@ -4280,11 +3995,7 @@ pgfnodeconnline{B}{C}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash alert<5,10-11,13>{ \backslash @@ -4293,11 +4004,7 @@ pgfnodeconnline{C}{D}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash alert<6,10-11,13>{ \backslash @@ -4306,20 +4013,7 @@ pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -4332,30 +4026,14 @@ colon$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash -only<2->{ -\end_layout - -\begin_layout Plain Layout - +only<2->{% \end_layout \begin_layout Plain Layout - + \backslash pgfputat{ \backslash @@ -4368,11 +4046,7 @@ colon$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A1}{ \backslash @@ -4381,11 +4055,7 @@ pgfxy(1,2.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B1}{ \backslash @@ -4394,11 +4064,7 @@ pgfxy(2,2.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C1}{ \backslash @@ -4407,11 +4073,7 @@ pgfxy(3,2.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D1}{ \backslash @@ -4420,19 +4082,7 @@ pgfxy(4,2.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A2}{ \backslash @@ -4441,11 +4091,7 @@ pgfxy(1,1.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B2}{ \backslash @@ -4454,11 +4100,7 @@ pgfxy(2,1.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C2}{ \backslash @@ -4467,11 +4109,7 @@ pgfxy(3,1.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D2}{ \backslash @@ -4480,11 +4118,7 @@ pgfxy(4,1.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A3}{ \backslash @@ -4493,11 +4127,7 @@ pgfxy(1,0.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B3}{ \backslash @@ -4506,11 +4136,7 @@ pgfxy(2,0.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C3}{ \backslash @@ -4519,11 +4145,7 @@ pgfxy(3,0.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D3}{ \backslash @@ -4532,11 +4154,7 @@ pgfxy(4,0.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A4}{ \backslash @@ -4545,11 +4163,7 @@ pgfxy(1,-.75)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B4}{ \backslash @@ -4558,11 +4172,7 @@ pgfxy(2,-.75)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C4}{ \backslash @@ -4571,11 +4181,7 @@ pgfxy(3,-.75)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D4}{ \backslash @@ -4584,22 +4190,14 @@ pgfxy(4,-.75)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - { + { \backslash color{white} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash @@ -4610,11 +4208,7 @@ pgfbox[center,center]{$s'$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash @@ -4625,1112 +4219,670 @@ pgfbox[center,center]{$t'$}} \begin_layout Plain Layout + } \end_layout \begin_layout Plain Layout - }} +} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - +\backslash +only<8->{% \end_layout \begin_layout Plain Layout + +\backslash +pgfsetlinewidth{0.4pt} \end_layout \begin_layout Plain Layout \backslash -only<8->{ +color{beamerexample!25!averagebackgroundcolor} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A2}{C1} \end_layout \begin_layout Plain Layout - + \backslash -pgfsetlinewidth{0.4pt} +pgfnodeconnline{A2}{D1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{A1} \end_layout \begin_layout Plain Layout - + \backslash -color{beamerexample!25!averagebackgroundcolor} +pgfnodeconnline{B2}{C1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{D1} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A2}{C1} +pgfnodeconnline{C2}{D1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{D2}{A1} \end_layout \begin_layout Plain Layout - -\backslash -pgfnodeconnline{A2}{D1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B2}{A1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B2}{C1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B2}{D1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C2}{D1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{D2}{A1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{D2}{B1} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{A3}{C2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{A3}{D2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B3}{A2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B3}{C2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B3}{D2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{C3}{D2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{D3}{A2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{D3}{B2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{A4}{C3} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{A4}{D3} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B4}{A3} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B4}{C3} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B4}{D3} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{C4}{D3} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{D4}{A3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{D4}{B3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfsetstartarrow{ -\backslash -pgfarrowto} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A1}{B1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B1}{C1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C1}{D1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A2}{B2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B2}{C2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash -pgfnodeconnline{C2}{D2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A3}{B3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B3}{C3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C3}{D3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A4}{B4} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B4}{C4} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C4}{D4} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfclearstartarrow -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -color{beamerexample} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfsetlinewidth{0.6pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - } -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -only<3->{ -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -color<3>{red} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B1}{A2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B2}{A3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B3}{A4} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - } -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - +pgfnodeconnline{D4}{A3} \end_layout \begin_layout Plain Layout \backslash -only<4->{ +pgfnodeconnline{D4}{B3} \end_layout \begin_layout Plain Layout + +\backslash +pgfsetstartarrow{ +\backslash +pgfarrowto} \end_layout \begin_layout Plain Layout - + \backslash -color<4>{red} +pgfnodeconnline{A1}{B1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B1}{C1} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B1}{C2} +pgfnodeconnline{C1}{D1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A2}{B2} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B2}{C3} +pgfnodeconnline{B2}{C2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{C2}{D2} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B3}{C4} +pgfnodeconnline{A3}{B3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{C3} \end_layout \begin_layout Plain Layout - } + +\backslash +pgfnodeconnline{C3}{D3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A4}{B4} \end_layout \begin_layout Plain Layout +\backslash +pgfnodeconnline{B4}{C4} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{C4}{D4} \end_layout \begin_layout Plain Layout \backslash -only<5->{ +pgfclearstartarrow \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout - + \backslash -color<5>{red} +pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{C1}{D2} +pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout - -\backslash -alert<11>{ + \backslash -pgfnodeconnline{C2}{D3}} +pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout - -\backslash -alert<12-13>{ + \backslash -pgfnodeconnline{C3}{D4}} +pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} \end_layout \begin_layout Plain Layout - } + +\backslash +pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout - + +\backslash +pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} \end_layout \begin_layout Plain Layout + +\backslash +color{beamerexample} \end_layout \begin_layout Plain Layout \backslash -only<6->{ +pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash -color<6>{red} +only<3->{% \end_layout \begin_layout Plain Layout + +\backslash +color<3>{red} \end_layout \begin_layout Plain Layout - -\backslash -alert<11>{ + \backslash -pgfnodeconnline{A1}{C2}} +pgfnodeconnline{B1}{A2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{A3} \end_layout \begin_layout Plain Layout - -\backslash -alert<12-13>{ + \backslash -pgfnodeconnline{A2}{C3}} +pgfnodeconnline{B3}{A4} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A3}{C4} +only<4->{% \end_layout \begin_layout Plain Layout + +\backslash +color<4>{red} \end_layout \begin_layout Plain Layout - } + +\backslash +pgfnodeconnline{B1}{C2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{C3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{C4} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash -only<7->{ +only<5->{% \end_layout \begin_layout Plain Layout + +\backslash +color<5>{red} \end_layout \begin_layout Plain Layout - + \backslash -color<7>{red} +pgfnodeconnline{C1}{D2} \end_layout \begin_layout Plain Layout + +\backslash +alert<11>{ +\backslash +pgfnodeconnline{C2}{D3}} \end_layout \begin_layout Plain Layout - + \backslash alert<12-13>{ \backslash -pgfnodeconnline{A1}{A2}} +pgfnodeconnline{C3}{D4}} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A2}{A3} +only<6->{% \end_layout \begin_layout Plain Layout + +\backslash +color<6>{red} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A3}{A4} +alert<11>{ +\backslash +pgfnodeconnline{A1}{C2}} \end_layout \begin_layout Plain Layout + +\backslash +alert<12-13>{ +\backslash +pgfnodeconnline{A2}{C3}} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B1}{B2} +pgfnodeconnline{A3}{C4} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B2}{B3} +only<7->{% \end_layout \begin_layout Plain Layout + +\backslash +color<7>{red} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B3}{B4} +alert<12-13>{ +\backslash +pgfnodeconnline{A1}{A2}} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A2}{A3} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{C1}{C2} +pgfnodeconnline{A3}{A4} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B1}{B2} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{C2}{C3} +pgfnodeconnline{B2}{B3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{B4} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{C3}{C4} +pgfnodeconnline{C1}{C2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{C2}{C3} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{D1}{D2} +pgfnodeconnline{C3}{C4} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{D1}{D2} \end_layout \begin_layout Plain Layout - + \backslash pgfnodeconnline{D2}{D3} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<11>{ \backslash @@ -5739,15 +4891,7 @@ pgfnodeconnline{D3}{D4}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - } -\end_layout - -\begin_layout Plain Layout - +} \end_layout \begin_layout Plain Layout @@ -5762,14 +4906,14 @@ end{pgfpicture} \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -<6> +6 \end_layout \end_inset @@ -5781,10 +4925,20 @@ hierarchy Complexity of: Approximating the Shortest Path \end_layout -\begin_layout BeginFrame -Approximators Compute Paths that Are Nearly As Short As a Shortest Path +\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 @@ -5843,7 +4997,16 @@ 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 \begin_inset Newline newline \end_inset @@ -5851,6 +5014,12 @@ There Exists a Logspace Approximation Scheme for 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}$ @@ -5861,8 +5030,10 @@ 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 @@ -5899,13 +5070,13 @@ beamergotobutton{More Details}} \end_layout +\end_deeper \begin_layout AgainFrame -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout - -<7> +7 \end_layout \end_inset @@ -5913,6 +5084,103 @@ status collapsed 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 + +\begin_deeper +\begin_layout Standard +\begin_inset listings +lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4" +inline false +status open + +\begin_layout Plain Layout + +def func(param): +\end_layout + +\begin_layout Plain Layout + + 'this is a python function' +\end_layout + +\begin_layout Plain Layout + + pass +\end_layout + +\begin_layout Plain Layout + +def func(param): +\end_layout + +\begin_layout Plain Layout + +'This is a German word: Tschüs' +\end_layout + +\begin_layout Plain Layout + +pass +\end_layout + +\begin_layout Plain Layout + +def func(param): +\end_layout + +\begin_layout Plain Layout + +'this is a python function' +\end_layout + +\begin_layout Plain Layout + +pass +\end_layout + +\end_inset + + +\end_layout + +\end_deeper \begin_layout Section* Summary \end_layout @@ -5921,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 +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Summary} +Summary \end_layout \end_inset @@ -6011,12 +5288,11 @@ in tournaments is \end_layout \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Outlook} +Outlook \end_layout \end_inset @@ -6079,18 +5355,29 @@ 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 collapsed +status open \begin_layout Plain Layout @@ -6270,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 collapsed +status open \begin_layout Plain Layout \backslash -AtBeginSubsection[]{} +AtBeginSubsection[]{} \end_layout \end_inset @@ -6299,20 +5583,30 @@ Appendix Graphs With Bounded Independence Number \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 3 status collapsed \begin_layout Plain Layout - -[label=independence] +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 @@ -6342,7 +5636,16 @@ 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 \begin_inset Newline newline \end_inset @@ -6350,6 +5653,12 @@ The Results for Tournaments also Apply to Graphs With Bounded Independence Number \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem For each \begin_inset space ~ @@ -6461,21 +5770,36 @@ in graphs with independence number at most . \end_layout +\end_deeper \begin_layout Subsection Finding Paths in Undirected Graphs \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 1 status collapsed \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 \begin_inset Newline newline \end_inset @@ -6483,6 +5807,12 @@ The Complexity of Finding Paths in Undirected Graphs Is Party Unknown. \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$ \end_inset @@ -6509,20 +5839,43 @@ the reachability problem in logspace iff \begin_layout Itemize the construction problem in logspace iff -\begin_inset ERT -status collapsed +\begin_inset Flex Alternative +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open \begin_layout Plain Layout +1 +\end_layout + +\end_inset + + +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +? +\end_layout + +\end_inset + + +\begin_inset Flex Alert +status open + +\begin_layout Plain Layout +\begin_inset Formula $\Class L=\Class{SL}$ +\end_inset + + +\end_layout + +\end_inset -\backslash -alt<1>{?}{ -\backslash -alert{$ -\backslash -Class L = -\backslash -Class{SL}$}} \end_layout \end_inset @@ -6532,20 +5885,43 @@ Class{SL}$}} \begin_layout Itemize the optimization problem in logspace iff -\begin_inset ERT -status collapsed +\begin_inset Flex Alternative +status open \begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +1 +\end_layout + +\end_inset + + +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +? +\end_layout + +\end_inset + + +\begin_inset Flex Alert +status open + +\begin_layout Plain Layout +\begin_inset Formula $\Class L=\Class{NL}$ +\end_inset + + +\end_layout + +\end_inset -\backslash -alt<1>{?}{ -\backslash -alert{$ -\backslash -Class L = -\backslash -Class{NL}$}} \end_layout \end_inset @@ -6558,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 +\begin_layout Frame +\begin_inset Argument 3 status collapsed \begin_layout Plain Layout - -[label=optimality] +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}$ @@ -6660,9 +6047,6 @@ qedhere \end_layout \end_deeper -\begin_layout EndFrame - -\end_layout - +\end_deeper \end_body \end_document