lib/examples/beamerlyxexample1.lyx

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