lib/examples/beamerlyxexample1.lyx

   1 #LyX 1.6.5svn created this file. For more info see http://www.lyx.org/
   2 \lyxformat 345
   3 \begin_document
   4 \begin_header
   5 \textclass beamer
   6 \begin_preamble
   7 \beamertemplateshadingbackground{red!5}{structure!5}
   8
   9 \usepackage{beamerthemeshadow}
  10 \usepackage{pgfnodes,pgfarrows,pgfheaps}
  11
  12 \beamertemplatetransparentcovereddynamicmedium
  13
  14
  15 \pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
  16 \logo{\pgfuseimage{icsi-logo}}
  17
  18
  19
  20
  21 \newcommand{\Class}[1]{\operatorname{\mathchoice
  22   {\text{\small #1}}
  23   {\text{\small #1}}
  24   {\text{#1}}
  25   {\text{#1}}}}
  26
  27 \newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
  28
  29 % This gets defined by beamerbasecolor.sty, but only at the beginning of
  30 % the document
  31 \colorlet{averagebackgroundcolor}{normal text.bg}
  32
  33 \newcommand{\tape}[3]{%
  34   \color{structure!30!averagebackgroundcolor}
  35   \pgfmoveto{\pgfxy(-0.5,0)}
  36   \pgflineto{\pgfxy(-0.6,0.1)}
  37   \pgflineto{\pgfxy(-0.4,0.2)}
  38   \pgflineto{\pgfxy(-0.6,0.3)}
  39   \pgflineto{\pgfxy(-0.4,0.4)}
  40   \pgflineto{\pgfxy(-0.5,0.5)}
  41   \pgflineto{\pgfxy(4,0.5)}
  42   \pgflineto{\pgfxy(4.1,0.4)}
  43   \pgflineto{\pgfxy(3.9,0.3)}
  44   \pgflineto{\pgfxy(4.1,0.2)}
  45   \pgflineto{\pgfxy(3.9,0.1)}
  46   \pgflineto{\pgfxy(4,0)}
  47   \pgfclosepath
  48   \pgffill
  49
  50   \color{structure}
  51   \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
  52   \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
  53
  54   \color{black}
  55   \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
  56 }
  57
  58 \newcommand{\shorttape}[3]{%
  59   \color{structure!30!averagebackgroundcolor}
  60   \pgfmoveto{\pgfxy(-0.5,0)}
  61   \pgflineto{\pgfxy(-0.6,0.1)}
  62   \pgflineto{\pgfxy(-0.4,0.2)}
  63   \pgflineto{\pgfxy(-0.6,0.3)}
  64   \pgflineto{\pgfxy(-0.4,0.4)}
  65   \pgflineto{\pgfxy(-0.5,0.5)}
  66   \pgflineto{\pgfxy(1,0.5)}
  67   \pgflineto{\pgfxy(1.1,0.4)}
  68   \pgflineto{\pgfxy(0.9,0.3)}
  69   \pgflineto{\pgfxy(1.1,0.2)}
  70   \pgflineto{\pgfxy(0.9,0.1)}
  71   \pgflineto{\pgfxy(1,0)}
  72   \pgfclosepath
  73   \pgffill
  74
  75   \color{structure}
  76   \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
  77   \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
  78
  79   \color{black}
  80   \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
  81 }
  82
  83 \pgfdeclareverticalshading{heap1}{\the\paperwidth}%
  84   {color(0pt)=(black); color(1cm)=(structure!65!white)}
  85 \pgfdeclareverticalshading{heap2}{\the\paperwidth}%
  86   {color(0pt)=(black); color(1cm)=(structure!55!white)}
  87 \pgfdeclareverticalshading{heap3}{\the\paperwidth}%
  88   {color(0pt)=(black); color(1cm)=(structure!45!white)}
  89 \pgfdeclareverticalshading{heap4}{\the\paperwidth}%
  90   {color(0pt)=(black); color(1cm)=(structure!35!white)}
  91 \pgfdeclareverticalshading{heap5}{\the\paperwidth}%
  92   {color(0pt)=(black); color(1cm)=(structure!25!white)}
  93 \pgfdeclareverticalshading{heap6}{\the\paperwidth}%
  94   {color(0pt)=(black); color(1cm)=(red!35!white)}
  95
  96 \newcommand{\heap}[5]{%
  97   \begin{pgfscope}
  98     \color{#4}
  99     \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
 100     \pgfclip
 101     \begin{pgfmagnify}{1}{#1}
 102       \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
 103     \end{pgfmagnify}
 104   \end{pgfscope}
 105   %\pgffill
 106
 107   \color{#4}
 108   \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
 109   \pgfstroke
 110
 111   \color{white}
 112   \pgfheaplabel{\pgfxy(0,#1)}{#3}%
 113 }
 114
 115
 116 \newcommand{\langat}[2]{%
 117   \color{black!30!beamerexample}
 118   \pgfsetlinewidth{0.6pt}
 119   \pgfsetendarrow{\pgfarrowdot}
 120   \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
 121   \color{beamerexample}
 122   \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
 123 }
 124
 125 \newcommand{\langatother}[2]{%
 126   \color{black!30!beamerexample}
 127   \pgfsetlinewidth{0.6pt}
 128   \pgfsetendarrow{\pgfarrowdot}
 129   \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
 130   \color{beamerexample}
 131   \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
 132 }
 133
 134
 135 \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}
 136
 137
 138 \pgfdeclareradialshading{graphnode}
 139   {\pgfpoint{-3pt}{3.6pt}}%
 140   {color(0cm)=(beamerexample!15);
 141     color(2.63pt)=(beamerexample!75);
 142     color(5.26pt)=(beamerexample!70!black);
 143     color(7.6pt)=(beamerexample!50!black);
 144     color(8pt)=(beamerexample!10!averagebackgroundcolor)}
 145
 146 \newcommand{\graphnode}[2]{
 147   \pgfnodecircle{#1}[virtual]{#2}{8pt}
 148   \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
 149 }
 150 \end_preamble
 151 \options notes=show
 152 \use_default_options false
 153 \language english
 154 \inputencoding auto
 155 \font_roman times
 156 \font_sans default
 157 \font_typewriter default
 158 \font_default_family default
 159 \font_sc false
 160 \font_osf false
 161 \font_sf_scale 100
 162 \font_tt_scale 100
 163
 164 \graphics default
 165 \paperfontsize default
 166 \spacing single
 167 \use_hyperref false
 168 \papersize default
 169 \use_geometry false
 170 \use_amsmath 2
 171 \use_esint 0
 172 \cite_engine basic
 173 \use_bibtopic false
 174 \paperorientation portrait
 175 \secnumdepth 2
 176 \tocdepth 2
 177 \paragraph_separation indent
 178 \defskip medskip
 179 \quotes_language english
 180 \papercolumns 1
 181 \papersides 1
 182 \paperpagestyle default
 183 \tracking_changes false
 184 \output_changes false
 185 \author ""
 186 \author ""
 187 \end_header
 188
 189 \begin_body
 190
 191 \begin_layout Title
 192 The Complexity of
 193 \begin_inset Newline newline
 194 \end_inset
 195
 196 Finding Paths in Tournaments
 197 \end_layout
 198
 199 \begin_layout Author
 200 Till Tantau
 201 \end_layout
 202
 203 \begin_layout Institute
 204 International Computer Schience Institute
 205 \begin_inset Newline newline
 206 \end_inset
 207
 208 Berkeley, California
 209 \begin_inset OptArg
 210 status collapsed
 211
 212 \begin_layout Plain Layout
 213 ICSI
 214 \end_layout
 215
 216 \end_inset
 217
 218
 219 \end_layout
 220
 221 \begin_layout Date
 222 January 30th, 2004
 223 \end_layout
 224
 225 \begin_layout BeginFrame
 226 Outline
 227 \end_layout
 228
 229 \begin_layout Standard
 230 \begin_inset CommandInset toc
 231 LatexCommand tableofcontents
 232
 233 \end_inset
 234
 235
 236 \begin_inset ERT
 237 status collapsed
 238
 239 \begin_layout Plain Layout
 240
 241 [pausesections]
 242 \end_layout
 243
 244 \end_inset
 245
 246
 247 \end_layout
 248
 249 \begin_layout EndFrame
 250
 251 \end_layout
 252
 253 \begin_layout Standard
 254 \begin_inset ERT
 255 status collapsed
 256
 257 \begin_layout Plain Layout
 258
 259 % Show the table of contents at the beginning
 260 \end_layout
 261
 262 \begin_layout Plain Layout
 263
 264 \end_layout
 265
 266 \begin_layout Plain Layout
 267
 268 % of every subsection.
 269 \end_layout
 270
 271 \begin_layout Plain Layout
 272
 273 \end_layout
 274
 275 \begin_layout Plain Layout
 276
 277
 278 \backslash
 279 AtBeginSubsection[]{
 280 \end_layout
 281
 282 \begin_layout Plain Layout
 283
 284 \end_layout
 285
 286 \begin_layout Plain Layout
 287
 288
 289 \backslash
 290 frame<handout:0>{
 291 \end_layout
 292
 293 \begin_layout Plain Layout
 294
 295 \end_layout
 296
 297 \begin_layout Plain Layout
 298
 299
 300 \backslash
 301 frametitle{Outline}
 302 \end_layout
 303
 304 \begin_layout Plain Layout
 305
 306 \end_layout
 307
 308 \begin_layout Plain Layout
 309
 310
 311 \backslash
 312 tableofcontents[current,currentsubsection]
 313 \end_layout
 314
 315 \begin_layout Plain Layout
 316
 317 \end_layout
 318
 319 \begin_layout Plain Layout
 320
 321   }
 322 \end_layout
 323
 324 \begin_layout Plain Layout
 325
 326 \end_layout
 327
 328 \begin_layout Plain Layout
 329
 330 }
 331 \end_layout
 332
 333 \end_inset
 334
 335
 336 \end_layout
 337
 338 \begin_layout Section
 339 Introduction
 340 \end_layout
 341
 342 \begin_layout Subsection
 343 What are Tournaments?
 344 \end_layout
 345
 346 \begin_layout BeginFrame
 347 Tournaments Consist of Jousts Between Knights
 348 \end_layout
 349
 350 \begin_layout Columns
 351
 352 \end_layout
 353
 354 \begin_deeper
 355 \begin_layout Column
 356 5.75cm
 357 \end_layout
 358
 359 \begin_layout Standard
 360 \begin_inset ERT
 361 status collapsed
 362
 363 \begin_layout Plain Layout
 364
 365
 366 \backslash
 367 begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}
 368 \end_layout
 369
 370 \begin_layout Plain Layout
 371
 372 \end_layout
 373
 374 \begin_layout Plain Layout
 375
 376
 377 \backslash
 378 pgfnodebox{A}[virtual]{
 379 \backslash
 380 pgfxy(2,1)}{
 381 \backslash
 382 pgfuseimage{knight1}}{2pt}{2pt}
 383 \end_layout
 384
 385 \begin_layout Plain Layout
 386
 387 \end_layout
 388
 389 \begin_layout Plain Layout
 390
 391
 392 \backslash
 393 pgfnodebox{B}[virtual]{
 394 \backslash
 395 pgfxy(6,1)}{
 396 \backslash
 397 pgfuseimage{knight2}}{2pt}{2pt}
 398 \end_layout
 399
 400 \begin_layout Plain Layout
 401
 402 \end_layout
 403
 404 \begin_layout Plain Layout
 405
 406
 407 \backslash
 408 pgfnodebox{C}[virtual]{
 409 \backslash
 410 pgfxy(4,-1)}{
 411 \backslash
 412 pgfuseimage{knight3}}{2pt}{2pt}
 413 \end_layout
 414
 415 \begin_layout Plain Layout
 416
 417 \end_layout
 418
 419 \begin_layout Plain Layout
 420
 421
 422 \backslash
 423 pgfnodebox{D}[virtual]{
 424 \backslash
 425 pgfxy(4,3)}{
 426 \backslash
 427 pgfuseimage{knight4}}{2pt}{2pt}
 428 \end_layout
 429
 430 \begin_layout Plain Layout
 431
 432 \end_layout
 433
 434 \begin_layout Plain Layout
 435
 436 \end_layout
 437
 438 \begin_layout Plain Layout
 439
 440 \end_layout
 441
 442 \begin_layout Plain Layout
 443
 444
 445 \backslash
 446 color{beamerexample}
 447 \end_layout
 448
 449 \begin_layout Plain Layout
 450
 451 \end_layout
 452
 453 \begin_layout Plain Layout
 454
 455
 456 \backslash
 457 only<3->{
 458 \backslash
 459 pgfsetendarrow{
 460 \backslash
 461 pgfarrowto}}
 462 \end_layout
 463
 464 \begin_layout Plain Layout
 465
 466 \end_layout
 467
 468 \begin_layout Plain Layout
 469
 470
 471 \backslash
 472 only<2->{
 473 \end_layout
 474
 475 \begin_layout Plain Layout
 476
 477 \end_layout
 478
 479 \begin_layout Plain Layout
 480
 481
 482 \backslash
 483 pgfsetlinewidth{0.6pt}
 484 \end_layout
 485
 486 \begin_layout Plain Layout
 487
 488 \end_layout
 489
 490 \begin_layout Plain Layout
 491
 492
 493 \backslash
 494 pgfnodeconnline{A}{B}
 495 \end_layout
 496
 497 \begin_layout Plain Layout
 498
 499 \end_layout
 500
 501 \begin_layout Plain Layout
 502
 503
 504 \backslash
 505 pgfnodeconnline{A}{C}
 506 \end_layout
 507
 508 \begin_layout Plain Layout
 509
 510 \end_layout
 511
 512 \begin_layout Plain Layout
 513
 514
 515 \backslash
 516 pgfnodeconnline{D}{A}
 517 \end_layout
 518
 519 \begin_layout Plain Layout
 520
 521 \end_layout
 522
 523 \begin_layout Plain Layout
 524
 525
 526 \backslash
 527 pgfnodeconnline{C}{B}
 528 \end_layout
 529
 530 \begin_layout Plain Layout
 531
 532 \end_layout
 533
 534 \begin_layout Plain Layout
 535
 536
 537 \backslash
 538 pgfnodeconnline{B}{D}
 539 \end_layout
 540
 541 \begin_layout Plain Layout
 542
 543 \end_layout
 544
 545 \begin_layout Plain Layout
 546
 547
 548 \backslash
 549 pgfnodeconnline{C}{D}}
 550 \end_layout
 551
 552 \begin_layout Plain Layout
 553
 554 \end_layout
 555
 556 \begin_layout Plain Layout
 557
 558
 559 \backslash
 560 end{pgfpicture}
 561 \end_layout
 562
 563 \end_inset
 564
 565
 566 \end_layout
 567
 568 \begin_layout Column
 569 6cm
 570 \end_layout
 571
 572 \begin_layout Block
 573 \begin_inset ERT
 574 status collapsed
 575
 576 \begin_layout Plain Layout
 577
 578 {What is a Tournament?}
 579 \end_layout
 580
 581 \end_inset
 582
 583
 584 \end_layout
 585
 586 \begin_deeper
 587 \begin_layout Itemize
 588 \begin_inset ERT
 589 status collapsed
 590
 591 \begin_layout Plain Layout
 592
 593 <1->
 594 \end_layout
 595
 596 \end_inset
 597
 598 A group of knights.
 599 \end_layout
 600
 601 \begin_layout Itemize
 602 \begin_inset ERT
 603 status collapsed
 604
 605 \begin_layout Plain Layout
 606
 607 <2->
 608 \end_layout
 609
 610 \end_inset
 611
 612 Every pair has a joust.
 613 \end_layout
 614
 615 \begin_layout Itemize
 616 \begin_inset ERT
 617 status collapsed
 618
 619 \begin_layout Plain Layout
 620
 621 <3->
 622 \end_layout
 623
 624 \end_inset
 625
 626 In every joust one knight wins.
 627 \end_layout
 628
 629 \end_deeper
 630 \end_deeper
 631 \begin_layout BeginFrame
 632 Tournaments are Complete Directed Graphs
 633 \end_layout
 634
 635 \begin_layout Columns
 636
 637 \end_layout
 638
 639 \begin_deeper
 640 \begin_layout Column
 641 5cm
 642 \end_layout
 643
 644 \begin_layout Standard
 645 \begin_inset ERT
 646 status collapsed
 647
 648 \begin_layout Plain Layout
 649
 650
 651 \backslash
 652 begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
 653 \end_layout
 654
 655 \begin_layout Plain Layout
 656
 657 \end_layout
 658
 659 \begin_layout Plain Layout
 660
 661
 662 \backslash
 663 color{beamerexample}
 664 \end_layout
 665
 666 \begin_layout Plain Layout
 667
 668 \end_layout
 669
 670 \begin_layout Plain Layout
 671
 672
 673 \backslash
 674 pgfsetlinewidth{0.6pt}
 675 \end_layout
 676
 677 \begin_layout Plain Layout
 678
 679 \end_layout
 680
 681 \begin_layout Plain Layout
 682
 683
 684 \backslash
 685 graphnode{A}{
 686 \backslash
 687 pgfxy(2.5,1)}
 688 \end_layout
 689
 690 \begin_layout Plain Layout
 691
 692 \end_layout
 693
 694 \begin_layout Plain Layout
 695
 696
 697 \backslash
 698 graphnode{B}{
 699 \backslash
 700 pgfxy(5.5,1)}
 701 \end_layout
 702
 703 \begin_layout Plain Layout
 704
 705 \end_layout
 706
 707 \begin_layout Plain Layout
 708
 709
 710 \backslash
 711 graphnode{C}{
 712 \backslash
 713 pgfxy(4,-0.5)}
 714 \end_layout
 715
 716 \begin_layout Plain Layout
 717
 718 \end_layout
 719
 720 \begin_layout Plain Layout
 721
 722
 723 \backslash
 724 graphnode{D}{
 725 \backslash
 726 pgfxy(4,2.5)}
 727 \end_layout
 728
 729 \begin_layout Plain Layout
 730
 731 \end_layout
 732
 733 \begin_layout Plain Layout
 734
 735 \end_layout
 736
 737 \begin_layout Plain Layout
 738
 739 \end_layout
 740
 741 \begin_layout Plain Layout
 742
 743
 744 \backslash
 745 color{white}
 746 \end_layout
 747
 748 \begin_layout Plain Layout
 749
 750 \end_layout
 751
 752 \begin_layout Plain Layout
 753
 754
 755 \backslash
 756 pgfputat{
 757 \backslash
 758 pgfnodecenter{A}}{
 759 \backslash
 760 pgfbox[center,center]{$v_2$}}
 761 \end_layout
 762
 763 \begin_layout Plain Layout
 764
 765 \end_layout
 766
 767 \begin_layout Plain Layout
 768
 769
 770 \backslash
 771 pgfputat{
 772 \backslash
 773 pgfnodecenter{B}}{
 774 \backslash
 775 pgfbox[center,center]{$v_3$}}
 776 \end_layout
 777
 778 \begin_layout Plain Layout
 779
 780 \end_layout
 781
 782 \begin_layout Plain Layout
 783
 784
 785 \backslash
 786 pgfputat{
 787 \backslash
 788 pgfnodecenter{C}}{
 789 \backslash
 790 pgfbox[center,center]{$v_4$}}
 791 \end_layout
 792
 793 \begin_layout Plain Layout
 794
 795 \end_layout
 796
 797 \begin_layout Plain Layout
 798
 799
 800 \backslash
 801 pgfputat{
 802 \backslash
 803 pgfnodecenter{D}}{
 804 \backslash
 805 pgfbox[center,center]{$v_1$}}
 806 \end_layout
 807
 808 \begin_layout Plain Layout
 809
 810 \end_layout
 811
 812 \begin_layout Plain Layout
 813
 814 \end_layout
 815
 816 \begin_layout Plain Layout
 817
 818 \end_layout
 819
 820 \begin_layout Plain Layout
 821
 822
 823 \backslash
 824 color{beamerexample}
 825 \end_layout
 826
 827 \begin_layout Plain Layout
 828
 829 \end_layout
 830
 831 \begin_layout Plain Layout
 832
 833
 834 \backslash
 835 pgfsetendarrow{
 836 \backslash
 837 pgfarrowto}
 838 \end_layout
 839
 840 \begin_layout Plain Layout
 841
 842 \end_layout
 843
 844 \begin_layout Plain Layout
 845
 846
 847 \backslash
 848 pgfnodesetsepstart{2pt}
 849 \end_layout
 850
 851 \begin_layout Plain Layout
 852
 853 \end_layout
 854
 855 \begin_layout Plain Layout
 856
 857
 858 \backslash
 859 pgfnodesetsepend{4pt}
 860 \end_layout
 861
 862 \begin_layout Plain Layout
 863
 864 \end_layout
 865
 866 \begin_layout Plain Layout
 867
 868
 869 \backslash
 870 pgfnodeconnline{A}{B}
 871 \end_layout
 872
 873 \begin_layout Plain Layout
 874
 875 \end_layout
 876
 877 \begin_layout Plain Layout
 878
 879
 880 \backslash
 881 pgfnodeconnline{A}{C}
 882 \end_layout
 883
 884 \begin_layout Plain Layout
 885
 886 \end_layout
 887
 888 \begin_layout Plain Layout
 889
 890
 891 \backslash
 892 pgfnodeconnline{D}{A}
 893 \end_layout
 894
 895 \begin_layout Plain Layout
 896
 897 \end_layout
 898
 899 \begin_layout Plain Layout
 900
 901
 902 \backslash
 903 pgfnodeconnline{C}{B}
 904 \end_layout
 905
 906 \begin_layout Plain Layout
 907
 908 \end_layout
 909
 910 \begin_layout Plain Layout
 911
 912
 913 \backslash
 914 pgfnodeconnline{B}{D}
 915 \end_layout
 916
 917 \begin_layout Plain Layout
 918
 919 \end_layout
 920
 921 \begin_layout Plain Layout
 922
 923
 924 \backslash
 925 pgfnodeconnline{D}{C}
 926 \end_layout
 927
 928 \begin_layout Plain Layout
 929
 930 \end_layout
 931
 932 \begin_layout Plain Layout
 933
 934
 935 \backslash
 936 end{pgfpicture}
 937 \end_layout
 938
 939 \end_inset
 940
 941
 942 \end_layout
 943
 944 \begin_layout Column
 945 6cm
 946 \end_layout
 947
 948 \begin_layout Definition
 949 \begin_inset ERT
 950 status collapsed
 951
 952 \begin_layout Plain Layout
 953
 954 <2->
 955 \end_layout
 956
 957 \end_inset
 958
 959 A
 960 \color none
 961
 962 \color red
 963 tournament
 964 \color none
 965
 966 \color inherit
 967 is a
 968 \end_layout
 969
 970 \begin_deeper
 971 \begin_layout Enumerate
 972 directed graphs,
 973 \end_layout
 974
 975 \begin_layout Enumerate
 976 with exactly one edge between
 977 \begin_inset Newline newline
 978 \end_inset
 979
 980 any two different vertices.
 981 \end_layout
 982
 983 \end_deeper
 984 \end_deeper
 985 \begin_layout BeginFrame
 986 \begin_inset ERT
 987 status collapsed
 988
 989 \begin_layout Plain Layout
 990
 991 [<+>]
 992 \end_layout
 993
 994 \end_inset
 995
 996 Tournaments Arise Naturally in Different Situations
 997 \end_layout
 998
 999 \begin_layout ExampleBlock
1000 \begin_inset ERT
1001 status collapsed
1002
1003 \begin_layout Plain Layout
1004
1005 {Applicatins in Ordering Theory}
1006 \end_layout
1007
1008 \end_inset
1009
1010
1011 \end_layout
1012
1013 \begin_deeper
1014 \begin_layout Standard
1015 Elements in a set need to be sorted.
1016
1017 \begin_inset Newline newline
1018 \end_inset
1019
1020 The comparison relation may be cyclic, however.
1021 \end_layout
1022
1023 \end_deeper
1024 \begin_layout Separator
1025
1026 \end_layout
1027
1028 \begin_layout ExampleBlock
1029 \begin_inset ERT
1030 status collapsed
1031
1032 \begin_layout Plain Layout
1033
1034 {Applications in Sociology}
1035 \end_layout
1036
1037 \end_inset
1038
1039
1040 \end_layout
1041
1042 \begin_deeper
1043 \begin_layout Standard
1044 Several candidates apply for a position.
1045 \begin_inset Newline newline
1046 \end_inset
1047
1048 Reviewers decide for any two candidates whom they prefer.
1049
1050 \end_layout
1051
1052 \end_deeper
1053 \begin_layout Separator
1054
1055 \end_layout
1056
1057 \begin_layout ExampleBlock
1058 \begin_inset ERT
1059 status collapsed
1060
1061 \begin_layout Plain Layout
1062
1063 {Applications in Structural Complexity Theory}
1064 \end_layout
1065
1066 \end_inset
1067
1068
1069 \end_layout
1070
1071 \begin_deeper
1072 \begin_layout Standard
1073 A language
1074 \begin_inset Formula $L$
1075 \end_inset
1076
1077  is given and a selector function
1078 \begin_inset Formula $f$
1079 \end_inset
1080
1081 .
1082 \begin_inset Newline newline
1083 \end_inset
1084
1085 It chooses from any two words the one more likely to be in
1086 \begin_inset Formula $f$
1087 \end_inset
1088
1089 .
1090 \end_layout
1091
1092 \end_deeper
1093 \begin_layout Subsection
1094 What Does ``Finding Paths'' Mean?
1095 \end_layout
1096
1097 \begin_layout BeginFrame
1098 ``Finding Paths'' is Ambiguous
1099 \end_layout
1100
1101 \begin_layout Block
1102 \begin_inset ERT
1103 status collapsed
1104
1105 \begin_layout Plain Layout
1106
1107 {
1108 \backslash
1109 strut Input for
1110 \backslash
1111 ignorespaces
1112 \backslash
1113 def
1114 \backslash
1115 par{}% because LyX inserts superfluous paragraphs
1116 \end_layout
1117
1118 \begin_layout Plain Layout
1119
1120 \end_layout
1121
1122 \begin_layout Plain Layout
1123
1124
1125 \backslash
1126 only<1>{Path Finding Problems}
1127 \backslash
1128 ignorespaces
1129 \end_layout
1130
1131 \begin_layout Plain Layout
1132
1133 \end_layout
1134
1135 \begin_layout Plain Layout
1136
1137
1138 \backslash
1139 only<2-3>{$
1140 \backslash
1141 Lang{reach}$}
1142 \backslash
1143 ignorespaces
1144 \end_layout
1145
1146 \begin_layout Plain Layout
1147
1148 \end_layout
1149
1150 \begin_layout Plain Layout
1151
1152
1153 \backslash
1154 only<4-5>{the Construction Problem}
1155 \backslash
1156 ignorespaces
1157 \end_layout
1158
1159 \begin_layout Plain Layout
1160
1161 \end_layout
1162
1163 \begin_layout Plain Layout
1164
1165
1166 \backslash
1167 only<6-7>{the Optimization Problem}
1168 \backslash
1169 ignorespaces
1170 \end_layout
1171
1172 \begin_layout Plain Layout
1173
1174 \end_layout
1175
1176 \begin_layout Plain Layout
1177
1178
1179 \backslash
1180 only<8-9>{$
1181 \backslash
1182 Lang{distance}$}
1183 \backslash
1184 ignorespaces
1185 \end_layout
1186
1187 \begin_layout Plain Layout
1188
1189 \end_layout
1190
1191 \begin_layout Plain Layout
1192
1193
1194 \backslash
1195 only<10->{the Approximation Problem}}
1196 \end_layout
1197
1198 \end_inset
1199
1200
1201 \end_layout
1202
1203 \begin_deeper
1204 \begin_layout Itemize
1205 A
1206 \color none
1207
1208 \color red
1209 graph
1210 \color none
1211
1212 \color inherit
1213
1214 \begin_inset Formula $G=(V,E)$
1215 \end_inset
1216
1217 , a
1218 \color none
1219
1220 \color red
1221 source
1222 \color none
1223
1224 \color inherit
1225
1226 \begin_inset Formula $s\in V$
1227 \end_inset
1228
1229  and a
1230 \color none
1231
1232 \color red
1233 target
1234 \color none
1235
1236 \color inherit
1237
1238 \begin_inset Formula $t\in V$
1239 \end_inset
1240
1241 .
1242 \end_layout
1243
1244 \begin_layout Itemize
1245 \begin_inset ERT
1246 status collapsed
1247
1248 \begin_layout Plain Layout
1249
1250 <only@-9| visible@8->
1251 \end_layout
1252
1253 \end_inset
1254
1255 A
1256 \color none
1257
1258 \color red
1259 maximum distance
1260 \color inherit
1261
1262 \begin_inset space ~
1263 \end_inset
1264
1265
1266 \begin_inset Formula $d$
1267 \end_inset
1268
1269 .
1270 \begin_inset ERT
1271 status collapsed
1272
1273 \begin_layout Plain Layout
1274
1275
1276 \backslash
1277 phantom{p}
1278 \end_layout
1279
1280 \end_inset
1281
1282
1283 \end_layout
1284
1285 \begin_layout Itemize
1286 \begin_inset ERT
1287 status collapsed
1288
1289 \begin_layout Plain Layout
1290
1291 <only@10->
1292 \end_layout
1293
1294 \end_inset
1295
1296 An
1297 \color none
1298
1299 \color red
1300 approximation ratio
1301 \color none
1302
1303 \color inherit
1304
1305 \begin_inset Formula $r>1$
1306 \end_inset
1307
1308 .
1309 \end_layout
1310
1311 \end_deeper
1312 \begin_layout Standard
1313 \begin_inset ERT
1314 status collapsed
1315
1316 \begin_layout Plain Layout
1317
1318
1319 \backslash
1320 nointerlineskip
1321 \end_layout
1322
1323 \end_inset
1324
1325
1326 \end_layout
1327
1328 \begin_layout Overprint
1329
1330 \end_layout
1331
1332 \begin_deeper
1333 \begin_layout Standard
1334 \begin_inset ERT
1335 status collapsed
1336
1337 \begin_layout Plain Layout
1338
1339
1340 \backslash
1341 onslide<1,3,5,7,9,11-12>
1342 \end_layout
1343
1344 \end_inset
1345
1346
1347 \end_layout
1348
1349 \begin_layout Columns
1350 \begin_inset ERT
1351 status collapsed
1352
1353 \begin_layout Plain Layout
1354
1355 [t,onlytextwidth]
1356 \end_layout
1357
1358 \end_inset
1359
1360
1361 \end_layout
1362
1363 \begin_deeper
1364 \begin_layout Standard
1365 \begin_inset ERT
1366 status collapsed
1367
1368 \begin_layout Plain Layout
1369
1370
1371 \backslash
1372 alt<1-2>{
1373 \backslash
1374 column{
1375 \backslash
1376 textwidth}}{
1377 \backslash
1378 column{5cm}}
1379 \end_layout
1380
1381 \end_inset
1382
1383
1384 \end_layout
1385
1386 \begin_layout ExampleBlock
1387 \begin_inset ERT
1388 status collapsed
1389
1390 \begin_layout Plain Layout
1391
1392 {Example Input}
1393 \end_layout
1394
1395 \end_inset
1396
1397
1398 \end_layout
1399
1400 \begin_deeper
1401 \begin_layout Standard
1402 \begin_inset ERT
1403 status collapsed
1404
1405 \begin_layout Plain Layout
1406
1407
1408 \backslash
1409 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1410 \end_layout
1411
1412 \begin_layout Plain Layout
1413
1414 \end_layout
1415
1416 \begin_layout Plain Layout
1417
1418
1419 \backslash
1420 color{beamerexample}
1421 \end_layout
1422
1423 \begin_layout Plain Layout
1424
1425 \end_layout
1426
1427 \begin_layout Plain Layout
1428
1429
1430 \backslash
1431 pgfsetlinewidth{0.6pt}
1432 \end_layout
1433
1434 \begin_layout Plain Layout
1435
1436 \end_layout
1437
1438 \begin_layout Plain Layout
1439
1440
1441 \backslash
1442 graphnode{A}{
1443 \backslash
1444 pgfxy(3,1)}
1445 \end_layout
1446
1447 \begin_layout Plain Layout
1448
1449 \end_layout
1450
1451 \begin_layout Plain Layout
1452
1453
1454 \backslash
1455 graphnode{B}{
1456 \backslash
1457 pgfxy(5,1)}
1458 \end_layout
1459
1460 \begin_layout Plain Layout
1461
1462 \end_layout
1463
1464 \begin_layout Plain Layout
1465
1466
1467 \backslash
1468 graphnode{C}{
1469 \backslash
1470 pgfxy(4,0)}
1471 \end_layout
1472
1473 \begin_layout Plain Layout
1474
1475 \end_layout
1476
1477 \begin_layout Plain Layout
1478
1479
1480 \backslash
1481 graphnode{D}{
1482 \backslash
1483 pgfxy(4,2)}
1484 \end_layout
1485
1486 \begin_layout Plain Layout
1487
1488 \end_layout
1489
1490 \begin_layout Plain Layout
1491
1492 \end_layout
1493
1494 \begin_layout Plain Layout
1495
1496 \end_layout
1497
1498 \begin_layout Plain Layout
1499
1500
1501 \backslash
1502 color{white}
1503 \end_layout
1504
1505 \begin_layout Plain Layout
1506
1507 \end_layout
1508
1509 \begin_layout Plain Layout
1510
1511
1512 \backslash
1513 pgfputat{
1514 \backslash
1515 pgfnodecenter{B}}{
1516 \backslash
1517 pgfbox[center,center]{$t$}}
1518 \end_layout
1519
1520 \begin_layout Plain Layout
1521
1522 \end_layout
1523
1524 \begin_layout Plain Layout
1525
1526
1527 \backslash
1528 pgfputat{
1529 \backslash
1530 pgfnodecenter{D}}{
1531 \backslash
1532 pgfbox[center,center]{$s$}}
1533 \end_layout
1534
1535 \begin_layout Plain Layout
1536
1537 \end_layout
1538
1539 \begin_layout Plain Layout
1540
1541 \end_layout
1542
1543 \begin_layout Plain Layout
1544
1545 \end_layout
1546
1547 \begin_layout Plain Layout
1548
1549
1550 \backslash
1551 color{beamerexample}
1552 \end_layout
1553
1554 \begin_layout Plain Layout
1555
1556 \end_layout
1557
1558 \begin_layout Plain Layout
1559
1560
1561 \backslash
1562 pgfsetendarrow{
1563 \backslash
1564 pgfarrowto}
1565 \end_layout
1566
1567 \begin_layout Plain Layout
1568
1569 \end_layout
1570
1571 \begin_layout Plain Layout
1572
1573
1574 \backslash
1575 pgfnodesetsepstart{2pt}
1576 \end_layout
1577
1578 \begin_layout Plain Layout
1579
1580 \end_layout
1581
1582 \begin_layout Plain Layout
1583
1584
1585 \backslash
1586 pgfnodesetsepend{4pt}
1587 \end_layout
1588
1589 \begin_layout Plain Layout
1590
1591 \end_layout
1592
1593 \begin_layout Plain Layout
1594
1595
1596 \backslash
1597 pgfnodeconnline{A}{B}
1598 \end_layout
1599
1600 \begin_layout Plain Layout
1601
1602 \end_layout
1603
1604 \begin_layout Plain Layout
1605
1606
1607 \backslash
1608 pgfnodeconnline{A}{C}
1609 \end_layout
1610
1611 \begin_layout Plain Layout
1612
1613 \end_layout
1614
1615 \begin_layout Plain Layout
1616
1617
1618 \backslash
1619 pgfnodeconnline{D}{A}
1620 \end_layout
1621
1622 \begin_layout Plain Layout
1623
1624 \end_layout
1625
1626 \begin_layout Plain Layout
1627
1628
1629 \backslash
1630 pgfnodeconnline{C}{B}
1631 \end_layout
1632
1633 \begin_layout Plain Layout
1634
1635 \end_layout
1636
1637 \begin_layout Plain Layout
1638
1639
1640 \backslash
1641 pgfnodeconnline{B}{D}
1642 \end_layout
1643
1644 \begin_layout Plain Layout
1645
1646 \end_layout
1647
1648 \begin_layout Plain Layout
1649
1650
1651 \backslash
1652 pgfnodeconnline{D}{C}
1653 \end_layout
1654
1655 \begin_layout Plain Layout
1656
1657 \end_layout
1658
1659 \begin_layout Plain Layout
1660
1661 \end_layout
1662
1663 \begin_layout Plain Layout
1664
1665 \end_layout
1666
1667 \begin_layout Plain Layout
1668
1669
1670 \backslash
1671 only<9> {
1672 \backslash
1673 pgfputat{
1674 \backslash
1675 pgfxy(5.3,1)}{
1676 \backslash
1677 pgfbox[left,center]{, $d=2$}}}
1678 \end_layout
1679
1680 \begin_layout Plain Layout
1681
1682 \end_layout
1683
1684 \begin_layout Plain Layout
1685
1686
1687 \backslash
1688 only<11>{
1689 \backslash
1690 pgfputat{
1691 \backslash
1692 pgfxy(5.3,1)}{
1693 \backslash
1694 pgfbox[left,center]{, $r=1.5$}}}
1695 \end_layout
1696
1697 \begin_layout Plain Layout
1698
1699 \end_layout
1700
1701 \begin_layout Plain Layout
1702
1703
1704 \backslash
1705 only<12>{
1706 \backslash
1707 pgfputat{
1708 \backslash
1709 pgfxy(5.3,1)}{
1710 \backslash
1711 pgfbox[left,center]{, $r=1.25$}}}
1712 \end_layout
1713
1714 \begin_layout Plain Layout
1715
1716 \end_layout
1717
1718 \begin_layout Plain Layout
1719
1720
1721 \backslash
1722 end{pgfpicture}
1723 \end_layout
1724
1725 \end_inset
1726
1727
1728 \end_layout
1729
1730 \end_deeper
1731 \begin_layout Standard
1732 \begin_inset ERT
1733 status collapsed
1734
1735 \begin_layout Plain Layout
1736
1737
1738 \backslash
1739 only<3->{
1740 \backslash
1741 column{5cm}}
1742 \end_layout
1743
1744 \end_inset
1745
1746
1747 \end_layout
1748
1749 \begin_layout ExampleBlock
1750 \begin_inset ERT
1751 status collapsed
1752
1753 \begin_layout Plain Layout
1754
1755 <only@3->{Example Output}
1756 \end_layout
1757
1758 \end_inset
1759
1760
1761 \end_layout
1762
1763 \begin_deeper
1764 \begin_layout Standard
1765 \begin_inset ERT
1766 status collapsed
1767
1768 \begin_layout Plain Layout
1769
1770
1771 \backslash
1772 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1773 \end_layout
1774
1775 \begin_layout Plain Layout
1776
1777 \end_layout
1778
1779 \begin_layout Plain Layout
1780
1781
1782 \backslash
1783 only<5-8,10->{
1784 \end_layout
1785
1786 \begin_layout Plain Layout
1787
1788 \end_layout
1789
1790 \begin_layout Plain Layout
1791
1792
1793 \backslash
1794 color{beamerexample}
1795 \end_layout
1796
1797 \begin_layout Plain Layout
1798
1799 \end_layout
1800
1801 \begin_layout Plain Layout
1802
1803
1804 \backslash
1805 pgfsetlinewidth{0.6pt}
1806 \end_layout
1807
1808 \begin_layout Plain Layout
1809
1810 \end_layout
1811
1812 \begin_layout Plain Layout
1813
1814
1815 \backslash
1816 graphnode{A}{
1817 \backslash
1818 pgfxy(3,1)}
1819 \end_layout
1820
1821 \begin_layout Plain Layout
1822
1823 \end_layout
1824
1825 \begin_layout Plain Layout
1826
1827
1828 \backslash
1829 graphnode{B}{
1830 \backslash
1831 pgfxy(5,1)}
1832 \end_layout
1833
1834 \begin_layout Plain Layout
1835
1836 \end_layout
1837
1838 \begin_layout Plain Layout
1839
1840
1841 \backslash
1842 graphnode{C}{
1843 \backslash
1844 pgfxy(4,0)}
1845 \end_layout
1846
1847 \begin_layout Plain Layout
1848
1849 \end_layout
1850
1851 \begin_layout Plain Layout
1852
1853
1854 \backslash
1855 graphnode{D}{
1856 \backslash
1857 pgfxy(4,2)}
1858 \end_layout
1859
1860 \begin_layout Plain Layout
1861
1862 \end_layout
1863
1864 \begin_layout Plain Layout
1865
1866 \end_layout
1867
1868 \begin_layout Plain Layout
1869
1870 \end_layout
1871
1872 \begin_layout Plain Layout
1873
1874
1875 \backslash
1876 color{white}
1877 \end_layout
1878
1879 \begin_layout Plain Layout
1880
1881 \end_layout
1882
1883 \begin_layout Plain Layout
1884
1885
1886 \backslash
1887 pgfputat{
1888 \backslash
1889 pgfnodecenter{B}}{
1890 \backslash
1891 pgfbox[center,center]{$t$}}
1892 \end_layout
1893
1894 \begin_layout Plain Layout
1895
1896 \end_layout
1897
1898 \begin_layout Plain Layout
1899
1900
1901 \backslash
1902 pgfputat{
1903 \backslash
1904 pgfnodecenter{D}}{
1905 \backslash
1906 pgfbox[center,center]{$s$}}
1907 \end_layout
1908
1909 \begin_layout Plain Layout
1910
1911 \end_layout
1912
1913 \begin_layout Plain Layout
1914
1915 \end_layout
1916
1917 \begin_layout Plain Layout
1918
1919 \end_layout
1920
1921 \begin_layout Plain Layout
1922
1923
1924 \backslash
1925 color{beamerexample}
1926 \end_layout
1927
1928 \begin_layout Plain Layout
1929
1930 \end_layout
1931
1932 \begin_layout Plain Layout
1933
1934
1935 \backslash
1936 pgfsetendarrow{
1937 \backslash
1938 pgfarrowto}
1939 \end_layout
1940
1941 \begin_layout Plain Layout
1942
1943 \end_layout
1944
1945 \begin_layout Plain Layout
1946
1947
1948 \backslash
1949 pgfnodesetsepstart{2pt}
1950 \end_layout
1951
1952 \begin_layout Plain Layout
1953
1954 \end_layout
1955
1956 \begin_layout Plain Layout
1957
1958
1959 \backslash
1960 pgfnodesetsepend{4pt}
1961 \end_layout
1962
1963 \begin_layout Plain Layout
1964
1965 \end_layout
1966
1967 \begin_layout Plain Layout
1968
1969
1970 \end_layout
1971
1972 \begin_layout Plain Layout
1973
1974 \end_layout
1975
1976 \begin_layout Plain Layout
1977
1978
1979 \backslash
1980 alert<7,12>{
1981 \backslash
1982 pgfnodeconnline{A}{B}}
1983 \end_layout
1984
1985 \begin_layout Plain Layout
1986
1987 \end_layout
1988
1989 \begin_layout Plain Layout
1990
1991
1992 \backslash
1993 alert<5,11>{
1994 \backslash
1995 pgfnodeconnline{A}{C}}
1996 \end_layout
1997
1998 \begin_layout Plain Layout
1999
2000 \end_layout
2001
2002 \begin_layout Plain Layout
2003
2004
2005 \backslash
2006 alert<5,7,11-12>{
2007 \backslash
2008 pgfnodeconnline{D}{A}}
2009 \end_layout
2010
2011 \begin_layout Plain Layout
2012
2013 \end_layout
2014
2015 \begin_layout Plain Layout
2016
2017
2018 \backslash
2019 alert<5,11>{
2020 \backslash
2021 pgfnodeconnline{C}{B}}
2022 \end_layout
2023
2024 \begin_layout Plain Layout
2025
2026 \end_layout
2027
2028 \begin_layout Plain Layout
2029
2030
2031 \backslash
2032 pgfnodeconnline{B}{D}
2033 \end_layout
2034
2035 \begin_layout Plain Layout
2036
2037 \end_layout
2038
2039 \begin_layout Plain Layout
2040
2041
2042 \backslash
2043 pgfnodeconnline{D}{C}
2044 \end_layout
2045
2046 \begin_layout Plain Layout
2047
2048 \end_layout
2049
2050 \begin_layout Plain Layout
2051
2052   }
2053 \end_layout
2054
2055 \begin_layout Plain Layout
2056
2057 \end_layout
2058
2059 \begin_layout Plain Layout
2060
2061
2062 \backslash
2063 only<3,9>{
2064 \backslash
2065 pgfputat{
2066 \backslash
2067 pgfxy(2.75,1)}{
2068 \backslash
2069 pgfbox[left,center]{
2070 \backslash
2071 alert{``Yes''}}}}
2072 \end_layout
2073
2074 \begin_layout Plain Layout
2075
2076 \end_layout
2077
2078 \begin_layout Plain Layout
2079
2080
2081 \backslash
2082 end{pgfpicture}
2083 \end_layout
2084
2085 \end_inset
2086
2087
2088 \end_layout
2089
2090 \end_deeper
2091 \end_deeper
2092 \begin_layout Standard
2093 \begin_inset ERT
2094 status collapsed
2095
2096 \begin_layout Plain Layout
2097
2098
2099 \backslash
2100 onslide<2,4,6,8,10>
2101 \end_layout
2102
2103 \end_inset
2104
2105
2106 \end_layout
2107
2108 \begin_layout Block
2109 \begin_inset ERT
2110 status collapsed
2111
2112 \begin_layout Plain Layout
2113
2114 {Variants of Path Finding Problems}
2115 \end_layout
2116
2117 \end_inset
2118
2119
2120 \end_layout
2121
2122 \begin_deeper
2123 \begin_layout Standard
2124 \begin_inset ERT
2125 status collapsed
2126
2127 \begin_layout Plain Layout
2128
2129
2130 \backslash
2131 usedescriptionitemofwidthas{Approximation Problem:}
2132 \end_layout
2133
2134 \end_inset
2135
2136
2137 \end_layout
2138
2139 \begin_layout Description
2140 Reachability
2141 \begin_inset space ~
2142 \end_inset
2143
2144 Problem:
2145 \begin_inset ERT
2146 status collapsed
2147
2148 \begin_layout Plain Layout
2149
2150 <2->
2151 \end_layout
2152
2153 \end_inset
2154
2155 Is there a path from
2156 \begin_inset Formula $s$
2157 \end_inset
2158
2159  to
2160 \begin_inset space ~
2161 \end_inset
2162
2163
2164 \begin_inset Formula $t$
2165 \end_inset
2166
2167 ?
2168 \end_layout
2169
2170 \begin_layout Description
2171 Construction
2172 \begin_inset space ~
2173 \end_inset
2174
2175 Problem:
2176 \begin_inset ERT
2177 status collapsed
2178
2179 \begin_layout Plain Layout
2180
2181 <4->
2182 \end_layout
2183
2184 \end_inset
2185
2186 Construct a path from
2187 \begin_inset Formula $s$
2188 \end_inset
2189
2190  to
2191 \begin_inset space ~
2192 \end_inset
2193
2194
2195 \begin_inset Formula $t$
2196 \end_inset
2197
2198 ?
2199 \end_layout
2200
2201 \begin_layout Description
2202 Optimization
2203 \begin_inset space ~
2204 \end_inset
2205
2206 Problem:
2207 \begin_inset ERT
2208 status collapsed
2209
2210 \begin_layout Plain Layout
2211
2212 <6->
2213 \end_layout
2214
2215 \end_inset
2216
2217 Construct a shortest path from
2218 \begin_inset Formula $s$
2219 \end_inset
2220
2221  to
2222 \begin_inset space ~
2223 \end_inset
2224
2225
2226 \begin_inset Formula $t$
2227 \end_inset
2228
2229 .
2230 \end_layout
2231
2232 \begin_layout Description
2233 Distance
2234 \begin_inset space ~
2235 \end_inset
2236
2237 Problem:
2238 \begin_inset ERT
2239 status collapsed
2240
2241 \begin_layout Plain Layout
2242
2243 <8->
2244 \end_layout
2245
2246 \end_inset
2247
2248 Is the distance of
2249 \begin_inset Formula $s$
2250 \end_inset
2251
2252  and
2253 \begin_inset space ~
2254 \end_inset
2255
2256
2257 \begin_inset Formula $t$
2258 \end_inset
2259
2260  at most
2261 \begin_inset space ~
2262 \end_inset
2263
2264
2265 \begin_inset Formula $d$
2266 \end_inset
2267
2268 ?
2269 \end_layout
2270
2271 \begin_layout Description
2272 Approximation
2273 \begin_inset space ~
2274 \end_inset
2275
2276 Problem:
2277 \begin_inset ERT
2278 status collapsed
2279
2280 \begin_layout Plain Layout
2281
2282 <10->
2283 \end_layout
2284
2285 \end_inset
2286
2287 Construct a path from
2288 \begin_inset Formula $s$
2289 \end_inset
2290
2291  to
2292 \begin_inset space ~
2293 \end_inset
2294
2295
2296 \begin_inset Formula $t$
2297 \end_inset
2298
2299  of length
2300 \begin_inset Newline newline
2301 \end_inset
2302
2303 approximately their distance.
2304 \end_layout
2305
2306 \end_deeper
2307 \end_deeper
2308 \begin_layout Section
2309 Review
2310 \end_layout
2311
2312 \begin_layout Subsection
2313 Standard Complexity Classes
2314 \end_layout
2315
2316 \begin_layout Standard
2317 \begin_inset ERT
2318 status collapsed
2319
2320 \begin_layout Plain Layout
2321
2322
2323 \backslash
2324 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2325 \backslash
2326 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2327 -g4}
2328 \end_layout
2329
2330 \end_inset
2331
2332
2333 \end_layout
2334
2335 \begin_layout BeginFrame
2336 The Classes L and NL are Defined via
2337 \begin_inset Newline newline
2338 \end_inset
2339
2340 Logspace Turing Machines
2341 \end_layout
2342
2343 \begin_layout Standard
2344 \begin_inset ERT
2345 status open
2346
2347 \begin_layout Plain Layout
2348
2349
2350 \backslash
2351 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2352 \end_layout
2353
2354 \begin_layout Plain Layout
2355
2356 \end_layout
2357
2358 \begin_layout Plain Layout
2359
2360
2361 \backslash
2362 pgfputat{
2363 \backslash
2364 pgfxy(0,4)}{
2365 \backslash
2366 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2367 \end_layout
2368
2369 \begin_layout Plain Layout
2370
2371 \end_layout
2372
2373 \begin_layout Plain Layout
2374
2375
2376 \backslash
2377 uncover<2->{
2378 \end_layout
2379
2380 \begin_layout Plain Layout
2381
2382 \end_layout
2383
2384 \begin_layout Plain Layout
2385
2386
2387 \backslash
2388 pgfputat{
2389 \backslash
2390 pgfxy(0,0.5)}{
2391 \backslash
2392 tape{}{output tape (write only)}{10690836937182}}}
2393 \end_layout
2394
2395 \begin_layout Plain Layout
2396
2397 \end_layout
2398
2399 \begin_layout Plain Layout
2400
2401
2402 \backslash
2403 uncover<3->{
2404 \end_layout
2405
2406 \begin_layout Plain Layout
2407
2408 \end_layout
2409
2410 \begin_layout Plain Layout
2411
2412
2413 \backslash
2414 pgfputat{
2415 \backslash
2416 pgfxy(7,2)}{
2417 \backslash
2418 shorttape{work tape (read/write), $O(
2419 \backslash
2420 log n)$ symbols}{}{42}}
2421 \end_layout
2422
2423 \begin_layout Plain Layout
2424
2425 \end_layout
2426
2427 \begin_layout Plain Layout
2428
2429
2430 \backslash
2431 pgfputat{
2432 \backslash
2433 pgfxy(1.75,2.5)}{
2434 \backslash
2435 pgfbox[center,center]{
2436 \backslash
2437 pgfuseimage{computer}}}
2438 \end_layout
2439
2440 \begin_layout Plain Layout
2441
2442 \end_layout
2443
2444 \begin_layout Plain Layout
2445
2446   }
2447 \end_layout
2448
2449 \begin_layout Plain Layout
2450
2451 \end_layout
2452
2453 \begin_layout Plain Layout
2454
2455
2456 \backslash
2457 pgfsetlinewidth{0.6pt}
2458 \end_layout
2459
2460 \begin_layout Plain Layout
2461
2462 \end_layout
2463
2464 \begin_layout Plain Layout
2465
2466 \end_layout
2467
2468 \begin_layout Plain Layout
2469
2470 \end_layout
2471
2472 \begin_layout Plain Layout
2473
2474
2475 \backslash
2476 color{structure}
2477 \end_layout
2478
2479 \begin_layout Plain Layout
2480
2481 \end_layout
2482
2483 \begin_layout Plain Layout
2484
2485
2486 \backslash
2487 pgfsetendarrow{
2488 \backslash
2489 pgfarrowto}
2490 \end_layout
2491
2492 \begin_layout Plain Layout
2493
2494 \end_layout
2495
2496 \begin_layout Plain Layout
2497
2498
2499 \backslash
2500 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2501 \end_layout
2502
2503 \begin_layout Plain Layout
2504
2505 \end_layout
2506
2507 \begin_layout Plain Layout
2508
2509
2510 \backslash
2511 uncover<2->{
2512 \backslash
2513 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2514 \end_layout
2515
2516 \begin_layout Plain Layout
2517
2518 \end_layout
2519
2520 \begin_layout Plain Layout
2521
2522
2523 \backslash
2524 uncover<3->{
2525 \backslash
2526 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2527 \end_layout
2528
2529 \begin_layout Plain Layout
2530
2531 \end_layout
2532
2533 \begin_layout Plain Layout
2534
2535
2536 \backslash
2537 end{pgfpicture}
2538 \end_layout
2539
2540 \end_inset
2541
2542
2543 \end_layout
2544
2545 \begin_layout BeginFrame
2546 Logspace Turing Machines Are Quite Powerful
2547 \end_layout
2548
2549 \begin_layout Block
2550 \begin_inset ERT
2551 status collapsed
2552
2553 \begin_layout Plain Layout
2554
2555 {Deterministic logspace machines can compute}
2556 \end_layout
2557
2558 \end_inset
2559
2560
2561 \end_layout
2562
2563 \begin_deeper
2564 \begin_layout Itemize
2565 addition, multiplication, and even division
2566 \end_layout
2567
2568 \begin_layout Itemize
2569 reductions used in completeness proofs,
2570 \end_layout
2571
2572 \begin_layout Itemize
2573 reachability in forests.
2574 \end_layout
2575
2576 \end_deeper
2577 \begin_layout Pause
2578
2579 \end_layout
2580
2581 \begin_layout Block
2582 \begin_inset ERT
2583 status collapsed
2584
2585 \begin_layout Plain Layout
2586
2587 {Non-deterministic logspace machines can compute}
2588 \end_layout
2589
2590 \end_inset
2591
2592
2593 \end_layout
2594
2595 \begin_deeper
2596 \begin_layout Itemize
2597 reachability in graphs,
2598 \end_layout
2599
2600 \begin_layout Itemize
2601 non-reachability in graphs,
2602 \end_layout
2603
2604 \begin_layout Itemize
2605 satisfiability with two literals per clause.
2606 \end_layout
2607
2608 \end_deeper
2609 \begin_layout BeginFrame
2610 \begin_inset ERT
2611 status collapsed
2612
2613 \begin_layout Plain Layout
2614
2615 <1>[label=hierarchy]
2616 \end_layout
2617
2618 \end_inset
2619
2620 The Complexity Class Hierarchy
2621 \end_layout
2622
2623 \begin_layout Standard
2624 \begin_inset ERT
2625 status collapsed
2626
2627 \begin_layout Plain Layout
2628
2629
2630 \backslash
2631 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2632 \end_layout
2633
2634 \begin_layout Plain Layout
2635
2636 \end_layout
2637
2638 \begin_layout Plain Layout
2639
2640
2641 \backslash
2642 pgfsetlinewidth{0.8pt}
2643 \end_layout
2644
2645 \begin_layout Plain Layout
2646
2647 \end_layout
2648
2649 \begin_layout Plain Layout
2650
2651
2652 \backslash
2653 heap{5.5}{3.5}{$
2654 \backslash
2655 Class P$}{black}{1}
2656 \end_layout
2657
2658 \begin_layout Plain Layout
2659
2660 \end_layout
2661
2662 \begin_layout Plain Layout
2663
2664
2665 \backslash
2666 pgfsetdash{{2pt}}{0pt}
2667 \end_layout
2668
2669 \begin_layout Plain Layout
2670
2671 \end_layout
2672
2673 \begin_layout Plain Layout
2674
2675
2676 \backslash
2677 only<2->{
2678 \backslash
2679 heap{4.5}{3}{$
2680 \backslash
2681 Class{NC}^2$}{black!50!structure}{2}}
2682 \end_layout
2683
2684 \begin_layout Plain Layout
2685
2686 \end_layout
2687
2688 \begin_layout Plain Layout
2689
2690
2691 \backslash
2692 heap{3.5}{2.5}{$
2693 \backslash
2694 Class{NL}$}{black!50!structure}{3}
2695 \end_layout
2696
2697 \begin_layout Plain Layout
2698
2699 \end_layout
2700
2701 \begin_layout Plain Layout
2702
2703
2704 \backslash
2705 heap{2.5}{2}{$
2706 \backslash
2707 Class{L}$}{black!50!structure}{4}
2708 \end_layout
2709
2710 \begin_layout Plain Layout
2711
2712 \end_layout
2713
2714 \begin_layout Plain Layout
2715
2716
2717 \backslash
2718 only<2->{
2719 \backslash
2720 heap{1.75}{1.5}{$
2721 \backslash
2722 vphantom{A}
2723 \backslash
2724 smash{
2725 \backslash
2726 Class{NC}^1}$}{black!50!structure}{5}}
2727 \end_layout
2728
2729 \begin_layout Plain Layout
2730
2731 \end_layout
2732
2733 \begin_layout Plain Layout
2734
2735
2736 \backslash
2737 pgfsetdash{}{0pt}
2738 \end_layout
2739
2740 \begin_layout Plain Layout
2741
2742 \end_layout
2743
2744 \begin_layout Plain Layout
2745
2746
2747 \backslash
2748 only<2->{
2749 \backslash
2750 heap{1.1}{1}{$
2751 \backslash
2752 vphantom{A}
2753 \backslash
2754 smash{
2755 \backslash
2756 Class{AC}^0}$}{black}{6}}
2757 \end_layout
2758
2759 \begin_layout Plain Layout
2760
2761 \end_layout
2762
2763 \begin_layout Plain Layout
2764
2765 \end_layout
2766
2767 \begin_layout Plain Layout
2768
2769 \end_layout
2770
2771 \begin_layout Plain Layout
2772
2773
2774 \backslash
2775 pgfsetlinewidth{1.0pt}
2776 \end_layout
2777
2778 \begin_layout Plain Layout
2779
2780 \end_layout
2781
2782 \begin_layout Plain Layout
2783
2784
2785 \backslash
2786 color{black}
2787 \end_layout
2788
2789 \begin_layout Plain Layout
2790
2791 \end_layout
2792
2793 \begin_layout Plain Layout
2794
2795
2796 \backslash
2797 pgfxyline(-5,0)(5,0)
2798 \end_layout
2799
2800 \begin_layout Plain Layout
2801
2802 \end_layout
2803
2804 \begin_layout Plain Layout
2805
2806 \end_layout
2807
2808 \begin_layout Plain Layout
2809
2810 \end_layout
2811
2812 \begin_layout Plain Layout
2813
2814
2815 \backslash
2816 only<1-2>{
2817 \backslash
2818 langat{3.375}{$
2819 \backslash
2820 Lang{reach}$}}
2821 \end_layout
2822
2823 \begin_layout Plain Layout
2824
2825 \end_layout
2826
2827 \begin_layout Plain Layout
2828
2829
2830 \backslash
2831 only<1-2>{
2832 \backslash
2833 langat{2.375}{$
2834 \backslash
2835 Lang{reach}_{
2836 \backslash
2837 operatorname{forest}}$}}
2838 \end_layout
2839
2840 \begin_layout Plain Layout
2841
2842 \end_layout
2843
2844 \begin_layout Plain Layout
2845
2846 \end_layout
2847
2848 \begin_layout Plain Layout
2849
2850 \end_layout
2851
2852 \begin_layout Plain Layout
2853
2854
2855 \backslash
2856 only<2>{
2857 \backslash
2858 langat{0.975}{$
2859 \backslash
2860 Lang{addition}$}}
2861 \end_layout
2862
2863 \begin_layout Plain Layout
2864
2865 \end_layout
2866
2867 \begin_layout Plain Layout
2868
2869
2870 \backslash
2871 only<2>{
2872 \backslash
2873 langatother{1.6}{
2874 \backslash
2875 vbox{
2876 \backslash
2877 hbox{$
2878 \backslash
2879 Lang{division}$,}
2880 \backslash
2881 hbox{$
2882 \backslash
2883 Lang{parity}$}}}}
2884 \end_layout
2885
2886 \begin_layout Plain Layout
2887
2888 \end_layout
2889
2890 \begin_layout Plain Layout
2891
2892
2893 \backslash
2894 only<3-5>{
2895 \backslash
2896 langat{3.375}{
2897 \backslash
2898 vbox{
2899 \backslash
2900 hbox{$
2901 \backslash
2902 Lang{distance}$,}
2903 \backslash
2904 hbox{$
2905 \backslash
2906 Lang{reach}$}}}}
2907 \end_layout
2908
2909 \begin_layout Plain Layout
2910
2911 \end_layout
2912
2913 \begin_layout Plain Layout
2914
2915
2916 \backslash
2917 only<4->{
2918 \backslash
2919 langatother{2.375}{
2920 \backslash
2921 vbox{
2922 \backslash
2923 ignorespaces
2924 \end_layout
2925
2926 \begin_layout Plain Layout
2927
2928 \end_layout
2929
2930 \begin_layout Plain Layout
2931
2932
2933 \backslash
2934 hbox{$
2935 \backslash
2936 Lang{distance}_{
2937 \backslash
2938 operatorname{forest}}$,}
2939 \backslash
2940 ignorespaces
2941 \end_layout
2942
2943 \begin_layout Plain Layout
2944
2945 \end_layout
2946
2947 \begin_layout Plain Layout
2948
2949
2950 \backslash
2951 hbox{$
2952 \backslash
2953 Lang{reach}_{
2954 \backslash
2955 operatorname{forest}}$,}
2956 \backslash
2957 ignorespaces
2958 \end_layout
2959
2960 \begin_layout Plain Layout
2961
2962 \end_layout
2963
2964 \begin_layout Plain Layout
2965
2966
2967 \backslash
2968 hbox{$
2969 \backslash
2970 Lang{distance}_{
2971 \backslash
2972 operatorname{path}}$,}
2973 \backslash
2974 ignorespaces
2975 \end_layout
2976
2977 \begin_layout Plain Layout
2978
2979 \end_layout
2980
2981 \begin_layout Plain Layout
2982
2983
2984 \backslash
2985 hbox{$
2986 \backslash
2987 Lang{reach}_{
2988 \backslash
2989 operatorname{path}}$}}}}
2990 \end_layout
2991
2992 \begin_layout Plain Layout
2993
2994 \end_layout
2995
2996 \begin_layout Plain Layout
2997
2998
2999 \backslash
3000 only<5->{
3001 \backslash
3002 langat{0.975}{$
3003 \backslash
3004 Lang{reach}_{
3005 \backslash
3006 operatorname{tourn}}$}}
3007 \end_layout
3008
3009 \begin_layout Plain Layout
3010
3011 \end_layout
3012
3013 \begin_layout Plain Layout
3014
3015
3016 \backslash
3017 only<6->{
3018 \backslash
3019 langat{3.375}{
3020 \backslash
3021 vbox{
3022 \backslash
3023 ignorespaces
3024 \end_layout
3025
3026 \begin_layout Plain Layout
3027
3028 \end_layout
3029
3030 \begin_layout Plain Layout
3031
3032
3033 \backslash
3034 hbox{$
3035 \backslash
3036 Lang{distance}_{
3037 \backslash
3038 operatorname{tourn}}$,}
3039 \backslash
3040 ignorespaces
3041 \end_layout
3042
3043 \begin_layout Plain Layout
3044
3045 \end_layout
3046
3047 \begin_layout Plain Layout
3048
3049
3050 \backslash
3051 hbox{$
3052 \backslash
3053 Lang{distance}$,}
3054 \backslash
3055 ignorespaces
3056 \end_layout
3057
3058 \begin_layout Plain Layout
3059
3060 \end_layout
3061
3062 \begin_layout Plain Layout
3063
3064
3065 \backslash
3066 hbox{$
3067 \backslash
3068 Lang{reach}$}}}}
3069 \end_layout
3070
3071 \begin_layout Plain Layout
3072
3073 \end_layout
3074
3075 \begin_layout Plain Layout
3076
3077
3078 \backslash
3079 only<7->{
3080 \backslash
3081 pgfsetdash{{1pt}}{0pt}
3082 \backslash
3083 langat{2.375}{``$
3084 \backslash
3085 Lang{approx}_{
3086 \backslash
3087 operatorname{tourn}}$''}}
3088 \end_layout
3089
3090 \begin_layout Plain Layout
3091
3092 \end_layout
3093
3094 \begin_layout Plain Layout
3095
3096
3097 \backslash
3098 end{pgfpicture}
3099 \end_layout
3100
3101 \end_inset
3102
3103
3104 \end_layout
3105
3106 \begin_layout BeginFrame
3107 The Circuit Complexity Classes AC
3108 \begin_inset Formula $^{0}$
3109 \end_inset
3110
3111 , NC
3112 \begin_inset Formula $^{1}$
3113 \end_inset
3114
3115 , and NC
3116 \begin_inset Formula $^{2}$
3117 \end_inset
3118
3119
3120 \begin_inset Newline newline
3121 \end_inset
3122
3123 Limit the Circuit Depth
3124 \end_layout
3125
3126 \begin_layout Standard
3127 \begin_inset ERT
3128 status collapsed
3129
3130 \begin_layout Plain Layout
3131
3132
3133 \backslash
3134 setlength
3135 \backslash
3136 leftmargini{1em}
3137 \end_layout
3138
3139 \begin_layout Plain Layout
3140
3141 \end_layout
3142
3143 \begin_layout Plain Layout
3144
3145
3146 \backslash
3147 nointerlineskip
3148 \end_layout
3149
3150 \end_inset
3151
3152
3153 \end_layout
3154
3155 \begin_layout Columns
3156 \begin_inset ERT
3157 status collapsed
3158
3159 \begin_layout Plain Layout
3160
3161 [t]
3162 \end_layout
3163
3164 \end_inset
3165
3166
3167 \end_layout
3168
3169 \begin_deeper
3170 \begin_layout Column
3171 3.6cm
3172 \end_layout
3173
3174 \begin_layout Block
3175 \begin_inset ERT
3176 status collapsed
3177
3178 \begin_layout Plain Layout
3179
3180 {
3181 \end_layout
3182
3183 \end_inset
3184
3185 Circuit Class
3186 \begin_inset Formula $\Class{AC}^{0}$
3187 \end_inset
3188
3189
3190 \begin_inset ERT
3191 status collapsed
3192
3193 \begin_layout Plain Layout
3194
3195 }
3196 \end_layout
3197
3198 \end_inset
3199
3200
3201 \end_layout
3202
3203 \begin_deeper
3204 \begin_layout Itemize
3205 \begin_inset Formula $O(1)$
3206 \end_inset
3207
3208  depth
3209 \end_layout
3210
3211 \begin_layout Itemize
3212 unbounded fan-in
3213 \end_layout
3214
3215 \end_deeper
3216 \begin_layout Examples
3217
3218 \end_layout
3219
3220 \begin_deeper
3221 \begin_layout Itemize
3222 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3223 \end_inset
3224
3225 .
3226 \end_layout
3227
3228 \begin_layout Itemize
3229 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3230 \end_inset
3231
3232 .
3233 \end_layout
3234
3235 \end_deeper
3236 \begin_layout Pause
3237
3238 \end_layout
3239
3240 \begin_layout Column
3241 3.6cm
3242 \end_layout
3243
3244 \begin_layout Block
3245 \begin_inset ERT
3246 status collapsed
3247
3248 \begin_layout Plain Layout
3249
3250 {
3251 \end_layout
3252
3253 \end_inset
3254
3255 Circuit Class
3256 \begin_inset Formula $\Class{NC}^{1}$
3257 \end_inset
3258
3259
3260 \begin_inset ERT
3261 status collapsed
3262
3263 \begin_layout Plain Layout
3264
3265 }
3266 \end_layout
3267
3268 \end_inset
3269
3270
3271 \end_layout
3272
3273 \begin_deeper
3274 \begin_layout Itemize
3275 \begin_inset Formula $O(\log n)$
3276 \end_inset
3277
3278  depth
3279 \end_layout
3280
3281 \begin_layout Itemize
3282 bounded fan-in
3283 \end_layout
3284
3285 \end_deeper
3286 \begin_layout Examples
3287
3288 \end_layout
3289
3290 \begin_deeper
3291 \begin_layout Itemize
3292 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3293 \end_inset
3294
3295 .
3296 \end_layout
3297
3298 \begin_layout Itemize
3299 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3300 \end_inset
3301
3302 .
3303 \end_layout
3304
3305 \begin_layout Itemize
3306 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3307 \end_inset
3308
3309 .
3310 \end_layout
3311
3312 \end_deeper
3313 \begin_layout Pause
3314
3315 \end_layout
3316
3317 \begin_layout Column
3318 3.6cm
3319 \end_layout
3320
3321 \begin_layout Block
3322 \begin_inset ERT
3323 status collapsed
3324
3325 \begin_layout Plain Layout
3326
3327 {
3328 \end_layout
3329
3330 \end_inset
3331
3332 Circuit Class
3333 \begin_inset Formula $\Class{NC}^{2}$
3334 \end_inset
3335
3336
3337 \begin_inset ERT
3338 status collapsed
3339
3340 \begin_layout Plain Layout
3341
3342 }
3343 \end_layout
3344
3345 \end_inset
3346
3347
3348 \end_layout
3349
3350 \begin_deeper
3351 \begin_layout Itemize
3352 \begin_inset Formula $O(\log^{2}n)$
3353 \end_inset
3354
3355  depth
3356 \end_layout
3357
3358 \begin_layout Itemize
3359 bounded fan-in
3360 \end_layout
3361
3362 \end_deeper
3363 \begin_layout Examples
3364
3365 \end_layout
3366
3367 \begin_deeper
3368 \begin_layout Itemize
3369 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3370 \end_inset
3371
3372 .
3373 \end_layout
3374
3375 \end_deeper
3376 \end_deeper
3377 \begin_layout AgainFrame
3378 \begin_inset ERT
3379 status collapsed
3380
3381 \begin_layout Plain Layout
3382
3383 <2>
3384 \end_layout
3385
3386 \end_inset
3387
3388 hierarchy
3389 \end_layout
3390
3391 \begin_layout Subsection
3392 Standard Complexity Results on Finding Paths
3393 \end_layout
3394
3395 \begin_layout BeginFrame
3396 All Variants of Finding Paths in Directed Graphs
3397 \begin_inset Newline newline
3398 \end_inset
3399
3400 Are Equally Difficult
3401 \end_layout
3402
3403 \begin_layout Fact
3404 \begin_inset Formula $\Lang{reach}$
3405 \end_inset
3406
3407  and
3408 \begin_inset Formula $\Lang{distance}$
3409 \end_inset
3410
3411  are
3412 \begin_inset Formula $\Class{NL}$
3413 \end_inset
3414
3415 -complete.
3416
3417 \end_layout
3418
3419 \begin_layout Pause
3420
3421 \end_layout
3422
3423 \begin_layout Corollary
3424 For directed graphs, we can solve
3425 \end_layout
3426
3427 \begin_deeper
3428 \begin_layout Itemize
3429 the reachability problem in logspace iff
3430 \begin_inset Formula $\Class{L}=\Class{NL}$
3431 \end_inset
3432
3433 .
3434 \end_layout
3435
3436 \begin_layout Itemize
3437 the construction problem in logspace iff
3438 \begin_inset Formula $\Class{L}=\Class{NL}$
3439 \end_inset
3440
3441 .
3442 \end_layout
3443
3444 \begin_layout Itemize
3445 the optimization problem in logspace iff
3446 \begin_inset Formula $\Class{L}=\Class{NL}$
3447 \end_inset
3448
3449 .
3450 \end_layout
3451
3452 \begin_layout Itemize
3453 the approximation problem in logspace iff
3454 \begin_inset Formula $\Class{L}=\Class{NL}$
3455 \end_inset
3456
3457 .
3458 \end_layout
3459
3460 \end_deeper
3461 \begin_layout AgainFrame
3462 \begin_inset ERT
3463 status collapsed
3464
3465 \begin_layout Plain Layout
3466
3467 <3>
3468 \end_layout
3469
3470 \end_inset
3471
3472 hierarchy
3473 \end_layout
3474
3475 \begin_layout BeginFrame
3476 FindingPaths in Forests and Directed Paths is Easy,
3477 \begin_inset Newline newline
3478 \end_inset
3479
3480 But Not Trivial
3481 \end_layout
3482
3483 \begin_layout Fact
3484 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3485 \end_inset
3486
3487  and
3488 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3489 \end_inset
3490
3491  are
3492 \begin_inset Formula $\Class{L}$
3493 \end_inset
3494
3495 -complete.
3496 \end_layout
3497
3498 \begin_layout Separator
3499
3500 \end_layout
3501
3502 \begin_layout Fact
3503 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3504 \end_inset
3505
3506  and
3507 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3508 \end_inset
3509
3510  are
3511 \begin_inset Formula $\Class{L}$
3512 \end_inset
3513
3514 -complete.
3515 \end_layout
3516
3517 \begin_layout AgainFrame
3518 \begin_inset ERT
3519 status collapsed
3520
3521 \begin_layout Plain Layout
3522
3523 <4>
3524 \end_layout
3525
3526 \end_inset
3527
3528 hierarchy
3529 \end_layout
3530
3531 \begin_layout Section
3532 Finding Paths in Tournaments
3533 \end_layout
3534
3535 \begin_layout Subsection
3536 Complexity of: Does a Path Exist?
3537 \end_layout
3538
3539 \begin_layout BeginFrame
3540 Definition of the Tournament Reachability Problem
3541 \end_layout
3542
3543 \begin_layout Definition
3544 Let
3545 \color none
3546
3547 \color red
3548
3549 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3550 \end_inset
3551
3552
3553 \color none
3554
3555 \color inherit
3556 contain all triples
3557 \begin_inset Formula $(T,s,t)$
3558 \end_inset
3559
3560  such that
3561 \end_layout
3562
3563 \begin_deeper
3564 \begin_layout Enumerate
3565 \begin_inset Formula $T=(V,E)$
3566 \end_inset
3567
3568  is a tournament and
3569 \end_layout
3570
3571 \begin_layout Enumerate
3572 there exists a path from
3573 \begin_inset space ~
3574 \end_inset
3575
3576
3577 \begin_inset Formula $s$
3578 \end_inset
3579
3580  to
3581 \begin_inset space ~
3582 \end_inset
3583
3584
3585 \begin_inset Formula $t$
3586 \end_inset
3587
3588 .
3589 \end_layout
3590
3591 \end_deeper
3592 \begin_layout BeginFrame
3593 The Tournament Reachability Problem is Very Easy
3594 \end_layout
3595
3596 \begin_layout Theorem
3597 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3598 \end_inset
3599
3600 .
3601 \end_layout
3602
3603 \begin_layout Pause
3604
3605 \end_layout
3606
3607 \begin_layout AlertBlock
3608 \begin_inset ERT
3609 status collapsed
3610
3611 \begin_layout Plain Layout
3612
3613 {Implications}
3614 \end_layout
3615
3616 \end_inset
3617
3618
3619 \end_layout
3620
3621 \begin_deeper
3622 \begin_layout Itemize
3623 The problem is
3624 \begin_inset Quotes eld
3625 \end_inset
3626
3627 easier
3628 \begin_inset Quotes erd
3629 \end_inset
3630
3631  than
3632 \begin_inset Formula $\Lang{reach}$
3633 \end_inset
3634
3635  and even
3636 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3637 \end_inset
3638
3639 .
3640 \end_layout
3641
3642 \begin_layout Itemize
3643 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3644 \end_inset
3645
3646 .
3647 \end_layout
3648
3649 \end_deeper
3650 \begin_layout AgainFrame
3651 \begin_inset ERT
3652 status collapsed
3653
3654 \begin_layout Plain Layout
3655
3656 <5>
3657 \end_layout
3658
3659 \end_inset
3660
3661 hierarchy
3662 \end_layout
3663
3664 \begin_layout Subsection
3665 Complexity of: Construct a Shortest Path
3666 \end_layout
3667
3668 \begin_layout BeginFrame
3669 Finding a Shortest Path Is as Difficult as
3670 \begin_inset Newline newline
3671 \end_inset
3672
3673 the Distance Problem
3674 \end_layout
3675
3676 \begin_layout Definition
3677 Let
3678 \color none
3679
3680 \color red
3681
3682 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3683 \end_inset
3684
3685
3686 \color none
3687
3688 \color inherit
3689 contain all tuples
3690 \begin_inset Formula $(T,s,t,d)$
3691 \end_inset
3692
3693  such that
3694 \end_layout
3695
3696 \begin_deeper
3697 \begin_layout Enumerate
3698 \begin_inset Formula $T=(V,E)$
3699 \end_inset
3700
3701  is a tournament in which
3702 \end_layout
3703
3704 \begin_layout Enumerate
3705 the distance of
3706 \begin_inset Formula $s$
3707 \end_inset
3708
3709  and
3710 \begin_inset space ~
3711 \end_inset
3712
3713
3714 \begin_inset Formula $t$
3715 \end_inset
3716
3717  is at most
3718 \begin_inset space ~
3719 \end_inset
3720
3721
3722 \begin_inset Formula $d$
3723 \end_inset
3724
3725 .
3726 \end_layout
3727
3728 \end_deeper
3729 \begin_layout BeginFrame
3730 The Tournament Distance Problem is Hard
3731 \end_layout
3732
3733 \begin_layout Theorem
3734 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3735 \end_inset
3736
3737  is
3738 \begin_inset Formula $\Class{NL}$
3739 \end_inset
3740
3741 -complete.
3742 \end_layout
3743
3744 \begin_layout Standard
3745 \begin_inset space \hfill{}
3746 \end_inset
3747
3748
3749 \begin_inset ERT
3750 status collapsed
3751
3752 \begin_layout Plain Layout
3753
3754
3755 \backslash
3756 hyperlink{hierarchy<6>}{
3757 \backslash
3758 beamerskipbutton{Skip Proof}}
3759 \end_layout
3760
3761 \end_inset
3762
3763
3764 \end_layout
3765
3766 \begin_layout Pause
3767
3768 \end_layout
3769
3770 \begin_layout Corollary
3771 Shortest path in tournaments can be constructed
3772 \begin_inset Newline newline
3773 \end_inset
3774
3775 in logarithmic space, iff
3776 \begin_inset Formula $\Class{L}=\Class{NL}$
3777 \end_inset
3778
3779 .
3780 \end_layout
3781
3782 \begin_layout Pause
3783
3784 \end_layout
3785
3786 \begin_layout Corollary
3787 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3788 \end_inset
3789
3790 .
3791 \end_layout
3792
3793 \begin_layout BeginFrame
3794 Proof That
3795 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3796 \end_inset
3797
3798  is NL-complete
3799 \end_layout
3800
3801 \begin_layout Standard
3802 \begin_inset ERT
3803 status collapsed
3804
3805 \begin_layout Plain Layout
3806
3807
3808 \backslash
3809 nointerlineskip
3810 \end_layout
3811
3812 \end_inset
3813
3814
3815 \end_layout
3816
3817 \begin_layout Columns
3818 \begin_inset ERT
3819 status collapsed
3820
3821 \begin_layout Plain Layout
3822
3823 [t,onlytextwidth]
3824 \end_layout
3825
3826 \end_inset
3827
3828
3829 \end_layout
3830
3831 \begin_deeper
3832 \begin_layout Column
3833 5.7cm
3834 \end_layout
3835
3836 \begin_layout Standard
3837 \begin_inset ERT
3838 status collapsed
3839
3840 \begin_layout Plain Layout
3841
3842
3843 \backslash
3844 setlength
3845 \backslash
3846 leftmargini{1.5em}
3847 \end_layout
3848
3849 \end_inset
3850
3851
3852 \end_layout
3853
3854 \begin_layout Block
3855 \begin_inset ERT
3856 status collapsed
3857
3858 \begin_layout Plain Layout
3859
3860 {
3861 \end_layout
3862
3863 \end_inset
3864
3865 Reduce
3866 \begin_inset Formula $\Lang{reach}$
3867 \end_inset
3868
3869  to
3870 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3871 \end_inset
3872
3873
3874 \begin_inset ERT
3875 status collapsed
3876
3877 \begin_layout Plain Layout
3878
3879 }
3880 \end_layout
3881
3882 \end_inset
3883
3884
3885 \end_layout
3886
3887 \begin_deeper
3888 \begin_layout Enumerate
3889 \begin_inset ERT
3890 status collapsed
3891
3892 \begin_layout Plain Layout
3893
3894 <alert@1>
3895 \end_layout
3896
3897 \end_inset
3898
3899 Is input
3900 \begin_inset Formula $(G,s,t)$
3901 \end_inset
3902
3903  in
3904 \begin_inset Formula $\Lang{reach}$
3905 \end_inset
3906
3907 ?
3908 \end_layout
3909
3910 \begin_layout Enumerate
3911 \begin_inset ERT
3912 status collapsed
3913
3914 \begin_layout Plain Layout
3915
3916 <2-| alert@2-8>
3917 \end_layout
3918
3919 \end_inset
3920
3921 Map
3922 \begin_inset Formula $G$
3923 \end_inset
3924
3925  to
3926 \begin_inset Formula $G'$
3927 \end_inset
3928
3929 .
3930 \end_layout
3931
3932 \begin_layout Enumerate
3933 \begin_inset ERT
3934 status collapsed
3935
3936 \begin_layout Plain Layout
3937
3938 <9-| alert@9>
3939 \end_layout
3940
3941 \end_inset
3942
3943 Query:
3944 \begin_inset Newline newline
3945 \end_inset
3946
3947
3948 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3949 \end_inset
3950
3951 ?
3952 \end_layout
3953
3954 \end_deeper
3955 \begin_layout Separator
3956
3957 \end_layout
3958
3959 \begin_layout Block
3960 \begin_inset ERT
3961 status collapsed
3962
3963 \begin_layout Plain Layout
3964
3965 {
3966 \end_layout
3967
3968 \end_inset
3969
3970 Correctness
3971 \begin_inset ERT
3972 status collapsed
3973
3974 \begin_layout Plain Layout
3975
3976 }
3977 \end_layout
3978
3979 \end_inset
3980
3981
3982 \begin_inset ERT
3983 status collapsed
3984
3985 \begin_layout Plain Layout
3986
3987 <10->
3988 \end_layout
3989
3990 \end_inset
3991
3992
3993 \end_layout
3994
3995 \begin_deeper
3996 \begin_layout Enumerate
3997 \begin_inset ERT
3998 status collapsed
3999
4000 \begin_layout Plain Layout
4001
4002 <10-| alert@10-11>
4003 \end_layout
4004
4005 \end_inset
4006
4007 A path in
4008 \begin_inset space ~
4009 \end_inset
4010
4011
4012 \begin_inset Formula $G$
4013 \end_inset
4014
4015  induces
4016 \begin_inset Newline newline
4017 \end_inset
4018
4019 a length-3 path in
4020 \begin_inset space ~
4021 \end_inset
4022
4023
4024 \begin_inset Formula $G'$
4025 \end_inset
4026
4027 .
4028 \end_layout
4029
4030 \begin_layout Enumerate
4031 \begin_inset ERT
4032 status collapsed
4033
4034 \begin_layout Plain Layout
4035
4036 <12-| alert@12-13>
4037 \end_layout
4038
4039 \end_inset
4040
4041 A length-3 path in
4042 \begin_inset space ~
4043 \end_inset
4044
4045
4046 \begin_inset Formula $G'$
4047 \end_inset
4048
4049  induces
4050 \begin_inset Newline newline
4051 \end_inset
4052
4053 a path in
4054 \begin_inset space ~
4055 \end_inset
4056
4057
4058 \begin_inset Formula $G'$
4059 \end_inset
4060
4061 .
4062 \end_layout
4063
4064 \end_deeper
4065 \begin_layout Column
4066 4.5cm
4067 \end_layout
4068
4069 \begin_layout Example
4070 \begin_inset ERT
4071 status collapsed
4072
4073 \begin_layout Plain Layout
4074
4075
4076 \backslash
4077 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
4078 \end_layout
4079
4080 \begin_layout Plain Layout
4081
4082 \end_layout
4083
4084 \begin_layout Plain Layout
4085
4086
4087 \backslash
4088 color{beamerexample}
4089 \end_layout
4090
4091 \begin_layout Plain Layout
4092
4093 \end_layout
4094
4095 \begin_layout Plain Layout
4096
4097
4098 \backslash
4099 pgfsetlinewidth{0.6pt}
4100 \end_layout
4101
4102 \begin_layout Plain Layout
4103
4104 \end_layout
4105
4106 \begin_layout Plain Layout
4107
4108
4109 \backslash
4110 graphnode{A}{
4111 \backslash
4112 pgfxy(1,3.3)}
4113 \end_layout
4114
4115 \begin_layout Plain Layout
4116
4117 \end_layout
4118
4119 \begin_layout Plain Layout
4120
4121
4122 \backslash
4123 graphnode{B}{
4124 \backslash
4125 pgfxy(2,3.3)}
4126 \end_layout
4127
4128 \begin_layout Plain Layout
4129
4130 \end_layout
4131
4132 \begin_layout Plain Layout
4133
4134
4135 \backslash
4136 graphnode{C}{
4137 \backslash
4138 pgfxy(3,3.3)}
4139 \end_layout
4140
4141 \begin_layout Plain Layout
4142
4143 \end_layout
4144
4145 \begin_layout Plain Layout
4146
4147
4148 \backslash
4149 graphnode{D}{
4150 \backslash
4151 pgfxy(4,3.3)}
4152 \end_layout
4153
4154 \begin_layout Plain Layout
4155
4156 \end_layout
4157
4158 \begin_layout Plain Layout
4159
4160 \end_layout
4161
4162 \begin_layout Plain Layout
4163
4164 \end_layout
4165
4166 \begin_layout Plain Layout
4167
4168
4169 \backslash
4170 color{white}
4171 \end_layout
4172
4173 \begin_layout Plain Layout
4174
4175 \end_layout
4176
4177 \begin_layout Plain Layout
4178
4179
4180 \backslash
4181 pgfputat{
4182 \backslash
4183 pgfnodecenter{A}}{
4184 \backslash
4185 pgfbox[center,center]{$s$}}
4186 \end_layout
4187
4188 \begin_layout Plain Layout
4189
4190 \end_layout
4191
4192 \begin_layout Plain Layout
4193
4194
4195 \backslash
4196 pgfputat{
4197 \backslash
4198 pgfnodecenter{D}}{
4199 \backslash
4200 pgfbox[center,center]{$t$}}
4201 \end_layout
4202
4203 \begin_layout Plain Layout
4204
4205 \end_layout
4206
4207 \begin_layout Plain Layout
4208
4209 \end_layout
4210
4211 \begin_layout Plain Layout
4212
4213 \end_layout
4214
4215 \begin_layout Plain Layout
4216
4217
4218 \backslash
4219 color{beamerexample}
4220 \end_layout
4221
4222 \begin_layout Plain Layout
4223
4224 \end_layout
4225
4226 \begin_layout Plain Layout
4227
4228
4229 \backslash
4230 pgfsetendarrow{
4231 \backslash
4232 pgfarrowto}
4233 \end_layout
4234
4235 \begin_layout Plain Layout
4236
4237 \end_layout
4238
4239 \begin_layout Plain Layout
4240
4241
4242 \backslash
4243 pgfnodesetsepstart{2pt}
4244 \end_layout
4245
4246 \begin_layout Plain Layout
4247
4248 \end_layout
4249
4250 \begin_layout Plain Layout
4251
4252
4253 \backslash
4254 pgfnodesetsepend{2pt}
4255 \end_layout
4256
4257 \begin_layout Plain Layout
4258
4259 \end_layout
4260
4261 \begin_layout Plain Layout
4262
4263
4264 \backslash
4265 alert<3>{
4266 \backslash
4267 pgfnodeconnline{B}{A}}
4268 \end_layout
4269
4270 \begin_layout Plain Layout
4271
4272 \end_layout
4273
4274 \begin_layout Plain Layout
4275
4276
4277 \backslash
4278 alert<4>{
4279 \backslash
4280 pgfnodeconnline{B}{C}}
4281 \end_layout
4282
4283 \begin_layout Plain Layout
4284
4285 \end_layout
4286
4287 \begin_layout Plain Layout
4288
4289
4290 \backslash
4291 alert<5,10-11,13>{
4292 \backslash
4293 pgfnodeconnline{C}{D}}
4294 \end_layout
4295
4296 \begin_layout Plain Layout
4297
4298 \end_layout
4299
4300 \begin_layout Plain Layout
4301
4302
4303 \backslash
4304 alert<6,10-11,13>{
4305 \backslash
4306 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4307 \end_layout
4308
4309 \begin_layout Plain Layout
4310
4311 \end_layout
4312
4313 \begin_layout Plain Layout
4314
4315
4316 \end_layout
4317
4318 \begin_layout Plain Layout
4319
4320 \end_layout
4321
4322 \begin_layout Plain Layout
4323
4324
4325 \backslash
4326 pgfputat{
4327 \backslash
4328 pgfxy(0,3.3)}{
4329 \backslash
4330 pgfbox[left,center]{$G
4331 \backslash
4332 colon$}}
4333 \end_layout
4334
4335 \begin_layout Plain Layout
4336
4337 \end_layout
4338
4339 \begin_layout Plain Layout
4340
4341 \end_layout
4342
4343 \begin_layout Plain Layout
4344
4345 \end_layout
4346
4347 \begin_layout Plain Layout
4348
4349
4350 \backslash
4351 only<2->{
4352 \end_layout
4353
4354 \begin_layout Plain Layout
4355
4356 \end_layout
4357
4358 \begin_layout Plain Layout
4359
4360
4361 \backslash
4362 pgfputat{
4363 \backslash
4364 pgfxy(0,2.25)}{
4365 \backslash
4366 pgfbox[left,center]{$G'
4367 \backslash
4368 colon$}}
4369 \end_layout
4370
4371 \begin_layout Plain Layout
4372
4373 \end_layout
4374
4375 \begin_layout Plain Layout
4376
4377
4378 \backslash
4379 graphnode{A1}{
4380 \backslash
4381 pgfxy(1,2.25)}
4382 \end_layout
4383
4384 \begin_layout Plain Layout
4385
4386 \end_layout
4387
4388 \begin_layout Plain Layout
4389
4390
4391 \backslash
4392 graphnode{B1}{
4393 \backslash
4394 pgfxy(2,2.25)}
4395 \end_layout
4396
4397 \begin_layout Plain Layout
4398
4399 \end_layout
4400
4401 \begin_layout Plain Layout
4402
4403
4404 \backslash
4405 graphnode{C1}{
4406 \backslash
4407 pgfxy(3,2.25)}
4408 \end_layout
4409
4410 \begin_layout Plain Layout
4411
4412 \end_layout
4413
4414 \begin_layout Plain Layout
4415
4416
4417 \backslash
4418 graphnode{D1}{
4419 \backslash
4420 pgfxy(4,2.25)}
4421 \end_layout
4422
4423 \begin_layout Plain Layout
4424
4425 \end_layout
4426
4427 \begin_layout Plain Layout
4428
4429 \end_layout
4430
4431 \begin_layout Plain Layout
4432
4433 \end_layout
4434
4435 \begin_layout Plain Layout
4436
4437
4438 \backslash
4439 graphnode{A2}{
4440 \backslash
4441 pgfxy(1,1.25)}
4442 \end_layout
4443
4444 \begin_layout Plain Layout
4445
4446 \end_layout
4447
4448 \begin_layout Plain Layout
4449
4450
4451 \backslash
4452 graphnode{B2}{
4453 \backslash
4454 pgfxy(2,1.25)}
4455 \end_layout
4456
4457 \begin_layout Plain Layout
4458
4459 \end_layout
4460
4461 \begin_layout Plain Layout
4462
4463
4464 \backslash
4465 graphnode{C2}{
4466 \backslash
4467 pgfxy(3,1.25)}
4468 \end_layout
4469
4470 \begin_layout Plain Layout
4471
4472 \end_layout
4473
4474 \begin_layout Plain Layout
4475
4476
4477 \backslash
4478 graphnode{D2}{
4479 \backslash
4480 pgfxy(4,1.25)}
4481 \end_layout
4482
4483 \begin_layout Plain Layout
4484
4485 \end_layout
4486
4487 \begin_layout Plain Layout
4488
4489
4490 \backslash
4491 graphnode{A3}{
4492 \backslash
4493 pgfxy(1,0.25)}
4494 \end_layout
4495
4496 \begin_layout Plain Layout
4497
4498 \end_layout
4499
4500 \begin_layout Plain Layout
4501
4502
4503 \backslash
4504 graphnode{B3}{
4505 \backslash
4506 pgfxy(2,0.25)}
4507 \end_layout
4508
4509 \begin_layout Plain Layout
4510
4511 \end_layout
4512
4513 \begin_layout Plain Layout
4514
4515
4516 \backslash
4517 graphnode{C3}{
4518 \backslash
4519 pgfxy(3,0.25)}
4520 \end_layout
4521
4522 \begin_layout Plain Layout
4523
4524 \end_layout
4525
4526 \begin_layout Plain Layout
4527
4528
4529 \backslash
4530 graphnode{D3}{
4531 \backslash
4532 pgfxy(4,0.25)}
4533 \end_layout
4534
4535 \begin_layout Plain Layout
4536
4537 \end_layout
4538
4539 \begin_layout Plain Layout
4540
4541
4542 \backslash
4543 graphnode{A4}{
4544 \backslash
4545 pgfxy(1,-.75)}
4546 \end_layout
4547
4548 \begin_layout Plain Layout
4549
4550 \end_layout
4551
4552 \begin_layout Plain Layout
4553
4554
4555 \backslash
4556 graphnode{B4}{
4557 \backslash
4558 pgfxy(2,-.75)}
4559 \end_layout
4560
4561 \begin_layout Plain Layout
4562
4563 \end_layout
4564
4565 \begin_layout Plain Layout
4566
4567
4568 \backslash
4569 graphnode{C4}{
4570 \backslash
4571 pgfxy(3,-.75)}
4572 \end_layout
4573
4574 \begin_layout Plain Layout
4575
4576 \end_layout
4577
4578 \begin_layout Plain Layout
4579
4580
4581 \backslash
4582 graphnode{D4}{
4583 \backslash
4584 pgfxy(4,-.75)}
4585 \end_layout
4586
4587 \begin_layout Plain Layout
4588
4589 \end_layout
4590
4591 \begin_layout Plain Layout
4592
4593      {
4594 \backslash
4595 color{white}
4596 \end_layout
4597
4598 \begin_layout Plain Layout
4599
4600 \end_layout
4601
4602 \begin_layout Plain Layout
4603
4604
4605 \backslash
4606 pgfputat{
4607 \backslash
4608 pgfnodecenter{A1}}{
4609 \backslash
4610 pgfbox[center,center]{$s'$}}
4611 \end_layout
4612
4613 \begin_layout Plain Layout
4614
4615 \end_layout
4616
4617 \begin_layout Plain Layout
4618
4619
4620 \backslash
4621 pgfputat{
4622 \backslash
4623 pgfnodecenter{D4}}{
4624 \backslash
4625 pgfbox[center,center]{$t'$}}
4626 \end_layout
4627
4628 \begin_layout Plain Layout
4629
4630 \end_layout
4631
4632 \begin_layout Plain Layout
4633
4634   }}
4635 \end_layout
4636
4637 \begin_layout Plain Layout
4638
4639 \end_layout
4640
4641 \begin_layout Plain Layout
4642
4643
4644 \end_layout
4645
4646 \begin_layout Plain Layout
4647
4648 \end_layout
4649
4650 \begin_layout Plain Layout
4651
4652
4653 \backslash
4654 only<8->{
4655 \end_layout
4656
4657 \begin_layout Plain Layout
4658
4659 \end_layout
4660
4661 \begin_layout Plain Layout
4662
4663
4664 \backslash
4665 pgfsetlinewidth{0.4pt}
4666 \end_layout
4667
4668 \begin_layout Plain Layout
4669
4670 \end_layout
4671
4672 \begin_layout Plain Layout
4673
4674
4675 \backslash
4676 color{beamerexample!25!averagebackgroundcolor}
4677 \end_layout
4678
4679 \begin_layout Plain Layout
4680
4681 \end_layout
4682
4683 \begin_layout Plain Layout
4684
4685
4686 \backslash
4687 pgfnodeconnline{A2}{C1}
4688 \end_layout
4689
4690 \begin_layout Plain Layout
4691
4692 \end_layout
4693
4694 \begin_layout Plain Layout
4695
4696
4697 \backslash
4698 pgfnodeconnline{A2}{D1}
4699 \end_layout
4700
4701 \begin_layout Plain Layout
4702
4703 \end_layout
4704
4705 \begin_layout Plain Layout
4706
4707
4708 \backslash
4709 pgfnodeconnline{B2}{A1}
4710 \end_layout
4711
4712 \begin_layout Plain Layout
4713
4714 \end_layout
4715
4716 \begin_layout Plain Layout
4717
4718
4719 \backslash
4720 pgfnodeconnline{B2}{C1}
4721 \end_layout
4722
4723 \begin_layout Plain Layout
4724
4725 \end_layout
4726
4727 \begin_layout Plain Layout
4728
4729
4730 \backslash
4731 pgfnodeconnline{B2}{D1}
4732 \end_layout
4733
4734 \begin_layout Plain Layout
4735
4736 \end_layout
4737
4738 \begin_layout Plain Layout
4739
4740
4741 \backslash
4742 pgfnodeconnline{C2}{D1}
4743 \end_layout
4744
4745 \begin_layout Plain Layout
4746
4747 \end_layout
4748
4749 \begin_layout Plain Layout
4750
4751
4752 \backslash
4753 pgfnodeconnline{D2}{A1}
4754 \end_layout
4755
4756 \begin_layout Plain Layout
4757
4758 \end_layout
4759
4760 \begin_layout Plain Layout
4761
4762
4763 \backslash
4764 pgfnodeconnline{D2}{B1}
4765 \end_layout
4766
4767 \begin_layout Plain Layout
4768
4769 \end_layout
4770
4771 \begin_layout Plain Layout
4772
4773
4774 \backslash
4775 pgfnodeconnline{A3}{C2}
4776 \end_layout
4777
4778 \begin_layout Plain Layout
4779
4780 \end_layout
4781
4782 \begin_layout Plain Layout
4783
4784
4785 \backslash
4786 pgfnodeconnline{A3}{D2}
4787 \end_layout
4788
4789 \begin_layout Plain Layout
4790
4791 \end_layout
4792
4793 \begin_layout Plain Layout
4794
4795
4796 \backslash
4797 pgfnodeconnline{B3}{A2}
4798 \end_layout
4799
4800 \begin_layout Plain Layout
4801
4802 \end_layout
4803
4804 \begin_layout Plain Layout
4805
4806
4807 \backslash
4808 pgfnodeconnline{B3}{C2}
4809 \end_layout
4810
4811 \begin_layout Plain Layout
4812
4813 \end_layout
4814
4815 \begin_layout Plain Layout
4816
4817
4818 \backslash
4819 pgfnodeconnline{B3}{D2}
4820 \end_layout
4821
4822 \begin_layout Plain Layout
4823
4824 \end_layout
4825
4826 \begin_layout Plain Layout
4827
4828
4829 \backslash
4830 pgfnodeconnline{C3}{D2}
4831 \end_layout
4832
4833 \begin_layout Plain Layout
4834
4835 \end_layout
4836
4837 \begin_layout Plain Layout
4838
4839
4840 \backslash
4841 pgfnodeconnline{D3}{A2}
4842 \end_layout
4843
4844 \begin_layout Plain Layout
4845
4846 \end_layout
4847
4848 \begin_layout Plain Layout
4849
4850
4851 \backslash
4852 pgfnodeconnline{D3}{B2}
4853 \end_layout
4854
4855 \begin_layout Plain Layout
4856
4857 \end_layout
4858
4859 \begin_layout Plain Layout
4860
4861
4862 \backslash
4863 pgfnodeconnline{A4}{C3}
4864 \end_layout
4865
4866 \begin_layout Plain Layout
4867
4868 \end_layout
4869
4870 \begin_layout Plain Layout
4871
4872
4873 \backslash
4874 pgfnodeconnline{A4}{D3}
4875 \end_layout
4876
4877 \begin_layout Plain Layout
4878
4879 \end_layout
4880
4881 \begin_layout Plain Layout
4882
4883
4884 \backslash
4885 pgfnodeconnline{B4}{A3}
4886 \end_layout
4887
4888 \begin_layout Plain Layout
4889
4890 \end_layout
4891
4892 \begin_layout Plain Layout
4893
4894
4895 \backslash
4896 pgfnodeconnline{B4}{C3}
4897 \end_layout
4898
4899 \begin_layout Plain Layout
4900
4901 \end_layout
4902
4903 \begin_layout Plain Layout
4904
4905
4906 \backslash
4907 pgfnodeconnline{B4}{D3}
4908 \end_layout
4909
4910 \begin_layout Plain Layout
4911
4912 \end_layout
4913
4914 \begin_layout Plain Layout
4915
4916
4917 \backslash
4918 pgfnodeconnline{C4}{D3}
4919 \end_layout
4920
4921 \begin_layout Plain Layout
4922
4923 \end_layout
4924
4925 \begin_layout Plain Layout
4926
4927
4928 \backslash
4929 pgfnodeconnline{D4}{A3}
4930 \end_layout
4931
4932 \begin_layout Plain Layout
4933
4934 \end_layout
4935
4936 \begin_layout Plain Layout
4937
4938
4939 \backslash
4940 pgfnodeconnline{D4}{B3}
4941 \end_layout
4942
4943 \begin_layout Plain Layout
4944
4945 \end_layout
4946
4947 \begin_layout Plain Layout
4948
4949 \end_layout
4950
4951 \begin_layout Plain Layout
4952
4953 \end_layout
4954
4955 \begin_layout Plain Layout
4956
4957
4958 \backslash
4959 pgfsetstartarrow{
4960 \backslash
4961 pgfarrowto}
4962 \end_layout
4963
4964 \begin_layout Plain Layout
4965
4966 \end_layout
4967
4968 \begin_layout Plain Layout
4969
4970
4971 \backslash
4972 pgfnodeconnline{A1}{B1}
4973 \end_layout
4974
4975 \begin_layout Plain Layout
4976
4977 \end_layout
4978
4979 \begin_layout Plain Layout
4980
4981
4982 \backslash
4983 pgfnodeconnline{B1}{C1}
4984 \end_layout
4985
4986 \begin_layout Plain Layout
4987
4988 \end_layout
4989
4990 \begin_layout Plain Layout
4991
4992
4993 \backslash
4994 pgfnodeconnline{C1}{D1}
4995 \end_layout
4996
4997 \begin_layout Plain Layout
4998
4999 \end_layout
5000
5001 \begin_layout Plain Layout
5002
5003
5004 \backslash
5005 pgfnodeconnline{A2}{B2}
5006 \end_layout
5007
5008 \begin_layout Plain Layout
5009
5010 \end_layout
5011
5012 \begin_layout Plain Layout
5013
5014
5015 \backslash
5016 pgfnodeconnline{B2}{C2}
5017 \end_layout
5018
5019 \begin_layout Plain Layout
5020
5021 \end_layout
5022
5023 \begin_layout Plain Layout
5024
5025
5026 \backslash
5027 pgfnodeconnline{C2}{D2}
5028 \end_layout
5029
5030 \begin_layout Plain Layout
5031
5032 \end_layout
5033
5034 \begin_layout Plain Layout
5035
5036
5037 \backslash
5038 pgfnodeconnline{A3}{B3}
5039 \end_layout
5040
5041 \begin_layout Plain Layout
5042
5043 \end_layout
5044
5045 \begin_layout Plain Layout
5046
5047
5048 \backslash
5049 pgfnodeconnline{B3}{C3}
5050 \end_layout
5051
5052 \begin_layout Plain Layout
5053
5054 \end_layout
5055
5056 \begin_layout Plain Layout
5057
5058
5059 \backslash
5060 pgfnodeconnline{C3}{D3}
5061 \end_layout
5062
5063 \begin_layout Plain Layout
5064
5065 \end_layout
5066
5067 \begin_layout Plain Layout
5068
5069
5070 \backslash
5071 pgfnodeconnline{A4}{B4}
5072 \end_layout
5073
5074 \begin_layout Plain Layout
5075
5076 \end_layout
5077
5078 \begin_layout Plain Layout
5079
5080
5081 \backslash
5082 pgfnodeconnline{B4}{C4}
5083 \end_layout
5084
5085 \begin_layout Plain Layout
5086
5087 \end_layout
5088
5089 \begin_layout Plain Layout
5090
5091
5092 \backslash
5093 pgfnodeconnline{C4}{D4}
5094 \end_layout
5095
5096 \begin_layout Plain Layout
5097
5098 \end_layout
5099
5100 \begin_layout Plain Layout
5101
5102 \end_layout
5103
5104 \begin_layout Plain Layout
5105
5106 \end_layout
5107
5108 \begin_layout Plain Layout
5109
5110
5111 \backslash
5112 pgfclearstartarrow
5113 \end_layout
5114
5115 \begin_layout Plain Layout
5116
5117 \end_layout
5118
5119 \begin_layout Plain Layout
5120
5121
5122 \backslash
5123 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
5124 \end_layout
5125
5126 \begin_layout Plain Layout
5127
5128 \end_layout
5129
5130 \begin_layout Plain Layout
5131
5132
5133 \backslash
5134 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
5135 \end_layout
5136
5137 \begin_layout Plain Layout
5138
5139 \end_layout
5140
5141 \begin_layout Plain Layout
5142
5143
5144 \backslash
5145 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
5146 \end_layout
5147
5148 \begin_layout Plain Layout
5149
5150 \end_layout
5151
5152 \begin_layout Plain Layout
5153
5154
5155 \backslash
5156 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
5157 \end_layout
5158
5159 \begin_layout Plain Layout
5160
5161 \end_layout
5162
5163 \begin_layout Plain Layout
5164
5165
5166 \backslash
5167 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
5168 \end_layout
5169
5170 \begin_layout Plain Layout
5171
5172 \end_layout
5173
5174 \begin_layout Plain Layout
5175
5176
5177 \backslash
5178 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
5179 \end_layout
5180
5181 \begin_layout Plain Layout
5182
5183 \end_layout
5184
5185 \begin_layout Plain Layout
5186
5187
5188 \backslash
5189 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
5190 \end_layout
5191
5192 \begin_layout Plain Layout
5193
5194 \end_layout
5195
5196 \begin_layout Plain Layout
5197
5198
5199 \backslash
5200 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
5201 \end_layout
5202
5203 \begin_layout Plain Layout
5204
5205 \end_layout
5206
5207 \begin_layout Plain Layout
5208
5209
5210 \backslash
5211 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
5212 \end_layout
5213
5214 \begin_layout Plain Layout
5215
5216 \end_layout
5217
5218 \begin_layout Plain Layout
5219
5220
5221 \backslash
5222 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
5223 \end_layout
5224
5225 \begin_layout Plain Layout
5226
5227 \end_layout
5228
5229 \begin_layout Plain Layout
5230
5231
5232 \backslash
5233 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
5234 \end_layout
5235
5236 \begin_layout Plain Layout
5237
5238 \end_layout
5239
5240 \begin_layout Plain Layout
5241
5242
5243 \backslash
5244 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
5245 \end_layout
5246
5247 \begin_layout Plain Layout
5248
5249 \end_layout
5250
5251 \begin_layout Plain Layout
5252
5253
5254 \backslash
5255 color{beamerexample}
5256 \end_layout
5257
5258 \begin_layout Plain Layout
5259
5260 \end_layout
5261
5262 \begin_layout Plain Layout
5263
5264
5265 \backslash
5266 pgfsetlinewidth{0.6pt}
5267 \end_layout
5268
5269 \begin_layout Plain Layout
5270
5271 \end_layout
5272
5273 \begin_layout Plain Layout
5274
5275   }
5276 \end_layout
5277
5278 \begin_layout Plain Layout
5279
5280 \end_layout
5281
5282 \begin_layout Plain Layout
5283
5284 \end_layout
5285
5286 \begin_layout Plain Layout
5287
5288 \end_layout
5289
5290 \begin_layout Plain Layout
5291
5292
5293 \backslash
5294 only<3->{
5295 \end_layout
5296
5297 \begin_layout Plain Layout
5298
5299 \end_layout
5300
5301 \begin_layout Plain Layout
5302
5303
5304 \backslash
5305 color<3>{red}
5306 \end_layout
5307
5308 \begin_layout Plain Layout
5309
5310 \end_layout
5311
5312 \begin_layout Plain Layout
5313
5314
5315 \backslash
5316 pgfnodeconnline{B1}{A2}
5317 \end_layout
5318
5319 \begin_layout Plain Layout
5320
5321 \end_layout
5322
5323 \begin_layout Plain Layout
5324
5325
5326 \backslash
5327 pgfnodeconnline{B2}{A3}
5328 \end_layout
5329
5330 \begin_layout Plain Layout
5331
5332 \end_layout
5333
5334 \begin_layout Plain Layout
5335
5336
5337 \backslash
5338 pgfnodeconnline{B3}{A4}
5339 \end_layout
5340
5341 \begin_layout Plain Layout
5342
5343 \end_layout
5344
5345 \begin_layout Plain Layout
5346
5347   }
5348 \end_layout
5349
5350 \begin_layout Plain Layout
5351
5352 \end_layout
5353
5354 \begin_layout Plain Layout
5355
5356 \end_layout
5357
5358 \begin_layout Plain Layout
5359
5360 \end_layout
5361
5362 \begin_layout Plain Layout
5363
5364
5365 \backslash
5366 only<4->{
5367 \end_layout
5368
5369 \begin_layout Plain Layout
5370
5371 \end_layout
5372
5373 \begin_layout Plain Layout
5374
5375
5376 \backslash
5377 color<4>{red}
5378 \end_layout
5379
5380 \begin_layout Plain Layout
5381
5382 \end_layout
5383
5384 \begin_layout Plain Layout
5385
5386
5387 \backslash
5388 pgfnodeconnline{B1}{C2}
5389 \end_layout
5390
5391 \begin_layout Plain Layout
5392
5393 \end_layout
5394
5395 \begin_layout Plain Layout
5396
5397
5398 \backslash
5399 pgfnodeconnline{B2}{C3}
5400 \end_layout
5401
5402 \begin_layout Plain Layout
5403
5404 \end_layout
5405
5406 \begin_layout Plain Layout
5407
5408
5409 \backslash
5410 pgfnodeconnline{B3}{C4}
5411 \end_layout
5412
5413 \begin_layout Plain Layout
5414
5415 \end_layout
5416
5417 \begin_layout Plain Layout
5418
5419   }
5420 \end_layout
5421
5422 \begin_layout Plain Layout
5423
5424 \end_layout
5425
5426 \begin_layout Plain Layout
5427
5428
5429 \end_layout
5430
5431 \begin_layout Plain Layout
5432
5433 \end_layout
5434
5435 \begin_layout Plain Layout
5436
5437
5438 \backslash
5439 only<5->{
5440 \end_layout
5441
5442 \begin_layout Plain Layout
5443
5444 \end_layout
5445
5446 \begin_layout Plain Layout
5447
5448
5449 \backslash
5450 color<5>{red}
5451 \end_layout
5452
5453 \begin_layout Plain Layout
5454
5455 \end_layout
5456
5457 \begin_layout Plain Layout
5458
5459
5460 \backslash
5461 pgfnodeconnline{C1}{D2}
5462 \end_layout
5463
5464 \begin_layout Plain Layout
5465
5466 \end_layout
5467
5468 \begin_layout Plain Layout
5469
5470
5471 \backslash
5472 alert<11>{
5473 \backslash
5474 pgfnodeconnline{C2}{D3}}
5475 \end_layout
5476
5477 \begin_layout Plain Layout
5478
5479 \end_layout
5480
5481 \begin_layout Plain Layout
5482
5483
5484 \backslash
5485 alert<12-13>{
5486 \backslash
5487 pgfnodeconnline{C3}{D4}}
5488 \end_layout
5489
5490 \begin_layout Plain Layout
5491
5492 \end_layout
5493
5494 \begin_layout Plain Layout
5495
5496   }
5497 \end_layout
5498
5499 \begin_layout Plain Layout
5500
5501 \end_layout
5502
5503 \begin_layout Plain Layout
5504
5505
5506 \end_layout
5507
5508 \begin_layout Plain Layout
5509
5510 \end_layout
5511
5512 \begin_layout Plain Layout
5513
5514
5515 \backslash
5516 only<6->{
5517 \end_layout
5518
5519 \begin_layout Plain Layout
5520
5521 \end_layout
5522
5523 \begin_layout Plain Layout
5524
5525
5526 \backslash
5527 color<6>{red}
5528 \end_layout
5529
5530 \begin_layout Plain Layout
5531
5532 \end_layout
5533
5534 \begin_layout Plain Layout
5535
5536
5537 \backslash
5538 alert<11>{
5539 \backslash
5540 pgfnodeconnline{A1}{C2}}
5541 \end_layout
5542
5543 \begin_layout Plain Layout
5544
5545 \end_layout
5546
5547 \begin_layout Plain Layout
5548
5549
5550 \backslash
5551 alert<12-13>{
5552 \backslash
5553 pgfnodeconnline{A2}{C3}}
5554 \end_layout
5555
5556 \begin_layout Plain Layout
5557
5558 \end_layout
5559
5560 \begin_layout Plain Layout
5561
5562
5563 \backslash
5564 pgfnodeconnline{A3}{C4}
5565 \end_layout
5566
5567 \begin_layout Plain Layout
5568
5569 \end_layout
5570
5571 \begin_layout Plain Layout
5572
5573   }
5574 \end_layout
5575
5576 \begin_layout Plain Layout
5577
5578 \end_layout
5579
5580 \begin_layout Plain Layout
5581
5582 \end_layout
5583
5584 \begin_layout Plain Layout
5585
5586 \end_layout
5587
5588 \begin_layout Plain Layout
5589
5590
5591 \backslash
5592 only<7->{
5593 \end_layout
5594
5595 \begin_layout Plain Layout
5596
5597 \end_layout
5598
5599 \begin_layout Plain Layout
5600
5601
5602 \backslash
5603 color<7>{red}
5604 \end_layout
5605
5606 \begin_layout Plain Layout
5607
5608 \end_layout
5609
5610 \begin_layout Plain Layout
5611
5612
5613 \backslash
5614 alert<12-13>{
5615 \backslash
5616 pgfnodeconnline{A1}{A2}}
5617 \end_layout
5618
5619 \begin_layout Plain Layout
5620
5621 \end_layout
5622
5623 \begin_layout Plain Layout
5624
5625
5626 \backslash
5627 pgfnodeconnline{A2}{A3}
5628 \end_layout
5629
5630 \begin_layout Plain Layout
5631
5632 \end_layout
5633
5634 \begin_layout Plain Layout
5635
5636
5637 \backslash
5638 pgfnodeconnline{A3}{A4}
5639 \end_layout
5640
5641 \begin_layout Plain Layout
5642
5643 \end_layout
5644
5645 \begin_layout Plain Layout
5646
5647
5648 \backslash
5649 pgfnodeconnline{B1}{B2}
5650 \end_layout
5651
5652 \begin_layout Plain Layout
5653
5654 \end_layout
5655
5656 \begin_layout Plain Layout
5657
5658
5659 \backslash
5660 pgfnodeconnline{B2}{B3}
5661 \end_layout
5662
5663 \begin_layout Plain Layout
5664
5665 \end_layout
5666
5667 \begin_layout Plain Layout
5668
5669
5670 \backslash
5671 pgfnodeconnline{B3}{B4}
5672 \end_layout
5673
5674 \begin_layout Plain Layout
5675
5676 \end_layout
5677
5678 \begin_layout Plain Layout
5679
5680
5681 \backslash
5682 pgfnodeconnline{C1}{C2}
5683 \end_layout
5684
5685 \begin_layout Plain Layout
5686
5687 \end_layout
5688
5689 \begin_layout Plain Layout
5690
5691
5692 \backslash
5693 pgfnodeconnline{C2}{C3}
5694 \end_layout
5695
5696 \begin_layout Plain Layout
5697
5698 \end_layout
5699
5700 \begin_layout Plain Layout
5701
5702
5703 \backslash
5704 pgfnodeconnline{C3}{C4}
5705 \end_layout
5706
5707 \begin_layout Plain Layout
5708
5709 \end_layout
5710
5711 \begin_layout Plain Layout
5712
5713
5714 \backslash
5715 pgfnodeconnline{D1}{D2}
5716 \end_layout
5717
5718 \begin_layout Plain Layout
5719
5720 \end_layout
5721
5722 \begin_layout Plain Layout
5723
5724
5725 \backslash
5726 pgfnodeconnline{D2}{D3}
5727 \end_layout
5728
5729 \begin_layout Plain Layout
5730
5731 \end_layout
5732
5733 \begin_layout Plain Layout
5734
5735
5736 \backslash
5737 alert<11>{
5738 \backslash
5739 pgfnodeconnline{D3}{D4}}
5740 \end_layout
5741
5742 \begin_layout Plain Layout
5743
5744 \end_layout
5745
5746 \begin_layout Plain Layout
5747
5748   }
5749 \end_layout
5750
5751 \begin_layout Plain Layout
5752
5753 \end_layout
5754
5755 \begin_layout Plain Layout
5756
5757
5758 \backslash
5759 end{pgfpicture}
5760 \end_layout
5761
5762 \end_inset
5763
5764
5765 \end_layout
5766
5767 \end_deeper
5768 \begin_layout AgainFrame
5769 \begin_inset ERT
5770 status collapsed
5771
5772 \begin_layout Plain Layout
5773
5774 <6>
5775 \end_layout
5776
5777 \end_inset
5778
5779 hierarchy
5780 \end_layout
5781
5782 \begin_layout Subsection
5783 Complexity of: Approximating the Shortest Path
5784 \end_layout
5785
5786 \begin_layout BeginFrame
5787 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5788 \end_layout
5789
5790 \begin_layout Definition
5791 An
5792 \color none
5793
5794 \color red
5795 approximation scheme for
5796 \begin_inset Formula $\Lang{tournament-shortest-path}$
5797 \end_inset
5798
5799
5800 \color none
5801
5802 \color inherit
5803 gets as input
5804 \end_layout
5805
5806 \begin_deeper
5807 \begin_layout Enumerate
5808 a tuple
5809 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5810 \end_inset
5811
5812  and
5813 \end_layout
5814
5815 \begin_layout Enumerate
5816 a number
5817 \begin_inset Formula $r>1$
5818 \end_inset
5819
5820 .
5821 \end_layout
5822
5823 \begin_layout Standard
5824 It outputs
5825 \end_layout
5826
5827 \begin_layout Itemize
5828 a path from
5829 \begin_inset Formula $s$
5830 \end_inset
5831
5832  to
5833 \begin_inset space ~
5834 \end_inset
5835
5836
5837 \begin_inset Formula $t$
5838 \end_inset
5839
5840  of length at most
5841 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5842 \end_inset
5843
5844 .
5845 \end_layout
5846
5847 \end_deeper
5848 \begin_layout BeginFrame
5849 There Exists a Logspace Approximation Scheme for
5850 \begin_inset Newline newline
5851 \end_inset
5852
5853 the Tournament Shortest Path Problem
5854 \end_layout
5855
5856 \begin_layout Theorem
5857 There exists an approximation scheme for
5858 \begin_inset Formula $\Lang{tournament-shortest-path}$
5859 \end_inset
5860
5861  that for
5862 \begin_inset Formula $1<r<2$
5863 \end_inset
5864
5865  needs space
5866 \begin_inset Formula \[
5867 O\left(\log|V|\log\frac{1}{r-1}\right).\]
5868
5869 \end_inset
5870
5871
5872 \end_layout
5873
5874 \begin_layout Pause
5875
5876 \end_layout
5877
5878 \begin_layout Corollary
5879 In tournaments, paths can be constructed in logarithmic space.
5880 \end_layout
5881
5882 \begin_layout Standard
5883 \begin_inset space \hfill{}
5884 \end_inset
5885
5886
5887 \begin_inset ERT
5888 status collapsed
5889
5890 \begin_layout Plain Layout
5891
5892
5893 \backslash
5894 hyperlink{optimality}{
5895 \backslash
5896 beamergotobutton{More Details}}
5897 \end_layout
5898
5899 \end_inset
5900
5901
5902 \end_layout
5903
5904 \begin_layout AgainFrame
5905 \begin_inset ERT
5906 status collapsed
5907
5908 \begin_layout Plain Layout
5909
5910 <7>
5911 \end_layout
5912
5913 \end_inset
5914
5915 hierarchy
5916 \end_layout
5917
5918 \begin_layout EndFrame
5919
5920 \end_layout
5921
5922 \begin_layout Standard
5923 \begin_inset Note Note
5924 status open
5925
5926 \begin_layout Plain Layout
5927 If a frame includes a program listing, the frame needs to be marked as
5928 \begin_inset Quotes eld
5929 \end_inset
5930
5931 fragile
5932 \begin_inset Quotes erd
5933 \end_inset
5934
5935 .
5936  This is not yet supported by LyX, so the frame is created using TeX code.
5937  Note that the
5938 \backslash
5939 begin{frame}[fragile] needs to be preceeded by an
5940 \emph on
5941 EndFrame
5942 \emph default
5943  environment.
5944 \end_layout
5945
5946 \end_inset
5947
5948
5949 \end_layout
5950
5951 \begin_layout Standard
5952 \begin_inset ERT
5953 status open
5954
5955 \begin_layout Plain Layout
5956
5957
5958 \backslash
5959 begin{frame}[fragile]
5960 \end_layout
5961
5962 \end_inset
5963
5964
5965 \end_layout
5966
5967 \begin_layout Standard
5968 \begin_inset ERT
5969 status collapsed
5970
5971 \begin_layout Plain Layout
5972
5973
5974 \backslash
5975 frametitle{
5976 \end_layout
5977
5978 \end_inset
5979
5980 Just a frame with a program code listing
5981 \begin_inset ERT
5982 status collapsed
5983
5984 \begin_layout Plain Layout
5985
5986 }
5987 \end_layout
5988
5989 \end_inset
5990
5991
5992 \end_layout
5993
5994 \begin_layout Standard
5995 This is some program code:
5996 \end_layout
5997
5998 \begin_layout Standard
5999 \begin_inset listings
6000 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
6001 inline false
6002 status open
6003
6004 \begin_layout Plain Layout
6005
6006 def func(param):
6007 \end_layout
6008
6009 \begin_layout Plain Layout
6010
6011     'this is a python function'
6012 \end_layout
6013
6014 \begin_layout Plain Layout
6015
6016     pass
6017 \end_layout
6018
6019 \begin_layout Plain Layout
6020
6021 def func(param):
6022 \end_layout
6023
6024 \begin_layout Plain Layout
6025
6026 'This is a German word: Tschüs'
6027 \end_layout
6028
6029 \begin_layout Plain Layout
6030
6031 pass
6032 \end_layout
6033
6034 \begin_layout Plain Layout
6035
6036 def func(param):
6037 \end_layout
6038
6039 \begin_layout Plain Layout
6040
6041 'this is a python function'
6042 \end_layout
6043
6044 \begin_layout Plain Layout
6045
6046 pass
6047 \end_layout
6048
6049 \end_inset
6050
6051
6052 \end_layout
6053
6054 \begin_layout Standard
6055 \begin_inset ERT
6056 status open
6057
6058 \begin_layout Plain Layout
6059
6060
6061 \backslash
6062 end{frame}
6063 \end_layout
6064
6065 \end_inset
6066
6067
6068 \end_layout
6069
6070 \begin_layout Section*
6071 Summary
6072 \end_layout
6073
6074 \begin_layout Subsection*
6075 Summary
6076 \end_layout
6077
6078 \begin_layout BeginFrame
6079 Summary
6080 \end_layout
6081
6082 \begin_layout Block
6083 \begin_inset ERT
6084 status collapsed
6085
6086 \begin_layout Plain Layout
6087
6088 {Summary}
6089 \end_layout
6090
6091 \end_inset
6092
6093
6094 \end_layout
6095
6096 \begin_deeper
6097 \begin_layout Itemize
6098 Tournament
6099 \color none
6100
6101 \color red
6102 reachability
6103 \color none
6104
6105 \color inherit
6106 is in
6107 \color none
6108
6109 \color red
6110
6111 \begin_inset Formula $\Class{AC}^{0}$
6112 \end_inset
6113
6114
6115 \color inherit
6116 .
6117
6118 \end_layout
6119
6120 \begin_layout Itemize
6121 There exists a
6122 \color none
6123
6124 \color red
6125 logspace approximation scheme
6126 \color none
6127
6128 \color inherit
6129 for
6130 \color none
6131
6132 \color red
6133 approximating
6134 \color none
6135
6136 \color inherit
6137 shortest paths in tournaments.
6138 \end_layout
6139
6140 \begin_layout Itemize
6141 Finding
6142 \color none
6143
6144 \color red
6145 shortest paths
6146 \color none
6147
6148 \color inherit
6149 in tournaments is
6150 \color none
6151
6152 \color red
6153
6154 \begin_inset Formula $\Class{NL}$
6155 \end_inset
6156
6157 -complete
6158 \color inherit
6159 .
6160 \end_layout
6161
6162 \end_deeper
6163 \begin_layout Separator
6164
6165 \end_layout
6166
6167 \begin_layout Block
6168 \begin_inset ERT
6169 status collapsed
6170
6171 \begin_layout Plain Layout
6172
6173 {Outlook}
6174 \end_layout
6175
6176 \end_inset
6177
6178
6179 \end_layout
6180
6181 \begin_deeper
6182 \begin_layout Itemize
6183 The same results apply to graphs with
6184 \begin_inset Newline newline
6185 \end_inset
6186
6187 bounded independence number.
6188 \begin_inset space \hfill{}
6189 \end_inset
6190
6191
6192 \begin_inset ERT
6193 status collapsed
6194
6195 \begin_layout Plain Layout
6196
6197
6198 \backslash
6199 hyperlink{independence}{
6200 \backslash
6201 beamergotobutton{More Details}}
6202 \end_layout
6203
6204 \end_inset
6205
6206
6207 \end_layout
6208
6209 \begin_layout Itemize
6210 The complexity of finding paths in undirected graphs
6211 \begin_inset Newline newline
6212 \end_inset
6213
6214 is partly open.
6215 \begin_inset space \hfill{}
6216 \end_inset
6217
6218
6219 \begin_inset ERT
6220 status collapsed
6221
6222 \begin_layout Plain Layout
6223
6224
6225 \backslash
6226 hyperlink{undirected}{
6227 \backslash
6228 beamergotobutton{More Details}}
6229 \end_layout
6230
6231 \end_inset
6232
6233
6234 \end_layout
6235
6236 \end_deeper
6237 \begin_layout Subsection*
6238 For Further Reading
6239 \end_layout
6240
6241 \begin_layout BeginFrame
6242 For Further Reading
6243 \end_layout
6244
6245 \begin_layout Standard
6246 \begin_inset ERT
6247 status collapsed
6248
6249 \begin_layout Plain Layout
6250
6251
6252 \backslash
6253 beamertemplatebookbibitems
6254 \end_layout
6255
6256 \end_inset
6257
6258
6259 \end_layout
6260
6261 \begin_layout Bibliography
6262 \begin_inset CommandInset bibitem
6263 LatexCommand bibitem
6264 key "Moon1968"
6265
6266 \end_inset
6267
6268
6269 \begin_inset space ~
6270 \end_inset
6271
6272 John Moon.
6273
6274 \begin_inset ERT
6275 status collapsed
6276
6277 \begin_layout Plain Layout
6278
6279
6280 \backslash
6281 newblock
6282 \end_layout
6283
6284 \end_inset
6285
6286
6287 \emph on
6288 Topics on Tournaments.
6289
6290 \emph default
6291
6292 \begin_inset ERT
6293 status collapsed
6294
6295 \begin_layout Plain Layout
6296
6297
6298 \backslash
6299 newblock
6300 \end_layout
6301
6302 \end_inset
6303
6304  Holt, Rinehart, and Winston, 1968.
6305
6306 \begin_inset ERT
6307 status collapsed
6308
6309 \begin_layout Plain Layout
6310
6311
6312 \backslash
6313 beamertemplatearticlebibitems
6314 \end_layout
6315
6316 \end_inset
6317
6318
6319 \end_layout
6320
6321 \begin_layout Bibliography
6322 \begin_inset CommandInset bibitem
6323 LatexCommand bibitem
6324 key "NickelsenT2002"
6325
6326 \end_inset
6327
6328
6329 \begin_inset space ~
6330 \end_inset
6331
6332 Arfst Nickelsen and Till Tantau.
6333
6334 \begin_inset ERT
6335 status collapsed
6336
6337 \begin_layout Plain Layout
6338
6339
6340 \backslash
6341 newblock
6342 \end_layout
6343
6344 \end_inset
6345
6346  On reachability in graphs with bounded independence number.
6347 \begin_inset ERT
6348 status collapsed
6349
6350 \begin_layout Plain Layout
6351
6352
6353 \backslash
6354 newblock
6355 \end_layout
6356
6357 \end_inset
6358
6359  In
6360 \emph on
6361 Proc.
6362  of COCOON 2002
6363 \emph default
6364 , Springer-Verlag, 2002.
6365 \end_layout
6366
6367 \begin_layout Bibliography
6368 \begin_inset CommandInset bibitem
6369 LatexCommand bibitem
6370 key "Tantau2004b"
6371
6372 \end_inset
6373
6374
6375 \begin_inset space ~
6376 \end_inset
6377
6378 Till Tantau
6379 \begin_inset ERT
6380 status collapsed
6381
6382 \begin_layout Plain Layout
6383
6384
6385 \backslash
6386 newblock
6387 \end_layout
6388
6389 \end_inset
6390
6391  A logspace approximation scheme for the shortest path problem for graphs
6392  with bounded independence number.
6393 \begin_inset ERT
6394 status collapsed
6395
6396 \begin_layout Plain Layout
6397
6398
6399 \backslash
6400 newblock
6401 \end_layout
6402
6403 \end_inset
6404
6405  In
6406 \emph on
6407 Proc.
6408  of STACS 2004
6409 \emph default
6410 , Springer-Verlag, 2004.
6411
6412 \begin_inset ERT
6413 status collapsed
6414
6415 \begin_layout Plain Layout
6416
6417
6418 \backslash
6419 newblock
6420 \end_layout
6421
6422 \end_inset
6423
6424  In press.
6425 \end_layout
6426
6427 \begin_layout EndFrame
6428
6429 \end_layout
6430
6431 \begin_layout Standard
6432 \start_of_appendix
6433 \begin_inset ERT
6434 status collapsed
6435
6436 \begin_layout Plain Layout
6437
6438
6439 \backslash
6440 AtBeginSubsection[]{}
6441 \end_layout
6442
6443 \end_inset
6444
6445
6446 \end_layout
6447
6448 \begin_layout Section
6449 Appendix
6450 \end_layout
6451
6452 \begin_layout Subsection
6453 Graphs With Bounded Independence Number
6454 \end_layout
6455
6456 \begin_layout BeginFrame
6457 \begin_inset ERT
6458 status collapsed
6459
6460 \begin_layout Plain Layout
6461
6462 [label=independence]
6463 \end_layout
6464
6465 \end_inset
6466
6467 Definition of Independence Number of a Graph
6468 \end_layout
6469
6470 \begin_layout Definition
6471 The
6472 \color none
6473
6474 \color red
6475 independence number
6476 \color none
6477
6478 \color inherit
6479
6480 \begin_inset Formula $\alpha(G)$
6481 \end_inset
6482
6483  of a directed graph
6484 \begin_inset Newline newline
6485 \end_inset
6486
6487 is the maximum number of vertices we can pick,
6488 \begin_inset Newline newline
6489 \end_inset
6490
6491 such that there is no edge between them.
6492 \end_layout
6493
6494 \begin_layout Example
6495 Tournaments have independence number 1.
6496
6497 \end_layout
6498
6499 \begin_layout BeginFrame
6500 The Results for Tournaments also Apply to
6501 \begin_inset Newline newline
6502 \end_inset
6503
6504 Graphs With Bounded Independence Number
6505 \end_layout
6506
6507 \begin_layout Theorem
6508 For each
6509 \begin_inset space ~
6510 \end_inset
6511
6512
6513 \begin_inset Formula $k$
6514 \end_inset
6515
6516 ,
6517 \color none
6518
6519 \color red
6520 reachability
6521 \color none
6522
6523 \color inherit
6524 in graphs with independence number
6525 \begin_inset Newline newline
6526 \end_inset
6527
6528 at most
6529 \begin_inset space ~
6530 \end_inset
6531
6532
6533 \begin_inset Formula $k$
6534 \end_inset
6535
6536  is in
6537 \begin_inset Formula $\Class{AC}^{0}$
6538 \end_inset
6539
6540 .
6541 \end_layout
6542
6543 \begin_layout Separator
6544
6545 \end_layout
6546
6547 \begin_layout Theorem
6548 For each
6549 \begin_inset space ~
6550 \end_inset
6551
6552
6553 \begin_inset Formula $k$
6554 \end_inset
6555
6556 , there exists a
6557 \color none
6558
6559 \color red
6560 logspace approximation scheme
6561 \color none
6562
6563 \color inherit
6564 for approximating the shortest path in graphs with independence number at
6565  most
6566 \begin_inset space ~
6567 \end_inset
6568
6569
6570 \begin_inset Formula $k$
6571 \end_inset
6572
6573
6574 \end_layout
6575
6576 \begin_layout Separator
6577
6578 \end_layout
6579
6580 \begin_layout Theorem
6581 For each
6582 \begin_inset space ~
6583 \end_inset
6584
6585
6586 \begin_inset Formula $k$
6587 \end_inset
6588
6589 , finding the
6590 \color none
6591
6592 \color red
6593 shortest path
6594 \color none
6595
6596 \color inherit
6597 in graphs with independence number at most
6598 \begin_inset space ~
6599 \end_inset
6600
6601
6602 \begin_inset Formula $k$
6603 \end_inset
6604
6605  is
6606 \color none
6607
6608 \color red
6609
6610 \begin_inset Formula $\Class{NL}$
6611 \end_inset
6612
6613 -complete
6614 \color inherit
6615 .
6616 \end_layout
6617
6618 \begin_layout Subsection
6619 Finding Paths in Undirected Graphs
6620 \end_layout
6621
6622 \begin_layout BeginFrame
6623 \begin_inset ERT
6624 status collapsed
6625
6626 \begin_layout Plain Layout
6627
6628 <1-2>[label=undirected]
6629 \end_layout
6630
6631 \end_inset
6632
6633 The Complexity of Finding Paths in Undirected Graphs
6634 \begin_inset Newline newline
6635 \end_inset
6636
6637 Is Party Unknown.
6638 \end_layout
6639
6640 \begin_layout Fact
6641 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6642 \end_inset
6643
6644  is
6645 \begin_inset Formula $\Class{SL}$
6646 \end_inset
6647
6648 -complete.
6649 \end_layout
6650
6651 \begin_layout Corollary
6652 For undirected graphs, we can solve
6653 \end_layout
6654
6655 \begin_deeper
6656 \begin_layout Itemize
6657 the reachability problem in logspace iff
6658 \begin_inset Formula $\Class L=\Class{SL}$
6659 \end_inset
6660
6661 ,
6662 \end_layout
6663
6664 \begin_layout Itemize
6665 the construction problem in logspace iff
6666 \begin_inset ERT
6667 status collapsed
6668
6669 \begin_layout Plain Layout
6670
6671
6672 \backslash
6673 alt<1>{?}{
6674 \backslash
6675 alert{$
6676 \backslash
6677 Class L =
6678 \backslash
6679 Class{SL}$}}
6680 \end_layout
6681
6682 \end_inset
6683
6684 ,
6685 \end_layout
6686
6687 \begin_layout Itemize
6688 the optimization problem in logspace iff
6689 \begin_inset ERT
6690 status collapsed
6691
6692 \begin_layout Plain Layout
6693
6694
6695 \backslash
6696 alt<1>{?}{
6697 \backslash
6698 alert{$
6699 \backslash
6700 Class L =
6701 \backslash
6702 Class{NL}$}}
6703 \end_layout
6704
6705 \end_inset
6706
6707 ,
6708 \end_layout
6709
6710 \begin_layout Itemize
6711 the approximation problem in logspace iff ?.
6712
6713 \end_layout
6714
6715 \end_deeper
6716 \begin_layout Subsection
6717 The Approximation Scheme is Optimal
6718 \end_layout
6719
6720 \begin_layout BeginFrame
6721 \begin_inset ERT
6722 status collapsed
6723
6724 \begin_layout Plain Layout
6725
6726 [label=optimality]
6727 \end_layout
6728
6729 \end_inset
6730
6731 The Approximation Scheme is Optimal
6732 \end_layout
6733
6734 \begin_layout Theorem
6735 Suppose there exists an approximation scheme for
6736 \begin_inset Formula $\Lang{tournament-shortest-path}$
6737 \end_inset
6738
6739  that needs space
6740 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6741 \end_inset
6742
6743 .
6744  Then
6745 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6746 \end_inset
6747
6748 .
6749 \end_layout
6750
6751 \begin_layout Proof
6752
6753 \end_layout
6754
6755 \begin_deeper
6756 \begin_layout Enumerate
6757 Suppose the approximation scheme exists.
6758 \begin_inset Newline newline
6759 \end_inset
6760
6761 We show
6762 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6763 \end_inset
6764
6765 .
6766
6767 \end_layout
6768
6769 \begin_layout Enumerate
6770 Let
6771 \begin_inset Formula $(T,s,t)$
6772 \end_inset
6773
6774  be an input.
6775  Let
6776 \begin_inset Formula $n$
6777 \end_inset
6778
6779  be the number of vertices.
6780 \end_layout
6781
6782 \begin_layout Enumerate
6783 Run the approximation scheme for
6784 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6785 \end_inset
6786
6787 .
6788 \begin_inset Newline newline
6789 \end_inset
6790
6791 This needs space
6792 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6793 \end_inset
6794
6795 .
6796 \end_layout
6797
6798 \begin_layout Enumerate
6799 The resulting path has optimal length.
6800
6801 \begin_inset ERT
6802 status collapsed
6803
6804 \begin_layout Plain Layout
6805
6806
6807 \backslash
6808 qedhere
6809 \end_layout
6810
6811 \end_inset
6812
6813
6814 \end_layout
6815
6816 \end_deeper
6817 \begin_layout EndFrame
6818
6819 \end_layout
6820
6821 \end_body
6822 \end_document