lib/examples/beamerlyxexample1.lyx

   1 #LyX 1.3 created this file. For more info see http://www.lyx.org/
   2 \lyxformat 221
   3 \textclass beamer
   4 \begin_preamble
   5 \beamertemplateshadingbackground{red!5}{structure!5}
   6
   7 \usepackage{beamerthemeshadow}
   8 \usepackage{pgfnodes,pgfarrows,pgfheaps}
   9
  10 \beamertemplatetransparentcovereddynamicmedium
  11
  12
  13 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
  14 \logo{\pgfuseimage{icsi-logo}}
  15
  16
  17
  18
  19 \newcommand{\Class}[1]{\operatorname{\mathchoice
  20   {\text{\small #1}}
  21   {\text{\small #1}}
  22   {\text{#1}}
  23   {\text{#1}}}}
  24
  25 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
  26
  27 \newcommand{\tape}[3]{%
  28   \color{structure!30!averagebackgroundcolor}
  29   \pgfmoveto{\pgfxy(-0.5,0)}
  30   \pgflineto{\pgfxy(-0.6,0.1)}
  31   \pgflineto{\pgfxy(-0.4,0.2)}
  32   \pgflineto{\pgfxy(-0.6,0.3)}
  33   \pgflineto{\pgfxy(-0.4,0.4)}
  34   \pgflineto{\pgfxy(-0.5,0.5)}
  35   \pgflineto{\pgfxy(4,0.5)}
  36   \pgflineto{\pgfxy(4.1,0.4)}
  37   \pgflineto{\pgfxy(3.9,0.3)}
  38   \pgflineto{\pgfxy(4.1,0.2)}
  39   \pgflineto{\pgfxy(3.9,0.1)}
  40   \pgflineto{\pgfxy(4,0)}
  41   \pgfclosepath
  42   \pgffill
  43
  44   \color{structure}
  45   \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
  46   \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
  47
  48   \color{black}
  49   \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
  50 }
  51
  52 \newcommand{\shorttape}[3]{%
  53   \color{structure!30!averagebackgroundcolor}
  54   \pgfmoveto{\pgfxy(-0.5,0)}
  55   \pgflineto{\pgfxy(-0.6,0.1)}
  56   \pgflineto{\pgfxy(-0.4,0.2)}
  57   \pgflineto{\pgfxy(-0.6,0.3)}
  58   \pgflineto{\pgfxy(-0.4,0.4)}
  59   \pgflineto{\pgfxy(-0.5,0.5)}
  60   \pgflineto{\pgfxy(1,0.5)}
  61   \pgflineto{\pgfxy(1.1,0.4)}
  62   \pgflineto{\pgfxy(0.9,0.3)}
  63   \pgflineto{\pgfxy(1.1,0.2)}
  64   \pgflineto{\pgfxy(0.9,0.1)}
  65   \pgflineto{\pgfxy(1,0)}
  66   \pgfclosepath
  67   \pgffill
  68
  69   \color{structure}
  70   \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
  71   \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
  72
  73   \color{black}
  74   \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
  75 }
  76
  77 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
  78   {color(0pt)=(black); color(1cm)=(structure!65!white)}
  79 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
  80   {color(0pt)=(black); color(1cm)=(structure!55!white)}
  81 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
  82   {color(0pt)=(black); color(1cm)=(structure!45!white)}
  83 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
  84   {color(0pt)=(black); color(1cm)=(structure!35!white)}
  85 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
  86   {color(0pt)=(black); color(1cm)=(structure!25!white)}
  87 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
  88   {color(0pt)=(black); color(1cm)=(red!35!white)}
  89
  90 \newcommand{\heap}[5]{%
  91   \begin{pgfscope}
  92     \color{#4}
  93     \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
  94     \pgfclip
  95     \begin{pgfmagnify}{1}{#1}
  96       \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
  97     \end{pgfmagnify}
  98   \end{pgfscope}
  99   %\pgffill
 100
 101   \color{#4}
 102   \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
 103   \pgfstroke
 104
 105   \color{white}
 106   \pgfheaplabel{\pgfxy(0,#1)}{#3}%
 107 }
 108
 109
 110 \newcommand{\langat}[2]{%
 111   \color{black!30!beamerexample}
 112   \pgfsetlinewidth{0.6pt}
 113   \pgfsetendarrow{\pgfarrowdot}
 114   \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
 115   \color{beamerexample}
 116   \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
 117 }
 118
 119 \newcommand{\langatother}[2]{%
 120   \color{black!30!beamerexample}
 121   \pgfsetlinewidth{0.6pt}
 122   \pgfsetendarrow{\pgfarrowdot}
 123   \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
 124   \color{beamerexample}
 125   \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
 126 }
 127
 128
 129 \pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
 130
 131
 132 \pgfdeclareradialshading{graphnode}
 133   {\pgfpoint{-3pt}{3.6pt}}%
 134   {color(0cm)=(beamerexample!15);
 135     color(2.63pt)=(beamerexample!75);
 136     color(5.26pt)=(beamerexample!70!black);
 137     color(7.6pt)=(beamerexample!50!black);
 138     color(8pt)=(beamerexample!10!averagebackgroundcolor)}
 139
 140 \newcommand{\graphnode}[2]{
 141   \pgfnodecircle{#1}[virtual]{#2}{8pt}
 142   \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
 143 }
 144 \end_preamble
 145 \options notes=show
 146 \language english
 147 \inputencoding auto
 148 \fontscheme times
 149 \graphics default
 150 \paperfontsize default
 151 \spacing single
 152 \papersize Default
 153 \paperpackage a4
 154 \use_geometry 0
 155 \use_amsmath 1
 156 \use_natbib 0
 157 \use_numerical_citations 0
 158 \paperorientation portrait
 159 \secnumdepth 2
 160 \tocdepth 2
 161 \paragraph_separation indent
 162 \defskip medskip
 163 \quotes_language english
 164 \quotes_times 2
 165 \papercolumns 1
 166 \papersides 1
 167 \paperpagestyle default
 168
 169 \layout Title
 170
 171 The Complexity of
 172 \newline
 173 Finding Paths in Tournaments
 174 \layout Author
 175
 176 Till Tantau
 177 \layout Institute
 178
 179 International Computer Schience Institute
 180 \newline
 181 Berkeley, California
 182 \begin_inset OptArg
 183 collapsed true
 184
 185 \layout Standard
 186
 187 ICSI
 188 \end_inset
 189
 190
 191 \layout Date
 192
 193 January 30th, 2004
 194 \layout BeginFrame
 195
 196 Outline
 197 \layout Standard
 198
 199
 200 \begin_inset LatexCommand \tableofcontents{}
 201
 202 \end_inset
 203
 204
 205 \begin_inset ERT
 206 status Collapsed
 207
 208 \layout Standard
 209 [pausesections]
 210 \end_inset
 211
 212
 213 \layout EndFrame
 214
 215 \layout Standard
 216
 217
 218 \begin_inset ERT
 219 status Collapsed
 220
 221 \layout Standard
 222 % Show the table of contents at the beginning
 223 \layout Standard
 224 % of every subsection.
 225 \layout Standard
 226
 227 \backslash
 228 AtBeginSubsection[]{
 229 \layout Standard
 230
 231 \backslash
 232 frame<handout:0>{
 233 \layout Standard
 234
 235 \backslash
 236 frametitle{Outline}
 237 \layout Standard
 238
 239 \backslash
 240 tableofcontents[current,currentsubsection]
 241 \layout Standard
 242   }
 243 \layout Standard
 244 }
 245 \end_inset
 246
 247
 248 \layout Section
 249
 250 Introduction
 251 \layout Subsection
 252
 253 What are Tournaments?
 254 \layout BeginFrame
 255
 256 Tournaments Consist of Jousts Between Knights
 257 \layout Columns
 258
 259 \begin_deeper
 260 \layout Column
 261
 262 5.75cm
 263 \layout Standard
 264
 265
 266 \begin_inset ERT
 267 status Inlined
 268
 269 \layout Standard
 270
 271 \backslash
 272 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
 273 \layout Standard
 274
 275 \backslash
 276 pgfnodebox{A}[virtual]{
 277 \backslash
 278 pgfxy(2,1)}{
 279 \backslash
 280 pgfuseimage{knight1}}{2pt}{2pt}
 281 \layout Standard
 282
 283 \backslash
 284 pgfnodebox{B}[virtual]{
 285 \backslash
 286 pgfxy(6,1)}{
 287 \backslash
 288 pgfuseimage{knight2}}{2pt}{2pt}
 289 \layout Standard
 290
 291 \backslash
 292 pgfnodebox{C}[virtual]{
 293 \backslash
 294 pgfxy(4,-1)}{
 295 \backslash
 296 pgfuseimage{knight3}}{2pt}{2pt}
 297 \layout Standard
 298
 299 \backslash
 300 pgfnodebox{D}[virtual]{
 301 \backslash
 302 pgfxy(4,3)}{
 303 \backslash
 304 pgfuseimage{knight4}}{2pt}{2pt}
 305 \layout Standard
 306
 307 \layout Standard
 308
 309 \backslash
 310 color{beamerexample}
 311 \layout Standard
 312
 313 \backslash
 314 only<3->{
 315 \backslash
 316 pgfsetendarrow{
 317 \backslash
 318 pgfarrowto}}
 319 \layout Standard
 320
 321 \backslash
 322 only<2->{
 323 \layout Standard
 324
 325 \backslash
 326 pgfsetlinewidth{0.6pt}
 327 \layout Standard
 328
 329 \backslash
 330 pgfnodeconnline{A}{B}
 331 \layout Standard
 332
 333 \backslash
 334 pgfnodeconnline{A}{C}
 335 \layout Standard
 336
 337 \backslash
 338 pgfnodeconnline{D}{A}
 339 \layout Standard
 340
 341 \backslash
 342 pgfnodeconnline{C}{B}
 343 \layout Standard
 344
 345 \backslash
 346 pgfnodeconnline{B}{D}
 347 \layout Standard
 348
 349 \backslash
 350 pgfnodeconnline{C}{D}}
 351 \layout Standard
 352
 353 \backslash
 354 end{pgfpicture}
 355 \end_inset
 356
 357
 358 \layout Column
 359
 360 6cm
 361 \layout Block
 362
 363
 364 \begin_inset ERT
 365 status Inlined
 366
 367 \layout Standard
 368 {What is a Tournament?}
 369 \end_inset
 370
 371
 372 \begin_deeper
 373 \layout Itemize
 374
 375
 376 \begin_inset ERT
 377 status Collapsed
 378
 379 \layout Standard
 380 <1->
 381 \end_inset
 382
 383 A group of knights.
 384 \layout Itemize
 385
 386
 387 \begin_inset ERT
 388 status Collapsed
 389
 390 \layout Standard
 391 <2->
 392 \end_inset
 393
 394 Every pair has a joust.
 395 \layout Itemize
 396
 397
 398 \begin_inset ERT
 399 status Collapsed
 400
 401 \layout Standard
 402 <3->
 403 \end_inset
 404
 405 In every joust one knight wins.
 406 \end_deeper
 407 \end_deeper
 408 \layout BeginFrame
 409
 410 Tournaments are Complete Directed Graphs
 411 \layout Columns
 412
 413 \begin_deeper
 414 \layout Column
 415
 416 5cm
 417 \layout Standard
 418
 419
 420 \begin_inset ERT
 421 status Inlined
 422
 423 \layout Standard
 424
 425 \backslash
 426 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
 427 \layout Standard
 428
 429 \backslash
 430 color{beamerexample}
 431 \layout Standard
 432
 433 \backslash
 434 pgfsetlinewidth{0.6pt}
 435 \layout Standard
 436
 437 \backslash
 438 graphnode{A}{
 439 \backslash
 440 pgfxy(2.5,1)}
 441 \layout Standard
 442
 443 \backslash
 444 graphnode{B}{
 445 \backslash
 446 pgfxy(5.5,1)}
 447 \layout Standard
 448
 449 \backslash
 450 graphnode{C}{
 451 \backslash
 452 pgfxy(4,-0.5)}
 453 \layout Standard
 454
 455 \backslash
 456 graphnode{D}{
 457 \backslash
 458 pgfxy(4,2.5)}
 459 \layout Standard
 460
 461 \layout Standard
 462
 463 \backslash
 464 color{white}
 465 \layout Standard
 466
 467 \backslash
 468 pgfputat{
 469 \backslash
 470 pgfnodecenter{A}}{
 471 \backslash
 472 pgfbox[center,center]{$v_2$}}
 473 \layout Standard
 474
 475 \backslash
 476 pgfputat{
 477 \backslash
 478 pgfnodecenter{B}}{
 479 \backslash
 480 pgfbox[center,center]{$v_3$}}
 481 \layout Standard
 482
 483 \backslash
 484 pgfputat{
 485 \backslash
 486 pgfnodecenter{C}}{
 487 \backslash
 488 pgfbox[center,center]{$v_4$}}
 489 \layout Standard
 490
 491 \backslash
 492 pgfputat{
 493 \backslash
 494 pgfnodecenter{D}}{
 495 \backslash
 496 pgfbox[center,center]{$v_1$}}
 497 \layout Standard
 498
 499 \layout Standard
 500
 501 \backslash
 502 color{beamerexample}
 503 \layout Standard
 504
 505 \backslash
 506 pgfsetendarrow{
 507 \backslash
 508 pgfarrowto}
 509 \layout Standard
 510
 511 \backslash
 512 pgfnodesetsepstart{2pt}
 513 \layout Standard
 514
 515 \backslash
 516 pgfnodesetsepend{4pt}
 517 \layout Standard
 518
 519 \backslash
 520 pgfnodeconnline{A}{B}
 521 \layout Standard
 522
 523 \backslash
 524 pgfnodeconnline{A}{C}
 525 \layout Standard
 526
 527 \backslash
 528 pgfnodeconnline{D}{A}
 529 \layout Standard
 530
 531 \backslash
 532 pgfnodeconnline{C}{B}
 533 \layout Standard
 534
 535 \backslash
 536 pgfnodeconnline{B}{D}
 537 \layout Standard
 538
 539 \backslash
 540 pgfnodeconnline{D}{C}
 541 \layout Standard
 542
 543 \backslash
 544 end{pgfpicture}
 545 \end_inset
 546
 547
 548 \layout Column
 549
 550 6cm
 551 \layout Definition
 552
 553
 554 \begin_inset ERT
 555 status Collapsed
 556
 557 \layout Standard
 558 <2->
 559 \end_inset
 560
 561 A
 562 \color red
 563 tournament
 564 \color default
 565  is a
 566 \begin_deeper
 567 \layout Enumerate
 568
 569 directed graphs,
 570 \layout Enumerate
 571
 572 with exactly one edge between
 573 \newline
 574 any two different vertices.
 575 \end_deeper
 576 \end_deeper
 577 \layout BeginFrame
 578
 579
 580 \begin_inset ERT
 581 status Collapsed
 582
 583 \layout Standard
 584 [<+>]
 585 \end_inset
 586
 587 Tournaments Arise Naturally in Different Situations
 588 \layout ExampleBlock
 589
 590
 591 \begin_inset ERT
 592 status Inlined
 593
 594 \layout Standard
 595 {Applicatins in Ordering Theory}
 596 \end_inset
 597
 598
 599 \begin_deeper
 600 \layout Standard
 601
 602 Elements in a set need to be sorted.
 603
 604 \newline
 605 The comparison relation may be cyclic, however.
 606 \end_deeper
 607 \layout Separator
 608
 609 \layout ExampleBlock
 610
 611
 612 \begin_inset ERT
 613 status Inlined
 614
 615 \layout Standard
 616 {Applications in Sociology}
 617 \end_inset
 618
 619
 620 \begin_deeper
 621 \layout Standard
 622
 623 Several candidates apply for a position.
 624 \newline
 625 Reviewers decide for any two candidates whom they prefer.
 626
 627 \end_deeper
 628 \layout Separator
 629
 630 \layout ExampleBlock
 631
 632
 633 \begin_inset ERT
 634 status Inlined
 635
 636 \layout Standard
 637 {Applications in Structural Complexity Theory}
 638 \end_inset
 639
 640
 641 \begin_deeper
 642 \layout Standard
 643
 644 A language
 645 \begin_inset Formula $L$
 646 \end_inset
 647
 648  is given and a selector function
 649 \begin_inset Formula $f$
 650 \end_inset
 651
 652 .
 653 \newline
 654 It chooses from any two words the one more likely to be in
 655 \begin_inset Formula $f$
 656 \end_inset
 657
 658 .
 659 \end_deeper
 660 \layout Subsection
 661
 662 What Does ``Finding Paths'' Mean?
 663 \layout BeginFrame
 664
 665 ``Finding Paths'' is Ambiguous
 666 \layout Block
 667
 668
 669 \begin_inset ERT
 670 status Inlined
 671
 672 \layout Standard
 673 {
 674 \backslash
 675 strut Input for
 676 \backslash
 677 ignorespaces
 678 \backslash
 679 def
 680 \backslash
 681 par{}% because LyX inserts superfluous paragraphs
 682 \layout Standard
 683
 684 \backslash
 685 only<1>{Path Finding Problems}
 686 \backslash
 687 ignorespaces
 688 \layout Standard
 689
 690 \backslash
 691 only<2-3>{$
 692 \backslash
 693 Lang{reach}$}
 694 \backslash
 695 ignorespaces
 696 \layout Standard
 697
 698 \backslash
 699 only<4-5>{the Construction Problem}
 700 \backslash
 701 ignorespaces
 702 \layout Standard
 703
 704 \backslash
 705 only<6-7>{the Optimization Problem}
 706 \backslash
 707 ignorespaces
 708 \layout Standard
 709
 710 \backslash
 711 only<8-9>{$
 712 \backslash
 713 Lang{distance}$}
 714 \backslash
 715 ignorespaces
 716 \layout Standard
 717
 718 \backslash
 719 only<10->{the Approximation Problem}}
 720 \end_inset
 721
 722
 723 \begin_deeper
 724 \layout Itemize
 725
 726 A
 727 \color red
 728 graph
 729 \color default
 730
 731 \begin_inset Formula $G=(V,E)$
 732 \end_inset
 733
 734 , a
 735 \color red
 736 source
 737 \color default
 738
 739 \begin_inset Formula $s\in V$
 740 \end_inset
 741
 742  and a
 743 \color red
 744 target
 745 \color default
 746
 747 \begin_inset Formula $t\in V$
 748 \end_inset
 749
 750 .
 751 \layout Itemize
 752
 753
 754 \begin_inset ERT
 755 status Collapsed
 756
 757 \layout Standard
 758 <only@-9| visible@8->
 759 \end_inset
 760
 761 A
 762 \color red
 763 maximum distance
 764 \color default
 765 \SpecialChar ~
 766
 767 \begin_inset Formula $d$
 768 \end_inset
 769
 770 .
 771 \begin_inset ERT
 772 status Collapsed
 773
 774 \layout Standard
 775
 776 \backslash
 777 phantom{p}
 778 \end_inset
 779
 780
 781 \layout Itemize
 782
 783
 784 \begin_inset ERT
 785 status Collapsed
 786
 787 \layout Standard
 788 <only@10->
 789 \end_inset
 790
 791 An
 792 \color red
 793 approximation ratio
 794 \color default
 795
 796 \begin_inset Formula $r>1$
 797 \end_inset
 798
 799 .
 800 \end_deeper
 801 \layout Standard
 802
 803
 804 \begin_inset ERT
 805 status Collapsed
 806
 807 \layout Standard
 808
 809 \backslash
 810 nointerlineskip
 811 \end_inset
 812
 813
 814 \layout Overprint
 815
 816 \begin_deeper
 817 \layout Standard
 818
 819
 820 \begin_inset ERT
 821 status Inlined
 822
 823 \layout Standard
 824
 825 \backslash
 826 onslide<1,3,5,7,9,11-12>
 827 \end_inset
 828
 829
 830 \layout Columns
 831
 832
 833 \begin_inset ERT
 834 status Inlined
 835
 836 \layout Standard
 837 [t,onlytextwidth]
 838 \end_inset
 839
 840
 841 \begin_deeper
 842 \layout Standard
 843
 844
 845 \begin_inset ERT
 846 status Inlined
 847
 848 \layout Standard
 849
 850 \backslash
 851 alt<1-2>{
 852 \backslash
 853 column{
 854 \backslash
 855 textwidth}}{
 856 \backslash
 857 column{5cm}}
 858 \end_inset
 859
 860
 861 \layout ExampleBlock
 862
 863
 864 \begin_inset ERT
 865 status Inlined
 866
 867 \layout Standard
 868 {Example Input}
 869 \end_inset
 870
 871
 872 \begin_deeper
 873 \layout Standard
 874
 875
 876 \begin_inset ERT
 877 status Inlined
 878
 879 \layout Standard
 880
 881 \backslash
 882 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
 883 \layout Standard
 884
 885 \backslash
 886 color{beamerexample}
 887 \layout Standard
 888
 889 \backslash
 890 pgfsetlinewidth{0.6pt}
 891 \layout Standard
 892
 893 \backslash
 894 graphnode{A}{
 895 \backslash
 896 pgfxy(3,1)}
 897 \layout Standard
 898
 899 \backslash
 900 graphnode{B}{
 901 \backslash
 902 pgfxy(5,1)}
 903 \layout Standard
 904
 905 \backslash
 906 graphnode{C}{
 907 \backslash
 908 pgfxy(4,0)}
 909 \layout Standard
 910
 911 \backslash
 912 graphnode{D}{
 913 \backslash
 914 pgfxy(4,2)}
 915 \layout Standard
 916
 917 \layout Standard
 918
 919 \backslash
 920 color{white}
 921 \layout Standard
 922
 923 \backslash
 924 pgfputat{
 925 \backslash
 926 pgfnodecenter{B}}{
 927 \backslash
 928 pgfbox[center,center]{$t$}}
 929 \layout Standard
 930
 931 \backslash
 932 pgfputat{
 933 \backslash
 934 pgfnodecenter{D}}{
 935 \backslash
 936 pgfbox[center,center]{$s$}}
 937 \layout Standard
 938
 939 \layout Standard
 940
 941 \backslash
 942 color{beamerexample}
 943 \layout Standard
 944
 945 \backslash
 946 pgfsetendarrow{
 947 \backslash
 948 pgfarrowto}
 949 \layout Standard
 950
 951 \backslash
 952 pgfnodesetsepstart{2pt}
 953 \layout Standard
 954
 955 \backslash
 956 pgfnodesetsepend{4pt}
 957 \layout Standard
 958
 959 \backslash
 960 pgfnodeconnline{A}{B}
 961 \layout Standard
 962
 963 \backslash
 964 pgfnodeconnline{A}{C}
 965 \layout Standard
 966
 967 \backslash
 968 pgfnodeconnline{D}{A}
 969 \layout Standard
 970
 971 \backslash
 972 pgfnodeconnline{C}{B}
 973 \layout Standard
 974
 975 \backslash
 976 pgfnodeconnline{B}{D}
 977 \layout Standard
 978
 979 \backslash
 980 pgfnodeconnline{D}{C}
 981 \layout Standard
 982
 983 \layout Standard
 984
 985 \backslash
 986 only<9> {
 987 \backslash
 988 pgfputat{
 989 \backslash
 990 pgfxy(5.3,1)}{
 991 \backslash
 992 pgfbox[left,center]{, $d=2$}}}
 993 \layout Standard
 994
 995 \backslash
 996 only<11>{
 997 \backslash
 998 pgfputat{
 999 \backslash
1000 pgfxy(5.3,1)}{
1001 \backslash
1002 pgfbox[left,center]{, $r=1.5$}}}
1003 \layout Standard
1004
1005 \backslash
1006 only<12>{
1007 \backslash
1008 pgfputat{
1009 \backslash
1010 pgfxy(5.3,1)}{
1011 \backslash
1012 pgfbox[left,center]{, $r=1.25$}}}
1013 \layout Standard
1014
1015 \backslash
1016 end{pgfpicture}
1017 \end_inset
1018
1019
1020 \end_deeper
1021 \layout Standard
1022
1023
1024 \begin_inset ERT
1025 status Inlined
1026
1027 \layout Standard
1028
1029 \backslash
1030 only<3->{
1031 \backslash
1032 column{5cm}}
1033 \end_inset
1034
1035
1036 \layout ExampleBlock
1037
1038
1039 \begin_inset ERT
1040 status Inlined
1041
1042 \layout Standard
1043 <only@3->{Example Output}
1044 \end_inset
1045
1046
1047 \begin_deeper
1048 \layout Standard
1049
1050
1051 \begin_inset ERT
1052 status Inlined
1053
1054 \layout Standard
1055
1056 \backslash
1057 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1058 \layout Standard
1059
1060 \backslash
1061 only<5-8,10->{
1062 \layout Standard
1063
1064 \backslash
1065 color{beamerexample}
1066 \layout Standard
1067
1068 \backslash
1069 pgfsetlinewidth{0.6pt}
1070 \layout Standard
1071
1072 \backslash
1073 graphnode{A}{
1074 \backslash
1075 pgfxy(3,1)}
1076 \layout Standard
1077
1078 \backslash
1079 graphnode{B}{
1080 \backslash
1081 pgfxy(5,1)}
1082 \layout Standard
1083
1084 \backslash
1085 graphnode{C}{
1086 \backslash
1087 pgfxy(4,0)}
1088 \layout Standard
1089
1090 \backslash
1091 graphnode{D}{
1092 \backslash
1093 pgfxy(4,2)}
1094 \layout Standard
1095
1096 \layout Standard
1097
1098 \backslash
1099 color{white}
1100 \layout Standard
1101
1102 \backslash
1103 pgfputat{
1104 \backslash
1105 pgfnodecenter{B}}{
1106 \backslash
1107 pgfbox[center,center]{$t$}}
1108 \layout Standard
1109
1110 \backslash
1111 pgfputat{
1112 \backslash
1113 pgfnodecenter{D}}{
1114 \backslash
1115 pgfbox[center,center]{$s$}}
1116 \layout Standard
1117
1118 \layout Standard
1119
1120 \backslash
1121 color{beamerexample}
1122 \layout Standard
1123
1124 \backslash
1125 pgfsetendarrow{
1126 \backslash
1127 pgfarrowto}
1128 \layout Standard
1129
1130 \backslash
1131 pgfnodesetsepstart{2pt}
1132 \layout Standard
1133
1134 \backslash
1135 pgfnodesetsepend{4pt}
1136 \layout Standard
1137
1138 \layout Standard
1139
1140 \backslash
1141 alert<7,12>{
1142 \backslash
1143 pgfnodeconnline{A}{B}}
1144 \layout Standard
1145
1146 \backslash
1147 alert<5,11>{
1148 \backslash
1149 pgfnodeconnline{A}{C}}
1150 \layout Standard
1151
1152 \backslash
1153 alert<5,7,11-12>{
1154 \backslash
1155 pgfnodeconnline{D}{A}}
1156 \layout Standard
1157
1158 \backslash
1159 alert<5,11>{
1160 \backslash
1161 pgfnodeconnline{C}{B}}
1162 \layout Standard
1163
1164 \backslash
1165 pgfnodeconnline{B}{D}
1166 \layout Standard
1167
1168 \backslash
1169 pgfnodeconnline{D}{C}
1170 \layout Standard
1171   }
1172 \layout Standard
1173
1174 \backslash
1175 only<3,9>{
1176 \backslash
1177 pgfputat{
1178 \backslash
1179 pgfxy(2.75,1)}{
1180 \backslash
1181 pgfbox[left,center]{
1182 \backslash
1183 alert{``Yes''}}}}
1184 \layout Standard
1185
1186 \backslash
1187 end{pgfpicture}
1188 \end_inset
1189
1190
1191 \end_deeper
1192 \end_deeper
1193 \layout Standard
1194
1195
1196 \begin_inset ERT
1197 status Inlined
1198
1199 \layout Standard
1200
1201 \backslash
1202 onslide<2,4,6,8,10>
1203 \end_inset
1204
1205
1206 \layout Block
1207
1208
1209 \begin_inset ERT
1210 status Inlined
1211
1212 \layout Standard
1213 {Variants of Path Finding Problems}
1214 \end_inset
1215
1216
1217 \begin_deeper
1218 \layout Standard
1219
1220
1221 \begin_inset ERT
1222 status Inlined
1223
1224 \layout Standard
1225
1226 \backslash
1227 usedescriptionitemofwidthas{Approximation Problem:}
1228 \end_inset
1229
1230
1231 \layout Description
1232
1233 Reachability\SpecialChar ~
1234 Problem:
1235 \begin_inset ERT
1236 status Collapsed
1237
1238 \layout Standard
1239 <2->
1240 \end_inset
1241
1242 Is there a path from
1243 \begin_inset Formula $s$
1244 \end_inset
1245
1246  to\SpecialChar ~
1247
1248 \begin_inset Formula $t$
1249 \end_inset
1250
1251 ?
1252 \layout Description
1253
1254 Construction\SpecialChar ~
1255 Problem:
1256 \begin_inset ERT
1257 status Collapsed
1258
1259 \layout Standard
1260 <4->
1261 \end_inset
1262
1263 Construct a path from
1264 \begin_inset Formula $s$
1265 \end_inset
1266
1267  to\SpecialChar ~
1268
1269 \begin_inset Formula $t$
1270 \end_inset
1271
1272 ?
1273 \layout Description
1274
1275 Optimization\SpecialChar ~
1276 Problem:
1277 \begin_inset ERT
1278 status Collapsed
1279
1280 \layout Standard
1281 <6->
1282 \end_inset
1283
1284 Construct a shortest path from
1285 \begin_inset Formula $s$
1286 \end_inset
1287
1288  to\SpecialChar ~
1289
1290 \begin_inset Formula $t$
1291 \end_inset
1292
1293 .
1294 \layout Description
1295
1296 Distance\SpecialChar ~
1297 Problem:
1298 \begin_inset ERT
1299 status Collapsed
1300
1301 \layout Standard
1302 <8->
1303 \end_inset
1304
1305 Is the distance of
1306 \begin_inset Formula $s$
1307 \end_inset
1308
1309  and\SpecialChar ~
1310
1311 \begin_inset Formula $t$
1312 \end_inset
1313
1314  at most\SpecialChar ~
1315
1316 \begin_inset Formula $d$
1317 \end_inset
1318
1319 ?
1320 \layout Description
1321
1322 Approximation\SpecialChar ~
1323 Problem:
1324 \begin_inset ERT
1325 status Collapsed
1326
1327 \layout Standard
1328 <10->
1329 \end_inset
1330
1331 Construct a path from
1332 \begin_inset Formula $s$
1333 \end_inset
1334
1335  to\SpecialChar ~
1336
1337 \begin_inset Formula $t$
1338 \end_inset
1339
1340  of length
1341 \newline
1342 approximately their distance.
1343 \end_deeper
1344 \end_deeper
1345 \layout Section
1346
1347 Review
1348 \layout Subsection
1349
1350 Standard Complexity Classes
1351 \layout Standard
1352
1353
1354 \begin_inset ERT
1355 status Inlined
1356
1357 \layout Standard
1358
1359 \backslash
1360 pgfdeclaremask{computer-mask}{beamer-g4-mask}
1361 \backslash
1362 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer-g4}
1363 \end_inset
1364
1365
1366 \layout BeginFrame
1367
1368 The Classes L and NL are Defined via
1369 \newline
1370 Logspace Turing Machines
1371 \layout Standard
1372
1373
1374 \begin_inset ERT
1375 status Open
1376
1377 \layout Standard
1378
1379 \backslash
1380 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
1381 \layout Standard
1382
1383 \backslash
1384 pgfputat{
1385 \backslash
1386 pgfxy(0,4)}{
1387 \backslash
1388 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
1389 \layout Standard
1390
1391 \backslash
1392 uncover<2->{
1393 \layout Standard
1394
1395 \backslash
1396 pgfputat{
1397 \backslash
1398 pgfxy(0,0.5)}{
1399 \backslash
1400 tape{}{output tape (write only)}{10690836937182}}}
1401 \layout Standard
1402
1403 \backslash
1404 uncover<3->{
1405 \layout Standard
1406
1407 \backslash
1408 pgfputat{
1409 \backslash
1410 pgfxy(7,2)}{
1411 \backslash
1412 shorttape{work tape (read/write), $O(
1413 \backslash
1414 log n)$ symbols}{}{42}}
1415 \layout Standard
1416
1417 \backslash
1418 pgfputat{
1419 \backslash
1420 pgfxy(1.75,2.5)}{
1421 \backslash
1422 pgfbox[center,center]{
1423 \backslash
1424 pgfuseimage{computer}}}
1425 \layout Standard
1426   }
1427 \layout Standard
1428
1429 \backslash
1430 pgfsetlinewidth{0.6pt}
1431 \layout Standard
1432
1433 \layout Standard
1434
1435 \backslash
1436 color{structure}
1437 \layout Standard
1438
1439 \backslash
1440 pgfsetendarrow{
1441 \backslash
1442 pgfarrowto}
1443 \layout Standard
1444
1445 \backslash
1446 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
1447 \layout Standard
1448
1449 \backslash
1450 uncover<2->{
1451 \backslash
1452 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
1453 \layout Standard
1454
1455 \backslash
1456 uncover<3->{
1457 \backslash
1458 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
1459 \layout Standard
1460
1461 \backslash
1462 end{pgfpicture}
1463 \end_inset
1464
1465
1466 \layout BeginFrame
1467
1468 Logspace Turing Machines Are Quite Powerful
1469 \layout Block
1470
1471
1472 \begin_inset ERT
1473 status Inlined
1474
1475 \layout Standard
1476 {Deterministic logspace machines can compute}
1477 \end_inset
1478
1479
1480 \begin_deeper
1481 \layout Itemize
1482
1483 addition, multiplication, and even division
1484 \layout Itemize
1485
1486 reductions used in completeness proofs,
1487 \layout Itemize
1488
1489 reachability in forests.
1490 \end_deeper
1491 \layout Pause
1492
1493 \layout Block
1494
1495
1496 \begin_inset ERT
1497 status Inlined
1498
1499 \layout Standard
1500 {Non-deterministic logspace machines can compute}
1501 \end_inset
1502
1503
1504 \begin_deeper
1505 \layout Itemize
1506
1507 reachability in graphs,
1508 \layout Itemize
1509
1510 non-reachability in graphs,
1511 \layout Itemize
1512
1513 satisfiability with two literals per clause.
1514 \end_deeper
1515 \layout BeginFrame
1516
1517
1518 \begin_inset ERT
1519 status Inlined
1520
1521 \layout Standard
1522 <1>[label=hierarchy]
1523 \end_inset
1524
1525 The Complexity Class Hierarchy
1526 \layout Standard
1527
1528
1529 \begin_inset ERT
1530 status Inlined
1531
1532 \layout Standard
1533
1534 \backslash
1535 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
1536 \layout Standard
1537
1538 \backslash
1539 pgfsetlinewidth{0.8pt}
1540 \layout Standard
1541
1542 \backslash
1543 heap{5.5}{3.5}{$
1544 \backslash
1545 Class P$}{black}{1}
1546 \layout Standard
1547
1548 \backslash
1549 pgfsetdash{{2pt}}{0pt}
1550 \layout Standard
1551
1552 \backslash
1553 only<2->{
1554 \backslash
1555 heap{4.5}{3}{$
1556 \backslash
1557 Class{NC}^2$}{black!50!structure}{2}}
1558 \layout Standard
1559
1560 \backslash
1561 heap{3.5}{2.5}{$
1562 \backslash
1563 Class{NL}$}{black!50!structure}{3}
1564 \layout Standard
1565
1566 \backslash
1567 heap{2.5}{2}{$
1568 \backslash
1569 Class{L}$}{black!50!structure}{4}
1570 \layout Standard
1571
1572 \backslash
1573 only<2->{
1574 \backslash
1575 heap{1.75}{1.5}{$
1576 \backslash
1577 vphantom{A}
1578 \backslash
1579 smash{
1580 \backslash
1581 Class{NC}^1}$}{black!50!structure}{5}}
1582 \layout Standard
1583
1584 \backslash
1585 pgfsetdash{}{0pt}
1586 \layout Standard
1587
1588 \backslash
1589 only<2->{
1590 \backslash
1591 heap{1.1}{1}{$
1592 \backslash
1593 vphantom{A}
1594 \backslash
1595 smash{
1596 \backslash
1597 Class{AC}^0}$}{black}{6}}
1598 \layout Standard
1599
1600 \layout Standard
1601
1602 \backslash
1603 pgfsetlinewidth{1.0pt}
1604 \layout Standard
1605
1606 \backslash
1607 color{black}
1608 \layout Standard
1609
1610 \backslash
1611 pgfxyline(-5,0)(5,0)
1612 \layout Standard
1613
1614 \layout Standard
1615
1616 \backslash
1617 only<1-2>{
1618 \backslash
1619 langat{3.375}{$
1620 \backslash
1621 Lang{reach}$}}
1622 \layout Standard
1623
1624 \backslash
1625 only<1-2>{
1626 \backslash
1627 langat{2.375}{$
1628 \backslash
1629 Lang{reach}_{
1630 \backslash
1631 operatorname{forest}}$}}
1632 \layout Standard
1633
1634 \layout Standard
1635
1636 \backslash
1637 only<2>{
1638 \backslash
1639 langat{0.975}{$
1640 \backslash
1641 Lang{addition}$}}
1642 \layout Standard
1643
1644 \backslash
1645 only<2>{
1646 \backslash
1647 langatother{1.6}{
1648 \backslash
1649 vbox{
1650 \backslash
1651 hbox{$
1652 \backslash
1653 Lang{division}$,}
1654 \backslash
1655 hbox{$
1656 \backslash
1657 Lang{parity}$}}}}
1658 \layout Standard
1659
1660 \backslash
1661 only<3-5>{
1662 \backslash
1663 langat{3.375}{
1664 \backslash
1665 vbox{
1666 \backslash
1667 hbox{$
1668 \backslash
1669 Lang{distance}$,}
1670 \backslash
1671 hbox{$
1672 \backslash
1673 Lang{reach}$}}}}
1674 \layout Standard
1675
1676 \backslash
1677 only<4->{
1678 \backslash
1679 langatother{2.375}{
1680 \backslash
1681 vbox{
1682 \backslash
1683 ignorespaces
1684 \layout Standard
1685
1686 \backslash
1687 hbox{$
1688 \backslash
1689 Lang{distance}_{
1690 \backslash
1691 operatorname{forest}}$,}
1692 \backslash
1693 ignorespaces
1694 \layout Standard
1695
1696 \backslash
1697 hbox{$
1698 \backslash
1699 Lang{reach}_{
1700 \backslash
1701 operatorname{forest}}$,}
1702 \backslash
1703 ignorespaces
1704 \layout Standard
1705
1706 \backslash
1707 hbox{$
1708 \backslash
1709 Lang{distance}_{
1710 \backslash
1711 operatorname{path}}$,}
1712 \backslash
1713 ignorespaces
1714 \layout Standard
1715
1716 \backslash
1717 hbox{$
1718 \backslash
1719 Lang{reach}_{
1720 \backslash
1721 operatorname{path}}$}}}}
1722 \layout Standard
1723
1724 \backslash
1725 only<5->{
1726 \backslash
1727 langat{0.975}{$
1728 \backslash
1729 Lang{reach}_{
1730 \backslash
1731 operatorname{tourn}}$}}
1732 \layout Standard
1733
1734 \backslash
1735 only<6->{
1736 \backslash
1737 langat{3.375}{
1738 \backslash
1739 vbox{
1740 \backslash
1741 ignorespaces
1742 \layout Standard
1743
1744 \backslash
1745 hbox{$
1746 \backslash
1747 Lang{distance}_{
1748 \backslash
1749 operatorname{tourn}}$,}
1750 \backslash
1751 ignorespaces
1752 \layout Standard
1753
1754 \backslash
1755 hbox{$
1756 \backslash
1757 Lang{distance}$,}
1758 \backslash
1759 ignorespaces
1760 \layout Standard
1761
1762 \backslash
1763 hbox{$
1764 \backslash
1765 Lang{reach}$}}}}
1766 \layout Standard
1767
1768 \backslash
1769 only<7->{
1770 \backslash
1771 pgfsetdash{{1pt}}{0pt}
1772 \backslash
1773 langat{2.375}{``$
1774 \backslash
1775 Lang{approx}_{
1776 \backslash
1777 operatorname{tourn}}$''}}
1778 \layout Standard
1779
1780 \backslash
1781 end{pgfpicture}
1782 \end_inset
1783
1784
1785 \layout BeginFrame
1786
1787 The Circuit Complexity Classes AC
1788 \begin_inset Formula $^{0}$
1789 \end_inset
1790
1791 , NC
1792 \begin_inset Formula $^{1}$
1793 \end_inset
1794
1795 , and NC
1796 \begin_inset Formula $^{2}$
1797 \end_inset
1798
1799
1800 \newline
1801 Limit the Circuit Depth
1802 \layout Standard
1803
1804
1805 \begin_inset ERT
1806 status Inlined
1807
1808 \layout Standard
1809
1810 \backslash
1811 setlength
1812 \backslash
1813 leftmargini{1em}
1814 \layout Standard
1815
1816 \backslash
1817 nointerlineskip
1818 \end_inset
1819
1820
1821 \layout Columns
1822
1823
1824 \begin_inset ERT
1825 status Collapsed
1826
1827 \layout Standard
1828 [t]
1829 \end_inset
1830
1831
1832 \begin_deeper
1833 \layout Column
1834
1835 3.6cm
1836 \layout Block
1837
1838
1839 \begin_inset ERT
1840 status Collapsed
1841
1842 \layout Standard
1843 {
1844 \end_inset
1845
1846 Circuit Class
1847 \begin_inset Formula $\Class{AC}^{0}$
1848 \end_inset
1849
1850
1851 \begin_inset ERT
1852 status Collapsed
1853
1854 \layout Standard
1855 }
1856 \end_inset
1857
1858
1859 \begin_deeper
1860 \layout Itemize
1861
1862
1863 \begin_inset Formula $O(1)$
1864 \end_inset
1865
1866  depth
1867 \layout Itemize
1868
1869 unbounded fan-in
1870 \end_deeper
1871 \layout Examples
1872
1873 \begin_deeper
1874 \layout Itemize
1875
1876
1877 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
1878 \end_inset
1879
1880 .
1881 \layout Itemize
1882
1883
1884 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
1885 \end_inset
1886
1887 .
1888 \end_deeper
1889 \layout Pause
1890
1891 \layout Column
1892
1893 3.6cm
1894 \layout Block
1895
1896
1897 \begin_inset ERT
1898 status Collapsed
1899
1900 \layout Standard
1901 {
1902 \end_inset
1903
1904 Circuit Class
1905 \begin_inset Formula $\Class{NC}^{1}$
1906 \end_inset
1907
1908
1909 \begin_inset ERT
1910 status Collapsed
1911
1912 \layout Standard
1913 }
1914 \end_inset
1915
1916
1917 \begin_deeper
1918 \layout Itemize
1919
1920
1921 \begin_inset Formula $O(\log n)$
1922 \end_inset
1923
1924  depth
1925 \layout Itemize
1926
1927 bounded fan-in
1928 \end_deeper
1929 \layout Examples
1930
1931 \begin_deeper
1932 \layout Itemize
1933
1934
1935 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
1936 \end_inset
1937
1938 .
1939 \layout Itemize
1940
1941
1942 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
1943 \end_inset
1944
1945 .
1946 \layout Itemize
1947
1948
1949 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
1950 \end_inset
1951
1952 .
1953 \end_deeper
1954 \layout Pause
1955
1956 \layout Column
1957
1958 3.6cm
1959 \layout Block
1960
1961
1962 \begin_inset ERT
1963 status Collapsed
1964
1965 \layout Standard
1966 {
1967 \end_inset
1968
1969 Circuit Class
1970 \begin_inset Formula $\Class{NC}^{2}$
1971 \end_inset
1972
1973
1974 \begin_inset ERT
1975 status Collapsed
1976
1977 \layout Standard
1978 }
1979 \end_inset
1980
1981
1982 \begin_deeper
1983 \layout Itemize
1984
1985
1986 \begin_inset Formula $O(\log^{2}n)$
1987 \end_inset
1988
1989  depth
1990 \layout Itemize
1991
1992 bounded fan-in
1993 \end_deeper
1994 \layout Examples
1995
1996 \begin_deeper
1997 \layout Itemize
1998
1999
2000 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
2001 \end_inset
2002
2003 .
2004 \end_deeper
2005 \end_deeper
2006 \layout AgainFrame
2007
2008
2009 \begin_inset ERT
2010 status Collapsed
2011
2012 \layout Standard
2013 <2>
2014 \end_inset
2015
2016 hierarchy
2017 \layout Subsection
2018
2019 Standard Complexity Results on Finding Paths
2020 \layout BeginFrame
2021
2022 All Variants of Finding Paths in Directed Graphs
2023 \newline
2024 Are Equally Difficult
2025 \layout Fact
2026
2027
2028 \begin_inset Formula $\Lang{reach}$
2029 \end_inset
2030
2031  and
2032 \begin_inset Formula $\Lang{distance}$
2033 \end_inset
2034
2035  are
2036 \begin_inset Formula $\Class{NL}$
2037 \end_inset
2038
2039 -complete.
2040
2041 \layout Pause
2042
2043 \layout Corollary
2044
2045 For directed graphs, we can solve
2046 \begin_deeper
2047 \layout Itemize
2048
2049 the reachability problem in logspace iff
2050 \begin_inset Formula $\Class{L}=\Class{NL}$
2051 \end_inset
2052
2053 .
2054 \layout Itemize
2055
2056 the construction problem in logspace iff
2057 \begin_inset Formula $\Class{L}=\Class{NL}$
2058 \end_inset
2059
2060 .
2061 \layout Itemize
2062
2063 the optimization problem in logspace iff
2064 \begin_inset Formula $\Class{L}=\Class{NL}$
2065 \end_inset
2066
2067 .
2068 \layout Itemize
2069
2070 the approximation problem in logspace iff
2071 \begin_inset Formula $\Class{L}=\Class{NL}$
2072 \end_inset
2073
2074 .
2075 \end_deeper
2076 \layout AgainFrame
2077
2078
2079 \begin_inset ERT
2080 status Collapsed
2081
2082 \layout Standard
2083 <3>
2084 \end_inset
2085
2086 hierarchy
2087 \layout BeginFrame
2088
2089 FindingPaths in Forests and Directed Paths is Easy,
2090 \newline
2091 But Not Trivial
2092 \layout Fact
2093
2094
2095 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
2096 \end_inset
2097
2098  and
2099 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
2100 \end_inset
2101
2102  are
2103 \begin_inset Formula $\Class{L}$
2104 \end_inset
2105
2106 -complete.
2107 \layout Separator
2108
2109 \layout Fact
2110
2111
2112 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
2113 \end_inset
2114
2115  and
2116 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
2117 \end_inset
2118
2119  are
2120 \begin_inset Formula $\Class{L}$
2121 \end_inset
2122
2123 -complete.
2124 \layout AgainFrame
2125
2126
2127 \begin_inset ERT
2128 status Collapsed
2129
2130 \layout Standard
2131 <4>
2132 \end_inset
2133
2134 hierarchy
2135 \layout Section
2136
2137 Finding Paths in Tournaments
2138 \layout Subsection
2139
2140 Complexity of: Does a Path Exist?
2141 \layout BeginFrame
2142
2143 Definition of the Tournament Reachability Problem
2144 \layout Definition
2145
2146 Let
2147 \color red
2148
2149 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
2150 \end_inset
2151
2152
2153 \color default
2154  contain all triples
2155 \begin_inset Formula $(T,s,t)$
2156 \end_inset
2157
2158  such that
2159 \begin_deeper
2160 \layout Enumerate
2161
2162
2163 \begin_inset Formula $T=(V,E)$
2164 \end_inset
2165
2166  is a tournament and
2167 \layout Enumerate
2168
2169 there exists a path from\SpecialChar ~
2170
2171 \begin_inset Formula $s$
2172 \end_inset
2173
2174  to\SpecialChar ~
2175
2176 \begin_inset Formula $t$
2177 \end_inset
2178
2179 .
2180 \end_deeper
2181 \layout BeginFrame
2182
2183 The Tournament Reachability Problem is Very Easy
2184 \layout Theorem
2185
2186
2187 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
2188 \end_inset
2189
2190 .
2191 \layout Pause
2192
2193 \layout AlertBlock
2194
2195
2196 \begin_inset ERT
2197 status Inlined
2198
2199 \layout Standard
2200 {Implications}
2201 \end_inset
2202
2203
2204 \begin_deeper
2205 \layout Itemize
2206
2207 The problem is
2208 \begin_inset Quotes eld
2209 \end_inset
2210
2211 easier
2212 \begin_inset Quotes erd
2213 \end_inset
2214
2215  than
2216 \begin_inset Formula $\Lang{reach}$
2217 \end_inset
2218
2219  and even
2220 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
2221 \end_inset
2222
2223 .
2224 \layout Itemize
2225
2226
2227 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
2228 \end_inset
2229
2230 .
2231 \end_deeper
2232 \layout AgainFrame
2233
2234
2235 \begin_inset ERT
2236 status Collapsed
2237
2238 \layout Standard
2239 <5>
2240 \end_inset
2241
2242 hierarchy
2243 \layout Subsection
2244
2245 Complexity of: Construct a Shortest Path
2246 \layout BeginFrame
2247
2248 Finding a Shortest Path Is as Difficult as
2249 \newline
2250 the Distance Problem
2251 \layout Definition
2252
2253 Let
2254 \color red
2255
2256 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
2257 \end_inset
2258
2259
2260 \color default
2261 contain all tuples
2262 \begin_inset Formula $(T,s,t,d)$
2263 \end_inset
2264
2265  such that
2266 \begin_deeper
2267 \layout Enumerate
2268
2269
2270 \begin_inset Formula $T=(V,E)$
2271 \end_inset
2272
2273  is a tournament in which
2274 \layout Enumerate
2275
2276 the distance of
2277 \begin_inset Formula $s$
2278 \end_inset
2279
2280  and\SpecialChar ~
2281
2282 \begin_inset Formula $t$
2283 \end_inset
2284
2285  is at most\SpecialChar ~
2286
2287 \begin_inset Formula $d$
2288 \end_inset
2289
2290 .
2291 \end_deeper
2292 \layout BeginFrame
2293
2294 The Tournament Distance Problem is Hard
2295 \layout Theorem
2296
2297
2298 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
2299 \end_inset
2300
2301  is
2302 \begin_inset Formula $\Class{NL}$
2303 \end_inset
2304
2305 -complete.
2306 \layout Standard
2307
2308
2309 \hfill
2310
2311 \begin_inset ERT
2312 status Inlined
2313
2314 \layout Standard
2315
2316 \backslash
2317 hyperlink{hierarchy<6>}{
2318 \backslash
2319 beamerskipbutton{Skip Proof}}
2320 \end_inset
2321
2322
2323 \layout Pause
2324
2325 \layout Corollary
2326
2327 Shortest path in tournaments can be constructed
2328 \newline
2329 in logarithmic space, iff
2330 \begin_inset Formula $\Class{L}=\Class{NL}$
2331 \end_inset
2332
2333 .
2334 \layout Pause
2335
2336 \layout Corollary
2337
2338
2339 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
2340 \end_inset
2341
2342 .
2343 \layout BeginFrame
2344
2345 Proof That
2346 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
2347 \end_inset
2348
2349  is NL-complete
2350 \layout Standard
2351
2352
2353 \begin_inset ERT
2354 status Collapsed
2355
2356 \layout Standard
2357
2358 \backslash
2359 nointerlineskip
2360 \end_inset
2361
2362
2363 \layout Columns
2364
2365
2366 \begin_inset ERT
2367 status Inlined
2368
2369 \layout Standard
2370 [t,onlytextwidth]
2371 \end_inset
2372
2373
2374 \begin_deeper
2375 \layout Column
2376
2377 5.7cm
2378 \layout Standard
2379
2380
2381 \begin_inset ERT
2382 status Inlined
2383
2384 \layout Standard
2385
2386 \backslash
2387 setlength
2388 \backslash
2389 leftmargini{1.5em}
2390 \end_inset
2391
2392
2393 \layout Block
2394
2395
2396 \begin_inset ERT
2397 status Collapsed
2398
2399 \layout Standard
2400 {
2401 \end_inset
2402
2403 Reduce
2404 \begin_inset Formula $\Lang{reach}$
2405 \end_inset
2406
2407  to
2408 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
2409 \end_inset
2410
2411
2412 \begin_inset ERT
2413 status Collapsed
2414
2415 \layout Standard
2416 }
2417 \end_inset
2418
2419
2420 \begin_deeper
2421 \layout Enumerate
2422
2423
2424 \begin_inset ERT
2425 status Inlined
2426
2427 \layout Standard
2428 <alert@1>
2429 \end_inset
2430
2431 Is input
2432 \begin_inset Formula $(G,s,t)$
2433 \end_inset
2434
2435  in
2436 \begin_inset Formula $\Lang{reach}$
2437 \end_inset
2438
2439 ?
2440 \layout Enumerate
2441
2442
2443 \begin_inset ERT
2444 status Inlined
2445
2446 \layout Standard
2447 <2-| alert@2-8>
2448 \end_inset
2449
2450 Map
2451 \begin_inset Formula $G$
2452 \end_inset
2453
2454  to
2455 \begin_inset Formula $G'$
2456 \end_inset
2457
2458 .
2459 \layout Enumerate
2460
2461
2462 \begin_inset ERT
2463 status Inlined
2464
2465 \layout Standard
2466 <9-| alert@9>
2467 \end_inset
2468
2469 Query:
2470 \newline
2471
2472 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
2473 \end_inset
2474
2475 ?
2476 \end_deeper
2477 \layout Separator
2478
2479 \layout Block
2480
2481
2482 \begin_inset ERT
2483 status Collapsed
2484
2485 \layout Standard
2486 {
2487 \end_inset
2488
2489 Correctness
2490 \begin_inset ERT
2491 status Collapsed
2492
2493 \layout Standard
2494 }
2495 \end_inset
2496
2497
2498 \begin_inset ERT
2499 status Collapsed
2500
2501 \layout Standard
2502 <10->
2503 \end_inset
2504
2505
2506 \begin_deeper
2507 \layout Enumerate
2508
2509
2510 \begin_inset ERT
2511 status Inlined
2512
2513 \layout Standard
2514 <10-| alert@10-11>
2515 \end_inset
2516
2517 A path in\SpecialChar ~
2518
2519 \begin_inset Formula $G$
2520 \end_inset
2521
2522  induces
2523 \newline
2524 a length-3 path in\SpecialChar ~
2525
2526 \begin_inset Formula $G'$
2527 \end_inset
2528
2529 .
2530 \layout Enumerate
2531
2532
2533 \begin_inset ERT
2534 status Inlined
2535
2536 \layout Standard
2537 <12-| alert@12-13>
2538 \end_inset
2539
2540 A length-3 path in\SpecialChar ~
2541
2542 \begin_inset Formula $G'$
2543 \end_inset
2544
2545  induces
2546 \newline
2547 a path in\SpecialChar ~
2548
2549 \begin_inset Formula $G'$
2550 \end_inset
2551
2552 .
2553 \end_deeper
2554 \layout Column
2555
2556 4.5cm
2557 \layout Example
2558
2559
2560 \begin_inset ERT
2561 status Inlined
2562
2563 \layout Standard
2564
2565 \backslash
2566 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
2567 \layout Standard
2568
2569 \backslash
2570 color{beamerexample}
2571 \layout Standard
2572
2573 \backslash
2574 pgfsetlinewidth{0.6pt}
2575 \layout Standard
2576
2577 \backslash
2578 graphnode{A}{
2579 \backslash
2580 pgfxy(1,3.3)}
2581 \layout Standard
2582
2583 \backslash
2584 graphnode{B}{
2585 \backslash
2586 pgfxy(2,3.3)}
2587 \layout Standard
2588
2589 \backslash
2590 graphnode{C}{
2591 \backslash
2592 pgfxy(3,3.3)}
2593 \layout Standard
2594
2595 \backslash
2596 graphnode{D}{
2597 \backslash
2598 pgfxy(4,3.3)}
2599 \layout Standard
2600
2601 \layout Standard
2602
2603 \backslash
2604 color{white}
2605 \layout Standard
2606
2607 \backslash
2608 pgfputat{
2609 \backslash
2610 pgfnodecenter{A}}{
2611 \backslash
2612 pgfbox[center,center]{$s$}}
2613 \layout Standard
2614
2615 \backslash
2616 pgfputat{
2617 \backslash
2618 pgfnodecenter{D}}{
2619 \backslash
2620 pgfbox[center,center]{$t$}}
2621 \layout Standard
2622
2623 \layout Standard
2624
2625 \backslash
2626 color{beamerexample}
2627 \layout Standard
2628
2629 \backslash
2630 pgfsetendarrow{
2631 \backslash
2632 pgfarrowto}
2633 \layout Standard
2634
2635 \backslash
2636 pgfnodesetsepstart{2pt}
2637 \layout Standard
2638
2639 \backslash
2640 pgfnodesetsepend{2pt}
2641 \layout Standard
2642
2643 \backslash
2644 alert<3>{
2645 \backslash
2646 pgfnodeconnline{B}{A}}
2647 \layout Standard
2648
2649 \backslash
2650 alert<4>{
2651 \backslash
2652 pgfnodeconnline{B}{C}}
2653 \layout Standard
2654
2655 \backslash
2656 alert<5,10-11,13>{
2657 \backslash
2658 pgfnodeconnline{C}{D}}
2659 \layout Standard
2660
2661 \backslash
2662 alert<6,10-11,13>{
2663 \backslash
2664 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
2665 \layout Standard
2666
2667 \layout Standard
2668
2669 \backslash
2670 pgfputat{
2671 \backslash
2672 pgfxy(0,3.3)}{
2673 \backslash
2674 pgfbox[left,center]{$G
2675 \backslash
2676 colon$}}
2677 \layout Standard
2678
2679 \layout Standard
2680
2681 \backslash
2682 only<2->{
2683 \layout Standard
2684
2685 \backslash
2686 pgfputat{
2687 \backslash
2688 pgfxy(0,2.25)}{
2689 \backslash
2690 pgfbox[left,center]{$G'
2691 \backslash
2692 colon$}}
2693 \layout Standard
2694
2695 \backslash
2696 graphnode{A1}{
2697 \backslash
2698 pgfxy(1,2.25)}
2699 \layout Standard
2700
2701 \backslash
2702 graphnode{B1}{
2703 \backslash
2704 pgfxy(2,2.25)}
2705 \layout Standard
2706
2707 \backslash
2708 graphnode{C1}{
2709 \backslash
2710 pgfxy(3,2.25)}
2711 \layout Standard
2712
2713 \backslash
2714 graphnode{D1}{
2715 \backslash
2716 pgfxy(4,2.25)}
2717 \layout Standard
2718
2719 \layout Standard
2720
2721 \backslash
2722 graphnode{A2}{
2723 \backslash
2724 pgfxy(1,1.25)}
2725 \layout Standard
2726
2727 \backslash
2728 graphnode{B2}{
2729 \backslash
2730 pgfxy(2,1.25)}
2731 \layout Standard
2732
2733 \backslash
2734 graphnode{C2}{
2735 \backslash
2736 pgfxy(3,1.25)}
2737 \layout Standard
2738
2739 \backslash
2740 graphnode{D2}{
2741 \backslash
2742 pgfxy(4,1.25)}
2743 \layout Standard
2744
2745 \backslash
2746 graphnode{A3}{
2747 \backslash
2748 pgfxy(1,0.25)}
2749 \layout Standard
2750
2751 \backslash
2752 graphnode{B3}{
2753 \backslash
2754 pgfxy(2,0.25)}
2755 \layout Standard
2756
2757 \backslash
2758 graphnode{C3}{
2759 \backslash
2760 pgfxy(3,0.25)}
2761 \layout Standard
2762
2763 \backslash
2764 graphnode{D3}{
2765 \backslash
2766 pgfxy(4,0.25)}
2767 \layout Standard
2768
2769 \backslash
2770 graphnode{A4}{
2771 \backslash
2772 pgfxy(1,-.75)}
2773 \layout Standard
2774
2775 \backslash
2776 graphnode{B4}{
2777 \backslash
2778 pgfxy(2,-.75)}
2779 \layout Standard
2780
2781 \backslash
2782 graphnode{C4}{
2783 \backslash
2784 pgfxy(3,-.75)}
2785 \layout Standard
2786
2787 \backslash
2788 graphnode{D4}{
2789 \backslash
2790 pgfxy(4,-.75)}
2791 \layout Standard
2792      {
2793 \backslash
2794 color{white}
2795 \layout Standard
2796
2797 \backslash
2798 pgfputat{
2799 \backslash
2800 pgfnodecenter{A1}}{
2801 \backslash
2802 pgfbox[center,center]{$s'$}}
2803 \layout Standard
2804
2805 \backslash
2806 pgfputat{
2807 \backslash
2808 pgfnodecenter{D4}}{
2809 \backslash
2810 pgfbox[center,center]{$t'$}}
2811 \layout Standard
2812   }}
2813 \layout Standard
2814
2815 \layout Standard
2816
2817 \backslash
2818 only<8->{
2819 \layout Standard
2820
2821 \backslash
2822 pgfsetlinewidth{0.4pt}
2823 \layout Standard
2824
2825 \backslash
2826 color{beamerexample!25!averagebackgroundcolor}
2827 \layout Standard
2828
2829 \backslash
2830 pgfnodeconnline{A2}{C1}
2831 \layout Standard
2832
2833 \backslash
2834 pgfnodeconnline{A2}{D1}
2835 \layout Standard
2836
2837 \backslash
2838 pgfnodeconnline{B2}{A1}
2839 \layout Standard
2840
2841 \backslash
2842 pgfnodeconnline{B2}{C1}
2843 \layout Standard
2844
2845 \backslash
2846 pgfnodeconnline{B2}{D1}
2847 \layout Standard
2848
2849 \backslash
2850 pgfnodeconnline{C2}{D1}
2851 \layout Standard
2852
2853 \backslash
2854 pgfnodeconnline{D2}{A1}
2855 \layout Standard
2856
2857 \backslash
2858 pgfnodeconnline{D2}{B1}
2859 \layout Standard
2860
2861 \backslash
2862 pgfnodeconnline{A3}{C2}
2863 \layout Standard
2864
2865 \backslash
2866 pgfnodeconnline{A3}{D2}
2867 \layout Standard
2868
2869 \backslash
2870 pgfnodeconnline{B3}{A2}
2871 \layout Standard
2872
2873 \backslash
2874 pgfnodeconnline{B3}{C2}
2875 \layout Standard
2876
2877 \backslash
2878 pgfnodeconnline{B3}{D2}
2879 \layout Standard
2880
2881 \backslash
2882 pgfnodeconnline{C3}{D2}
2883 \layout Standard
2884
2885 \backslash
2886 pgfnodeconnline{D3}{A2}
2887 \layout Standard
2888
2889 \backslash
2890 pgfnodeconnline{D3}{B2}
2891 \layout Standard
2892
2893 \backslash
2894 pgfnodeconnline{A4}{C3}
2895 \layout Standard
2896
2897 \backslash
2898 pgfnodeconnline{A4}{D3}
2899 \layout Standard
2900
2901 \backslash
2902 pgfnodeconnline{B4}{A3}
2903 \layout Standard
2904
2905 \backslash
2906 pgfnodeconnline{B4}{C3}
2907 \layout Standard
2908
2909 \backslash
2910 pgfnodeconnline{B4}{D3}
2911 \layout Standard
2912
2913 \backslash
2914 pgfnodeconnline{C4}{D3}
2915 \layout Standard
2916
2917 \backslash
2918 pgfnodeconnline{D4}{A3}
2919 \layout Standard
2920
2921 \backslash
2922 pgfnodeconnline{D4}{B3}
2923 \layout Standard
2924
2925 \layout Standard
2926
2927 \backslash
2928 pgfsetstartarrow{
2929 \backslash
2930 pgfarrowto}
2931 \layout Standard
2932
2933 \backslash
2934 pgfnodeconnline{A1}{B1}
2935 \layout Standard
2936
2937 \backslash
2938 pgfnodeconnline{B1}{C1}
2939 \layout Standard
2940
2941 \backslash
2942 pgfnodeconnline{C1}{D1}
2943 \layout Standard
2944
2945 \backslash
2946 pgfnodeconnline{A2}{B2}
2947 \layout Standard
2948
2949 \backslash
2950 pgfnodeconnline{B2}{C2}
2951 \layout Standard
2952
2953 \backslash
2954 pgfnodeconnline{C2}{D2}
2955 \layout Standard
2956
2957 \backslash
2958 pgfnodeconnline{A3}{B3}
2959 \layout Standard
2960
2961 \backslash
2962 pgfnodeconnline{B3}{C3}
2963 \layout Standard
2964
2965 \backslash
2966 pgfnodeconnline{C3}{D3}
2967 \layout Standard
2968
2969 \backslash
2970 pgfnodeconnline{A4}{B4}
2971 \layout Standard
2972
2973 \backslash
2974 pgfnodeconnline{B4}{C4}
2975 \layout Standard
2976
2977 \backslash
2978 pgfnodeconnline{C4}{D4}
2979 \layout Standard
2980
2981 \layout Standard
2982
2983 \backslash
2984 pgfclearstartarrow
2985 \layout Standard
2986
2987 \backslash
2988 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
2989 \layout Standard
2990
2991 \backslash
2992 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
2993 \layout Standard
2994
2995 \backslash
2996 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
2997 \layout Standard
2998
2999 \backslash
3000 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
3001 \layout Standard
3002
3003 \backslash
3004 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
3005 \layout Standard
3006
3007 \backslash
3008 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
3009 \layout Standard
3010
3011 \backslash
3012 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
3013 \layout Standard
3014
3015 \backslash
3016 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
3017 \layout Standard
3018
3019 \backslash
3020 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
3021 \layout Standard
3022
3023 \backslash
3024 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
3025 \layout Standard
3026
3027 \backslash
3028 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
3029 \layout Standard
3030
3031 \backslash
3032 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
3033 \layout Standard
3034
3035 \backslash
3036 color{beamerexample}
3037 \layout Standard
3038
3039 \backslash
3040 pgfsetlinewidth{0.6pt}
3041 \layout Standard
3042   }
3043 \layout Standard
3044
3045 \layout Standard
3046
3047 \backslash
3048 only<3->{
3049 \layout Standard
3050
3051 \backslash
3052 color<3>{red}
3053 \layout Standard
3054
3055 \backslash
3056 pgfnodeconnline{B1}{A2}
3057 \layout Standard
3058
3059 \backslash
3060 pgfnodeconnline{B2}{A3}
3061 \layout Standard
3062
3063 \backslash
3064 pgfnodeconnline{B3}{A4}
3065 \layout Standard
3066   }
3067 \layout Standard
3068
3069 \layout Standard
3070
3071 \backslash
3072 only<4->{
3073 \layout Standard
3074
3075 \backslash
3076 color<4>{red}
3077 \layout Standard
3078
3079 \backslash
3080 pgfnodeconnline{B1}{C2}
3081 \layout Standard
3082
3083 \backslash
3084 pgfnodeconnline{B2}{C3}
3085 \layout Standard
3086
3087 \backslash
3088 pgfnodeconnline{B3}{C4}
3089 \layout Standard
3090   }
3091 \layout Standard
3092
3093 \layout Standard
3094
3095 \backslash
3096 only<5->{
3097 \layout Standard
3098
3099 \backslash
3100 color<5>{red}
3101 \layout Standard
3102
3103 \backslash
3104 pgfnodeconnline{C1}{D2}
3105 \layout Standard
3106
3107 \backslash
3108 alert<11>{
3109 \backslash
3110 pgfnodeconnline{C2}{D3}}
3111 \layout Standard
3112
3113 \backslash
3114 alert<12-13>{
3115 \backslash
3116 pgfnodeconnline{C3}{D4}}
3117 \layout Standard
3118   }
3119 \layout Standard
3120
3121 \layout Standard
3122
3123 \backslash
3124 only<6->{
3125 \layout Standard
3126
3127 \backslash
3128 color<6>{red}
3129 \layout Standard
3130
3131 \backslash
3132 alert<11>{
3133 \backslash
3134 pgfnodeconnline{A1}{C2}}
3135 \layout Standard
3136
3137 \backslash
3138 alert<12-13>{
3139 \backslash
3140 pgfnodeconnline{A2}{C3}}
3141 \layout Standard
3142
3143 \backslash
3144 pgfnodeconnline{A3}{C4}
3145 \layout Standard
3146   }
3147 \layout Standard
3148
3149 \layout Standard
3150
3151 \backslash
3152 only<7->{
3153 \layout Standard
3154
3155 \backslash
3156 color<7>{red}
3157 \layout Standard
3158
3159 \backslash
3160 alert<12-13>{
3161 \backslash
3162 pgfnodeconnline{A1}{A2}}
3163 \layout Standard
3164
3165 \backslash
3166 pgfnodeconnline{A2}{A3}
3167 \layout Standard
3168
3169 \backslash
3170 pgfnodeconnline{A3}{A4}
3171 \layout Standard
3172
3173 \backslash
3174 pgfnodeconnline{B1}{B2}
3175 \layout Standard
3176
3177 \backslash
3178 pgfnodeconnline{B2}{B3}
3179 \layout Standard
3180
3181 \backslash
3182 pgfnodeconnline{B3}{B4}
3183 \layout Standard
3184
3185 \backslash
3186 pgfnodeconnline{C1}{C2}
3187 \layout Standard
3188
3189 \backslash
3190 pgfnodeconnline{C2}{C3}
3191 \layout Standard
3192
3193 \backslash
3194 pgfnodeconnline{C3}{C4}
3195 \layout Standard
3196
3197 \backslash
3198 pgfnodeconnline{D1}{D2}
3199 \layout Standard
3200
3201 \backslash
3202 pgfnodeconnline{D2}{D3}
3203 \layout Standard
3204
3205 \backslash
3206 alert<11>{
3207 \backslash
3208 pgfnodeconnline{D3}{D4}}
3209 \layout Standard
3210   }
3211 \layout Standard
3212
3213 \backslash
3214 end{pgfpicture}
3215 \end_inset
3216
3217
3218 \end_deeper
3219 \layout AgainFrame
3220
3221
3222 \begin_inset ERT
3223 status Collapsed
3224
3225 \layout Standard
3226 <6>
3227 \end_inset
3228
3229 hierarchy
3230 \layout Subsection
3231
3232 Complexity of: Approximating the Shortest Path
3233 \layout BeginFrame
3234
3235 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
3236 \layout Definition
3237
3238 An
3239 \color red
3240 approximation scheme for
3241 \begin_inset Formula $\Lang{tournament-shortest-path}$
3242 \end_inset
3243
3244
3245 \color default
3246  gets as input
3247 \begin_deeper
3248 \layout Enumerate
3249
3250 a tuple
3251 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
3252 \end_inset
3253
3254  and
3255 \layout Enumerate
3256
3257 a number
3258 \begin_inset Formula $r>1$
3259 \end_inset
3260
3261 .
3262 \layout Standard
3263
3264 It outputs
3265 \layout Itemize
3266
3267 a path from
3268 \begin_inset Formula $s$
3269 \end_inset
3270
3271  to\SpecialChar ~
3272
3273 \begin_inset Formula $t$
3274 \end_inset
3275
3276  of length at most
3277 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
3278 \end_inset
3279
3280 .
3281 \end_deeper
3282 \layout BeginFrame
3283
3284 There Exists a Logspace Approximation Scheme for
3285 \newline
3286 the Tournament Shortest Path Problem
3287 \layout Theorem
3288
3289 There exists an approximation scheme for
3290 \begin_inset Formula $\Lang{tournament-shortest-path}$
3291 \end_inset
3292
3293  that for
3294 \begin_inset Formula $1<r<2$
3295 \end_inset
3296
3297  needs space
3298 \begin_inset Formula \[
3299 O\left(\log|V|\log\frac{1}{r-1}\right).\]
3300
3301 \end_inset
3302
3303
3304 \layout Pause
3305
3306 \layout Corollary
3307
3308 In tournaments, paths can be constructed in logarithmic space.
3309 \layout Standard
3310
3311
3312 \hfill
3313
3314 \begin_inset ERT
3315 status Inlined
3316
3317 \layout Standard
3318
3319 \backslash
3320 hyperlink{optimality}{
3321 \backslash
3322 beamergotobutton{More Details}}
3323 \end_inset
3324
3325
3326 \layout AgainFrame
3327
3328
3329 \begin_inset ERT
3330 status Collapsed
3331
3332 \layout Standard
3333 <7>
3334 \end_inset
3335
3336 hierarchy
3337 \layout Section*
3338
3339 Summary
3340 \layout Subsection*
3341
3342 Summary
3343 \layout BeginFrame
3344
3345 Summary
3346 \layout Block
3347
3348
3349 \begin_inset ERT
3350 status Inlined
3351
3352 \layout Standard
3353 {Summary}
3354 \end_inset
3355
3356
3357 \begin_deeper
3358 \layout Itemize
3359
3360 Tournament
3361 \color red
3362 reachability
3363 \color default
3364  is in
3365 \color red
3366
3367 \begin_inset Formula $\Class{AC}^{0}$
3368 \end_inset
3369
3370
3371 \color default
3372 .
3373
3374 \layout Itemize
3375
3376 There exists a
3377 \color red
3378 logspace approximation scheme
3379 \color default
3380  for
3381 \color red
3382 approximating
3383 \color default
3384  shortest paths in tournaments.
3385 \layout Itemize
3386
3387 Finding
3388 \color red
3389 shortest paths
3390 \color default
3391  in tournaments is
3392 \color red
3393
3394 \begin_inset Formula $\Class{NL}$
3395 \end_inset
3396
3397 -complete
3398 \color default
3399 .
3400 \end_deeper
3401 \layout Separator
3402
3403 \layout Block
3404
3405
3406 \begin_inset ERT
3407 status Inlined
3408
3409 \layout Standard
3410 {Outlook}
3411 \end_inset
3412
3413
3414 \begin_deeper
3415 \layout Itemize
3416
3417 The same results apply to graphs with
3418 \newline
3419 bounded independence number.
3420 \hfill
3421
3422 \begin_inset ERT
3423 status Inlined
3424
3425 \layout Standard
3426
3427 \backslash
3428 hyperlink{independence}{
3429 \backslash
3430 beamergotobutton{More Details}}
3431 \end_inset
3432
3433
3434 \layout Itemize
3435
3436 The complexity of finding paths in undirected graphs
3437 \newline
3438 is partly open.
3439 \hfill
3440
3441 \begin_inset ERT
3442 status Inlined
3443
3444 \layout Standard
3445
3446 \backslash
3447 hyperlink{undirected}{
3448 \backslash
3449 beamergotobutton{More Details}}
3450 \end_inset
3451
3452
3453 \end_deeper
3454 \layout Subsection*
3455
3456 For Further Reading
3457 \layout BeginFrame
3458
3459 For Further Reading
3460 \layout Standard
3461
3462
3463 \begin_inset ERT
3464 status Inlined
3465
3466 \layout Standard
3467
3468 \backslash
3469 beamertemplatebookbibitems
3470 \end_inset
3471
3472
3473 \layout Bibliography
3474 \bibitem {Moon1968}
3475
3476 \SpecialChar ~
3477 John Moon.
3478
3479 \begin_inset ERT
3480 status Collapsed
3481
3482 \layout Standard
3483
3484 \backslash
3485 newblock
3486 \end_inset
3487
3488
3489 \emph on
3490 Topics on Tournaments.
3491
3492 \emph default
3493
3494 \begin_inset ERT
3495 status Collapsed
3496
3497 \layout Standard
3498
3499 \backslash
3500 newblock
3501 \end_inset
3502
3503  Holt, Rinehart, and Winston, 1968.
3504
3505 \begin_inset ERT
3506 status Inlined
3507
3508 \layout Standard
3509
3510 \backslash
3511 beamertemplatearticlebibitems
3512 \end_inset
3513
3514
3515 \layout Bibliography
3516 \bibitem {NickelsenT2002}
3517
3518 \SpecialChar ~
3519 Arfst Nickelsen and Till Tantau.
3520
3521 \begin_inset ERT
3522 status Collapsed
3523
3524 \layout Standard
3525
3526 \backslash
3527 newblock
3528 \end_inset
3529
3530  On reachability in graphs with bounded independence number.
3531 \begin_inset ERT
3532 status Collapsed
3533
3534 \layout Standard
3535
3536 \backslash
3537 newblock
3538 \end_inset
3539
3540  In
3541 \emph on
3542 Proc.
3543  of COCOON 2002
3544 \emph default
3545 , Springer-Verlag, 2002.
3546 \layout Bibliography
3547 \bibitem {Tantau2004b}
3548
3549 \SpecialChar ~
3550 Till Tantau
3551 \begin_inset ERT
3552 status Collapsed
3553
3554 \layout Standard
3555
3556 \backslash
3557 newblock
3558 \end_inset
3559
3560  A logspace approximation scheme for the shortest path problem for graphs
3561  with bounded independence number.
3562 \begin_inset ERT
3563 status Collapsed
3564
3565 \layout Standard
3566
3567 \backslash
3568 newblock
3569 \end_inset
3570
3571  In
3572 \emph on
3573 Proc.
3574  of STACS 2004
3575 \emph default
3576 , Springer-Verlag, 2004.
3577
3578 \begin_inset ERT
3579 status Collapsed
3580
3581 \layout Standard
3582
3583 \backslash
3584 newblock
3585 \end_inset
3586
3587  In press.
3588 \layout EndFrame
3589
3590 \layout Standard
3591 \start_of_appendix
3592
3593 \begin_inset ERT
3594 status Inlined
3595
3596 \layout Standard
3597
3598 \backslash
3599 AtBeginSubsection[]{}
3600 \end_inset
3601
3602
3603 \layout Section
3604
3605 Appendix
3606 \layout Subsection
3607
3608 Graphs With Bounded Independence Number
3609 \layout BeginFrame
3610
3611
3612 \begin_inset ERT
3613 status Inlined
3614
3615 \layout Standard
3616 [label=independence]
3617 \end_inset
3618
3619 Definition of Independence Number of a Graph
3620 \layout Definition
3621
3622 The
3623 \color red
3624 independence number
3625 \color default
3626
3627 \begin_inset Formula $\alpha(G)$
3628 \end_inset
3629
3630  of a directed graph
3631 \newline
3632 is the maximum number of vertices we can pick,
3633 \newline
3634 such that there is no edge between them.
3635 \layout Example
3636
3637 Tournaments have independence number 1.
3638
3639 \layout BeginFrame
3640
3641 The Results for Tournaments also Apply to
3642 \newline
3643 Graphs With Bounded Independence Number
3644 \layout Theorem
3645
3646 For each\SpecialChar ~
3647
3648 \begin_inset Formula $k$
3649 \end_inset
3650
3651 ,
3652 \color red
3653 reachability
3654 \color default
3655  in graphs with independence number
3656 \newline
3657 at most\SpecialChar ~
3658
3659 \begin_inset Formula $k$
3660 \end_inset
3661
3662  is in
3663 \begin_inset Formula $\Class{AC}^{0}$
3664 \end_inset
3665
3666 .
3667 \layout Separator
3668
3669 \layout Theorem
3670
3671 For each\SpecialChar ~
3672
3673 \begin_inset Formula $k$
3674 \end_inset
3675
3676 , there exists a
3677 \color red
3678 logspace approximation scheme
3679 \color default
3680  for approximating the shortest path in graphs with independence number
3681  at most\SpecialChar ~
3682
3683 \begin_inset Formula $k$
3684 \end_inset
3685
3686
3687 \layout Separator
3688
3689 \layout Theorem
3690
3691 For each\SpecialChar ~
3692
3693 \begin_inset Formula $k$
3694 \end_inset
3695
3696 , finding the
3697 \color red
3698 shortest path
3699 \color default
3700  in graphs with independence number at most\SpecialChar ~
3701
3702 \begin_inset Formula $k$
3703 \end_inset
3704
3705  is
3706 \color red
3707
3708 \begin_inset Formula $\Class{NL}$
3709 \end_inset
3710
3711 -complete
3712 \color default
3713 .
3714 \layout Subsection
3715
3716 Finding Paths in Undirected Graphs
3717 \layout BeginFrame
3718
3719
3720 \begin_inset ERT
3721 status Inlined
3722
3723 \layout Standard
3724 <1-2>[label=undirected]
3725 \end_inset
3726
3727 The Complexity of Finding Paths in Undirected Graphs
3728 \newline
3729 Is Party Unknown.
3730 \layout Fact
3731
3732
3733 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
3734 \end_inset
3735
3736  is
3737 \begin_inset Formula $\Class{SL}$
3738 \end_inset
3739
3740 -complete.
3741 \layout Corollary
3742
3743 For undirected graphs, we can solve
3744 \begin_deeper
3745 \layout Itemize
3746
3747 the reachability problem in logspace iff
3748 \begin_inset Formula $\Class L=\Class{SL}$
3749 \end_inset
3750
3751 ,
3752 \layout Itemize
3753
3754 the construction problem in logspace iff
3755 \begin_inset ERT
3756 status Inlined
3757
3758 \layout Standard
3759
3760 \backslash
3761 alt<1>{?}{
3762 \backslash
3763 alert{$
3764 \backslash
3765 Class L =
3766 \backslash
3767 Class{SL}$}}
3768 \end_inset
3769
3770 ,
3771 \layout Itemize
3772
3773 the optimization problem in logspace iff
3774 \begin_inset ERT
3775 status Inlined
3776
3777 \layout Standard
3778
3779 \backslash
3780 alt<1>{?}{
3781 \backslash
3782 alert{$
3783 \backslash
3784 Class L =
3785 \backslash
3786 Class{NL}$}}
3787 \end_inset
3788
3789 ,
3790 \layout Itemize
3791
3792 the approximation problem in logspace iff ?.
3793
3794 \end_deeper
3795 \layout Subsection
3796
3797 The Approximation Scheme is Optimal
3798 \layout BeginFrame
3799
3800
3801 \begin_inset ERT
3802 status Inlined
3803
3804 \layout Standard
3805 [label=optimality]
3806 \end_inset
3807
3808 The Approximation Scheme is Optimal
3809 \layout Theorem
3810
3811 Suppose there exists an approximation scheme for
3812 \begin_inset Formula $\Lang{tournament-shortest-path}$
3813 \end_inset
3814
3815  that needs space
3816 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
3817 \end_inset
3818
3819 .
3820  Then
3821 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
3822 \end_inset
3823
3824 .
3825 \layout Proof
3826
3827 \begin_deeper
3828 \layout Enumerate
3829
3830 Suppose the approximation scheme exists.
3831 \newline
3832 We show
3833 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
3834 \end_inset
3835
3836 .
3837
3838 \layout Enumerate
3839
3840 Let
3841 \begin_inset Formula $(T,s,t)$
3842 \end_inset
3843
3844  be an input.
3845  Let
3846 \begin_inset Formula $n$
3847 \end_inset
3848
3849  be the number of vertices.
3850 \layout Enumerate
3851
3852 Run the approximation scheme for
3853 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
3854 \end_inset
3855
3856 .
3857 \newline
3858 This needs space
3859 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
3860 \end_inset
3861
3862 .
3863 \layout Enumerate
3864
3865 The resulting path has optimal length.
3866
3867 \begin_inset ERT
3868 status Collapsed
3869
3870 \layout Standard
3871
3872 \backslash
3873 qedhere
3874 \end_inset
3875
3876
3877 \end_deeper
3878 \layout EndFrame
3879
3880 \the_end