X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=lib%2Fexamples%2Fbeamerlyxexample1.lyx;h=a59c85925fcca9c41243e4d313f395eb6fb4a759;hb=3c93d5078918f43af76827d2991ed5fa35a3a20e;hp=78100ad07f55ef1de0c3d5d996d9b0b92969a1d5;hpb=551fe7988038f3132c350a77b2eabe6c80859f7f;p=lyx.git diff --git a/lib/examples/beamerlyxexample1.lyx b/lib/examples/beamerlyxexample1.lyx index 78100ad07f..a59c85925f 100644 --- a/lib/examples/beamerlyxexample1.lyx +++ b/lib/examples/beamerlyxexample1.lyx @@ -1,5 +1,5 @@ -#LyX 1.4.3 created this file. For more info see http://www.lyx.org/ -\lyxformat 245 +#LyX 2.0 created this file. For more info see http://www.lyx.org/ +\lyxformat 413 \begin_document \begin_header \textclass beamer @@ -26,6 +26,10 @@ \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}} +% This gets defined by beamerbasecolor.sty, but only at the beginning of +% the document +\colorlet{averagebackgroundcolor}{normal text.bg} + \newcommand{\tape}[3]{% \color{structure!30!averagebackgroundcolor} \pgfmoveto{\pgfxy(-0.5,0)} @@ -145,35 +149,68 @@ } \end_preamble \options notes=show +\use_default_options false +\maintain_unincluded_children false \language english +\language_package default \inputencoding auto -\fontscheme times +\fontencoding global +\font_roman times +\font_sans default +\font_typewriter default +\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_mhchem 1 +\use_mathdots 1 \cite_engine basic \use_bibtopic false +\use_indices false \paperorientation portrait +\suppress_date false +\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 true +\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 @@ -183,12 +220,14 @@ Till Tantau \begin_layout Institute International Computer Schience Institute -\newline +\begin_inset Newline newline +\end_inset + Berkeley, California -\begin_inset OptArg +\begin_inset Argument status collapsed -\begin_layout Standard +\begin_layout Plain Layout ICSI \end_layout @@ -206,7 +245,8 @@ Outline \end_layout \begin_layout Standard -\begin_inset LatexCommand \tableofcontents{} +\begin_inset CommandInset toc +LatexCommand tableofcontents \end_inset @@ -214,7 +254,7 @@ Outline \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout [pausesections] \end_layout @@ -232,78 +272,78 @@ status collapsed \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout % Show the table of contents at the beginning \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout % of every subsection. \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash AtBeginSubsection[]{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash frame{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash frametitle{Outline} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash tableofcontents[current,currentsubsection] \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 } \end_layout @@ -336,20 +376,20 @@ 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 +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -360,11 +400,11 @@ pgfxy(2,1)}{ pgfuseimage{knight1}}{2pt}{2pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -375,11 +415,11 @@ pgfxy(6,1)}{ pgfuseimage{knight2}}{2pt}{2pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -390,11 +430,11 @@ pgfxy(4,-1)}{ pgfuseimage{knight3}}{2pt}{2pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -405,30 +445,30 @@ pgfxy(4,3)}{ pgfuseimage{knight4}}{2pt}{2pt} \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 @@ -439,99 +479,99 @@ pgfsetendarrow{ pgfarrowto}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash only<2->{ \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 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{C}{D}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -549,9 +589,9 @@ end{pgfpicture} \begin_layout Block \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {What is a Tournament?} \end_layout @@ -566,7 +606,7 @@ status inlined \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <1-> \end_layout @@ -580,7 +620,7 @@ A group of knights. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <2-> \end_layout @@ -594,7 +634,7 @@ Every pair has a joust. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <3-> \end_layout @@ -621,42 +661,42 @@ 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 +\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 @@ -665,11 +705,11 @@ graphnode{A}{ pgfxy(2.5,1)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -678,11 +718,11 @@ graphnode{B}{ pgfxy(5.5,1)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -691,11 +731,11 @@ graphnode{C}{ pgfxy(4,-0.5)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -704,30 +744,30 @@ graphnode{D}{ pgfxy(4,2.5)} \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 @@ -738,11 +778,11 @@ pgfnodecenter{A}}{ pgfbox[center,center]{$v_2$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -753,11 +793,11 @@ pgfnodecenter{B}}{ pgfbox[center,center]{$v_3$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -768,11 +808,11 @@ pgfnodecenter{C}}{ pgfbox[center,center]{$v_4$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -783,30 +823,30 @@ pgfnodecenter{D}}{ pgfbox[center,center]{$v_1$}} \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 @@ -815,99 +855,99 @@ 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 \backslash @@ -927,18 +967,22 @@ end{pgfpicture} \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <2-> \end_layout \end_inset -A +A +\color none + \color red tournament +\color none + \color inherit - is a +is a \end_layout \begin_deeper @@ -948,7 +992,9 @@ directed graphs, \begin_layout Enumerate with exactly one edge between -\newline +\begin_inset Newline newline +\end_inset + any two different vertices. \end_layout @@ -958,7 +1004,7 @@ any two different vertices. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout [<+>] \end_layout @@ -970,9 +1016,9 @@ Tournaments Arise Naturally in Different Situations \begin_layout ExampleBlock \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Applicatins in Ordering Theory} \end_layout @@ -986,7 +1032,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 @@ -997,9 +1045,9 @@ The comparison relation may be cyclic, however. \begin_layout ExampleBlock \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Applications in Sociology} \end_layout @@ -1012,9 +1060,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 @@ -1025,9 +1074,9 @@ Reviewers decide for any two candidates \begin_layout ExampleBlock \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Applications in Structural Complexity Theory} \end_layout @@ -1048,7 +1097,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 @@ -1067,9 +1118,9 @@ What Does ``Finding Paths'' Mean? \begin_layout Block \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout { \backslash @@ -1082,11 +1133,11 @@ def par{}% because LyX inserts superfluous paragraphs \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1095,11 +1146,11 @@ only<1>{Path Finding Problems} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1110,11 +1161,11 @@ Lang{reach}$} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1123,11 +1174,11 @@ only<4-5>{the Construction Problem} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1136,11 +1187,11 @@ only<6-7>{the Optimization Problem} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1151,11 +1202,11 @@ Lang{distance}$} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1169,27 +1220,39 @@ only<10->{the Approximation Problem}} \begin_deeper \begin_layout Itemize -A +A +\color none + \color red graph -\color inherit +\color none +\color inherit + \begin_inset Formula $G=(V,E)$ \end_inset -, a +, a +\color none + \color red source -\color inherit +\color none +\color inherit + \begin_inset Formula $s\in V$ \end_inset - and a + and a +\color none + \color red target -\color inherit +\color none +\color inherit + \begin_inset Formula $t\in V$ \end_inset @@ -1200,18 +1263,23 @@ target \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \end_layout \end_inset -A +A +\color none + \color red maximum distance \color inherit -\InsetSpace ~ + +\begin_inset space ~ +\end_inset + \begin_inset Formula $d$ \end_inset @@ -1220,7 +1288,7 @@ maximum distance \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1236,18 +1304,22 @@ phantom{p} \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \end_layout \end_inset -An +An +\color none + \color red approximation ratio -\color inherit +\color none +\color inherit + \begin_inset Formula $r>1$ \end_inset @@ -1259,7 +1331,7 @@ approximation ratio \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1278,9 +1350,9 @@ nointerlineskip \begin_deeper \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1294,9 +1366,9 @@ onslide<1,3,5,7,9,11-12> \begin_layout Columns \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout [t,onlytextwidth] \end_layout @@ -1309,9 +1381,9 @@ status inlined \begin_deeper \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1331,9 +1403,9 @@ column{5cm}} \begin_layout ExampleBlock \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Example Input} \end_layout @@ -1346,42 +1418,42 @@ 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 +\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 @@ -1390,11 +1462,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 @@ -1403,11 +1475,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 @@ -1416,11 +1488,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 @@ -1429,30 +1501,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 @@ -1463,11 +1535,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 @@ -1478,30 +1550,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 @@ -1510,107 +1582,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 @@ -1623,11 +1695,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 @@ -1640,11 +1712,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 @@ -1657,11 +1729,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 @@ -1676,9 +1748,9 @@ end{pgfpicture} \end_deeper \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1694,9 +1766,9 @@ column{5cm}} \begin_layout ExampleBlock \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Example Output} \end_layout @@ -1709,53 +1781,53 @@ 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 +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash only<5-8,10->{ \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 @@ -1764,11 +1836,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 @@ -1777,11 +1849,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 @@ -1790,11 +1862,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 @@ -1803,30 +1875,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 @@ -1837,11 +1909,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 @@ -1852,30 +1924,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 @@ -1884,42 +1956,42 @@ 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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1928,11 +2000,11 @@ alert<7,12>{ pgfnodeconnline{A}{B}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1941,11 +2013,11 @@ alert<5,11>{ pgfnodeconnline{A}{C}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1954,11 +2026,11 @@ alert<5,7,11-12>{ pgfnodeconnline{D}{A}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -1967,42 +2039,42 @@ alert<5,11>{ 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 @@ -2017,11 +2089,11 @@ pgfbox[left,center]{ alert{``Yes''}}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2037,9 +2109,9 @@ end{pgfpicture} \end_deeper \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2053,9 +2125,9 @@ onslide<2,4,6,8,10> \begin_layout Block \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Variants of Path Finding Problems} \end_layout @@ -2068,9 +2140,9 @@ status inlined \begin_deeper \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2083,12 +2155,15 @@ usedescriptionitemofwidthas{Approximation Problem:} \end_layout \begin_layout Description -Reachability\InsetSpace ~ +Reachability +\begin_inset space ~ +\end_inset + Problem: \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <2-> \end_layout @@ -2099,7 +2174,10 @@ 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 @@ -2108,12 +2186,15 @@ Is there a path from \end_layout \begin_layout Description -Construction\InsetSpace ~ +Construction +\begin_inset space ~ +\end_inset + Problem: \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <4-> \end_layout @@ -2124,7 +2205,10 @@ Construct a path from \begin_inset Formula $s$ \end_inset - to\InsetSpace ~ + to +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset @@ -2133,12 +2217,15 @@ Construct a path from \end_layout \begin_layout Description -Optimization\InsetSpace ~ +Optimization +\begin_inset space ~ +\end_inset + Problem: \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <6-> \end_layout @@ -2149,7 +2236,10 @@ 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 @@ -2158,12 +2248,15 @@ Construct a shortest path from \end_layout \begin_layout Description -Distance\InsetSpace ~ +Distance +\begin_inset space ~ +\end_inset + Problem: \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <8-> \end_layout @@ -2174,12 +2267,18 @@ 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 @@ -2188,12 +2287,15 @@ Is the distance of \end_layout \begin_layout Description -Approximation\InsetSpace ~ +Approximation +\begin_inset space ~ +\end_inset + Problem: \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <10-> \end_layout @@ -2204,13 +2306,18 @@ 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 @@ -2226,9 +2333,9 @@ Standard Complexity Classes \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2245,7 +2352,9 @@ pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer \begin_layout BeginFrame The Classes L and NL are Defined via -\newline +\begin_inset Newline newline +\end_inset + Logspace Turing Machines \end_layout @@ -2253,18 +2362,18 @@ Logspace Turing Machines \begin_inset ERT status open -\begin_layout Standard +\begin_layout Plain Layout \backslash begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2275,22 +2384,22 @@ pgfxy(0,4)}{ tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash uncover<2->{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2301,22 +2410,22 @@ pgfxy(0,0.5)}{ tape{}{output tape (write only)}{10690836937182}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash uncover<3->{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2329,11 +2438,11 @@ shorttape{work tape (read/write), $O( log n)$ symbols}{}{42}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2346,50 +2455,50 @@ pgfbox[center,center]{ pgfuseimage{computer}}} \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 pgfsetlinewidth{0.6pt} \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{structure} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2398,22 +2507,22 @@ pgfsetendarrow{ pgfarrowto} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85) \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2422,11 +2531,11 @@ uncover<2->{ pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2435,11 +2544,11 @@ uncover<3->{ pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2457,9 +2566,9 @@ Logspace Turing Machines Are Quite Powerful \begin_layout Block \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Deterministic logspace machines can compute} \end_layout @@ -2489,9 +2598,9 @@ reachability in forests. \begin_layout Block \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Non-deterministic logspace machines can compute} \end_layout @@ -2517,9 +2626,9 @@ satisfiability with two literals per clause. \end_deeper \begin_layout BeginFrame \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout <1>[label=hierarchy] \end_layout @@ -2531,31 +2640,31 @@ The Complexity Class Hierarchy \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfsetlinewidth{0.8pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2564,22 +2673,22 @@ heap{5.5}{3.5}{$ Class P$}{black}{1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfsetdash{{2pt}}{0pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2590,11 +2699,11 @@ heap{4.5}{3}{$ Class{NC}^2$}{black!50!structure}{2}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2603,11 +2712,11 @@ heap{3.5}{2.5}{$ Class{NL}$}{black!50!structure}{3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2616,11 +2725,11 @@ heap{2.5}{2}{$ Class{L}$}{black!50!structure}{4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2635,22 +2744,22 @@ smash{ 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 +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2665,60 +2774,60 @@ smash{ Class{AC}^0}$}{black}{6}} \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 pgfsetlinewidth{1.0pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color{black} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfxyline(-5,0)(5,0) \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 @@ -2729,11 +2838,11 @@ langat{3.375}{$ Lang{reach}$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2746,19 +2855,19 @@ Lang{reach}_{ operatorname{forest}}$}} \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 @@ -2769,11 +2878,11 @@ langat{0.975}{$ Lang{addition}$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2792,11 +2901,11 @@ hbox{$ Lang{parity}$}}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2815,11 +2924,11 @@ hbox{$ Lang{reach}$}}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2832,11 +2941,11 @@ vbox{ ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2849,11 +2958,11 @@ operatorname{forest}}$,} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2866,11 +2975,11 @@ operatorname{forest}}$,} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2883,11 +2992,11 @@ operatorname{path}}$,} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2898,11 +3007,11 @@ Lang{reach}_{ operatorname{path}}$}}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2915,11 +3024,11 @@ Lang{reach}_{ operatorname{tourn}}$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2932,11 +3041,11 @@ vbox{ ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2949,11 +3058,11 @@ operatorname{tourn}}$,} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2964,11 +3073,11 @@ Lang{distance}$,} ignorespaces \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2977,11 +3086,11 @@ hbox{$ Lang{reach}$}}}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -2996,11 +3105,11 @@ Lang{approx}_{ operatorname{tourn}}$''}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3026,15 +3135,17 @@ The Circuit Complexity Classes AC \end_inset -\newline +\begin_inset Newline newline +\end_inset + Limit the Circuit Depth \end_layout \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3043,11 +3154,11 @@ setlength leftmargini{1em} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3063,7 +3174,7 @@ nointerlineskip \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout [t] \end_layout @@ -3082,7 +3193,7 @@ status collapsed \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout { \end_layout @@ -3097,7 +3208,7 @@ Circuit Class \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout } \end_layout @@ -3152,7 +3263,7 @@ unbounded fan-in \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout { \end_layout @@ -3167,7 +3278,7 @@ Circuit Class \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout } \end_layout @@ -3229,7 +3340,7 @@ bounded fan-in \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout { \end_layout @@ -3244,7 +3355,7 @@ Circuit Class \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout } \end_layout @@ -3285,7 +3396,7 @@ bounded fan-in \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <2> \end_layout @@ -3301,7 +3412,9 @@ Standard Complexity Results on Finding Paths \begin_layout BeginFrame All Variants of Finding Paths in Directed Graphs -\newline +\begin_inset Newline newline +\end_inset + Are Equally Difficult \end_layout @@ -3367,7 +3480,7 @@ the approximation problem in logspace iff \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <3> \end_layout @@ -3379,7 +3492,9 @@ hierarchy \begin_layout BeginFrame FindingPaths in Forests and Directed Paths is Easy, -\newline +\begin_inset Newline newline +\end_inset + But Not Trivial \end_layout @@ -3421,7 +3536,7 @@ But Not Trivial \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <4> \end_layout @@ -3444,15 +3559,19 @@ Definition of the Tournament Reachability Problem \end_layout \begin_layout Definition -Let +Let +\color none + \color red \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$ \end_inset +\color none + \color inherit - contain all triples +contain all triples \begin_inset Formula $(T,s,t)$ \end_inset @@ -3468,12 +3587,18 @@ Let \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 @@ -3499,9 +3624,9 @@ The Tournament Reachability Problem is Very Easy \begin_layout AlertBlock \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Implications} \end_layout @@ -3544,7 +3669,7 @@ easier \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <5> \end_layout @@ -3560,17 +3685,23 @@ Complexity of: Construct a Shortest Path \begin_layout BeginFrame Finding a Shortest Path Is as Difficult as -\newline +\begin_inset Newline newline +\end_inset + the Distance Problem \end_layout \begin_layout Definition -Let +Let +\color none + \color red \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset + +\color none \color inherit contain all tuples @@ -3593,12 +3724,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 @@ -3623,13 +3760,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 @@ -3649,9 +3787,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 @@ -3681,7 +3820,7 @@ Proof That \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3695,9 +3834,9 @@ nointerlineskip \begin_layout Columns \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout [t,onlytextwidth] \end_layout @@ -3714,9 +3853,9 @@ status inlined \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3734,7 +3873,7 @@ leftmargini{1.5em} \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout { \end_layout @@ -3753,7 +3892,7 @@ Reduce \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout } \end_layout @@ -3766,9 +3905,9 @@ status collapsed \begin_deeper \begin_layout Enumerate \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \end_layout @@ -3788,9 +3927,9 @@ Is input \begin_layout Enumerate \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout <2-| alert@2-8> \end_layout @@ -3810,9 +3949,9 @@ Map \begin_layout Enumerate \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout <9-| alert@9> \end_layout @@ -3820,7 +3959,9 @@ status inlined \end_inset Query: -\newline +\begin_inset Newline newline +\end_inset + \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$ \end_inset @@ -3837,7 +3978,7 @@ Query: \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout { \end_layout @@ -3848,7 +3989,7 @@ Correctness \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout } \end_layout @@ -3859,7 +4000,7 @@ status collapsed \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <10-> \end_layout @@ -3872,23 +4013,31 @@ status collapsed \begin_deeper \begin_layout Enumerate \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\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 @@ -3898,23 +4047,31 @@ a length-3 path in\InsetSpace ~ \begin_layout Enumerate \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\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 @@ -3929,42 +4086,42 @@ 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 +\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 @@ -3973,11 +4130,11 @@ graphnode{A}{ pgfxy(1,3.3)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3986,11 +4143,11 @@ graphnode{B}{ pgfxy(2,3.3)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -3999,11 +4156,11 @@ graphnode{C}{ pgfxy(3,3.3)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4012,30 +4169,30 @@ graphnode{D}{ pgfxy(4,3.3)} \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 @@ -4046,11 +4203,11 @@ pgfnodecenter{A}}{ pgfbox[center,center]{$s$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4061,30 +4218,30 @@ pgfnodecenter{D}}{ 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 \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 @@ -4093,33 +4250,33 @@ 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{2pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4128,11 +4285,11 @@ alert<3>{ pgfnodeconnline{B}{A}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4141,11 +4298,11 @@ alert<4>{ pgfnodeconnline{B}{C}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4154,11 +4311,11 @@ alert<5,10-11,13>{ pgfnodeconnline{C}{D}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4167,20 +4324,20 @@ alert<6,10-11,13>{ pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}} \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 @@ -4193,30 +4350,30 @@ pgfbox[left,center]{$G colon$}} \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 only<2->{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4229,11 +4386,11 @@ pgfbox[left,center]{$G' colon$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4242,11 +4399,11 @@ graphnode{A1}{ pgfxy(1,2.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4255,11 +4412,11 @@ graphnode{B1}{ pgfxy(2,2.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4268,11 +4425,11 @@ graphnode{C1}{ pgfxy(3,2.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4281,19 +4438,19 @@ graphnode{D1}{ pgfxy(4,2.25)} \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 @@ -4302,11 +4459,11 @@ graphnode{A2}{ pgfxy(1,1.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4315,11 +4472,11 @@ graphnode{B2}{ pgfxy(2,1.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4328,11 +4485,11 @@ graphnode{C2}{ pgfxy(3,1.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4341,11 +4498,11 @@ graphnode{D2}{ pgfxy(4,1.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4354,11 +4511,11 @@ graphnode{A3}{ pgfxy(1,0.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4367,11 +4524,11 @@ graphnode{B3}{ pgfxy(2,0.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4380,11 +4537,11 @@ graphnode{C3}{ pgfxy(3,0.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4393,11 +4550,11 @@ graphnode{D3}{ pgfxy(4,0.25)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4406,11 +4563,11 @@ graphnode{A4}{ pgfxy(1,-.75)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4419,11 +4576,11 @@ graphnode{B4}{ pgfxy(2,-.75)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4432,11 +4589,11 @@ graphnode{C4}{ pgfxy(3,-.75)} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4445,22 +4602,22 @@ graphnode{D4}{ pgfxy(4,-.75)} \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 @@ -4471,11 +4628,11 @@ pgfnodecenter{A1}}{ pgfbox[center,center]{$s'$}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -4486,334 +4643,334 @@ 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 \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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfsetlinewidth{0.4pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color{beamerexample!25!averagebackgroundcolor} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A2}{C1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A2}{D1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B2}{A1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B2}{C1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B2}{D1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C2}{D1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D2}{A1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D2}{B1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A3}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A3}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B3}{A2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B3}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B3}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C3}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D3}{A2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D3}{B2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A4}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A4}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B4}{A3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B4}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B4}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C4}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D4}{A3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D4}{B3} \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 @@ -4822,511 +4979,511 @@ pgfsetstartarrow{ pgfarrowto} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A1}{B1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B1}{C1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C1}{D1} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A2}{B2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B2}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C2}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A3}{B3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B3}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C3}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A4}{B4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B4}{C4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C4}{D4} \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 pgfclearstartarrow \end_layout -\begin_layout Standard +\begin_layout Plain Layout \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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \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 \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 \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 \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 \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 } \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 only<3->{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color<3>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B1}{A2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B2}{A3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B3}{A4} \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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash only<4->{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color<4>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B1}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B2}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \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 } \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 only<5->{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color<5>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C1}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5335,11 +5492,11 @@ alert<11>{ pgfnodeconnline{C2}{D3}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5348,51 +5505,51 @@ alert<12-13>{ pgfnodeconnline{C3}{D4}} \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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash only<6->{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color<6>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5401,11 +5558,11 @@ alert<11>{ pgfnodeconnline{A1}{C2}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5414,61 +5571,61 @@ alert<12-13>{ pgfnodeconnline{A2}{C3}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A3}{C4} \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 \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash only<7->{ \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash color<7>{red} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5477,121 +5634,121 @@ alert<12-13>{ pgfnodeconnline{A1}{A2}} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A2}{A3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{A3}{A4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B1}{B2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B2}{B3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{B3}{B4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C1}{C2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C2}{C3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{C3}{C4} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D1}{D2} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash pgfnodeconnline{D2}{D3} \end_layout -\begin_layout Standard +\begin_layout Plain Layout \end_layout -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5600,20 +5757,20 @@ alert<11>{ pgfnodeconnline{D3}{D4}} \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 @@ -5630,7 +5787,7 @@ end{pgfpicture} \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <6> \end_layout @@ -5649,15 +5806,19 @@ Approximators Compute Paths that Are Nearly As Short As a Shortest Path \end_layout \begin_layout Definition -An +An +\color none + \color red approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ \end_inset +\color none + \color inherit - gets as input +gets as input \end_layout \begin_deeper @@ -5686,7 +5847,10 @@ a path from \begin_inset Formula $s$ \end_inset - to\InsetSpace ~ + to +\begin_inset space ~ +\end_inset + \begin_inset Formula $t$ \end_inset @@ -5701,9 +5865,10 @@ a path from \end_deeper \begin_layout BeginFrame 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 \begin_layout Theorem @@ -5716,8 +5881,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 @@ -5733,13 +5900,14 @@ In tournaments, paths can be constructed in logarithmic space. \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 @@ -5757,7 +5925,7 @@ beamergotobutton{More Details}} \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout <7> \end_layout @@ -5767,6 +5935,158 @@ status collapsed hierarchy \end_layout +\begin_layout EndFrame + +\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 + +. + This is not yet supported by LyX, so the frame is created using TeX code. + Note that the +\backslash +begin{frame}[fragile] needs to be preceeded by an +\emph on +EndFrame +\emph default + environment. +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +begin{frame}[fragile] +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + + +\backslash +frametitle{ +\end_layout + +\end_inset + +Just a frame with a program code listing +\begin_inset ERT +status collapsed + +\begin_layout Plain Layout + +} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +This is some program code: +\end_layout + +\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 + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +end{frame} +\end_layout + +\end_inset + + +\end_layout + \begin_layout Section* Summary \end_layout @@ -5781,9 +6101,9 @@ Summary \begin_layout Block \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Summary} \end_layout @@ -5795,13 +6115,19 @@ status inlined \begin_deeper \begin_layout Itemize -Tournament +Tournament +\color none + \color red reachability +\color none + \color inherit - is in -\color red +is in +\color none +\color red + \begin_inset Formula $\Class{AC}^{0}$ \end_inset @@ -5812,25 +6138,39 @@ reachability \end_layout \begin_layout Itemize -There exists a +There exists a +\color none + \color red logspace approximation scheme +\color none + \color inherit - for +for +\color none + \color red approximating +\color none + \color inherit - shortest paths in tournaments. +shortest paths in tournaments. \end_layout \begin_layout Itemize -Finding +Finding +\color none + \color red shortest paths +\color none + \color inherit - in tournaments is -\color red +in tournaments is +\color none +\color red + \begin_inset Formula $\Class{NL}$ \end_inset @@ -5846,9 +6186,9 @@ shortest paths \begin_layout Block \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout {Outlook} \end_layout @@ -5861,14 +6201,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 @@ -5884,14 +6228,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 @@ -5916,9 +6264,9 @@ For Further Reading \begin_layout Standard \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5931,15 +6279,23 @@ beamertemplatebookbibitems \end_layout \begin_layout Bibliography +\labelwidthstring References +\begin_inset CommandInset bibitem +LatexCommand bibitem +key "Moon1968" + +\end_inset + + +\begin_inset space ~ +\end_inset -\bibitem {Moon1968} -\InsetSpace ~ John Moon. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5957,7 +6313,7 @@ Topics on Tournaments. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5969,9 +6325,9 @@ newblock Holt, Rinehart, and Winston, 1968. \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -5984,15 +6340,23 @@ beamertemplatearticlebibitems \end_layout \begin_layout Bibliography +\labelwidthstring References +\begin_inset CommandInset bibitem +LatexCommand bibitem +key "NickelsenT2002" + +\end_inset + + +\begin_inset space ~ +\end_inset -\bibitem {NickelsenT2002} -\InsetSpace ~ Arfst Nickelsen and Till Tantau. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6005,7 +6369,7 @@ newblock \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6023,14 +6387,22 @@ Proc. \end_layout \begin_layout Bibliography +\labelwidthstring References +\begin_inset CommandInset bibitem +LatexCommand bibitem +key "Tantau2004b" + +\end_inset + + +\begin_inset space ~ +\end_inset -\bibitem {Tantau2004b} -\InsetSpace ~ Till Tantau \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6044,7 +6416,7 @@ newblock \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6063,7 +6435,7 @@ Proc. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6082,9 +6454,9 @@ newblock \begin_layout Standard \start_of_appendix \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6106,9 +6478,9 @@ Graphs With Bounded Independence Number \begin_layout BeginFrame \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout [label=independence] \end_layout @@ -6119,20 +6491,27 @@ Definition of Independence Number of a Graph \end_layout \begin_layout Definition -The +The +\color none + \color red independence number -\color inherit +\color none +\color inherit + \begin_inset Formula $\alpha(G)$ \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 @@ -6142,24 +6521,37 @@ Tournaments have independence number 1. \begin_layout BeginFrame 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 \begin_layout Theorem -For each\InsetSpace ~ +For each +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset -, +, +\color none + \color red reachability +\color none + \color inherit - in graphs with independence number -\newline -at most\InsetSpace ~ +in graphs with independence number +\begin_inset Newline newline +\end_inset + +at most +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset @@ -6176,17 +6568,27 @@ at most\InsetSpace ~ \end_layout \begin_layout Theorem -For each\InsetSpace ~ +For each +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset -, there exists a +, there exists a +\color none + \color red 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 @@ -6199,21 +6601,33 @@ logspace approximation scheme \end_layout \begin_layout Theorem -For each\InsetSpace ~ +For each +\begin_inset space ~ +\end_inset + \begin_inset Formula $k$ \end_inset -, finding the +, finding the +\color none + \color red 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 - is + is +\color none + \color red \begin_inset Formula $\Class{NL}$ @@ -6230,9 +6644,9 @@ Finding Paths in Undirected Graphs \begin_layout BeginFrame \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout <1-2>[label=undirected] \end_layout @@ -6240,7 +6654,9 @@ status inlined \end_inset The Complexity of Finding Paths in Undirected Graphs -\newline +\begin_inset Newline newline +\end_inset + Is Party Unknown. \end_layout @@ -6271,9 +6687,9 @@ the reachability problem in logspace iff \begin_layout Itemize the construction problem in logspace iff \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6294,9 +6710,9 @@ Class{SL}$}} \begin_layout Itemize the optimization problem in logspace iff \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash @@ -6326,9 +6742,9 @@ The Approximation Scheme is Optimal \begin_layout BeginFrame \begin_inset ERT -status inlined +status collapsed -\begin_layout Standard +\begin_layout Plain Layout [label=optimality] \end_layout @@ -6362,7 +6778,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 @@ -6390,7 +6808,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 @@ -6404,7 +6824,7 @@ The resulting path has optimal length. \begin_inset ERT status collapsed -\begin_layout Standard +\begin_layout Plain Layout \backslash