lib/examples/beamerlyxexample1.lyx

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