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