lib/examples/beamerlyxexample1.lyx

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