+\backslash
+langat{2.375}{``$
+\backslash
+Lang{approx}_{
+\backslash
+operatorname{tourn}}$''}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{pgfpicture}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout 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
+
+, NC
+\begin_inset Formula $^{1}$
+\end_inset
+
+, and NC
+\begin_inset Formula $^{2}$
+\end_inset
+
+
+\begin_inset Newline newline
+\end_inset
+
+Limit the Circuit Depth
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+setlength
+\backslash
+leftmargini{1em}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+nointerlineskip
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Columns
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+t
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Column
+3.6cm
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Circuit Class
+\begin_inset Formula $\Class{AC}^{0}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $O(1)$
+\end_inset
+
+ depth
+\end_layout
+
+\begin_layout Itemize
+unbounded fan-in
+\end_layout
+
+\end_deeper
+\begin_layout Examples
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Column
+3.6cm
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Circuit Class
+\begin_inset Formula $\Class{NC}^{1}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $O(\log n)$
+\end_inset
+
+ depth
+\end_layout
+
+\begin_layout Itemize
+bounded fan-in
+\end_layout
+
+\end_deeper
+\begin_layout Examples
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Column
+3.6cm
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Circuit Class
+\begin_inset Formula $\Class{NC}^{2}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $O(\log^{2}n)$
+\end_inset
+
+ depth
+\end_layout
+
+\begin_layout Itemize
+bounded fan-in
+\end_layout
+
+\end_deeper
+\begin_layout Examples
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status collapsed
+
+\begin_layout Plain Layout
+2
+\end_layout
+
+\end_inset
+
+hierarchy
+\end_layout
+
+\begin_layout Subsection
+Standard Complexity Results on Finding Paths
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+All Variants of Finding Paths in Directed Graphs
+\begin_inset Newline newline
+\end_inset
+
+Are Equally Difficult
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Fact
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+ and
+\begin_inset Formula $\Lang{distance}$
+\end_inset
+
+ are
+\begin_inset Formula $\Class{NL}$
+\end_inset
+
+-complete.
+
+\end_layout
+
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Corollary
+For directed graphs, we can solve
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+the reachability problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+the construction problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+the optimization problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+the approximation problem in logspace iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status collapsed
+
+\begin_layout Plain Layout
+3
+\end_layout
+
+\end_inset
+
+hierarchy
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+Finding Paths in Forests and Directed Paths is Easy,
+\begin_inset Newline newline
+\end_inset
+
+But Not Trivial
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Fact
+\begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
+\end_inset
+
+ and
+\begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
+\end_inset
+
+ are
+\begin_inset Formula $\Class{L}$
+\end_inset
+
+-complete.
+\end_layout
+
+\begin_layout Separator
+
+\end_layout
+
+\begin_layout Fact
+\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
+\end_inset
+
+ and
+\begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
+\end_inset
+
+ are
+\begin_inset Formula $\Class{L}$
+\end_inset
+
+-complete.
+\end_layout
+
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status collapsed
+
+\begin_layout Plain Layout
+4
+\end_layout
+
+\end_inset
+
+hierarchy
+\end_layout
+
+\begin_layout Section
+Finding Paths in Tournaments
+\end_layout
+
+\begin_layout Subsection
+Complexity of: Does a Path Exist?
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+Definition of the Tournament Reachability Problem
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Definition
+Let
+\color none
+
+\color red
+
+\begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
+\end_inset
+
+
+\color none
+
+\color inherit
+contain all triples
+\begin_inset Formula $(T,s,t)$
+\end_inset
+
+ such that
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Formula $T=(V,E)$
+\end_inset
+
+ is a tournament and
+\end_layout
+
+\begin_layout Enumerate
+there exists a path from
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $s$
+\end_inset
+
+ to
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $t$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout 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
+
+.
+\end_layout
+
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout AlertBlock
+\begin_inset Argument 2
+status collapsed
+
+\begin_layout Plain Layout
+Implications
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+The problem is
+\begin_inset Quotes eld
+\end_inset
+
+easier
+\begin_inset Quotes erd
+\end_inset
+
+ than
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+ and even
+\begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout AgainFrame
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+5
+\end_layout
+
+\end_inset
+
+hierarchy
+\end_layout
+
+\begin_layout Subsection
+Complexity of: Construct a Shortest Path
+\end_layout
+
+\begin_layout Frame
+\begin_inset Argument 4
+status open
+
+\begin_layout Plain Layout
+Finding a Shortest Path Is as Difficult as
+\begin_inset Newline newline
+\end_inset
+
+the Distance Problem
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Definition
+Let
+\color none
+
+\color red
+
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+
+\color none
+
+\color inherit
+contain all tuples
+\begin_inset Formula $(T,s,t,d)$
+\end_inset
+
+ such that
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Formula $T=(V,E)$
+\end_inset
+
+ is a tournament in which
+\end_layout
+
+\begin_layout Enumerate
+the distance of
+\begin_inset Formula $s$
+\end_inset
+
+ and
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $t$
+\end_inset
+
+ is at most
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $d$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_deeper
+\begin_layout 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
+
+ is
+\begin_inset Formula $\Class{NL}$
+\end_inset
+
+-complete.
+\end_layout
+
+\begin_layout Standard
+\begin_inset space \hfill{}
+\end_inset
+
+
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+hyperlink{hierarchy<6>}{
+\backslash
+beamerskipbutton{Skip Proof}}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Corollary
+Shortest path in tournaments can be constructed
+\begin_inset Newline newline
+\end_inset
+
+in logarithmic space, iff
+\begin_inset Formula $\Class{L}=\Class{NL}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Pause
+
+\end_layout
+
+\begin_layout Corollary
+\begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout 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
+
+ is NL-complete
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+nointerlineskip
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Columns
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+t,onlytextwidth
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Column
+5.7cm
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+setlength
+\backslash
+leftmargini{1.5em}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Reduce
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+ to
+\begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+alert@1
+\end_layout
+
+\end_inset
+
+Is input
+\begin_inset Formula $(G,s,t)$
+\end_inset
+
+ in
+\begin_inset Formula $\Lang{reach}$
+\end_inset
+
+?
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+2-| alert@2-8
+\end_layout
+
+\end_inset
+
+Map
+\begin_inset Formula $G$
+\end_inset
+
+ to
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+9-| alert@9
+\end_layout
+
+\end_inset
+
+Query:
+\begin_inset Newline newline
+\end_inset
+
+
+\begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
+\end_inset
+
+?
+\end_layout
+
+\end_deeper
+\begin_layout Separator
+
+\end_layout
+
+\begin_layout Block
+\begin_inset Argument 2
+status open
+
+\begin_layout Plain Layout
+Correctness
+\end_layout
+
+\end_inset
+
+
+\begin_inset Argument 1
+status open
+
+\begin_layout Plain Layout
+10-
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+10-| alert@10-11
+\end_layout
+
+\end_inset
+
+A path in
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ induces
+\begin_inset Newline newline
+\end_inset
+
+a length-3 path in
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:2
+status open
+
+\begin_layout Plain Layout
+12-| alert@12-13
+\end_layout
+
+\end_inset
+
+A length-3 path in
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $G'$
+\end_inset
+
+ induces
+\begin_inset Newline newline
+\end_inset
+
+a path in
+\begin_inset space ~
+\end_inset
+
+
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Column
+4.5cm
+\end_layout
+
+\begin_layout Example
+\begin_inset ERT
+status collapsed
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+color{beamerexample}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfsetlinewidth{0.6pt}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+graphnode{A}{
+\backslash
+pgfxy(1,3.3)}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+graphnode{B}{
+\backslash
+pgfxy(2,3.3)}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+graphnode{C}{
+\backslash
+pgfxy(3,3.3)}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+graphnode{D}{
+\backslash
+pgfxy(4,3.3)}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+color{white}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{A}}{
+\backslash
+pgfbox[center,center]{$s$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+pgfputat{
+\backslash
+pgfnodecenter{D}}{
+\backslash
+pgfbox[center,center]{$t$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+color{beamerexample}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash