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 ERT
1369 status collapsed
1370
1371 \begin_layout Plain Layout
1372
1373 [t,onlytextwidth]
1374 \end_layout
1375
1376 \end_inset
1377
1378
1379 \end_layout
1380
1381 \begin_deeper
1382 \begin_layout Standard
1383 \begin_inset ERT
1384 status collapsed
1385
1386 \begin_layout Plain Layout
1387
1388
1389 \backslash
1390 alt<1-2>{
1391 \backslash
1392 column{
1393 \backslash
1394 textwidth}}{
1395 \backslash
1396 column{5cm}}
1397 \end_layout
1398
1399 \end_inset
1400
1401
1402 \end_layout
1403
1404 \begin_layout ExampleBlock
1405 \begin_inset ERT
1406 status collapsed
1407
1408 \begin_layout Plain Layout
1409
1410 {Example Input}
1411 \end_layout
1412
1413 \end_inset
1414
1415
1416 \end_layout
1417
1418 \begin_deeper
1419 \begin_layout Standard
1420 \begin_inset ERT
1421 status collapsed
1422
1423 \begin_layout Plain Layout
1424
1425
1426 \backslash
1427 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1428 \end_layout
1429
1430 \begin_layout Plain Layout
1431
1432 \end_layout
1433
1434 \begin_layout Plain Layout
1435
1436
1437 \backslash
1438 color{beamerexample}
1439 \end_layout
1440
1441 \begin_layout Plain Layout
1442
1443 \end_layout
1444
1445 \begin_layout Plain Layout
1446
1447
1448 \backslash
1449 pgfsetlinewidth{0.6pt}
1450 \end_layout
1451
1452 \begin_layout Plain Layout
1453
1454 \end_layout
1455
1456 \begin_layout Plain Layout
1457
1458
1459 \backslash
1460 graphnode{A}{
1461 \backslash
1462 pgfxy(3,1)}
1463 \end_layout
1464
1465 \begin_layout Plain Layout
1466
1467 \end_layout
1468
1469 \begin_layout Plain Layout
1470
1471
1472 \backslash
1473 graphnode{B}{
1474 \backslash
1475 pgfxy(5,1)}
1476 \end_layout
1477
1478 \begin_layout Plain Layout
1479
1480 \end_layout
1481
1482 \begin_layout Plain Layout
1483
1484
1485 \backslash
1486 graphnode{C}{
1487 \backslash
1488 pgfxy(4,0)}
1489 \end_layout
1490
1491 \begin_layout Plain Layout
1492
1493 \end_layout
1494
1495 \begin_layout Plain Layout
1496
1497
1498 \backslash
1499 graphnode{D}{
1500 \backslash
1501 pgfxy(4,2)}
1502 \end_layout
1503
1504 \begin_layout Plain Layout
1505
1506 \end_layout
1507
1508 \begin_layout Plain Layout
1509
1510 \end_layout
1511
1512 \begin_layout Plain Layout
1513
1514 \end_layout
1515
1516 \begin_layout Plain Layout
1517
1518
1519 \backslash
1520 color{white}
1521 \end_layout
1522
1523 \begin_layout Plain Layout
1524
1525 \end_layout
1526
1527 \begin_layout Plain Layout
1528
1529
1530 \backslash
1531 pgfputat{
1532 \backslash
1533 pgfnodecenter{B}}{
1534 \backslash
1535 pgfbox[center,center]{$t$}}
1536 \end_layout
1537
1538 \begin_layout Plain Layout
1539
1540 \end_layout
1541
1542 \begin_layout Plain Layout
1543
1544
1545 \backslash
1546 pgfputat{
1547 \backslash
1548 pgfnodecenter{D}}{
1549 \backslash
1550 pgfbox[center,center]{$s$}}
1551 \end_layout
1552
1553 \begin_layout Plain Layout
1554
1555 \end_layout
1556
1557 \begin_layout Plain Layout
1558
1559 \end_layout
1560
1561 \begin_layout Plain Layout
1562
1563 \end_layout
1564
1565 \begin_layout Plain Layout
1566
1567
1568 \backslash
1569 color{beamerexample}
1570 \end_layout
1571
1572 \begin_layout Plain Layout
1573
1574 \end_layout
1575
1576 \begin_layout Plain Layout
1577
1578
1579 \backslash
1580 pgfsetendarrow{
1581 \backslash
1582 pgfarrowto}
1583 \end_layout
1584
1585 \begin_layout Plain Layout
1586
1587 \end_layout
1588
1589 \begin_layout Plain Layout
1590
1591
1592 \backslash
1593 pgfnodesetsepstart{2pt}
1594 \end_layout
1595
1596 \begin_layout Plain Layout
1597
1598 \end_layout
1599
1600 \begin_layout Plain Layout
1601
1602
1603 \backslash
1604 pgfnodesetsepend{4pt}
1605 \end_layout
1606
1607 \begin_layout Plain Layout
1608
1609 \end_layout
1610
1611 \begin_layout Plain Layout
1612
1613
1614 \backslash
1615 pgfnodeconnline{A}{B}
1616 \end_layout
1617
1618 \begin_layout Plain Layout
1619
1620 \end_layout
1621
1622 \begin_layout Plain Layout
1623
1624
1625 \backslash
1626 pgfnodeconnline{A}{C}
1627 \end_layout
1628
1629 \begin_layout Plain Layout
1630
1631 \end_layout
1632
1633 \begin_layout Plain Layout
1634
1635
1636 \backslash
1637 pgfnodeconnline{D}{A}
1638 \end_layout
1639
1640 \begin_layout Plain Layout
1641
1642 \end_layout
1643
1644 \begin_layout Plain Layout
1645
1646
1647 \backslash
1648 pgfnodeconnline{C}{B}
1649 \end_layout
1650
1651 \begin_layout Plain Layout
1652
1653 \end_layout
1654
1655 \begin_layout Plain Layout
1656
1657
1658 \backslash
1659 pgfnodeconnline{B}{D}
1660 \end_layout
1661
1662 \begin_layout Plain Layout
1663
1664 \end_layout
1665
1666 \begin_layout Plain Layout
1667
1668
1669 \backslash
1670 pgfnodeconnline{D}{C}
1671 \end_layout
1672
1673 \begin_layout Plain Layout
1674
1675 \end_layout
1676
1677 \begin_layout Plain Layout
1678
1679 \end_layout
1680
1681 \begin_layout Plain Layout
1682
1683 \end_layout
1684
1685 \begin_layout Plain Layout
1686
1687
1688 \backslash
1689 only<9> {
1690 \backslash
1691 pgfputat{
1692 \backslash
1693 pgfxy(5.3,1)}{
1694 \backslash
1695 pgfbox[left,center]{, $d=2$}}}
1696 \end_layout
1697
1698 \begin_layout Plain Layout
1699
1700 \end_layout
1701
1702 \begin_layout Plain Layout
1703
1704
1705 \backslash
1706 only<11>{
1707 \backslash
1708 pgfputat{
1709 \backslash
1710 pgfxy(5.3,1)}{
1711 \backslash
1712 pgfbox[left,center]{, $r=1.5$}}}
1713 \end_layout
1714
1715 \begin_layout Plain Layout
1716
1717 \end_layout
1718
1719 \begin_layout Plain Layout
1720
1721
1722 \backslash
1723 only<12>{
1724 \backslash
1725 pgfputat{
1726 \backslash
1727 pgfxy(5.3,1)}{
1728 \backslash
1729 pgfbox[left,center]{, $r=1.25$}}}
1730 \end_layout
1731
1732 \begin_layout Plain Layout
1733
1734 \end_layout
1735
1736 \begin_layout Plain Layout
1737
1738
1739 \backslash
1740 end{pgfpicture}
1741 \end_layout
1742
1743 \end_inset
1744
1745
1746 \end_layout
1747
1748 \end_deeper
1749 \begin_layout Standard
1750 \begin_inset ERT
1751 status collapsed
1752
1753 \begin_layout Plain Layout
1754
1755
1756 \backslash
1757 only<3->{
1758 \backslash
1759 column{5cm}}
1760 \end_layout
1761
1762 \end_inset
1763
1764
1765 \end_layout
1766
1767 \begin_layout ExampleBlock
1768 \begin_inset ERT
1769 status collapsed
1770
1771 \begin_layout Plain Layout
1772
1773 <only@3->{Example Output}
1774 \end_layout
1775
1776 \end_inset
1777
1778
1779 \end_layout
1780
1781 \begin_deeper
1782 \begin_layout Standard
1783 \begin_inset ERT
1784 status collapsed
1785
1786 \begin_layout Plain Layout
1787
1788
1789 \backslash
1790 begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
1791 \end_layout
1792
1793 \begin_layout Plain Layout
1794
1795 \end_layout
1796
1797 \begin_layout Plain Layout
1798
1799
1800 \backslash
1801 only<5-8,10->{
1802 \end_layout
1803
1804 \begin_layout Plain Layout
1805
1806 \end_layout
1807
1808 \begin_layout Plain Layout
1809
1810
1811 \backslash
1812 color{beamerexample}
1813 \end_layout
1814
1815 \begin_layout Plain Layout
1816
1817 \end_layout
1818
1819 \begin_layout Plain Layout
1820
1821
1822 \backslash
1823 pgfsetlinewidth{0.6pt}
1824 \end_layout
1825
1826 \begin_layout Plain Layout
1827
1828 \end_layout
1829
1830 \begin_layout Plain Layout
1831
1832
1833 \backslash
1834 graphnode{A}{
1835 \backslash
1836 pgfxy(3,1)}
1837 \end_layout
1838
1839 \begin_layout Plain Layout
1840
1841 \end_layout
1842
1843 \begin_layout Plain Layout
1844
1845
1846 \backslash
1847 graphnode{B}{
1848 \backslash
1849 pgfxy(5,1)}
1850 \end_layout
1851
1852 \begin_layout Plain Layout
1853
1854 \end_layout
1855
1856 \begin_layout Plain Layout
1857
1858
1859 \backslash
1860 graphnode{C}{
1861 \backslash
1862 pgfxy(4,0)}
1863 \end_layout
1864
1865 \begin_layout Plain Layout
1866
1867 \end_layout
1868
1869 \begin_layout Plain Layout
1870
1871
1872 \backslash
1873 graphnode{D}{
1874 \backslash
1875 pgfxy(4,2)}
1876 \end_layout
1877
1878 \begin_layout Plain Layout
1879
1880 \end_layout
1881
1882 \begin_layout Plain Layout
1883
1884 \end_layout
1885
1886 \begin_layout Plain Layout
1887
1888 \end_layout
1889
1890 \begin_layout Plain Layout
1891
1892
1893 \backslash
1894 color{white}
1895 \end_layout
1896
1897 \begin_layout Plain Layout
1898
1899 \end_layout
1900
1901 \begin_layout Plain Layout
1902
1903
1904 \backslash
1905 pgfputat{
1906 \backslash
1907 pgfnodecenter{B}}{
1908 \backslash
1909 pgfbox[center,center]{$t$}}
1910 \end_layout
1911
1912 \begin_layout Plain Layout
1913
1914 \end_layout
1915
1916 \begin_layout Plain Layout
1917
1918
1919 \backslash
1920 pgfputat{
1921 \backslash
1922 pgfnodecenter{D}}{
1923 \backslash
1924 pgfbox[center,center]{$s$}}
1925 \end_layout
1926
1927 \begin_layout Plain Layout
1928
1929 \end_layout
1930
1931 \begin_layout Plain Layout
1932
1933 \end_layout
1934
1935 \begin_layout Plain Layout
1936
1937 \end_layout
1938
1939 \begin_layout Plain Layout
1940
1941
1942 \backslash
1943 color{beamerexample}
1944 \end_layout
1945
1946 \begin_layout Plain Layout
1947
1948 \end_layout
1949
1950 \begin_layout Plain Layout
1951
1952
1953 \backslash
1954 pgfsetendarrow{
1955 \backslash
1956 pgfarrowto}
1957 \end_layout
1958
1959 \begin_layout Plain Layout
1960
1961 \end_layout
1962
1963 \begin_layout Plain Layout
1964
1965
1966 \backslash
1967 pgfnodesetsepstart{2pt}
1968 \end_layout
1969
1970 \begin_layout Plain Layout
1971
1972 \end_layout
1973
1974 \begin_layout Plain Layout
1975
1976
1977 \backslash
1978 pgfnodesetsepend{4pt}
1979 \end_layout
1980
1981 \begin_layout Plain Layout
1982
1983 \end_layout
1984
1985 \begin_layout Plain Layout
1986
1987
1988 \end_layout
1989
1990 \begin_layout Plain Layout
1991
1992 \end_layout
1993
1994 \begin_layout Plain Layout
1995
1996
1997 \backslash
1998 alert<7,12>{
1999 \backslash
2000 pgfnodeconnline{A}{B}}
2001 \end_layout
2002
2003 \begin_layout Plain Layout
2004
2005 \end_layout
2006
2007 \begin_layout Plain Layout
2008
2009
2010 \backslash
2011 alert<5,11>{
2012 \backslash
2013 pgfnodeconnline{A}{C}}
2014 \end_layout
2015
2016 \begin_layout Plain Layout
2017
2018 \end_layout
2019
2020 \begin_layout Plain Layout
2021
2022
2023 \backslash
2024 alert<5,7,11-12>{
2025 \backslash
2026 pgfnodeconnline{D}{A}}
2027 \end_layout
2028
2029 \begin_layout Plain Layout
2030
2031 \end_layout
2032
2033 \begin_layout Plain Layout
2034
2035
2036 \backslash
2037 alert<5,11>{
2038 \backslash
2039 pgfnodeconnline{C}{B}}
2040 \end_layout
2041
2042 \begin_layout Plain Layout
2043
2044 \end_layout
2045
2046 \begin_layout Plain Layout
2047
2048
2049 \backslash
2050 pgfnodeconnline{B}{D}
2051 \end_layout
2052
2053 \begin_layout Plain Layout
2054
2055 \end_layout
2056
2057 \begin_layout Plain Layout
2058
2059
2060 \backslash
2061 pgfnodeconnline{D}{C}
2062 \end_layout
2063
2064 \begin_layout Plain Layout
2065
2066 \end_layout
2067
2068 \begin_layout Plain Layout
2069
2070   }
2071 \end_layout
2072
2073 \begin_layout Plain Layout
2074
2075 \end_layout
2076
2077 \begin_layout Plain Layout
2078
2079
2080 \backslash
2081 only<3,9>{
2082 \backslash
2083 pgfputat{
2084 \backslash
2085 pgfxy(2.75,1)}{
2086 \backslash
2087 pgfbox[left,center]{
2088 \backslash
2089 alert{``Yes''}}}}
2090 \end_layout
2091
2092 \begin_layout Plain Layout
2093
2094 \end_layout
2095
2096 \begin_layout Plain Layout
2097
2098
2099 \backslash
2100 end{pgfpicture}
2101 \end_layout
2102
2103 \end_inset
2104
2105
2106 \end_layout
2107
2108 \end_deeper
2109 \end_deeper
2110 \begin_layout Standard
2111 \begin_inset ERT
2112 status collapsed
2113
2114 \begin_layout Plain Layout
2115
2116
2117 \backslash
2118 onslide<2,4,6,8,10>
2119 \end_layout
2120
2121 \end_inset
2122
2123
2124 \end_layout
2125
2126 \begin_layout Block
2127 \begin_inset ERT
2128 status collapsed
2129
2130 \begin_layout Plain Layout
2131
2132 {Variants of Path Finding Problems}
2133 \end_layout
2134
2135 \end_inset
2136
2137
2138 \end_layout
2139
2140 \begin_deeper
2141 \begin_layout Standard
2142 \begin_inset ERT
2143 status collapsed
2144
2145 \begin_layout Plain Layout
2146
2147
2148 \backslash
2149 usedescriptionitemofwidthas{Approximation Problem:}
2150 \end_layout
2151
2152 \end_inset
2153
2154
2155 \end_layout
2156
2157 \begin_layout Description
2158 Reachability
2159 \begin_inset space ~
2160 \end_inset
2161
2162 Problem:
2163 \begin_inset ERT
2164 status collapsed
2165
2166 \begin_layout Plain Layout
2167
2168 <2->
2169 \end_layout
2170
2171 \end_inset
2172
2173 Is there a path from
2174 \begin_inset Formula $s$
2175 \end_inset
2176
2177  to
2178 \begin_inset space ~
2179 \end_inset
2180
2181
2182 \begin_inset Formula $t$
2183 \end_inset
2184
2185 ?
2186 \end_layout
2187
2188 \begin_layout Description
2189 Construction
2190 \begin_inset space ~
2191 \end_inset
2192
2193 Problem:
2194 \begin_inset ERT
2195 status collapsed
2196
2197 \begin_layout Plain Layout
2198
2199 <4->
2200 \end_layout
2201
2202 \end_inset
2203
2204 Construct a path from
2205 \begin_inset Formula $s$
2206 \end_inset
2207
2208  to
2209 \begin_inset space ~
2210 \end_inset
2211
2212
2213 \begin_inset Formula $t$
2214 \end_inset
2215
2216 ?
2217 \end_layout
2218
2219 \begin_layout Description
2220 Optimization
2221 \begin_inset space ~
2222 \end_inset
2223
2224 Problem:
2225 \begin_inset ERT
2226 status collapsed
2227
2228 \begin_layout Plain Layout
2229
2230 <6->
2231 \end_layout
2232
2233 \end_inset
2234
2235 Construct a shortest path from
2236 \begin_inset Formula $s$
2237 \end_inset
2238
2239  to
2240 \begin_inset space ~
2241 \end_inset
2242
2243
2244 \begin_inset Formula $t$
2245 \end_inset
2246
2247 .
2248 \end_layout
2249
2250 \begin_layout Description
2251 Distance
2252 \begin_inset space ~
2253 \end_inset
2254
2255 Problem:
2256 \begin_inset ERT
2257 status collapsed
2258
2259 \begin_layout Plain Layout
2260
2261 <8->
2262 \end_layout
2263
2264 \end_inset
2265
2266 Is the distance of
2267 \begin_inset Formula $s$
2268 \end_inset
2269
2270  and
2271 \begin_inset space ~
2272 \end_inset
2273
2274
2275 \begin_inset Formula $t$
2276 \end_inset
2277
2278  at most
2279 \begin_inset space ~
2280 \end_inset
2281
2282
2283 \begin_inset Formula $d$
2284 \end_inset
2285
2286 ?
2287 \end_layout
2288
2289 \begin_layout Description
2290 Approximation
2291 \begin_inset space ~
2292 \end_inset
2293
2294 Problem:
2295 \begin_inset ERT
2296 status collapsed
2297
2298 \begin_layout Plain Layout
2299
2300 <10->
2301 \end_layout
2302
2303 \end_inset
2304
2305 Construct a path from
2306 \begin_inset Formula $s$
2307 \end_inset
2308
2309  to
2310 \begin_inset space ~
2311 \end_inset
2312
2313
2314 \begin_inset Formula $t$
2315 \end_inset
2316
2317  of length
2318 \begin_inset Newline newline
2319 \end_inset
2320
2321 approximately their distance.
2322 \end_layout
2323
2324 \end_deeper
2325 \end_deeper
2326 \begin_layout Section
2327 Review
2328 \end_layout
2329
2330 \begin_layout Subsection
2331 Standard Complexity Classes
2332 \end_layout
2333
2334 \begin_layout Standard
2335 \begin_inset ERT
2336 status collapsed
2337
2338 \begin_layout Plain Layout
2339
2340
2341 \backslash
2342 pgfdeclaremask{computer-mask}{beamer-g4-mask}
2343 \backslash
2344 pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer
2345 -g4}
2346 \end_layout
2347
2348 \end_inset
2349
2350
2351 \end_layout
2352
2353 \begin_layout BeginFrame
2354 The Classes L and NL are Defined via
2355 \begin_inset Newline newline
2356 \end_inset
2357
2358 Logspace Turing Machines
2359 \end_layout
2360
2361 \begin_layout Standard
2362 \begin_inset ERT
2363 status open
2364
2365 \begin_layout Plain Layout
2366
2367
2368 \backslash
2369 begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
2370 \end_layout
2371
2372 \begin_layout Plain Layout
2373
2374 \end_layout
2375
2376 \begin_layout Plain Layout
2377
2378
2379 \backslash
2380 pgfputat{
2381 \backslash
2382 pgfxy(0,4)}{
2383 \backslash
2384 tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}}
2385 \end_layout
2386
2387 \begin_layout Plain Layout
2388
2389 \end_layout
2390
2391 \begin_layout Plain Layout
2392
2393
2394 \backslash
2395 uncover<2->{
2396 \end_layout
2397
2398 \begin_layout Plain Layout
2399
2400 \end_layout
2401
2402 \begin_layout Plain Layout
2403
2404
2405 \backslash
2406 pgfputat{
2407 \backslash
2408 pgfxy(0,0.5)}{
2409 \backslash
2410 tape{}{output tape (write only)}{10690836937182}}}
2411 \end_layout
2412
2413 \begin_layout Plain Layout
2414
2415 \end_layout
2416
2417 \begin_layout Plain Layout
2418
2419
2420 \backslash
2421 uncover<3->{
2422 \end_layout
2423
2424 \begin_layout Plain Layout
2425
2426 \end_layout
2427
2428 \begin_layout Plain Layout
2429
2430
2431 \backslash
2432 pgfputat{
2433 \backslash
2434 pgfxy(7,2)}{
2435 \backslash
2436 shorttape{work tape (read/write), $O(
2437 \backslash
2438 log n)$ symbols}{}{42}}
2439 \end_layout
2440
2441 \begin_layout Plain Layout
2442
2443 \end_layout
2444
2445 \begin_layout Plain Layout
2446
2447
2448 \backslash
2449 pgfputat{
2450 \backslash
2451 pgfxy(1.75,2.5)}{
2452 \backslash
2453 pgfbox[center,center]{
2454 \backslash
2455 pgfuseimage{computer}}}
2456 \end_layout
2457
2458 \begin_layout Plain Layout
2459
2460 \end_layout
2461
2462 \begin_layout Plain Layout
2463
2464   }
2465 \end_layout
2466
2467 \begin_layout Plain Layout
2468
2469 \end_layout
2470
2471 \begin_layout Plain Layout
2472
2473
2474 \backslash
2475 pgfsetlinewidth{0.6pt}
2476 \end_layout
2477
2478 \begin_layout Plain Layout
2479
2480 \end_layout
2481
2482 \begin_layout Plain Layout
2483
2484 \end_layout
2485
2486 \begin_layout Plain Layout
2487
2488 \end_layout
2489
2490 \begin_layout Plain Layout
2491
2492
2493 \backslash
2494 color{structure}
2495 \end_layout
2496
2497 \begin_layout Plain Layout
2498
2499 \end_layout
2500
2501 \begin_layout Plain Layout
2502
2503
2504 \backslash
2505 pgfsetendarrow{
2506 \backslash
2507 pgfarrowto}
2508 \end_layout
2509
2510 \begin_layout Plain Layout
2511
2512 \end_layout
2513
2514 \begin_layout Plain Layout
2515
2516
2517 \backslash
2518 pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
2519 \end_layout
2520
2521 \begin_layout Plain Layout
2522
2523 \end_layout
2524
2525 \begin_layout Plain Layout
2526
2527
2528 \backslash
2529 uncover<2->{
2530 \backslash
2531 pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
2532 \end_layout
2533
2534 \begin_layout Plain Layout
2535
2536 \end_layout
2537
2538 \begin_layout Plain Layout
2539
2540
2541 \backslash
2542 uncover<3->{
2543 \backslash
2544 pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
2545 \end_layout
2546
2547 \begin_layout Plain Layout
2548
2549 \end_layout
2550
2551 \begin_layout Plain Layout
2552
2553
2554 \backslash
2555 end{pgfpicture}
2556 \end_layout
2557
2558 \end_inset
2559
2560
2561 \end_layout
2562
2563 \begin_layout BeginFrame
2564 Logspace Turing Machines Are Quite Powerful
2565 \end_layout
2566
2567 \begin_layout Block
2568 \begin_inset ERT
2569 status collapsed
2570
2571 \begin_layout Plain Layout
2572
2573 {Deterministic logspace machines can compute}
2574 \end_layout
2575
2576 \end_inset
2577
2578
2579 \end_layout
2580
2581 \begin_deeper
2582 \begin_layout Itemize
2583 addition, multiplication, and even division
2584 \end_layout
2585
2586 \begin_layout Itemize
2587 reductions used in completeness proofs,
2588 \end_layout
2589
2590 \begin_layout Itemize
2591 reachability in forests.
2592 \end_layout
2593
2594 \end_deeper
2595 \begin_layout Pause
2596
2597 \end_layout
2598
2599 \begin_layout Block
2600 \begin_inset ERT
2601 status collapsed
2602
2603 \begin_layout Plain Layout
2604
2605 {Non-deterministic logspace machines can compute}
2606 \end_layout
2607
2608 \end_inset
2609
2610
2611 \end_layout
2612
2613 \begin_deeper
2614 \begin_layout Itemize
2615 reachability in graphs,
2616 \end_layout
2617
2618 \begin_layout Itemize
2619 non-reachability in graphs,
2620 \end_layout
2621
2622 \begin_layout Itemize
2623 satisfiability with two literals per clause.
2624 \end_layout
2625
2626 \end_deeper
2627 \begin_layout BeginFrame
2628 \begin_inset ERT
2629 status collapsed
2630
2631 \begin_layout Plain Layout
2632
2633 <1>[label=hierarchy]
2634 \end_layout
2635
2636 \end_inset
2637
2638 The Complexity Class Hierarchy
2639 \end_layout
2640
2641 \begin_layout Standard
2642 \begin_inset ERT
2643 status collapsed
2644
2645 \begin_layout Plain Layout
2646
2647
2648 \backslash
2649 begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
2650 \end_layout
2651
2652 \begin_layout Plain Layout
2653
2654 \end_layout
2655
2656 \begin_layout Plain Layout
2657
2658
2659 \backslash
2660 pgfsetlinewidth{0.8pt}
2661 \end_layout
2662
2663 \begin_layout Plain Layout
2664
2665 \end_layout
2666
2667 \begin_layout Plain Layout
2668
2669
2670 \backslash
2671 heap{5.5}{3.5}{$
2672 \backslash
2673 Class P$}{black}{1}
2674 \end_layout
2675
2676 \begin_layout Plain Layout
2677
2678 \end_layout
2679
2680 \begin_layout Plain Layout
2681
2682
2683 \backslash
2684 pgfsetdash{{2pt}}{0pt}
2685 \end_layout
2686
2687 \begin_layout Plain Layout
2688
2689 \end_layout
2690
2691 \begin_layout Plain Layout
2692
2693
2694 \backslash
2695 only<2->{
2696 \backslash
2697 heap{4.5}{3}{$
2698 \backslash
2699 Class{NC}^2$}{black!50!structure}{2}}
2700 \end_layout
2701
2702 \begin_layout Plain Layout
2703
2704 \end_layout
2705
2706 \begin_layout Plain Layout
2707
2708
2709 \backslash
2710 heap{3.5}{2.5}{$
2711 \backslash
2712 Class{NL}$}{black!50!structure}{3}
2713 \end_layout
2714
2715 \begin_layout Plain Layout
2716
2717 \end_layout
2718
2719 \begin_layout Plain Layout
2720
2721
2722 \backslash
2723 heap{2.5}{2}{$
2724 \backslash
2725 Class{L}$}{black!50!structure}{4}
2726 \end_layout
2727
2728 \begin_layout Plain Layout
2729
2730 \end_layout
2731
2732 \begin_layout Plain Layout
2733
2734
2735 \backslash
2736 only<2->{
2737 \backslash
2738 heap{1.75}{1.5}{$
2739 \backslash
2740 vphantom{A}
2741 \backslash
2742 smash{
2743 \backslash
2744 Class{NC}^1}$}{black!50!structure}{5}}
2745 \end_layout
2746
2747 \begin_layout Plain Layout
2748
2749 \end_layout
2750
2751 \begin_layout Plain Layout
2752
2753
2754 \backslash
2755 pgfsetdash{}{0pt}
2756 \end_layout
2757
2758 \begin_layout Plain Layout
2759
2760 \end_layout
2761
2762 \begin_layout Plain Layout
2763
2764
2765 \backslash
2766 only<2->{
2767 \backslash
2768 heap{1.1}{1}{$
2769 \backslash
2770 vphantom{A}
2771 \backslash
2772 smash{
2773 \backslash
2774 Class{AC}^0}$}{black}{6}}
2775 \end_layout
2776
2777 \begin_layout Plain Layout
2778
2779 \end_layout
2780
2781 \begin_layout Plain Layout
2782
2783 \end_layout
2784
2785 \begin_layout Plain Layout
2786
2787 \end_layout
2788
2789 \begin_layout Plain Layout
2790
2791
2792 \backslash
2793 pgfsetlinewidth{1.0pt}
2794 \end_layout
2795
2796 \begin_layout Plain Layout
2797
2798 \end_layout
2799
2800 \begin_layout Plain Layout
2801
2802
2803 \backslash
2804 color{black}
2805 \end_layout
2806
2807 \begin_layout Plain Layout
2808
2809 \end_layout
2810
2811 \begin_layout Plain Layout
2812
2813
2814 \backslash
2815 pgfxyline(-5,0)(5,0)
2816 \end_layout
2817
2818 \begin_layout Plain Layout
2819
2820 \end_layout
2821
2822 \begin_layout Plain Layout
2823
2824 \end_layout
2825
2826 \begin_layout Plain Layout
2827
2828 \end_layout
2829
2830 \begin_layout Plain Layout
2831
2832
2833 \backslash
2834 only<1-2>{
2835 \backslash
2836 langat{3.375}{$
2837 \backslash
2838 Lang{reach}$}}
2839 \end_layout
2840
2841 \begin_layout Plain Layout
2842
2843 \end_layout
2844
2845 \begin_layout Plain Layout
2846
2847
2848 \backslash
2849 only<1-2>{
2850 \backslash
2851 langat{2.375}{$
2852 \backslash
2853 Lang{reach}_{
2854 \backslash
2855 operatorname{forest}}$}}
2856 \end_layout
2857
2858 \begin_layout Plain Layout
2859
2860 \end_layout
2861
2862 \begin_layout Plain Layout
2863
2864 \end_layout
2865
2866 \begin_layout Plain Layout
2867
2868 \end_layout
2869
2870 \begin_layout Plain Layout
2871
2872
2873 \backslash
2874 only<2>{
2875 \backslash
2876 langat{0.975}{$
2877 \backslash
2878 Lang{addition}$}}
2879 \end_layout
2880
2881 \begin_layout Plain Layout
2882
2883 \end_layout
2884
2885 \begin_layout Plain Layout
2886
2887
2888 \backslash
2889 only<2>{
2890 \backslash
2891 langatother{1.6}{
2892 \backslash
2893 vbox{
2894 \backslash
2895 hbox{$
2896 \backslash
2897 Lang{division}$,}
2898 \backslash
2899 hbox{$
2900 \backslash
2901 Lang{parity}$}}}}
2902 \end_layout
2903
2904 \begin_layout Plain Layout
2905
2906 \end_layout
2907
2908 \begin_layout Plain Layout
2909
2910
2911 \backslash
2912 only<3-5>{
2913 \backslash
2914 langat{3.375}{
2915 \backslash
2916 vbox{
2917 \backslash
2918 hbox{$
2919 \backslash
2920 Lang{distance}$,}
2921 \backslash
2922 hbox{$
2923 \backslash
2924 Lang{reach}$}}}}
2925 \end_layout
2926
2927 \begin_layout Plain Layout
2928
2929 \end_layout
2930
2931 \begin_layout Plain Layout
2932
2933
2934 \backslash
2935 only<4->{
2936 \backslash
2937 langatother{2.375}{
2938 \backslash
2939 vbox{
2940 \backslash
2941 ignorespaces
2942 \end_layout
2943
2944 \begin_layout Plain Layout
2945
2946 \end_layout
2947
2948 \begin_layout Plain Layout
2949
2950
2951 \backslash
2952 hbox{$
2953 \backslash
2954 Lang{distance}_{
2955 \backslash
2956 operatorname{forest}}$,}
2957 \backslash
2958 ignorespaces
2959 \end_layout
2960
2961 \begin_layout Plain Layout
2962
2963 \end_layout
2964
2965 \begin_layout Plain Layout
2966
2967
2968 \backslash
2969 hbox{$
2970 \backslash
2971 Lang{reach}_{
2972 \backslash
2973 operatorname{forest}}$,}
2974 \backslash
2975 ignorespaces
2976 \end_layout
2977
2978 \begin_layout Plain Layout
2979
2980 \end_layout
2981
2982 \begin_layout Plain Layout
2983
2984
2985 \backslash
2986 hbox{$
2987 \backslash
2988 Lang{distance}_{
2989 \backslash
2990 operatorname{path}}$,}
2991 \backslash
2992 ignorespaces
2993 \end_layout
2994
2995 \begin_layout Plain Layout
2996
2997 \end_layout
2998
2999 \begin_layout Plain Layout
3000
3001
3002 \backslash
3003 hbox{$
3004 \backslash
3005 Lang{reach}_{
3006 \backslash
3007 operatorname{path}}$}}}}
3008 \end_layout
3009
3010 \begin_layout Plain Layout
3011
3012 \end_layout
3013
3014 \begin_layout Plain Layout
3015
3016
3017 \backslash
3018 only<5->{
3019 \backslash
3020 langat{0.975}{$
3021 \backslash
3022 Lang{reach}_{
3023 \backslash
3024 operatorname{tourn}}$}}
3025 \end_layout
3026
3027 \begin_layout Plain Layout
3028
3029 \end_layout
3030
3031 \begin_layout Plain Layout
3032
3033
3034 \backslash
3035 only<6->{
3036 \backslash
3037 langat{3.375}{
3038 \backslash
3039 vbox{
3040 \backslash
3041 ignorespaces
3042 \end_layout
3043
3044 \begin_layout Plain Layout
3045
3046 \end_layout
3047
3048 \begin_layout Plain Layout
3049
3050
3051 \backslash
3052 hbox{$
3053 \backslash
3054 Lang{distance}_{
3055 \backslash
3056 operatorname{tourn}}$,}
3057 \backslash
3058 ignorespaces
3059 \end_layout
3060
3061 \begin_layout Plain Layout
3062
3063 \end_layout
3064
3065 \begin_layout Plain Layout
3066
3067
3068 \backslash
3069 hbox{$
3070 \backslash
3071 Lang{distance}$,}
3072 \backslash
3073 ignorespaces
3074 \end_layout
3075
3076 \begin_layout Plain Layout
3077
3078 \end_layout
3079
3080 \begin_layout Plain Layout
3081
3082
3083 \backslash
3084 hbox{$
3085 \backslash
3086 Lang{reach}$}}}}
3087 \end_layout
3088
3089 \begin_layout Plain Layout
3090
3091 \end_layout
3092
3093 \begin_layout Plain Layout
3094
3095
3096 \backslash
3097 only<7->{
3098 \backslash
3099 pgfsetdash{{1pt}}{0pt}
3100 \backslash
3101 langat{2.375}{``$
3102 \backslash
3103 Lang{approx}_{
3104 \backslash
3105 operatorname{tourn}}$''}}
3106 \end_layout
3107
3108 \begin_layout Plain Layout
3109
3110 \end_layout
3111
3112 \begin_layout Plain Layout
3113
3114
3115 \backslash
3116 end{pgfpicture}
3117 \end_layout
3118
3119 \end_inset
3120
3121
3122 \end_layout
3123
3124 \begin_layout BeginFrame
3125 The Circuit Complexity Classes AC
3126 \begin_inset Formula $^{0}$
3127 \end_inset
3128
3129 , NC
3130 \begin_inset Formula $^{1}$
3131 \end_inset
3132
3133 , and NC
3134 \begin_inset Formula $^{2}$
3135 \end_inset
3136
3137
3138 \begin_inset Newline newline
3139 \end_inset
3140
3141 Limit the Circuit Depth
3142 \end_layout
3143
3144 \begin_layout Standard
3145 \begin_inset ERT
3146 status collapsed
3147
3148 \begin_layout Plain Layout
3149
3150
3151 \backslash
3152 setlength
3153 \backslash
3154 leftmargini{1em}
3155 \end_layout
3156
3157 \begin_layout Plain Layout
3158
3159 \end_layout
3160
3161 \begin_layout Plain Layout
3162
3163
3164 \backslash
3165 nointerlineskip
3166 \end_layout
3167
3168 \end_inset
3169
3170
3171 \end_layout
3172
3173 \begin_layout Columns
3174 \begin_inset ERT
3175 status collapsed
3176
3177 \begin_layout Plain Layout
3178
3179 [t]
3180 \end_layout
3181
3182 \end_inset
3183
3184
3185 \end_layout
3186
3187 \begin_deeper
3188 \begin_layout Column
3189 3.6cm
3190 \end_layout
3191
3192 \begin_layout Block
3193 \begin_inset ERT
3194 status collapsed
3195
3196 \begin_layout Plain Layout
3197
3198 {
3199 \end_layout
3200
3201 \end_inset
3202
3203 Circuit Class
3204 \begin_inset Formula $\Class{AC}^{0}$
3205 \end_inset
3206
3207
3208 \begin_inset ERT
3209 status collapsed
3210
3211 \begin_layout Plain Layout
3212
3213 }
3214 \end_layout
3215
3216 \end_inset
3217
3218
3219 \end_layout
3220
3221 \begin_deeper
3222 \begin_layout Itemize
3223 \begin_inset Formula $O(1)$
3224 \end_inset
3225
3226  depth
3227 \end_layout
3228
3229 \begin_layout Itemize
3230 unbounded fan-in
3231 \end_layout
3232
3233 \end_deeper
3234 \begin_layout Examples
3235
3236 \end_layout
3237
3238 \begin_deeper
3239 \begin_layout Itemize
3240 \begin_inset Formula $\Lang{addition}\in\Class{AC}^{0}$
3241 \end_inset
3242
3243 .
3244 \end_layout
3245
3246 \begin_layout Itemize
3247 \begin_inset Formula $\Lang{parity}\notin\Class{AC}^{0}$
3248 \end_inset
3249
3250 .
3251 \end_layout
3252
3253 \end_deeper
3254 \begin_layout Pause
3255
3256 \end_layout
3257
3258 \begin_layout Column
3259 3.6cm
3260 \end_layout
3261
3262 \begin_layout Block
3263 \begin_inset ERT
3264 status collapsed
3265
3266 \begin_layout Plain Layout
3267
3268 {
3269 \end_layout
3270
3271 \end_inset
3272
3273 Circuit Class
3274 \begin_inset Formula $\Class{NC}^{1}$
3275 \end_inset
3276
3277
3278 \begin_inset ERT
3279 status collapsed
3280
3281 \begin_layout Plain Layout
3282
3283 }
3284 \end_layout
3285
3286 \end_inset
3287
3288
3289 \end_layout
3290
3291 \begin_deeper
3292 \begin_layout Itemize
3293 \begin_inset Formula $O(\log n)$
3294 \end_inset
3295
3296  depth
3297 \end_layout
3298
3299 \begin_layout Itemize
3300 bounded fan-in
3301 \end_layout
3302
3303 \end_deeper
3304 \begin_layout Examples
3305
3306 \end_layout
3307
3308 \begin_deeper
3309 \begin_layout Itemize
3310 \begin_inset Formula $\Lang{parity}\in\Class{NC}^{1}$
3311 \end_inset
3312
3313 .
3314 \end_layout
3315
3316 \begin_layout Itemize
3317 \begin_inset Formula $\Lang{mutiply}\in\Class{NC}^{1}$
3318 \end_inset
3319
3320 .
3321 \end_layout
3322
3323 \begin_layout Itemize
3324 \begin_inset Formula $\Lang{divide}\in\Class{NC}^{1}$
3325 \end_inset
3326
3327 .
3328 \end_layout
3329
3330 \end_deeper
3331 \begin_layout Pause
3332
3333 \end_layout
3334
3335 \begin_layout Column
3336 3.6cm
3337 \end_layout
3338
3339 \begin_layout Block
3340 \begin_inset ERT
3341 status collapsed
3342
3343 \begin_layout Plain Layout
3344
3345 {
3346 \end_layout
3347
3348 \end_inset
3349
3350 Circuit Class
3351 \begin_inset Formula $\Class{NC}^{2}$
3352 \end_inset
3353
3354
3355 \begin_inset ERT
3356 status collapsed
3357
3358 \begin_layout Plain Layout
3359
3360 }
3361 \end_layout
3362
3363 \end_inset
3364
3365
3366 \end_layout
3367
3368 \begin_deeper
3369 \begin_layout Itemize
3370 \begin_inset Formula $O(\log^{2}n)$
3371 \end_inset
3372
3373  depth
3374 \end_layout
3375
3376 \begin_layout Itemize
3377 bounded fan-in
3378 \end_layout
3379
3380 \end_deeper
3381 \begin_layout Examples
3382
3383 \end_layout
3384
3385 \begin_deeper
3386 \begin_layout Itemize
3387 \begin_inset Formula $\Class{NL}\subseteq\Class{NC}^{2}$
3388 \end_inset
3389
3390 .
3391 \end_layout
3392
3393 \end_deeper
3394 \end_deeper
3395 \begin_layout AgainFrame
3396 \begin_inset ERT
3397 status collapsed
3398
3399 \begin_layout Plain Layout
3400
3401 <2>
3402 \end_layout
3403
3404 \end_inset
3405
3406 hierarchy
3407 \end_layout
3408
3409 \begin_layout Subsection
3410 Standard Complexity Results on Finding Paths
3411 \end_layout
3412
3413 \begin_layout BeginFrame
3414 All Variants of Finding Paths in Directed Graphs
3415 \begin_inset Newline newline
3416 \end_inset
3417
3418 Are Equally Difficult
3419 \end_layout
3420
3421 \begin_layout Fact
3422 \begin_inset Formula $\Lang{reach}$
3423 \end_inset
3424
3425  and
3426 \begin_inset Formula $\Lang{distance}$
3427 \end_inset
3428
3429  are
3430 \begin_inset Formula $\Class{NL}$
3431 \end_inset
3432
3433 -complete.
3434
3435 \end_layout
3436
3437 \begin_layout Pause
3438
3439 \end_layout
3440
3441 \begin_layout Corollary
3442 For directed graphs, we can solve
3443 \end_layout
3444
3445 \begin_deeper
3446 \begin_layout Itemize
3447 the reachability problem in logspace iff
3448 \begin_inset Formula $\Class{L}=\Class{NL}$
3449 \end_inset
3450
3451 .
3452 \end_layout
3453
3454 \begin_layout Itemize
3455 the construction problem in logspace iff
3456 \begin_inset Formula $\Class{L}=\Class{NL}$
3457 \end_inset
3458
3459 .
3460 \end_layout
3461
3462 \begin_layout Itemize
3463 the optimization problem in logspace iff
3464 \begin_inset Formula $\Class{L}=\Class{NL}$
3465 \end_inset
3466
3467 .
3468 \end_layout
3469
3470 \begin_layout Itemize
3471 the approximation problem in logspace iff
3472 \begin_inset Formula $\Class{L}=\Class{NL}$
3473 \end_inset
3474
3475 .
3476 \end_layout
3477
3478 \end_deeper
3479 \begin_layout AgainFrame
3480 \begin_inset ERT
3481 status collapsed
3482
3483 \begin_layout Plain Layout
3484
3485 <3>
3486 \end_layout
3487
3488 \end_inset
3489
3490 hierarchy
3491 \end_layout
3492
3493 \begin_layout BeginFrame
3494 FindingPaths in Forests and Directed Paths is Easy,
3495 \begin_inset Newline newline
3496 \end_inset
3497
3498 But Not Trivial
3499 \end_layout
3500
3501 \begin_layout Fact
3502 \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$
3503 \end_inset
3504
3505  and
3506 \begin_inset Formula $\Lang{distance}_{\operatorname{forest}}$
3507 \end_inset
3508
3509  are
3510 \begin_inset Formula $\Class{L}$
3511 \end_inset
3512
3513 -complete.
3514 \end_layout
3515
3516 \begin_layout Separator
3517
3518 \end_layout
3519
3520 \begin_layout Fact
3521 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3522 \end_inset
3523
3524  and
3525 \begin_inset Formula $\Lang{distance}_{\operatorname{path}}$
3526 \end_inset
3527
3528  are
3529 \begin_inset Formula $\Class{L}$
3530 \end_inset
3531
3532 -complete.
3533 \end_layout
3534
3535 \begin_layout AgainFrame
3536 \begin_inset ERT
3537 status collapsed
3538
3539 \begin_layout Plain Layout
3540
3541 <4>
3542 \end_layout
3543
3544 \end_inset
3545
3546 hierarchy
3547 \end_layout
3548
3549 \begin_layout Section
3550 Finding Paths in Tournaments
3551 \end_layout
3552
3553 \begin_layout Subsection
3554 Complexity of: Does a Path Exist?
3555 \end_layout
3556
3557 \begin_layout BeginFrame
3558 Definition of the Tournament Reachability Problem
3559 \end_layout
3560
3561 \begin_layout Definition
3562 Let
3563 \color none
3564
3565 \color red
3566
3567 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}$
3568 \end_inset
3569
3570
3571 \color none
3572
3573 \color inherit
3574 contain all triples
3575 \begin_inset Formula $(T,s,t)$
3576 \end_inset
3577
3578  such that
3579 \end_layout
3580
3581 \begin_deeper
3582 \begin_layout Enumerate
3583 \begin_inset Formula $T=(V,E)$
3584 \end_inset
3585
3586  is a tournament and
3587 \end_layout
3588
3589 \begin_layout Enumerate
3590 there exists a path from
3591 \begin_inset space ~
3592 \end_inset
3593
3594
3595 \begin_inset Formula $s$
3596 \end_inset
3597
3598  to
3599 \begin_inset space ~
3600 \end_inset
3601
3602
3603 \begin_inset Formula $t$
3604 \end_inset
3605
3606 .
3607 \end_layout
3608
3609 \end_deeper
3610 \begin_layout BeginFrame
3611 The Tournament Reachability Problem is Very Easy
3612 \end_layout
3613
3614 \begin_layout Theorem
3615 \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$
3616 \end_inset
3617
3618 .
3619 \end_layout
3620
3621 \begin_layout Pause
3622
3623 \end_layout
3624
3625 \begin_layout AlertBlock
3626 \begin_inset ERT
3627 status collapsed
3628
3629 \begin_layout Plain Layout
3630
3631 {Implications}
3632 \end_layout
3633
3634 \end_inset
3635
3636
3637 \end_layout
3638
3639 \begin_deeper
3640 \begin_layout Itemize
3641 The problem is
3642 \begin_inset Quotes eld
3643 \end_inset
3644
3645 easier
3646 \begin_inset Quotes erd
3647 \end_inset
3648
3649  than
3650 \begin_inset Formula $\Lang{reach}$
3651 \end_inset
3652
3653  and even
3654 \begin_inset Formula $\Lang{reach}_{\operatorname{path}}$
3655 \end_inset
3656
3657 .
3658 \end_layout
3659
3660 \begin_layout Itemize
3661 \begin_inset Formula $\Lang{reach}\not\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{reach}_{\operatorname{tourn}}$
3662 \end_inset
3663
3664 .
3665 \end_layout
3666
3667 \end_deeper
3668 \begin_layout AgainFrame
3669 \begin_inset ERT
3670 status collapsed
3671
3672 \begin_layout Plain Layout
3673
3674 <5>
3675 \end_layout
3676
3677 \end_inset
3678
3679 hierarchy
3680 \end_layout
3681
3682 \begin_layout Subsection
3683 Complexity of: Construct a Shortest Path
3684 \end_layout
3685
3686 \begin_layout BeginFrame
3687 Finding a Shortest Path Is as Difficult as
3688 \begin_inset Newline newline
3689 \end_inset
3690
3691 the Distance Problem
3692 \end_layout
3693
3694 \begin_layout Definition
3695 Let
3696 \color none
3697
3698 \color red
3699
3700 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3701 \end_inset
3702
3703
3704 \color none
3705
3706 \color inherit
3707 contain all tuples
3708 \begin_inset Formula $(T,s,t,d)$
3709 \end_inset
3710
3711  such that
3712 \end_layout
3713
3714 \begin_deeper
3715 \begin_layout Enumerate
3716 \begin_inset Formula $T=(V,E)$
3717 \end_inset
3718
3719  is a tournament in which
3720 \end_layout
3721
3722 \begin_layout Enumerate
3723 the distance of
3724 \begin_inset Formula $s$
3725 \end_inset
3726
3727  and
3728 \begin_inset space ~
3729 \end_inset
3730
3731
3732 \begin_inset Formula $t$
3733 \end_inset
3734
3735  is at most
3736 \begin_inset space ~
3737 \end_inset
3738
3739
3740 \begin_inset Formula $d$
3741 \end_inset
3742
3743 .
3744 \end_layout
3745
3746 \end_deeper
3747 \begin_layout BeginFrame
3748 The Tournament Distance Problem is Hard
3749 \end_layout
3750
3751 \begin_layout Theorem
3752 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3753 \end_inset
3754
3755  is
3756 \begin_inset Formula $\Class{NL}$
3757 \end_inset
3758
3759 -complete.
3760 \end_layout
3761
3762 \begin_layout Standard
3763 \begin_inset space \hfill{}
3764 \end_inset
3765
3766
3767 \begin_inset ERT
3768 status collapsed
3769
3770 \begin_layout Plain Layout
3771
3772
3773 \backslash
3774 hyperlink{hierarchy<6>}{
3775 \backslash
3776 beamerskipbutton{Skip Proof}}
3777 \end_layout
3778
3779 \end_inset
3780
3781
3782 \end_layout
3783
3784 \begin_layout Pause
3785
3786 \end_layout
3787
3788 \begin_layout Corollary
3789 Shortest path in tournaments can be constructed
3790 \begin_inset Newline newline
3791 \end_inset
3792
3793 in logarithmic space, iff
3794 \begin_inset Formula $\Class{L}=\Class{NL}$
3795 \end_inset
3796
3797 .
3798 \end_layout
3799
3800 \begin_layout Pause
3801
3802 \end_layout
3803
3804 \begin_layout Corollary
3805 \begin_inset Formula $\Lang{distance}\le_{\operatorname{m}}^{\Class{AC}^{0}}\Lang{distance}_{\operatorname{tourn}}$
3806 \end_inset
3807
3808 .
3809 \end_layout
3810
3811 \begin_layout BeginFrame
3812 Proof That
3813 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3814 \end_inset
3815
3816  is NL-complete
3817 \end_layout
3818
3819 \begin_layout Standard
3820 \begin_inset ERT
3821 status collapsed
3822
3823 \begin_layout Plain Layout
3824
3825
3826 \backslash
3827 nointerlineskip
3828 \end_layout
3829
3830 \end_inset
3831
3832
3833 \end_layout
3834
3835 \begin_layout Columns
3836 \begin_inset ERT
3837 status collapsed
3838
3839 \begin_layout Plain Layout
3840
3841 [t,onlytextwidth]
3842 \end_layout
3843
3844 \end_inset
3845
3846
3847 \end_layout
3848
3849 \begin_deeper
3850 \begin_layout Column
3851 5.7cm
3852 \end_layout
3853
3854 \begin_layout Standard
3855 \begin_inset ERT
3856 status collapsed
3857
3858 \begin_layout Plain Layout
3859
3860
3861 \backslash
3862 setlength
3863 \backslash
3864 leftmargini{1.5em}
3865 \end_layout
3866
3867 \end_inset
3868
3869
3870 \end_layout
3871
3872 \begin_layout Block
3873 \begin_inset ERT
3874 status collapsed
3875
3876 \begin_layout Plain Layout
3877
3878 {
3879 \end_layout
3880
3881 \end_inset
3882
3883 Reduce
3884 \begin_inset Formula $\Lang{reach}$
3885 \end_inset
3886
3887  to
3888 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$
3889 \end_inset
3890
3891
3892 \begin_inset ERT
3893 status collapsed
3894
3895 \begin_layout Plain Layout
3896
3897 }
3898 \end_layout
3899
3900 \end_inset
3901
3902
3903 \end_layout
3904
3905 \begin_deeper
3906 \begin_layout Enumerate
3907 \begin_inset ERT
3908 status collapsed
3909
3910 \begin_layout Plain Layout
3911
3912 <alert@1>
3913 \end_layout
3914
3915 \end_inset
3916
3917 Is input
3918 \begin_inset Formula $(G,s,t)$
3919 \end_inset
3920
3921  in
3922 \begin_inset Formula $\Lang{reach}$
3923 \end_inset
3924
3925 ?
3926 \end_layout
3927
3928 \begin_layout Enumerate
3929 \begin_inset ERT
3930 status collapsed
3931
3932 \begin_layout Plain Layout
3933
3934 <2-| alert@2-8>
3935 \end_layout
3936
3937 \end_inset
3938
3939 Map
3940 \begin_inset Formula $G$
3941 \end_inset
3942
3943  to
3944 \begin_inset Formula $G'$
3945 \end_inset
3946
3947 .
3948 \end_layout
3949
3950 \begin_layout Enumerate
3951 \begin_inset ERT
3952 status collapsed
3953
3954 \begin_layout Plain Layout
3955
3956 <9-| alert@9>
3957 \end_layout
3958
3959 \end_inset
3960
3961 Query:
3962 \begin_inset Newline newline
3963 \end_inset
3964
3965
3966 \begin_inset Formula $(G',s',t',3)\in\Lang{distance}_{\operatorname{tourn}}$
3967 \end_inset
3968
3969 ?
3970 \end_layout
3971
3972 \end_deeper
3973 \begin_layout Separator
3974
3975 \end_layout
3976
3977 \begin_layout Block
3978 \begin_inset ERT
3979 status collapsed
3980
3981 \begin_layout Plain Layout
3982
3983 {
3984 \end_layout
3985
3986 \end_inset
3987
3988 Correctness
3989 \begin_inset ERT
3990 status collapsed
3991
3992 \begin_layout Plain Layout
3993
3994 }
3995 \end_layout
3996
3997 \end_inset
3998
3999
4000 \begin_inset ERT
4001 status collapsed
4002
4003 \begin_layout Plain Layout
4004
4005 <10->
4006 \end_layout
4007
4008 \end_inset
4009
4010
4011 \end_layout
4012
4013 \begin_deeper
4014 \begin_layout Enumerate
4015 \begin_inset ERT
4016 status collapsed
4017
4018 \begin_layout Plain Layout
4019
4020 <10-| alert@10-11>
4021 \end_layout
4022
4023 \end_inset
4024
4025 A path in
4026 \begin_inset space ~
4027 \end_inset
4028
4029
4030 \begin_inset Formula $G$
4031 \end_inset
4032
4033  induces
4034 \begin_inset Newline newline
4035 \end_inset
4036
4037 a length-3 path in
4038 \begin_inset space ~
4039 \end_inset
4040
4041
4042 \begin_inset Formula $G'$
4043 \end_inset
4044
4045 .
4046 \end_layout
4047
4048 \begin_layout Enumerate
4049 \begin_inset ERT
4050 status collapsed
4051
4052 \begin_layout Plain Layout
4053
4054 <12-| alert@12-13>
4055 \end_layout
4056
4057 \end_inset
4058
4059 A length-3 path in
4060 \begin_inset space ~
4061 \end_inset
4062
4063
4064 \begin_inset Formula $G'$
4065 \end_inset
4066
4067  induces
4068 \begin_inset Newline newline
4069 \end_inset
4070
4071 a path in
4072 \begin_inset space ~
4073 \end_inset
4074
4075
4076 \begin_inset Formula $G'$
4077 \end_inset
4078
4079 .
4080 \end_layout
4081
4082 \end_deeper
4083 \begin_layout Column
4084 4.5cm
4085 \end_layout
4086
4087 \begin_layout Example
4088 \begin_inset ERT
4089 status collapsed
4090
4091 \begin_layout Plain Layout
4092
4093
4094 \backslash
4095 begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm}
4096 \end_layout
4097
4098 \begin_layout Plain Layout
4099
4100 \end_layout
4101
4102 \begin_layout Plain Layout
4103
4104
4105 \backslash
4106 color{beamerexample}
4107 \end_layout
4108
4109 \begin_layout Plain Layout
4110
4111 \end_layout
4112
4113 \begin_layout Plain Layout
4114
4115
4116 \backslash
4117 pgfsetlinewidth{0.6pt}
4118 \end_layout
4119
4120 \begin_layout Plain Layout
4121
4122 \end_layout
4123
4124 \begin_layout Plain Layout
4125
4126
4127 \backslash
4128 graphnode{A}{
4129 \backslash
4130 pgfxy(1,3.3)}
4131 \end_layout
4132
4133 \begin_layout Plain Layout
4134
4135 \end_layout
4136
4137 \begin_layout Plain Layout
4138
4139
4140 \backslash
4141 graphnode{B}{
4142 \backslash
4143 pgfxy(2,3.3)}
4144 \end_layout
4145
4146 \begin_layout Plain Layout
4147
4148 \end_layout
4149
4150 \begin_layout Plain Layout
4151
4152
4153 \backslash
4154 graphnode{C}{
4155 \backslash
4156 pgfxy(3,3.3)}
4157 \end_layout
4158
4159 \begin_layout Plain Layout
4160
4161 \end_layout
4162
4163 \begin_layout Plain Layout
4164
4165
4166 \backslash
4167 graphnode{D}{
4168 \backslash
4169 pgfxy(4,3.3)}
4170 \end_layout
4171
4172 \begin_layout Plain Layout
4173
4174 \end_layout
4175
4176 \begin_layout Plain Layout
4177
4178 \end_layout
4179
4180 \begin_layout Plain Layout
4181
4182 \end_layout
4183
4184 \begin_layout Plain Layout
4185
4186
4187 \backslash
4188 color{white}
4189 \end_layout
4190
4191 \begin_layout Plain Layout
4192
4193 \end_layout
4194
4195 \begin_layout Plain Layout
4196
4197
4198 \backslash
4199 pgfputat{
4200 \backslash
4201 pgfnodecenter{A}}{
4202 \backslash
4203 pgfbox[center,center]{$s$}}
4204 \end_layout
4205
4206 \begin_layout Plain Layout
4207
4208 \end_layout
4209
4210 \begin_layout Plain Layout
4211
4212
4213 \backslash
4214 pgfputat{
4215 \backslash
4216 pgfnodecenter{D}}{
4217 \backslash
4218 pgfbox[center,center]{$t$}}
4219 \end_layout
4220
4221 \begin_layout Plain Layout
4222
4223 \end_layout
4224
4225 \begin_layout Plain Layout
4226
4227 \end_layout
4228
4229 \begin_layout Plain Layout
4230
4231 \end_layout
4232
4233 \begin_layout Plain Layout
4234
4235
4236 \backslash
4237 color{beamerexample}
4238 \end_layout
4239
4240 \begin_layout Plain Layout
4241
4242 \end_layout
4243
4244 \begin_layout Plain Layout
4245
4246
4247 \backslash
4248 pgfsetendarrow{
4249 \backslash
4250 pgfarrowto}
4251 \end_layout
4252
4253 \begin_layout Plain Layout
4254
4255 \end_layout
4256
4257 \begin_layout Plain Layout
4258
4259
4260 \backslash
4261 pgfnodesetsepstart{2pt}
4262 \end_layout
4263
4264 \begin_layout Plain Layout
4265
4266 \end_layout
4267
4268 \begin_layout Plain Layout
4269
4270
4271 \backslash
4272 pgfnodesetsepend{2pt}
4273 \end_layout
4274
4275 \begin_layout Plain Layout
4276
4277 \end_layout
4278
4279 \begin_layout Plain Layout
4280
4281
4282 \backslash
4283 alert<3>{
4284 \backslash
4285 pgfnodeconnline{B}{A}}
4286 \end_layout
4287
4288 \begin_layout Plain Layout
4289
4290 \end_layout
4291
4292 \begin_layout Plain Layout
4293
4294
4295 \backslash
4296 alert<4>{
4297 \backslash
4298 pgfnodeconnline{B}{C}}
4299 \end_layout
4300
4301 \begin_layout Plain Layout
4302
4303 \end_layout
4304
4305 \begin_layout Plain Layout
4306
4307
4308 \backslash
4309 alert<5,10-11,13>{
4310 \backslash
4311 pgfnodeconnline{C}{D}}
4312 \end_layout
4313
4314 \begin_layout Plain Layout
4315
4316 \end_layout
4317
4318 \begin_layout Plain Layout
4319
4320
4321 \backslash
4322 alert<6,10-11,13>{
4323 \backslash
4324 pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}}
4325 \end_layout
4326
4327 \begin_layout Plain Layout
4328
4329 \end_layout
4330
4331 \begin_layout Plain Layout
4332
4333
4334 \end_layout
4335
4336 \begin_layout Plain Layout
4337
4338 \end_layout
4339
4340 \begin_layout Plain Layout
4341
4342
4343 \backslash
4344 pgfputat{
4345 \backslash
4346 pgfxy(0,3.3)}{
4347 \backslash
4348 pgfbox[left,center]{$G
4349 \backslash
4350 colon$}}
4351 \end_layout
4352
4353 \begin_layout Plain Layout
4354
4355 \end_layout
4356
4357 \begin_layout Plain Layout
4358
4359 \end_layout
4360
4361 \begin_layout Plain Layout
4362
4363 \end_layout
4364
4365 \begin_layout Plain Layout
4366
4367
4368 \backslash
4369 only<2->{
4370 \end_layout
4371
4372 \begin_layout Plain Layout
4373
4374 \end_layout
4375
4376 \begin_layout Plain Layout
4377
4378
4379 \backslash
4380 pgfputat{
4381 \backslash
4382 pgfxy(0,2.25)}{
4383 \backslash
4384 pgfbox[left,center]{$G'
4385 \backslash
4386 colon$}}
4387 \end_layout
4388
4389 \begin_layout Plain Layout
4390
4391 \end_layout
4392
4393 \begin_layout Plain Layout
4394
4395
4396 \backslash
4397 graphnode{A1}{
4398 \backslash
4399 pgfxy(1,2.25)}
4400 \end_layout
4401
4402 \begin_layout Plain Layout
4403
4404 \end_layout
4405
4406 \begin_layout Plain Layout
4407
4408
4409 \backslash
4410 graphnode{B1}{
4411 \backslash
4412 pgfxy(2,2.25)}
4413 \end_layout
4414
4415 \begin_layout Plain Layout
4416
4417 \end_layout
4418
4419 \begin_layout Plain Layout
4420
4421
4422 \backslash
4423 graphnode{C1}{
4424 \backslash
4425 pgfxy(3,2.25)}
4426 \end_layout
4427
4428 \begin_layout Plain Layout
4429
4430 \end_layout
4431
4432 \begin_layout Plain Layout
4433
4434
4435 \backslash
4436 graphnode{D1}{
4437 \backslash
4438 pgfxy(4,2.25)}
4439 \end_layout
4440
4441 \begin_layout Plain Layout
4442
4443 \end_layout
4444
4445 \begin_layout Plain Layout
4446
4447 \end_layout
4448
4449 \begin_layout Plain Layout
4450
4451 \end_layout
4452
4453 \begin_layout Plain Layout
4454
4455
4456 \backslash
4457 graphnode{A2}{
4458 \backslash
4459 pgfxy(1,1.25)}
4460 \end_layout
4461
4462 \begin_layout Plain Layout
4463
4464 \end_layout
4465
4466 \begin_layout Plain Layout
4467
4468
4469 \backslash
4470 graphnode{B2}{
4471 \backslash
4472 pgfxy(2,1.25)}
4473 \end_layout
4474
4475 \begin_layout Plain Layout
4476
4477 \end_layout
4478
4479 \begin_layout Plain Layout
4480
4481
4482 \backslash
4483 graphnode{C2}{
4484 \backslash
4485 pgfxy(3,1.25)}
4486 \end_layout
4487
4488 \begin_layout Plain Layout
4489
4490 \end_layout
4491
4492 \begin_layout Plain Layout
4493
4494
4495 \backslash
4496 graphnode{D2}{
4497 \backslash
4498 pgfxy(4,1.25)}
4499 \end_layout
4500
4501 \begin_layout Plain Layout
4502
4503 \end_layout
4504
4505 \begin_layout Plain Layout
4506
4507
4508 \backslash
4509 graphnode{A3}{
4510 \backslash
4511 pgfxy(1,0.25)}
4512 \end_layout
4513
4514 \begin_layout Plain Layout
4515
4516 \end_layout
4517
4518 \begin_layout Plain Layout
4519
4520
4521 \backslash
4522 graphnode{B3}{
4523 \backslash
4524 pgfxy(2,0.25)}
4525 \end_layout
4526
4527 \begin_layout Plain Layout
4528
4529 \end_layout
4530
4531 \begin_layout Plain Layout
4532
4533
4534 \backslash
4535 graphnode{C3}{
4536 \backslash
4537 pgfxy(3,0.25)}
4538 \end_layout
4539
4540 \begin_layout Plain Layout
4541
4542 \end_layout
4543
4544 \begin_layout Plain Layout
4545
4546
4547 \backslash
4548 graphnode{D3}{
4549 \backslash
4550 pgfxy(4,0.25)}
4551 \end_layout
4552
4553 \begin_layout Plain Layout
4554
4555 \end_layout
4556
4557 \begin_layout Plain Layout
4558
4559
4560 \backslash
4561 graphnode{A4}{
4562 \backslash
4563 pgfxy(1,-.75)}
4564 \end_layout
4565
4566 \begin_layout Plain Layout
4567
4568 \end_layout
4569
4570 \begin_layout Plain Layout
4571
4572
4573 \backslash
4574 graphnode{B4}{
4575 \backslash
4576 pgfxy(2,-.75)}
4577 \end_layout
4578
4579 \begin_layout Plain Layout
4580
4581 \end_layout
4582
4583 \begin_layout Plain Layout
4584
4585
4586 \backslash
4587 graphnode{C4}{
4588 \backslash
4589 pgfxy(3,-.75)}
4590 \end_layout
4591
4592 \begin_layout Plain Layout
4593
4594 \end_layout
4595
4596 \begin_layout Plain Layout
4597
4598
4599 \backslash
4600 graphnode{D4}{
4601 \backslash
4602 pgfxy(4,-.75)}
4603 \end_layout
4604
4605 \begin_layout Plain Layout
4606
4607 \end_layout
4608
4609 \begin_layout Plain Layout
4610
4611      {
4612 \backslash
4613 color{white}
4614 \end_layout
4615
4616 \begin_layout Plain Layout
4617
4618 \end_layout
4619
4620 \begin_layout Plain Layout
4621
4622
4623 \backslash
4624 pgfputat{
4625 \backslash
4626 pgfnodecenter{A1}}{
4627 \backslash
4628 pgfbox[center,center]{$s'$}}
4629 \end_layout
4630
4631 \begin_layout Plain Layout
4632
4633 \end_layout
4634
4635 \begin_layout Plain Layout
4636
4637
4638 \backslash
4639 pgfputat{
4640 \backslash
4641 pgfnodecenter{D4}}{
4642 \backslash
4643 pgfbox[center,center]{$t'$}}
4644 \end_layout
4645
4646 \begin_layout Plain Layout
4647
4648 \end_layout
4649
4650 \begin_layout Plain Layout
4651
4652   }}
4653 \end_layout
4654
4655 \begin_layout Plain Layout
4656
4657 \end_layout
4658
4659 \begin_layout Plain Layout
4660
4661
4662 \end_layout
4663
4664 \begin_layout Plain Layout
4665
4666 \end_layout
4667
4668 \begin_layout Plain Layout
4669
4670
4671 \backslash
4672 only<8->{
4673 \end_layout
4674
4675 \begin_layout Plain Layout
4676
4677 \end_layout
4678
4679 \begin_layout Plain Layout
4680
4681
4682 \backslash
4683 pgfsetlinewidth{0.4pt}
4684 \end_layout
4685
4686 \begin_layout Plain Layout
4687
4688 \end_layout
4689
4690 \begin_layout Plain Layout
4691
4692
4693 \backslash
4694 color{beamerexample!25!averagebackgroundcolor}
4695 \end_layout
4696
4697 \begin_layout Plain Layout
4698
4699 \end_layout
4700
4701 \begin_layout Plain Layout
4702
4703
4704 \backslash
4705 pgfnodeconnline{A2}{C1}
4706 \end_layout
4707
4708 \begin_layout Plain Layout
4709
4710 \end_layout
4711
4712 \begin_layout Plain Layout
4713
4714
4715 \backslash
4716 pgfnodeconnline{A2}{D1}
4717 \end_layout
4718
4719 \begin_layout Plain Layout
4720
4721 \end_layout
4722
4723 \begin_layout Plain Layout
4724
4725
4726 \backslash
4727 pgfnodeconnline{B2}{A1}
4728 \end_layout
4729
4730 \begin_layout Plain Layout
4731
4732 \end_layout
4733
4734 \begin_layout Plain Layout
4735
4736
4737 \backslash
4738 pgfnodeconnline{B2}{C1}
4739 \end_layout
4740
4741 \begin_layout Plain Layout
4742
4743 \end_layout
4744
4745 \begin_layout Plain Layout
4746
4747
4748 \backslash
4749 pgfnodeconnline{B2}{D1}
4750 \end_layout
4751
4752 \begin_layout Plain Layout
4753
4754 \end_layout
4755
4756 \begin_layout Plain Layout
4757
4758
4759 \backslash
4760 pgfnodeconnline{C2}{D1}
4761 \end_layout
4762
4763 \begin_layout Plain Layout
4764
4765 \end_layout
4766
4767 \begin_layout Plain Layout
4768
4769
4770 \backslash
4771 pgfnodeconnline{D2}{A1}
4772 \end_layout
4773
4774 \begin_layout Plain Layout
4775
4776 \end_layout
4777
4778 \begin_layout Plain Layout
4779
4780
4781 \backslash
4782 pgfnodeconnline{D2}{B1}
4783 \end_layout
4784
4785 \begin_layout Plain Layout
4786
4787 \end_layout
4788
4789 \begin_layout Plain Layout
4790
4791
4792 \backslash
4793 pgfnodeconnline{A3}{C2}
4794 \end_layout
4795
4796 \begin_layout Plain Layout
4797
4798 \end_layout
4799
4800 \begin_layout Plain Layout
4801
4802
4803 \backslash
4804 pgfnodeconnline{A3}{D2}
4805 \end_layout
4806
4807 \begin_layout Plain Layout
4808
4809 \end_layout
4810
4811 \begin_layout Plain Layout
4812
4813
4814 \backslash
4815 pgfnodeconnline{B3}{A2}
4816 \end_layout
4817
4818 \begin_layout Plain Layout
4819
4820 \end_layout
4821
4822 \begin_layout Plain Layout
4823
4824
4825 \backslash
4826 pgfnodeconnline{B3}{C2}
4827 \end_layout
4828
4829 \begin_layout Plain Layout
4830
4831 \end_layout
4832
4833 \begin_layout Plain Layout
4834
4835
4836 \backslash
4837 pgfnodeconnline{B3}{D2}
4838 \end_layout
4839
4840 \begin_layout Plain Layout
4841
4842 \end_layout
4843
4844 \begin_layout Plain Layout
4845
4846
4847 \backslash
4848 pgfnodeconnline{C3}{D2}
4849 \end_layout
4850
4851 \begin_layout Plain Layout
4852
4853 \end_layout
4854
4855 \begin_layout Plain Layout
4856
4857
4858 \backslash
4859 pgfnodeconnline{D3}{A2}
4860 \end_layout
4861
4862 \begin_layout Plain Layout
4863
4864 \end_layout
4865
4866 \begin_layout Plain Layout
4867
4868
4869 \backslash
4870 pgfnodeconnline{D3}{B2}
4871 \end_layout
4872
4873 \begin_layout Plain Layout
4874
4875 \end_layout
4876
4877 \begin_layout Plain Layout
4878
4879
4880 \backslash
4881 pgfnodeconnline{A4}{C3}
4882 \end_layout
4883
4884 \begin_layout Plain Layout
4885
4886 \end_layout
4887
4888 \begin_layout Plain Layout
4889
4890
4891 \backslash
4892 pgfnodeconnline{A4}{D3}
4893 \end_layout
4894
4895 \begin_layout Plain Layout
4896
4897 \end_layout
4898
4899 \begin_layout Plain Layout
4900
4901
4902 \backslash
4903 pgfnodeconnline{B4}{A3}
4904 \end_layout
4905
4906 \begin_layout Plain Layout
4907
4908 \end_layout
4909
4910 \begin_layout Plain Layout
4911
4912
4913 \backslash
4914 pgfnodeconnline{B4}{C3}
4915 \end_layout
4916
4917 \begin_layout Plain Layout
4918
4919 \end_layout
4920
4921 \begin_layout Plain Layout
4922
4923
4924 \backslash
4925 pgfnodeconnline{B4}{D3}
4926 \end_layout
4927
4928 \begin_layout Plain Layout
4929
4930 \end_layout
4931
4932 \begin_layout Plain Layout
4933
4934
4935 \backslash
4936 pgfnodeconnline{C4}{D3}
4937 \end_layout
4938
4939 \begin_layout Plain Layout
4940
4941 \end_layout
4942
4943 \begin_layout Plain Layout
4944
4945
4946 \backslash
4947 pgfnodeconnline{D4}{A3}
4948 \end_layout
4949
4950 \begin_layout Plain Layout
4951
4952 \end_layout
4953
4954 \begin_layout Plain Layout
4955
4956
4957 \backslash
4958 pgfnodeconnline{D4}{B3}
4959 \end_layout
4960
4961 \begin_layout Plain Layout
4962
4963 \end_layout
4964
4965 \begin_layout Plain Layout
4966
4967 \end_layout
4968
4969 \begin_layout Plain Layout
4970
4971 \end_layout
4972
4973 \begin_layout Plain Layout
4974
4975
4976 \backslash
4977 pgfsetstartarrow{
4978 \backslash
4979 pgfarrowto}
4980 \end_layout
4981
4982 \begin_layout Plain Layout
4983
4984 \end_layout
4985
4986 \begin_layout Plain Layout
4987
4988
4989 \backslash
4990 pgfnodeconnline{A1}{B1}
4991 \end_layout
4992
4993 \begin_layout Plain Layout
4994
4995 \end_layout
4996
4997 \begin_layout Plain Layout
4998
4999
5000 \backslash
5001 pgfnodeconnline{B1}{C1}
5002 \end_layout
5003
5004 \begin_layout Plain Layout
5005
5006 \end_layout
5007
5008 \begin_layout Plain Layout
5009
5010
5011 \backslash
5012 pgfnodeconnline{C1}{D1}
5013 \end_layout
5014
5015 \begin_layout Plain Layout
5016
5017 \end_layout
5018
5019 \begin_layout Plain Layout
5020
5021
5022 \backslash
5023 pgfnodeconnline{A2}{B2}
5024 \end_layout
5025
5026 \begin_layout Plain Layout
5027
5028 \end_layout
5029
5030 \begin_layout Plain Layout
5031
5032
5033 \backslash
5034 pgfnodeconnline{B2}{C2}
5035 \end_layout
5036
5037 \begin_layout Plain Layout
5038
5039 \end_layout
5040
5041 \begin_layout Plain Layout
5042
5043
5044 \backslash
5045 pgfnodeconnline{C2}{D2}
5046 \end_layout
5047
5048 \begin_layout Plain Layout
5049
5050 \end_layout
5051
5052 \begin_layout Plain Layout
5053
5054
5055 \backslash
5056 pgfnodeconnline{A3}{B3}
5057 \end_layout
5058
5059 \begin_layout Plain Layout
5060
5061 \end_layout
5062
5063 \begin_layout Plain Layout
5064
5065
5066 \backslash
5067 pgfnodeconnline{B3}{C3}
5068 \end_layout
5069
5070 \begin_layout Plain Layout
5071
5072 \end_layout
5073
5074 \begin_layout Plain Layout
5075
5076
5077 \backslash
5078 pgfnodeconnline{C3}{D3}
5079 \end_layout
5080
5081 \begin_layout Plain Layout
5082
5083 \end_layout
5084
5085 \begin_layout Plain Layout
5086
5087
5088 \backslash
5089 pgfnodeconnline{A4}{B4}
5090 \end_layout
5091
5092 \begin_layout Plain Layout
5093
5094 \end_layout
5095
5096 \begin_layout Plain Layout
5097
5098
5099 \backslash
5100 pgfnodeconnline{B4}{C4}
5101 \end_layout
5102
5103 \begin_layout Plain Layout
5104
5105 \end_layout
5106
5107 \begin_layout Plain Layout
5108
5109
5110 \backslash
5111 pgfnodeconnline{C4}{D4}
5112 \end_layout
5113
5114 \begin_layout Plain Layout
5115
5116 \end_layout
5117
5118 \begin_layout Plain Layout
5119
5120 \end_layout
5121
5122 \begin_layout Plain Layout
5123
5124 \end_layout
5125
5126 \begin_layout Plain Layout
5127
5128
5129 \backslash
5130 pgfclearstartarrow
5131 \end_layout
5132
5133 \begin_layout Plain Layout
5134
5135 \end_layout
5136
5137 \begin_layout Plain Layout
5138
5139
5140 \backslash
5141 pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt}
5142 \end_layout
5143
5144 \begin_layout Plain Layout
5145
5146 \end_layout
5147
5148 \begin_layout Plain Layout
5149
5150
5151 \backslash
5152 pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt}
5153 \end_layout
5154
5155 \begin_layout Plain Layout
5156
5157 \end_layout
5158
5159 \begin_layout Plain Layout
5160
5161
5162 \backslash
5163 pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt}
5164 \end_layout
5165
5166 \begin_layout Plain Layout
5167
5168 \end_layout
5169
5170 \begin_layout Plain Layout
5171
5172
5173 \backslash
5174 pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt}
5175 \end_layout
5176
5177 \begin_layout Plain Layout
5178
5179 \end_layout
5180
5181 \begin_layout Plain Layout
5182
5183
5184 \backslash
5185 pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt}
5186 \end_layout
5187
5188 \begin_layout Plain Layout
5189
5190 \end_layout
5191
5192 \begin_layout Plain Layout
5193
5194
5195 \backslash
5196 pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt}
5197 \end_layout
5198
5199 \begin_layout Plain Layout
5200
5201 \end_layout
5202
5203 \begin_layout Plain Layout
5204
5205
5206 \backslash
5207 pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt}
5208 \end_layout
5209
5210 \begin_layout Plain Layout
5211
5212 \end_layout
5213
5214 \begin_layout Plain Layout
5215
5216
5217 \backslash
5218 pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt}
5219 \end_layout
5220
5221 \begin_layout Plain Layout
5222
5223 \end_layout
5224
5225 \begin_layout Plain Layout
5226
5227
5228 \backslash
5229 pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt}
5230 \end_layout
5231
5232 \begin_layout Plain Layout
5233
5234 \end_layout
5235
5236 \begin_layout Plain Layout
5237
5238
5239 \backslash
5240 pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt}
5241 \end_layout
5242
5243 \begin_layout Plain Layout
5244
5245 \end_layout
5246
5247 \begin_layout Plain Layout
5248
5249
5250 \backslash
5251 pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt}
5252 \end_layout
5253
5254 \begin_layout Plain Layout
5255
5256 \end_layout
5257
5258 \begin_layout Plain Layout
5259
5260
5261 \backslash
5262 pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt}
5263 \end_layout
5264
5265 \begin_layout Plain Layout
5266
5267 \end_layout
5268
5269 \begin_layout Plain Layout
5270
5271
5272 \backslash
5273 color{beamerexample}
5274 \end_layout
5275
5276 \begin_layout Plain Layout
5277
5278 \end_layout
5279
5280 \begin_layout Plain Layout
5281
5282
5283 \backslash
5284 pgfsetlinewidth{0.6pt}
5285 \end_layout
5286
5287 \begin_layout Plain Layout
5288
5289 \end_layout
5290
5291 \begin_layout Plain Layout
5292
5293   }
5294 \end_layout
5295
5296 \begin_layout Plain Layout
5297
5298 \end_layout
5299
5300 \begin_layout Plain Layout
5301
5302 \end_layout
5303
5304 \begin_layout Plain Layout
5305
5306 \end_layout
5307
5308 \begin_layout Plain Layout
5309
5310
5311 \backslash
5312 only<3->{
5313 \end_layout
5314
5315 \begin_layout Plain Layout
5316
5317 \end_layout
5318
5319 \begin_layout Plain Layout
5320
5321
5322 \backslash
5323 color<3>{red}
5324 \end_layout
5325
5326 \begin_layout Plain Layout
5327
5328 \end_layout
5329
5330 \begin_layout Plain Layout
5331
5332
5333 \backslash
5334 pgfnodeconnline{B1}{A2}
5335 \end_layout
5336
5337 \begin_layout Plain Layout
5338
5339 \end_layout
5340
5341 \begin_layout Plain Layout
5342
5343
5344 \backslash
5345 pgfnodeconnline{B2}{A3}
5346 \end_layout
5347
5348 \begin_layout Plain Layout
5349
5350 \end_layout
5351
5352 \begin_layout Plain Layout
5353
5354
5355 \backslash
5356 pgfnodeconnline{B3}{A4}
5357 \end_layout
5358
5359 \begin_layout Plain Layout
5360
5361 \end_layout
5362
5363 \begin_layout Plain Layout
5364
5365   }
5366 \end_layout
5367
5368 \begin_layout Plain Layout
5369
5370 \end_layout
5371
5372 \begin_layout Plain Layout
5373
5374 \end_layout
5375
5376 \begin_layout Plain Layout
5377
5378 \end_layout
5379
5380 \begin_layout Plain Layout
5381
5382
5383 \backslash
5384 only<4->{
5385 \end_layout
5386
5387 \begin_layout Plain Layout
5388
5389 \end_layout
5390
5391 \begin_layout Plain Layout
5392
5393
5394 \backslash
5395 color<4>{red}
5396 \end_layout
5397
5398 \begin_layout Plain Layout
5399
5400 \end_layout
5401
5402 \begin_layout Plain Layout
5403
5404
5405 \backslash
5406 pgfnodeconnline{B1}{C2}
5407 \end_layout
5408
5409 \begin_layout Plain Layout
5410
5411 \end_layout
5412
5413 \begin_layout Plain Layout
5414
5415
5416 \backslash
5417 pgfnodeconnline{B2}{C3}
5418 \end_layout
5419
5420 \begin_layout Plain Layout
5421
5422 \end_layout
5423
5424 \begin_layout Plain Layout
5425
5426
5427 \backslash
5428 pgfnodeconnline{B3}{C4}
5429 \end_layout
5430
5431 \begin_layout Plain Layout
5432
5433 \end_layout
5434
5435 \begin_layout Plain Layout
5436
5437   }
5438 \end_layout
5439
5440 \begin_layout Plain Layout
5441
5442 \end_layout
5443
5444 \begin_layout Plain Layout
5445
5446
5447 \end_layout
5448
5449 \begin_layout Plain Layout
5450
5451 \end_layout
5452
5453 \begin_layout Plain Layout
5454
5455
5456 \backslash
5457 only<5->{
5458 \end_layout
5459
5460 \begin_layout Plain Layout
5461
5462 \end_layout
5463
5464 \begin_layout Plain Layout
5465
5466
5467 \backslash
5468 color<5>{red}
5469 \end_layout
5470
5471 \begin_layout Plain Layout
5472
5473 \end_layout
5474
5475 \begin_layout Plain Layout
5476
5477
5478 \backslash
5479 pgfnodeconnline{C1}{D2}
5480 \end_layout
5481
5482 \begin_layout Plain Layout
5483
5484 \end_layout
5485
5486 \begin_layout Plain Layout
5487
5488
5489 \backslash
5490 alert<11>{
5491 \backslash
5492 pgfnodeconnline{C2}{D3}}
5493 \end_layout
5494
5495 \begin_layout Plain Layout
5496
5497 \end_layout
5498
5499 \begin_layout Plain Layout
5500
5501
5502 \backslash
5503 alert<12-13>{
5504 \backslash
5505 pgfnodeconnline{C3}{D4}}
5506 \end_layout
5507
5508 \begin_layout Plain Layout
5509
5510 \end_layout
5511
5512 \begin_layout Plain Layout
5513
5514   }
5515 \end_layout
5516
5517 \begin_layout Plain Layout
5518
5519 \end_layout
5520
5521 \begin_layout Plain Layout
5522
5523
5524 \end_layout
5525
5526 \begin_layout Plain Layout
5527
5528 \end_layout
5529
5530 \begin_layout Plain Layout
5531
5532
5533 \backslash
5534 only<6->{
5535 \end_layout
5536
5537 \begin_layout Plain Layout
5538
5539 \end_layout
5540
5541 \begin_layout Plain Layout
5542
5543
5544 \backslash
5545 color<6>{red}
5546 \end_layout
5547
5548 \begin_layout Plain Layout
5549
5550 \end_layout
5551
5552 \begin_layout Plain Layout
5553
5554
5555 \backslash
5556 alert<11>{
5557 \backslash
5558 pgfnodeconnline{A1}{C2}}
5559 \end_layout
5560
5561 \begin_layout Plain Layout
5562
5563 \end_layout
5564
5565 \begin_layout Plain Layout
5566
5567
5568 \backslash
5569 alert<12-13>{
5570 \backslash
5571 pgfnodeconnline{A2}{C3}}
5572 \end_layout
5573
5574 \begin_layout Plain Layout
5575
5576 \end_layout
5577
5578 \begin_layout Plain Layout
5579
5580
5581 \backslash
5582 pgfnodeconnline{A3}{C4}
5583 \end_layout
5584
5585 \begin_layout Plain Layout
5586
5587 \end_layout
5588
5589 \begin_layout Plain Layout
5590
5591   }
5592 \end_layout
5593
5594 \begin_layout Plain Layout
5595
5596 \end_layout
5597
5598 \begin_layout Plain Layout
5599
5600 \end_layout
5601
5602 \begin_layout Plain Layout
5603
5604 \end_layout
5605
5606 \begin_layout Plain Layout
5607
5608
5609 \backslash
5610 only<7->{
5611 \end_layout
5612
5613 \begin_layout Plain Layout
5614
5615 \end_layout
5616
5617 \begin_layout Plain Layout
5618
5619
5620 \backslash
5621 color<7>{red}
5622 \end_layout
5623
5624 \begin_layout Plain Layout
5625
5626 \end_layout
5627
5628 \begin_layout Plain Layout
5629
5630
5631 \backslash
5632 alert<12-13>{
5633 \backslash
5634 pgfnodeconnline{A1}{A2}}
5635 \end_layout
5636
5637 \begin_layout Plain Layout
5638
5639 \end_layout
5640
5641 \begin_layout Plain Layout
5642
5643
5644 \backslash
5645 pgfnodeconnline{A2}{A3}
5646 \end_layout
5647
5648 \begin_layout Plain Layout
5649
5650 \end_layout
5651
5652 \begin_layout Plain Layout
5653
5654
5655 \backslash
5656 pgfnodeconnline{A3}{A4}
5657 \end_layout
5658
5659 \begin_layout Plain Layout
5660
5661 \end_layout
5662
5663 \begin_layout Plain Layout
5664
5665
5666 \backslash
5667 pgfnodeconnline{B1}{B2}
5668 \end_layout
5669
5670 \begin_layout Plain Layout
5671
5672 \end_layout
5673
5674 \begin_layout Plain Layout
5675
5676
5677 \backslash
5678 pgfnodeconnline{B2}{B3}
5679 \end_layout
5680
5681 \begin_layout Plain Layout
5682
5683 \end_layout
5684
5685 \begin_layout Plain Layout
5686
5687
5688 \backslash
5689 pgfnodeconnline{B3}{B4}
5690 \end_layout
5691
5692 \begin_layout Plain Layout
5693
5694 \end_layout
5695
5696 \begin_layout Plain Layout
5697
5698
5699 \backslash
5700 pgfnodeconnline{C1}{C2}
5701 \end_layout
5702
5703 \begin_layout Plain Layout
5704
5705 \end_layout
5706
5707 \begin_layout Plain Layout
5708
5709
5710 \backslash
5711 pgfnodeconnline{C2}{C3}
5712 \end_layout
5713
5714 \begin_layout Plain Layout
5715
5716 \end_layout
5717
5718 \begin_layout Plain Layout
5719
5720
5721 \backslash
5722 pgfnodeconnline{C3}{C4}
5723 \end_layout
5724
5725 \begin_layout Plain Layout
5726
5727 \end_layout
5728
5729 \begin_layout Plain Layout
5730
5731
5732 \backslash
5733 pgfnodeconnline{D1}{D2}
5734 \end_layout
5735
5736 \begin_layout Plain Layout
5737
5738 \end_layout
5739
5740 \begin_layout Plain Layout
5741
5742
5743 \backslash
5744 pgfnodeconnline{D2}{D3}
5745 \end_layout
5746
5747 \begin_layout Plain Layout
5748
5749 \end_layout
5750
5751 \begin_layout Plain Layout
5752
5753
5754 \backslash
5755 alert<11>{
5756 \backslash
5757 pgfnodeconnline{D3}{D4}}
5758 \end_layout
5759
5760 \begin_layout Plain Layout
5761
5762 \end_layout
5763
5764 \begin_layout Plain Layout
5765
5766   }
5767 \end_layout
5768
5769 \begin_layout Plain Layout
5770
5771 \end_layout
5772
5773 \begin_layout Plain Layout
5774
5775
5776 \backslash
5777 end{pgfpicture}
5778 \end_layout
5779
5780 \end_inset
5781
5782
5783 \end_layout
5784
5785 \end_deeper
5786 \begin_layout AgainFrame
5787 \begin_inset ERT
5788 status collapsed
5789
5790 \begin_layout Plain Layout
5791
5792 <6>
5793 \end_layout
5794
5795 \end_inset
5796
5797 hierarchy
5798 \end_layout
5799
5800 \begin_layout Subsection
5801 Complexity of: Approximating the Shortest Path
5802 \end_layout
5803
5804 \begin_layout BeginFrame
5805 Approximators Compute Paths that Are Nearly As Short As a Shortest Path
5806 \end_layout
5807
5808 \begin_layout Definition
5809 An
5810 \color none
5811
5812 \color red
5813 approximation scheme for
5814 \begin_inset Formula $\Lang{tournament-shortest-path}$
5815 \end_inset
5816
5817
5818 \color none
5819
5820 \color inherit
5821 gets as input
5822 \end_layout
5823
5824 \begin_deeper
5825 \begin_layout Enumerate
5826 a tuple
5827 \begin_inset Formula $(T,s,t)\in\Lang{reach}_{\operatorname{tourn}}$
5828 \end_inset
5829
5830  and
5831 \end_layout
5832
5833 \begin_layout Enumerate
5834 a number
5835 \begin_inset Formula $r>1$
5836 \end_inset
5837
5838 .
5839 \end_layout
5840
5841 \begin_layout Standard
5842 It outputs
5843 \end_layout
5844
5845 \begin_layout Itemize
5846 a path from
5847 \begin_inset Formula $s$
5848 \end_inset
5849
5850  to
5851 \begin_inset space ~
5852 \end_inset
5853
5854
5855 \begin_inset Formula $t$
5856 \end_inset
5857
5858  of length at most
5859 \begin_inset Formula $r\operatorname{d_{T}}(s,t)$
5860 \end_inset
5861
5862 .
5863 \end_layout
5864
5865 \end_deeper
5866 \begin_layout BeginFrame
5867 There Exists a Logspace Approximation Scheme for
5868 \begin_inset Newline newline
5869 \end_inset
5870
5871 the Tournament Shortest Path Problem
5872 \end_layout
5873
5874 \begin_layout Theorem
5875 There exists an approximation scheme for
5876 \begin_inset Formula $\Lang{tournament-shortest-path}$
5877 \end_inset
5878
5879  that for
5880 \begin_inset Formula $1<r<2$
5881 \end_inset
5882
5883  needs space
5884 \begin_inset Formula
5885 \[
5886 O\left(\log|V|\log\frac{1}{r-1}\right).
5887 \]
5888
5889 \end_inset
5890
5891
5892 \end_layout
5893
5894 \begin_layout Pause
5895
5896 \end_layout
5897
5898 \begin_layout Corollary
5899 In tournaments, paths can be constructed in logarithmic space.
5900 \end_layout
5901
5902 \begin_layout Standard
5903 \begin_inset space \hfill{}
5904 \end_inset
5905
5906
5907 \begin_inset ERT
5908 status collapsed
5909
5910 \begin_layout Plain Layout
5911
5912
5913 \backslash
5914 hyperlink{optimality}{
5915 \backslash
5916 beamergotobutton{More Details}}
5917 \end_layout
5918
5919 \end_inset
5920
5921
5922 \end_layout
5923
5924 \begin_layout AgainFrame
5925 \begin_inset ERT
5926 status collapsed
5927
5928 \begin_layout Plain Layout
5929
5930 <7>
5931 \end_layout
5932
5933 \end_inset
5934
5935 hierarchy
5936 \end_layout
5937
5938 \begin_layout EndFrame
5939
5940 \end_layout
5941
5942 \begin_layout Standard
5943 \begin_inset Note Note
5944 status open
5945
5946 \begin_layout Plain Layout
5947 If a frame includes a program listing, the frame needs to be marked as
5948 \begin_inset Quotes eld
5949 \end_inset
5950
5951 fragile
5952 \begin_inset Quotes erd
5953 \end_inset
5954
5955 .
5956  This is not yet supported by LyX, so the frame is created using TeX code.
5957  Note that the
5958 \backslash
5959 begin{frame}[fragile] needs to be preceeded by an
5960 \emph on
5961 EndFrame
5962 \emph default
5963  environment.
5964 \end_layout
5965
5966 \end_inset
5967
5968
5969 \end_layout
5970
5971 \begin_layout Standard
5972 \begin_inset ERT
5973 status open
5974
5975 \begin_layout Plain Layout
5976
5977
5978 \backslash
5979 begin{frame}[fragile]
5980 \end_layout
5981
5982 \end_inset
5983
5984
5985 \end_layout
5986
5987 \begin_layout Standard
5988 \begin_inset ERT
5989 status collapsed
5990
5991 \begin_layout Plain Layout
5992
5993
5994 \backslash
5995 frametitle{
5996 \end_layout
5997
5998 \end_inset
5999
6000 Just a frame with a program code listing
6001 \begin_inset ERT
6002 status collapsed
6003
6004 \begin_layout Plain Layout
6005
6006 }
6007 \end_layout
6008
6009 \end_inset
6010
6011
6012 \end_layout
6013
6014 \begin_layout Standard
6015 This is some program code:
6016 \end_layout
6017
6018 \begin_layout Standard
6019 \begin_inset listings
6020 lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4"
6021 inline false
6022 status open
6023
6024 \begin_layout Plain Layout
6025
6026 def func(param):
6027 \end_layout
6028
6029 \begin_layout Plain Layout
6030
6031     'this is a python function'
6032 \end_layout
6033
6034 \begin_layout Plain Layout
6035
6036     pass
6037 \end_layout
6038
6039 \begin_layout Plain Layout
6040
6041 def func(param):
6042 \end_layout
6043
6044 \begin_layout Plain Layout
6045
6046 'This is a German word: Tschüs'
6047 \end_layout
6048
6049 \begin_layout Plain Layout
6050
6051 pass
6052 \end_layout
6053
6054 \begin_layout Plain Layout
6055
6056 def func(param):
6057 \end_layout
6058
6059 \begin_layout Plain Layout
6060
6061 'this is a python function'
6062 \end_layout
6063
6064 \begin_layout Plain Layout
6065
6066 pass
6067 \end_layout
6068
6069 \end_inset
6070
6071
6072 \end_layout
6073
6074 \begin_layout Standard
6075 \begin_inset ERT
6076 status open
6077
6078 \begin_layout Plain Layout
6079
6080
6081 \backslash
6082 end{frame}
6083 \end_layout
6084
6085 \end_inset
6086
6087
6088 \end_layout
6089
6090 \begin_layout Section*
6091 Summary
6092 \end_layout
6093
6094 \begin_layout Subsection*
6095 Summary
6096 \end_layout
6097
6098 \begin_layout BeginFrame
6099 Summary
6100 \end_layout
6101
6102 \begin_layout Block
6103 \begin_inset ERT
6104 status collapsed
6105
6106 \begin_layout Plain Layout
6107
6108 {Summary}
6109 \end_layout
6110
6111 \end_inset
6112
6113
6114 \end_layout
6115
6116 \begin_deeper
6117 \begin_layout Itemize
6118 Tournament
6119 \color none
6120
6121 \color red
6122 reachability
6123 \color none
6124
6125 \color inherit
6126 is in
6127 \color none
6128
6129 \color red
6130
6131 \begin_inset Formula $\Class{AC}^{0}$
6132 \end_inset
6133
6134
6135 \color inherit
6136 .
6137
6138 \end_layout
6139
6140 \begin_layout Itemize
6141 There exists a
6142 \color none
6143
6144 \color red
6145 logspace approximation scheme
6146 \color none
6147
6148 \color inherit
6149 for
6150 \color none
6151
6152 \color red
6153 approximating
6154 \color none
6155
6156 \color inherit
6157 shortest paths in tournaments.
6158 \end_layout
6159
6160 \begin_layout Itemize
6161 Finding
6162 \color none
6163
6164 \color red
6165 shortest paths
6166 \color none
6167
6168 \color inherit
6169 in tournaments is
6170 \color none
6171
6172 \color red
6173
6174 \begin_inset Formula $\Class{NL}$
6175 \end_inset
6176
6177 -complete
6178 \color inherit
6179 .
6180 \end_layout
6181
6182 \end_deeper
6183 \begin_layout Separator
6184
6185 \end_layout
6186
6187 \begin_layout Block
6188 \begin_inset ERT
6189 status collapsed
6190
6191 \begin_layout Plain Layout
6192
6193 {Outlook}
6194 \end_layout
6195
6196 \end_inset
6197
6198
6199 \end_layout
6200
6201 \begin_deeper
6202 \begin_layout Itemize
6203 The same results apply to graphs with
6204 \begin_inset Newline newline
6205 \end_inset
6206
6207 bounded independence number.
6208 \begin_inset space \hfill{}
6209 \end_inset
6210
6211
6212 \begin_inset ERT
6213 status collapsed
6214
6215 \begin_layout Plain Layout
6216
6217
6218 \backslash
6219 hyperlink{independence}{
6220 \backslash
6221 beamergotobutton{More Details}}
6222 \end_layout
6223
6224 \end_inset
6225
6226
6227 \end_layout
6228
6229 \begin_layout Itemize
6230 The complexity of finding paths in undirected graphs
6231 \begin_inset Newline newline
6232 \end_inset
6233
6234 is partly open.
6235 \begin_inset space \hfill{}
6236 \end_inset
6237
6238
6239 \begin_inset ERT
6240 status collapsed
6241
6242 \begin_layout Plain Layout
6243
6244
6245 \backslash
6246 hyperlink{undirected}{
6247 \backslash
6248 beamergotobutton{More Details}}
6249 \end_layout
6250
6251 \end_inset
6252
6253
6254 \end_layout
6255
6256 \end_deeper
6257 \begin_layout Subsection*
6258 For Further Reading
6259 \end_layout
6260
6261 \begin_layout BeginFrame
6262 For Further Reading
6263 \end_layout
6264
6265 \begin_layout Standard
6266 \begin_inset ERT
6267 status collapsed
6268
6269 \begin_layout Plain Layout
6270
6271
6272 \backslash
6273 beamertemplatebookbibitems
6274 \end_layout
6275
6276 \end_inset
6277
6278
6279 \end_layout
6280
6281 \begin_layout Bibliography
6282 \labelwidthstring References
6283 \begin_inset CommandInset bibitem
6284 LatexCommand bibitem
6285 key "Moon1968"
6286
6287 \end_inset
6288
6289
6290 \begin_inset space ~
6291 \end_inset
6292
6293 John Moon.
6294
6295 \begin_inset ERT
6296 status collapsed
6297
6298 \begin_layout Plain Layout
6299
6300
6301 \backslash
6302 newblock
6303 \end_layout
6304
6305 \end_inset
6306
6307
6308 \emph on
6309 Topics on Tournaments.
6310
6311 \emph default
6312
6313 \begin_inset ERT
6314 status collapsed
6315
6316 \begin_layout Plain Layout
6317
6318
6319 \backslash
6320 newblock
6321 \end_layout
6322
6323 \end_inset
6324
6325  Holt, Rinehart, and Winston, 1968.
6326
6327 \begin_inset ERT
6328 status collapsed
6329
6330 \begin_layout Plain Layout
6331
6332
6333 \backslash
6334 beamertemplatearticlebibitems
6335 \end_layout
6336
6337 \end_inset
6338
6339
6340 \end_layout
6341
6342 \begin_layout Bibliography
6343 \labelwidthstring References
6344 \begin_inset CommandInset bibitem
6345 LatexCommand bibitem
6346 key "NickelsenT2002"
6347
6348 \end_inset
6349
6350
6351 \begin_inset space ~
6352 \end_inset
6353
6354 Arfst Nickelsen and Till Tantau.
6355
6356 \begin_inset ERT
6357 status collapsed
6358
6359 \begin_layout Plain Layout
6360
6361
6362 \backslash
6363 newblock
6364 \end_layout
6365
6366 \end_inset
6367
6368  On reachability in graphs with bounded independence number.
6369 \begin_inset ERT
6370 status collapsed
6371
6372 \begin_layout Plain Layout
6373
6374
6375 \backslash
6376 newblock
6377 \end_layout
6378
6379 \end_inset
6380
6381  In
6382 \emph on
6383 Proc.
6384  of COCOON 2002
6385 \emph default
6386 , Springer-Verlag, 2002.
6387 \end_layout
6388
6389 \begin_layout Bibliography
6390 \labelwidthstring References
6391 \begin_inset CommandInset bibitem
6392 LatexCommand bibitem
6393 key "Tantau2004b"
6394
6395 \end_inset
6396
6397
6398 \begin_inset space ~
6399 \end_inset
6400
6401 Till Tantau
6402 \begin_inset ERT
6403 status collapsed
6404
6405 \begin_layout Plain Layout
6406
6407
6408 \backslash
6409 newblock
6410 \end_layout
6411
6412 \end_inset
6413
6414  A logspace approximation scheme for the shortest path problem for graphs
6415  with bounded independence number.
6416 \begin_inset ERT
6417 status collapsed
6418
6419 \begin_layout Plain Layout
6420
6421
6422 \backslash
6423 newblock
6424 \end_layout
6425
6426 \end_inset
6427
6428  In
6429 \emph on
6430 Proc.
6431  of STACS 2004
6432 \emph default
6433 , Springer-Verlag, 2004.
6434
6435 \begin_inset ERT
6436 status collapsed
6437
6438 \begin_layout Plain Layout
6439
6440
6441 \backslash
6442 newblock
6443 \end_layout
6444
6445 \end_inset
6446
6447  In press.
6448 \end_layout
6449
6450 \begin_layout EndFrame
6451
6452 \end_layout
6453
6454 \begin_layout Standard
6455 \start_of_appendix
6456 \begin_inset ERT
6457 status collapsed
6458
6459 \begin_layout Plain Layout
6460
6461
6462 \backslash
6463 AtBeginSubsection[]{}
6464 \end_layout
6465
6466 \end_inset
6467
6468
6469 \end_layout
6470
6471 \begin_layout Section
6472 Appendix
6473 \end_layout
6474
6475 \begin_layout Subsection
6476 Graphs With Bounded Independence Number
6477 \end_layout
6478
6479 \begin_layout BeginFrame
6480 \begin_inset ERT
6481 status collapsed
6482
6483 \begin_layout Plain Layout
6484
6485 [label=independence]
6486 \end_layout
6487
6488 \end_inset
6489
6490 Definition of Independence Number of a Graph
6491 \end_layout
6492
6493 \begin_layout Definition
6494 The
6495 \color none
6496
6497 \color red
6498 independence number
6499 \color none
6500
6501 \color inherit
6502
6503 \begin_inset Formula $\alpha(G)$
6504 \end_inset
6505
6506  of a directed graph
6507 \begin_inset Newline newline
6508 \end_inset
6509
6510 is the maximum number of vertices we can pick,
6511 \begin_inset Newline newline
6512 \end_inset
6513
6514 such that there is no edge between them.
6515 \end_layout
6516
6517 \begin_layout Example
6518 Tournaments have independence number 1.
6519
6520 \end_layout
6521
6522 \begin_layout BeginFrame
6523 The Results for Tournaments also Apply to
6524 \begin_inset Newline newline
6525 \end_inset
6526
6527 Graphs With Bounded Independence Number
6528 \end_layout
6529
6530 \begin_layout Theorem
6531 For each
6532 \begin_inset space ~
6533 \end_inset
6534
6535
6536 \begin_inset Formula $k$
6537 \end_inset
6538
6539 ,
6540 \color none
6541
6542 \color red
6543 reachability
6544 \color none
6545
6546 \color inherit
6547 in graphs with independence number
6548 \begin_inset Newline newline
6549 \end_inset
6550
6551 at most
6552 \begin_inset space ~
6553 \end_inset
6554
6555
6556 \begin_inset Formula $k$
6557 \end_inset
6558
6559  is in
6560 \begin_inset Formula $\Class{AC}^{0}$
6561 \end_inset
6562
6563 .
6564 \end_layout
6565
6566 \begin_layout Separator
6567
6568 \end_layout
6569
6570 \begin_layout Theorem
6571 For each
6572 \begin_inset space ~
6573 \end_inset
6574
6575
6576 \begin_inset Formula $k$
6577 \end_inset
6578
6579 , there exists a
6580 \color none
6581
6582 \color red
6583 logspace approximation scheme
6584 \color none
6585
6586 \color inherit
6587 for approximating the shortest path in graphs with independence number at
6588  most
6589 \begin_inset space ~
6590 \end_inset
6591
6592
6593 \begin_inset Formula $k$
6594 \end_inset
6595
6596
6597 \end_layout
6598
6599 \begin_layout Separator
6600
6601 \end_layout
6602
6603 \begin_layout Theorem
6604 For each
6605 \begin_inset space ~
6606 \end_inset
6607
6608
6609 \begin_inset Formula $k$
6610 \end_inset
6611
6612 , finding the
6613 \color none
6614
6615 \color red
6616 shortest path
6617 \color none
6618
6619 \color inherit
6620 in graphs with independence number at most
6621 \begin_inset space ~
6622 \end_inset
6623
6624
6625 \begin_inset Formula $k$
6626 \end_inset
6627
6628  is
6629 \color none
6630
6631 \color red
6632
6633 \begin_inset Formula $\Class{NL}$
6634 \end_inset
6635
6636 -complete
6637 \color inherit
6638 .
6639 \end_layout
6640
6641 \begin_layout Subsection
6642 Finding Paths in Undirected Graphs
6643 \end_layout
6644
6645 \begin_layout BeginFrame
6646 \begin_inset ERT
6647 status collapsed
6648
6649 \begin_layout Plain Layout
6650
6651 <1-2>[label=undirected]
6652 \end_layout
6653
6654 \end_inset
6655
6656 The Complexity of Finding Paths in Undirected Graphs
6657 \begin_inset Newline newline
6658 \end_inset
6659
6660 Is Party Unknown.
6661 \end_layout
6662
6663 \begin_layout Fact
6664 \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$
6665 \end_inset
6666
6667  is
6668 \begin_inset Formula $\Class{SL}$
6669 \end_inset
6670
6671 -complete.
6672 \end_layout
6673
6674 \begin_layout Corollary
6675 For undirected graphs, we can solve
6676 \end_layout
6677
6678 \begin_deeper
6679 \begin_layout Itemize
6680 the reachability problem in logspace iff
6681 \begin_inset Formula $\Class L=\Class{SL}$
6682 \end_inset
6683
6684 ,
6685 \end_layout
6686
6687 \begin_layout Itemize
6688 the construction problem in logspace iff
6689 \begin_inset ERT
6690 status collapsed
6691
6692 \begin_layout Plain Layout
6693
6694
6695 \backslash
6696 alt<1>{?}{
6697 \backslash
6698 alert{$
6699 \backslash
6700 Class L =
6701 \backslash
6702 Class{SL}$}}
6703 \end_layout
6704
6705 \end_inset
6706
6707 ,
6708 \end_layout
6709
6710 \begin_layout Itemize
6711 the optimization problem in logspace iff
6712 \begin_inset ERT
6713 status collapsed
6714
6715 \begin_layout Plain Layout
6716
6717
6718 \backslash
6719 alt<1>{?}{
6720 \backslash
6721 alert{$
6722 \backslash
6723 Class L =
6724 \backslash
6725 Class{NL}$}}
6726 \end_layout
6727
6728 \end_inset
6729
6730 ,
6731 \end_layout
6732
6733 \begin_layout Itemize
6734 the approximation problem in logspace iff ?.
6735
6736 \end_layout
6737
6738 \end_deeper
6739 \begin_layout Subsection
6740 The Approximation Scheme is Optimal
6741 \end_layout
6742
6743 \begin_layout BeginFrame
6744 \begin_inset ERT
6745 status collapsed
6746
6747 \begin_layout Plain Layout
6748
6749 [label=optimality]
6750 \end_layout
6751
6752 \end_inset
6753
6754 The Approximation Scheme is Optimal
6755 \end_layout
6756
6757 \begin_layout Theorem
6758 Suppose there exists an approximation scheme for
6759 \begin_inset Formula $\Lang{tournament-shortest-path}$
6760 \end_inset
6761
6762  that needs space
6763 \begin_inset Formula $O\bigl(\log|V|\log^{1-\epsilon}\frac{1}{r-1}\bigr)$
6764 \end_inset
6765
6766 .
6767  Then
6768 \begin_inset Formula $\Class{NL}\subseteq\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6769 \end_inset
6770
6771 .
6772 \end_layout
6773
6774 \begin_layout Proof
6775
6776 \end_layout
6777
6778 \begin_deeper
6779 \begin_layout Enumerate
6780 Suppose the approximation scheme exists.
6781 \begin_inset Newline newline
6782 \end_inset
6783
6784 We show
6785 \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}\in\Class{DSPACE}\bigl[\log^{2-\epsilon}n\bigr]$
6786 \end_inset
6787
6788 .
6789
6790 \end_layout
6791
6792 \begin_layout Enumerate
6793 Let
6794 \begin_inset Formula $(T,s,t)$
6795 \end_inset
6796
6797  be an input.
6798  Let
6799 \begin_inset Formula $n$
6800 \end_inset
6801
6802  be the number of vertices.
6803 \end_layout
6804
6805 \begin_layout Enumerate
6806 Run the approximation scheme for
6807 \begin_inset Formula $r:=1+\smash{\frac{1}{n+1}}$
6808 \end_inset
6809
6810 .
6811 \begin_inset Newline newline
6812 \end_inset
6813
6814 This needs space
6815 \begin_inset Formula $\smash{O(\log^{2-\epsilon}n)}$
6816 \end_inset
6817
6818 .
6819 \end_layout
6820
6821 \begin_layout Enumerate
6822 The resulting path has optimal length.
6823
6824 \begin_inset ERT
6825 status collapsed
6826
6827 \begin_layout Plain Layout
6828
6829
6830 \backslash
6831 qedhere
6832 \end_layout
6833
6834 \end_inset
6835
6836
6837 \end_layout
6838
6839 \end_deeper
6840 \begin_layout EndFrame
6841
6842 \end_layout
6843
6844 \end_body
6845 \end_document