lib/examples/beamerlyxexample1.lyx

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