lib/examples/beamerlyxexample1.lyx

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