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