lib/examples/beamerlyxexample1.lyx

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