lib/examples/beamerlyxexample1.lyx

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