lib/examples/beamerlyxexample1.lyx

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