lib/examples/beamerlyxexample1.lyx

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