lib/examples/beamerlyxexample1.lyx

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