lib/examples/beamerlyxexample1.lyx

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