lib/examples/beamerlyxexample1.lyx

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