lib/examples/beamerlyxexample1.lyx

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