%!PS-Adobe-1.0 %%Creator: csr:bmkapron (Bruce Kapron) %%Title: stdin (ditroff) %%CreationDate: Thu Apr 11 13:23:03 1996 %%EndComments % Start of psdit.pro -- prolog for ditroff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: psdit.pro,v 2.2 87/11/17 16:40:42 byron Rel $ /$DITroff 140 dict def $DITroff begin /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /xiL {72 8.25 mul 72 11 mul translate -90 rotate 72 resolution div dup neg scale 0 0 moveto /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F /pagesave save def}def /PB{save /psv exch def currentpoint translate resolution 72 div dup neg scale 0 0 moveto}def /PE{psv restore}def /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def /tan{dup sin exch cos div}bind def /point{resolution 72 div mul}bind def /dround {transform round exch round exch itransform}bind def /xT{/devname exch def}def /xr{/mh exch def /my exch def /resolution exch def}def /xp{}def /xs{docsave restore end}def /xt{}def /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not {fonts slotno fontname findfont put fontnames slotno fontname put}if}def /xH{/fontheight exch def F}bind def /xS{/fontslant exch def F}bind def /s{/fontsize exch def /fontheight fontsize def F}bind def /f{/fontnum exch def F}bind def /F{fontheight 0 le {/fontheight fontsize def}if fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}bind def /X{exch currentpoint exch pop moveto show}bind def /N{3 1 roll moveto show}bind def /Y{exch currentpoint pop exch moveto show}bind def /S /show load def /ditpush{}def/ditpop{}def /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}bind def /AN{4 2 roll moveto 0 exch ashow}bind def /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}bind def /AS{0 exch ashow}bind def /MX{currentpoint exch pop moveto}bind def /MY{currentpoint pop exch moveto}bind def /MXY /moveto load def /cb{pop}def % action on unknown char -- nothing for now /n{}def/w{}def /p{pop showpage pagesave restore /pagesave save def}def % Manual Feed Definitions /SetStTime{statusdict /manualfeedtimeout 120 put} def /SetStatus{statusdict /manualfeed true put statusdict /product get (LaserWriter) eq {version (23.0) eq % Don't redefine the show page if printer is not "Classic LW" {/p { {statusdict /printerstatus get exec 16#22000000 and 0 eq{exit}if}loop pop showpage pagesave restore /pagesave save def}def}if }if}def /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def /dstroke{currentpoint stroke moveto}bind def /Dl{2 copy gsave rlineto stroke grestore rmoveto}bind def /arcellipse{oldmat currentmatrix pop currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def rad 0 rad -180 180 arc oldmat setmatrix}def /Dc{gsave dup /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /De{gsave /diamv exch def /diamh exch def arcellipse dstroke grestore diamh 0 rmoveto}def /Da{currentpoint /by exch def /bx exch def /fy exch def /fx exch def /cy exch def /cx exch def /rad cx cx mul cy cy mul add sqrt def /ang1 cy neg cx neg atan def /ang2 fy fx atan def cx bx add cy by add 2 copy rad ang1 ang2 arcn stroke exch fx add exch fy add moveto}def /Barray 200 array def % 200 values in a wiggle /D~{mark}def /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put Bcontrol Blen 2 sub 2 copy get 2 mul put Bcontrol Blen 1 sub 2 copy get 2 mul put /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub {/i exch def Bcontrol i get 3 div Bcontrol i 1 add get 3 div Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div /Xbi Xcont Bcontrol i 2 add get 2 div add def /Ybi Ycont Bcontrol i 3 add get 2 div add def /Xcont Xcont Bcontrol i 2 add get add def /Ycont Ycont Bcontrol i 3 add get add def Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto }for dstroke}if}def end /ditstart{$DITroff begin /nfonts 60 def % NFONTS makedev/ditroff dependent! /fonts[nfonts{0}repeat]def /fontnames[nfonts{()}repeat]def /docsave save def }def % character outcalls /oc {/pswid exch def /cc exch def /name exch def /ditwid pswid fontsize mul resolution mul 72000 div def /ditsiz fontsize resolution mul 72 div def ocprocs name known{ocprocs name get exec}{name cb} ifelse}def /fractm [.65 0 0 .6 0 0] def /fraction {/fden exch def /fnum exch def gsave /cf currentfont def cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto fnum show rmoveto currentfont cf setfont(\244)show setfont fden show grestore ditwid 0 rmoveto} def /oce {grestore ditwid 0 rmoveto}def /dm {ditsiz mul}def /ocprocs 50 dict def ocprocs begin (14){(1)(4)fraction}def (12){(1)(2)fraction}def (34){(3)(4)fraction}def (13){(1)(3)fraction}def (23){(2)(3)fraction}def (18){(1)(8)fraction}def (38){(3)(8)fraction}def (58){(5)(8)fraction}def (78){(7)(8)fraction}def (sr){gsave .05 dm .16 dm rmoveto(\326)show oce}def (is){gsave 0 .15 dm rmoveto(\362)show oce}def (->){gsave 0 .02 dm rmoveto(\256)show oce}def (<-){gsave 0 .02 dm rmoveto(\254)show oce}def (==){gsave 0 .05 dm rmoveto(\272)show oce}def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop ditstart (psc)xT 576 1 1 xr 1(Times-Roman)xf 1 f 2(Times-Italic)xf 2 f 3(Times-Bold)xf 3 f 4(Times-BoldItalic)xf 4 f 5(Helvetica)xf 5 f 6(Helvetica-Bold)xf 6 f 7(Courier)xf 7 f 8(Courier-Bold)xf 8 f 9(Symbol)xf 9 f 10(DIThacks)xf 10 f 10 s 1 f xi %%EndProlog %%Page: 1 1 10 s 0 xH 0 xS 1 f 2094 795(MY)N 2243(THESIS)X 2264 975(by)N 2095 1155(Valerie)N 2352(King)X 1 p %%Page: 1 2 10 s 0 xH 0 xS 1 f 3 f 12 s 2021 972(CHAPTER)N 2538(1)X 2043 1296(Introduction)N 1 f 10 s 848 1743(Suppose)N 1148(we)X 1270(would)X 1498(like)X 1646(to)X 1736(determine)X 2085(whether)X 2372(an)X 2476(unknown)X 2802(input)X 2994(graph)X 3205(on)X 3313(nodes)X 3528(V={1,2,...,)X 2 f 3869(n)X 1 f 3922(})X 648 1923(has,)N 796(for)X 911(example,)X 1224(a)X 1281(node)X 1458(with)X 2 f 1621(n)X 1 f 1674(-1)X 1762(incoming)X 2085(edges)X 2289(and)X 2426(we)X 2541(can)X 2674(obtain)X 2895(information)X 3294(only)X 3457(by)X 3557(asking)X 3786(ques-)X 648 2103(tions)N 829(of)X 922(the)X 1046(form)X 1228("Is)X 1345(edge)X 1523({i,j})X 1689(in)X 1777(the)X 1901(graph?",)X 2199(where)X 2422(the)X 2546(choice)X 2782(of)X 2874(question)X 3170(may)X 3333(depend)X 3590(only)X 3757(on)X 3862(the)X 648 2283(information)N 1051(gained)X 1290(so)X 1386(far.)X 1521(The)X 2 f 1671(deterministic)X 1 f 2114(complexity)X 2 f 2499(D)X 1 f 2570(\()X 2 f 2597(P)X 1 f 2659(\))X 2711(of)X 2803(a)X 2863(property)X 3159(P)X 3227(is)X 3304(the)X 3426(number)X 3695(of)X 3786(ques-)X 648 2463(tions)N 824(that)X 965(must)X 1141(be)X 1238(asked)X 1442(in)X 1525(the)X 1644(worst)X 1843(case.)X 2023(A)X 2102(property)X 2395(is)X 2 f 2469(evasive)X 1 f 2727(if)X 2797(its)X 2893(complexity)X 3274(is)X 3348(the)X 3467(total)X 3630(input)X 3815(size,)X 648 2706(e.g.,)N 2 f 10 f 817 2660(I)N 817 2740(L)N 1 f 2748(2)Y 2 f 837 2667(n)N 10 f 890 2620(M)N 890 2700(N)N 890 2780(O)N 1 f 930 2706(for)N 2 f 1044(n)X 1 f 1097(-node)X 1300(graph)X 1503(properties.)X 848 2985(Any)N 1011(algorithm)X 1347(which)X 1568(computes)X 1900(a)X 1961(property)X 2258(in)X 2345(this)X 2484(manner)X 2749(may)X 2911(be)X 3011(represented)X 3406(by)X 3510(a)X 3570(binary)X 3799(deci-)X 648 3165(sion)N 815(tree)X 970(which)X 1200(describes)X 1533(its)X 1642(performance)X 2083(of)X 2184(all)X 2298(possible)X 2 f 2594(n)X 1 f 2647(-node)X 2864(input)X 3062(graphs.)X 3330(Each)X 3525(internal)X 3804(node)X 648 3345(corresponds)N 1058(to)X 1142(a)X 1200(query.)X 1425(The)X 1572(algorithm)X 1904(branches)X 2211(to)X 2294(the)X 2413(left)X 2541(or)X 2629(right)X 2801(subtree,)X 3074(depending)X 3429(on)X 3530(the)X 3649(answer)X 3898(to)X 648 3525(the)N 767(query,)X 991(until)X 1157(reaching)X 1454(a)X 1510(leaf)X 1651(which)X 1867(is)X 1940(labelled)X 2214("accept")X 2506(or)X 2593("reject".)X 2878(Then)X 3063(D\(P\))X 3239(is)X 3312(the)X 3430(minimum)X 3760(height)X 648 3705(of)N 735(any)X 871(decision)X 1158(tree)X 1299(that)X 1439(computes)X 1766(P.)X 848 3918(A)N 933(graph)X 1142(on)X 1248(V={1,2,...,)X 2 f 1589(n)X 1 f 1642(})X 1706(may)X 1870(be)X 1972(viewed)X 2230(as)X 2323(a)X 2385(subset)X 2611(of)X 2704(edges)X 2913(E={{i,j})X 9 f 3185(|)X 1 f (for)S 3321(all)X 3427(i,j)X 9 f 3517(\316)X 1 f 3600(V,)X 3704(i)X 2 f 9 f 3752(\271)X 1 f 3796(j}.)X 3902(A)X 648 4098(collection)N 996(of)X 1095(such)X 1274(graphs)X 1519(is)X 1603(called)X 1826(a)X 2 f 1893(graph)X 2115(property)X 1 f 2422(on)X 2 f 2533(n)X 1 f 2617(nodes)X 2835(provided)X 3151(that)X 3302(it)X 3377(is)X 3461(invariant)X 3777(under)X 648 4278(renumbering)N 1079(of)X 1167(the)X 1286(nodes.)X 1514(The)X 1660(de\256nition)X 1987(of)X 2 f 2075(digraph)X 2349(property)X 1 f 2646(is)X 2720(the)X 2839(same,)X 3044(except)X 3274(the)X 3392(edges)X 3595(are)X 3714(ordered)X 648 4458(pairs)N 824(of)X 911(nodes.)X 848 4671(A)N 2 f 931(bipartite)X 1231(graph)X 1447(property)X 1 f 1748(on)X 1853(node)X 2034(sets)X 2179(V)X 2262(and)X 2403(W)X 2503(is)X 2580(a)X 2640(collection)X 2980(P)X 3048(of)X 3139(subsets)X 3394(of)X 3485(V)X 2 f 9 f 3543(\264)X 1 f 3587(W)X 3687(which)X 3907(is)X 648 4851(invariant)N 953(under)X 1156(permutations)X 1594(of)X 1681(V)X 1759(and)X 1895(of)X 1982(W.)X 848 5064(A)N 926(graph)X 1129(property)X 1421(is)X 2 f 1494(nontrivial)X 1 f 1829(if)X 1898(it)X 1962(holds)X 2155(for)X 2269(some)X 2458(but)X 2580(not)X 2702(all)X 2802(graphs.)X 848 5277(It)N 917(is)X 2 f 990(monotone)X 1 f 1326(\(increasing\))X 1730(if)X 1799(it)X 1863(is)X 1936(not)X 2058(destroyed)X 2390(by)X 2490(the)X 2608(addition)X 2890(of)X 2977(edges.)X 848 5490(In)N 948(1973,)X 1161(Aanderaa)X 1503(and)X 1652(Rosenberg)X 2028(conjectured)X 2436(that)X 2589(the)X 2720(deterministic)X 3171(complexity)X 3564(of)X 3664(any)X 3813(non-)X 648 5670(trivial)N 863(monotone)X 1207(graph)X 1414(or)X 1505(digraph)X 1774(property)X 2069(on)X 2 f 2172(n)X 1 f 2248(nodes)X 2458(is)X 2534(at)X 2615(least)X 2 f 9 f 2785(e)X 2 f 2820(n)X 7 s 1 f 2869 5637(2)N 10 s 2920 5670(for)N 3037(some)X 3229(constant)X 2 f 9 f 3519(e)X 1 f 3554(.)X 3617(Rivest)X 3844(and)X 2 p %%Page: 2 3 10 s 0 xH 0 xS 1 f 3920 666(2)N 648 954(Vuillemin)N 998(proved)X 1247(the)X 1371(conjecture)X 1732(in)X 1819(1975)X 2004([RV].)X 2214(Their)X 2413(bound)X 2638(of)X 2 f 2730(n)X 7 s 1 f 2779 921(2)N 2 f 10 s 954(/)Y 1 f 2829(16)X 2934(was)X 3084(improved)X 3416(by)X 3521(Kleitman)X 3844(and)X 648 1134(Kwiatkowski)N 1098([KK])X 1291(and)X 1430(then)X 1591(by)X 1693(Kahn,)X 1909(Saks,)X 2102(Sturtevant)X 2453([KSS])X 2675(to)X 2 f 2759(n)X 7 s 1 f 2808 1101(2)N 2 f 10 s 1134(/)Y 1 f 2858(4)X 2 f 9 f (+)S 2 f 2942(o)X 1 f 2995(\()X 2 f 3022(n)X 7 s 1 f 3071 1101(2)N 10 s 1134(\).)Y 3188(In)X 3277(Chaper)X 3531(2,)X 3613(we)X 3729(discuss)X 648 1314(some)N 842(of)X 934(the)X 1057(techniques)X 1425(which)X 1646(were)X 1828(used,)X 2020(and)X 2161(we)X 2280(prove)X 2488(a)X 2549(new)X 2708(lower)X 2916(bound)X 3141(on)X 3246(the)X 3369(complexity)X 3753(of)X 3844(any)X 648 1494(nontrivial)N 981(monotone)X 1323(digraph)X 1590(property)X 1884(on)X 2 f 1986(n)X 1 f 2061(nodes)X 2270(of)X 2 f 2359(n)X 7 s 1 f 2408 1461(2)N 2 f 10 s 1494(/)Y 1 f 2458(4)X 2 f 9 f (+)S 2 f 2542(o)X 1 f 2595(\()X 2 f 2622(n)X 7 s 1 f 2671 1461(2)N 10 s 1494(\).)Y 2788(Karp's)X 3029(conjecture,)X 3406(that)X 3548(all)X 3649(nontrivial)X 648 1674(monotone)N 988(graph)X 1191(properties)X 1532(are)X 1651(evasive,)X 1932(remains)X 2206(open.)X 848 1887(In)N 950(Chapter)X 1239(3,)X 1334(we)X 1462(consider)X 1768(the)X 1900(cost)X 2063(of)X 2164(computing)X 2540(when)X 2748(the)X 2880(choice)X 3124(of)X 3225(query)X 3442(may)X 3614(depend)X 3880(on)X 648 2067(coin\257ips.)N 992(A)X 2 f 1079(randomized)X 1486(decision)X 1782(tree)X 1936(algorithm)X 1 f 2280(can)X 2421(be)X 2526(represented)X 2926(by)X 3035(a)X 3100(binary)X 3333(tree)X 3482(whose)X 3715(internal)X 648 2247(nodes)N 858(correspond)X 1238(to)X 1323(either)X 1529(queries)X 1784(or)X 1874(coin\257ips.)X 2192(The)X 2340(algorithm)X 2674(branches)X 2983(to)X 3068(the)X 3189(right)X 3363(or)X 3452(left)X 3581(subtree)X 3835(of)X 3924(a)X 648 2427(coin\257ip)N 922(node)X 1108(depending)X 1472(on)X 1582(the)X 1710(outcome)X 2016(of)X 2112(the)X 2239(coin\257ip.)X 2552(The)X 2706(cost)X 2864(of)X 2960(the)X 3087(algorithm)X 3427(is)X 3509(the)X 3636(maximum)X 648 2607(over)N 815(all)X 919(input)X 1107(graphs)X 1345(of)X 1436(the)X 1558(expected)X 1868(number)X 2137(of)X 2227(questions)X 2552(asked.)X 2798(The)X 2 f 2946(randomized)X 3347(complexity)X 3718(R\(P\))X 1 f 3893(of)X 648 2787(a)N 704(property)X 996(P)X 1060(is)X 1133(the)X 1251(minimum)X 1581(cost)X 1730(of)X 1817(any)X 1953(randomized)X 2352(decision)X 2639(tree)X 2780(algorithm)X 3111(which)X 3327(computes)X 3654(P.)X 848 3000(The)N 1007(randomized)X 1420(complexity)X 1814(of)X 1915(nontrivial)X 2260(monotone)X 2614(graph)X 2831(properties)X 3186(was)X 3345(\256rst)X 3503(studied)X 3768(by)X 3882(A.)X 648 3180(Yao.)N 824(In)X 913(1977,)X 1115(he)X 1213(conjectured)X 1610(a)X 1668(lower)X 1873(bound)X 2095(of)X 2 f 9 f 2184(W)X 1 f 2246(\()X 2 f 2273(n)X 7 s 1 f 2322 3147(2)N 10 s 3180(\))Y 2399(and)X 2537(observed)X 2849(a)X 2907(lower)X 3111(bound)X 3332(of)X 2 f 9 f 3420(W)X 1 f 3482(\()X 2 f 3509(n)X 1 f 3562(\))X 3610(on)X 3711(the)X 3830(ran-)X 648 3360(domized)N 958(complexity)X 1352(of)X 1453(nontrivial)X 1798(monotone)X 2 f 2152(n)X 1 f 2205(-node)X 2422(graph)X 2639(properties.)X 3013(No)X 3144(progress)X 3449(was)X 3607(made)X 3814(until)X 648 3540(1987,)N 853(when)X 1052(Yao)X 1211(proved)X 1459(a)X 1520(lower)X 1728(bound)X 1953(of)X 2 f 9 f 2045(W)X 1 f 2107(\()X 2 f 2134(n)X 1 f 2187(\(log)X 2 f 2316(n)X 1 f 2369(\))X 7 s 2396 3507(1)N 2 f (/)S 1 f 2440(12)X 10 s 3540(\).)Y 2568(We)X 2705(improve)X 2997(this)X 3137(to)X 2 f 9 f 3224(W)X 1 f 3286(\()X 2 f 3313(n)X 7 s 1 f 3362 3507(5)N 2 f (/)S 1 f 3406(4)X 10 s 3540(\).)Y 3506(Yao's)X 3723(conjec-)X 648 3720(ture)N 805(remains)X 1091(open,)X 1298(for)X 1423(no)X 1534(nontrivial)X 1876(monotone)X 2227(graph)X 2441(property)X 2744(has)X 2882(been)X 3065(shown)X 3305(to)X 3398(have)X 3581(randomized)X 648 3963(complexity)N 1028(less)X 1168(than)X 1346 4020(2)N 1346 3915(1)N 2 f 10 f 1334 3939(h)N 1358(h)X 2 f 10 f 1419 3877(I)N 1419 3957(J)N 1419 4037(L)N 1 f 4005(2)Y 2 f 1439 3924(n)N 10 f 1492 3877(M)N 1492 3957(J)N 1492 4037(O)N 1 f 848 4242(In)N 940(Chapter)X 1219(4,)X 1304(we)X 1423(relax)X 1609(the)X 1732(model)X 1957(again)X 2156(by)X 2261(allowing)X 2566(the)X 2689(randomized)X 3093(algorithm)X 3429(to)X 3515(err)X 3629(with)X 3795(max-)X 648 4422(imum)N 860(probability)X 2 f 9 f 1237(e)X 1 f 1298(on)X 1404(any)X 1546(input)X 1735(graph.)X 1963(We)X 2100(show)X 2294(that)X 2439(for)X 2558(any)X 2699(constant)X 2991(epsilon)X 2 f 3247(<)X 1 f (1)S 2 f (/)S 1 f 3363(5)X 3428(these)X 3618(algorithms)X 648 4602(have)N 820(complexity)X 2 f 9 f 1200(W)X 1 f 1262(\()X 2 f 1289(n)X 7 s 1 f 1338 4569(5)N 2 f (/)S 1 f 1382(4)X 10 s 4602(\).)Y 848 4905(Below,)N 1097(we)X 1211(de\256ne)X 1427(other)X 1612(terms)X 1810(which)X 2026(are)X 2145(used)X 2312(throughout)X 2683(the)X 2801(thesis.)X 848 5118(The)N 994(concepts)X 1296(of)X 1384(deterministic)X 1823(and)X 1959(randomized)X 2378(complexity)X 2758(for)X 2872(graph)X 3075(properties)X 3416(may)X 3574(be)X 3670(extended)X 648 5298(to)N 740(any)X 886(set)X 1005(property.)X 1327(A)X 2 f 1415(set)X 1534(property)X 1 f 1840(is)X 1923(a)X 1989(collection)X 2335(of)X 2432(subsets)X 2693(of)X 2790(an)X 2896(element)X 3179(set)X 3297(X=)X 3429({)X 2 f 3467(x)X 7 s 1 f 3512 5316(1)N 10 s 5298(,)Y 2 f (x)S 7 s 1 f 3605 5316(2)N 10 s 5298(,)Y 2 f 3673 5274(.)N 3713(.)X 3753(.)X 1 f 3793 5298(,)N 2 f (x)S 7 s 3849 5316(m)N 10 s 1 f 3902 5298(}.)N 648 5481(Given)N 866(a)X 924(set)X 1035(property)X 1329(S)X 1395(of)X 1484(subsets)X 1737(of)X 1826(X)X 1906(and)X 2044(an)X 2142(input)X 2328(set)X 2439(I)X 2487(which)X 2704(is)X 2778(a)X 2835(\256xed)X 3016(but)X 3139(unknown)X 3458(subset)X 3679(of)X 3767(X,)X 3866(we)X 648 5661(would)N 871(like)X 1013(to)X 1097(determine)X 1440(whether)X 1721(I)X 9 f 1770(\316)X 1 f 1849(S)X 1915(by)X 2017(asking)X 2248(questions)X 2572(of)X 2661(the)X 2781(form)X 2959("Is)X 2 f 3072(x)X 7 s 3108 5679(i)N 10 s 1 f 9 f 3159 5661(\316)N 1 f 3238(I?")X 3356(A)X 3436(set)X 3547(property)X 3841(S)X 3907(is)X 3 p %%Page: 3 4 10 s 0 xH 0 xS 1 f 3920 666(3)N 2 f 648 954(evasive)N 1 f 911(if)X 2 f 986(m)X 1 f 1083(queries)X 1341(must)X 1522(be)X 1624(asked)X 1833(by)X 1939(a)X 2001(decision)X 2294(tree)X 2441(algorithm)X 2778(in)X 2866(the)X 2990(worst)X 3194(case.)X 3379(The)X 3530(de\256nitions)X 3893(of)X 648 1134(monotone)N 988(and)X 1124(nontrivial)X 1455(can)X 1587(be)X 1683(naturally)X 1988(extended)X 2298(from)X 2474(graph)X 2677(properties)X 3018(to)X 3100(any)X 3236(set)X 3345(property.)X 848 1347(A)N 2 f 931(bipartite)X 1231(graph)X 1447(property)X 1 f 1748(on)X 1853(node)X 2034(sets)X 2179(V)X 2262(and)X 2403(W)X 2503(is)X 2580(a)X 2640(collection)X 2980(P)X 3048(of)X 3139(subsets)X 3394(of)X 3485(V)X 2 f 9 f 3543(\264)X 1 f 3587(W)X 3687(which)X 3907(is)X 648 1527(invariant)N 953(under)X 1156(permutations)X 1594(of)X 1681(V)X 1759(and)X 1895(of)X 1982(W.)X 848 1740(We)N 980(review)X 1219(the)X 1337(standard)X 1629(de\256nition)X 1955(of)X 2042(a)X 2098(group)X 2305(action.)X 848 1953(A)N 933(group)X 1147(G)X 2 f 1232(acts)X 1388(on)X 1 f 1495(a)X 1558(set)X 1674(X)X 1759(if)X 1835(there)X 2023(is)X 2103(a)X 2166(mapping)X 2473(from)X 2656(G)X 2 f 9 f 2741(\264)X 1 f 2812(X)X 2897(->)X 2996(X)X 3081(such)X 3254(that)X 3400(the)X 3524(following)X 3861(are)X 648 2133(true.)N 813(\(The)X 985(image)X 1201(of)X 1288(\(g,x\))X 1462(for)X 1576(g)X 9 f 1636(\316)X 1 f 1713(G,)X 1811(x)X 9 f 1871(\316)X 1 f 1948(X,)X 2046(is)X 2119(denoted)X 2393(by)X 2493(gx.\):)X 648 2346(\(i\))N 764(For)X 895(g,)X 975(g')X 9 f 1062(\316)X 1 f 1139(G,)X 1237(x)X 9 f 1297(\316)X 1 f 1374(X,)X 1472(g\(g'x\))X 1693(=)X 1758(\(gg'\)x.)X 648 2559(\(ii\))N 786(Let)X 913(e)X 969(be)X 1065(the)X 1183(identity)X 1447(element)X 1721(of)X 1808(G.)X 1926(Then)X 2111(ex=x.)X 848 2772(G)N 929(acts)X 2 f 1077(transitively)X 1 f 1460(on)X 1563(X)X 1644(if)X 1715(for)X 1831(any)X 1969(x,x')X 9 f 2118(\316)X 1 f 2197(X,)X 2297(there)X 2480(exists)X 2684(a)X 2742(g)X 9 f 2804(\316)X 1 f 2883(G)X 2963(such)X 3132(that)X 3274(gx=x'.)X 3528(The)X 3675(action)X 3893(of)X 648 2952(G)N 727(on)X 828(X)X 907(induces)X 1173(an)X 1270(action)X 1487(on)X 1587(the)X 1705(set)X 1814(of)X 1901(all)X 2001(subsets)X 2252(of)X 2339(X,)X 2437(e.g.,)X 2593(g{)X 2 f 2671(x)X 7 s 2707 2970(a)N 1 f 2744(,)X 2 f 10 s 2952(x)Y 7 s 2794 2970(b)N 10 s 2835 2952(,)N 2875(.)X 2915(.)X 2955(.)X 2995(,)X 3028(x)X 7 s 3064 2970(z)N 10 s 1 f 3099 2952(})N 3157(=)X 3222({)X 2 f 3280(gx)X 7 s 3356 2970(a)N 1 f 3393(,)X 2 f 10 s 2952(gx)Y 7 s 3483 2970(b)N 10 s 3524 2952(,)N 3564(.)X 3604(.)X 3644(.)X 3684(,)X 3717(gx)X 7 s 3793 2970(z)N 10 s 1 f 3828 2952(}.)N 3906(If)X 648 3135(S)N 725(is)X 811(any)X 960(collection)X 1308(of)X 1407(subsets)X 1670(of)X 1769(X)X 1859(such)X 2038(that)X 2190(for)X 2316(all)X 2428(I)X 9 f 2487(\316)X 1 f 2576(S)X 2652(and)X 2800(all)X 2912(g)X 9 f 2984(\316)X 1 f 3073(G,)X 3183(gI)X 9 f 3282(\316)X 1 f 3371(S,)X 3467(then)X 3637(we)X 3763(say)X 3902(G)X 2 f 648 3315(preserves)N 1 f 976(S)X 1040(or)X 1127(S)X 1191(is)X 2 f 1264(invariant)X 1 f 1577(under)X 1780(G.)X 848 3528(A)N 955(graph)X 1187(property)X 1508(on)X 2 f 1637(n)X 1 f 1739(nodes)X 1975(can)X 2136(thus)X 2318(be)X 2443(viewed)X 2723(as)X 2838(a)X 2922(set)X 3059(property)X 3379(with)X 3569(element)X 3871(set)X 2 f 648 3708(E)N 9 f 710(=)X 2 f 754({{i)X 1 f 853(,)X 2 f 880(j)X 915(})X 1 f 9 f 960(|)X 2 f 989(i)X 1 f 1024(,)X 2 f 1051(j)X 9 f 1086(\316)X 2 f 1143(V)X 1 f 1205(,)X 2 f (i)S 9 f 1260(\271)X 2 f 1311(j)X 1346(})X 1 f 1403(which)X 1624(is)X 1702(invariant)X 2011(under)X 2218(the)X 2340(group)X 2551(of)X 2642(permutations)X 3084(of)X 3175(V,)X 3277(where)X 3498(each)X 3670(permuta-)X 648 3888(tion)N 2 f 9 f 792(p)X 1 f 856(maps)X 1045(each)X 1213(edge)X 1385({)X 2 f 1423(i)X 1 f 1458(,)X 2 f 1485(j)X 1 f 1520(})X 1578(to)X 1660({)X 2 f 9 f 1698(p)X 2 f 1742(i)X 1 f 1777(,)X 2 f 9 f (p)S 2 f 1848(j)X 1 f 1883(}.)X 4 p %%Page: 4 5 10 s 0 xH 0 xS 1 f 3 f 12 s 2021 972(CHAPTER)N 2538(2)X 1776 1296(Deterministic)N 2356(Complexity)X 10 s 648 1806(2.1.)N 808(Overview)X 1 f 848 2019(The)N 1005(complexity)X 1397(of)X 1496(digraph)X 1773(properties)X 2126(was)X 2283(\256rst)X 2439(investigated)X 2858(by)X 2970(Holt)X 3143(and)X 3290(Reingold,)X 3634(who)X 3803(were)X 648 2199(seeking)N 922(to)X 1013(\256nd)X 1166(a)X 1231(lower)X 1443(bound)X 1672(for)X 1795(any)X 1940(cycle)X 2139(detection)X 2461(algorithm)X 2800([B],[MW].)X 3176(Lower)X 3414(bounds)X 3673(for)X 3795(other)X 648 2379(graph)N 854(properties)X 1198(were)X 1378(proved)X 1624(by)X 1727(Hopcroft)X 2040(and)X 2179(Tarjan,)X 2432(Kirkpatrick,)X 2845(Milner)X 3086(and)X 3225(Walsh,)X 3472(Bollobas,)X 3798(Best,)X 648 2559(van)N 785(Emde)X 993(Boas)X 1174(and)X 1311(H.)X 1410(Lenstra)X 1672([HT],)X 1874([K],)X 2027([MW],[B],)X 2396([BVL].)X 2670(Much)X 2877(of)X 2964(the)X 3082(pre-1978)X 3392(work)X 3577(on)X 3677(the)X 3795(com-)X 648 2739(plexity)N 891(of)X 979(monotone)X 1320(and)X 1457(non-monotone)X 1945(graph)X 2149(properties)X 2491(is)X 2565(described)X 2894(in)X 2 f 2977(Extremal)X 3292(Graph)X 3522(Properties)X 1 f 3880(by)X 648 2919(Bollobas)N 952([B].)X 848 3132(Rosenberg)N 1216(conjectured)X 1616(the)X 1739(existence)X 2063(of)X 2154(a)X 2214(constant)X 2 f 9 f 2505(e)X 1 f 2564(such)X 2735(that)X 2879(every)X 3082(nontrivial)X 3417(graph)X 3624(or)X 3715(digraph)X 648 3312(property)N 958(has)X 1102(complexity)X 1519(at)X 1614(least)X 2 f 9 f 1798(e)X 2 f 1833(n)X 7 s 1 f 1882 3279(2)N 10 s 3312(.)Y 1967(However,)X 2319(Aanderaa)X 2665(showed)X 2947(a)X 3020(counterexample)X 3570(for)X 3701(directed)X 648 3492(graphs.)N 913(He)X 1038(observed)X 1359(that)X 1510(it)X 1585(was)X 1741(possible)X 2034(to)X 2127(determine)X 2479(whether)X 2769(a)X 2835(digraph)X 3110(with)X 2 f 3282(n)X 1 f 3365(nodes)X 3582(contained)X 3924(a)X 648 3672("sink",)N 903(i.e.,)X 1057(a)X 1129(node)X 1321(with)X 1499(in-degree)X 2 f 1839(n)X 9 f 1892(-)X 1 f 1936(1)X 2012(and)X 2164(out-degree)X 2544(0,)X 2640(in)X 2738(3)X 2 f (n)S 1 f 2867(queries.)X 3155(Together,)X 3500(Aanderaa)X 3844(and)X 648 3852(Rosenberg)N 1014(formulated)X 1389(the)X 1510(following)X 1843(conjecture)X 2200(which)X 2418(appeared)X 2731(in)X 2815(1973.)X 3017(\(It)X 3115(has)X 3244(also)X 3395(been)X 3569(attributed)X 3898(to)X 648 4032(Lipton)N 881(and)X 1017(Snyder)X 1264([B].\))X 3 f 648 4245(Aanderaa-Rosenberg)N 1413(Conjecture:)X 2 f 1859(There)X 2081(exists)X 2294(a)X 2369(constant)X 9 f 2675(e)X 2 f 2745(such)X 2927(that)X 3086(every)X 3295(nontrivial)X 3644(monotone)X 648 4425(graph)N 859(or)X 950(digraph)X 1223(property)X 1519(on)X 1619(n)X 1679(nodes)X 1886(has)X 2017(complexity)X 2385(at)X 2467(least)X 9 f 2638(e)X 2 f 2673(n)X 7 s 1 f 2722 4392(2)N 2 f 10 s 4425(.)Y 1 f 848 4638(The)N 1006(\256rst)X 1163(example)X 1468(of)X 1568(a)X 1637(family)X 1879(of)X 1979(\(non-monotone\))X 2533(graph)X 2749(properties)X 3103(with)X 3278(complexity)X 3670(less)X 3822(than)X 2 f 9 f 648 4818(W)N 1 f 710(\()X 2 f 737(n)X 7 s 1 f 786 4785(2)N 10 s 4818(\))Y 870(was)X 1024(shown)X 1262(in)X 1353(1974)X 1542(by)X 1651(M.)X 1771(R.)X 1873(Best,)X 2084(P.)X 2177(van)X 2321(Emde)X 2536(Boas,)X 2744(and)X 2888(H.)X 2994(W.)X 3118(Lenstra,)X 3407(Jr.)X 3533([BVL].)X 3795(They)X 648 4998(gave)N 821(an)X 918(algorithm)X 1250(with)X 1413(complexity)X 1794(6)X 2 f (n)S 1 f 1907(which)X 2123(determines)X 2495(whether)X 2774(a)X 2830(graph)X 3033(is)X 3106(a)X 3162("scorpion")X 3524(graph,)X 3747(that)X 3887(is,)X 648 5178(if)N 721(it)X 789(has)X 920(a)X 980(node)X 2 f 1160(b)X 1 f 1237(of)X 1328(degree)X 2 f 1567(n)X 9 f 1620(-)X 1 f 1664(2,)X 1748(a)X 1808(node)X 2 f 1988(t)X 1 f 2047(of)X 2138(degree)X 2377(1,)X 2461(and)X 2601(a)X 2661(node)X 2 f 2841(u)X 1 f 2918(of)X 3009(degree)X 3248(2)X 3312(which)X 3531(is)X 3607(adjacent)X 3898(to)X 648 5358(both)N 2 f 810(t)X 1 f 865(and)X 2 f 1001(b)X 1 f 1054(.)X 1094(Edges)X 1310(among)X 1548(the)X 1666(remaining)X 2 f 2011(n)X 9 f 2064(-)X 1 f 2108(3)X 2168(nodes)X 2375(may)X 2533(or)X 2620(may)X 2778(not)X 2900(be)X 2996(present.)X 848 5571(The)N 999 0.2279(Aanderaa-Rosenberg)AX 1704(Conjecture)X 2082(was)X 2233(proved)X 2482(in)X 2570(1975)X 2756(by)X 2862(R.)X 2960(Rivest)X 3189(and)X 3330(J.)X 3406(Vuillemin.)X 3795(They)X 648 5751(showed)N 933(that)X 1093(the)X 1231(conjecture)X 1606(holds)X 1819(true)X 1984(for)X 2 f 9 f 2118(e=)X 1 f 2197(1)X 2 f (/)S 1 f 2259(16.)X 2399(The)X 2564(constant)X 2870(was)X 3034(further)X 3292(improved)X 3638(to)X 3739(1)X 2 f (/)S 1 f 3801(9)X 3880(by)X 3920 6048(4)N 5 p %%Page: 5 6 10 s 0 xH 0 xS 1 f 3920 666(5)N 648 954(Kleitman)N 971(and)X 1112(Kwiatkowski.)X 1584(Both)X 1763(results)X 1996(relied)X 2203(on)X 2307(a)X 2367(similar)X 2613(technique)X 2949(for)X 3067(proving)X 3340(evasiveness)X 3743(of)X 3834(cer-)X 648 1134(tain)N 788(set)X 897(properties.)X 1278(That)X 1445(technique)X 1777(is)X 1850(presented)X 2178(in)X 2260(the)X 2378(next)X 2536(section.)X 848 1347(In)N 941(1984,)X 1147(Kahn,)X 1367(Saks,)X 1564(and)X 1706(Sturtevant)X 2061(developed)X 2416(a)X 2477(more)X 2667(general)X 2929(method)X 3194(to)X 3281(prove)X 3489(evasiveness)X 3893(of)X 648 1527(set)N 760(properties)X 1104(and)X 1243(of)X 1333(graph)X 1539(and)X 1678(digraph)X 1946(properties)X 2290(where)X 2510(the)X 2631(number)X 2899(of)X 2989(nodes)X 3199(is)X 3275(a)X 3334(prime)X 3543(power.)X 3786(Their)X 648 1707(topological)N 1028(approach)X 1343(is)X 1416(discussed)X 1743(in)X 1825(section)X 2072(2.3.)X 848 1920(By)N 975(plugging)X 1293(their)X 1474(proof)X 1682(of)X 1783(evasiveness)X 2196(into)X 2353(a)X 2422(recursive)X 2750(formula)X 3037(developed)X 3400(by)X 3513(Kleitman)X 3844(and)X 648 2100(Kwiatkowski,)N 1120(Kahn,)X 1339(Saks,)X 1535(and)X 1676(Sturtevant)X 2030(raised)X 2247(the)X 2370(lower)X 2578(bound)X 2803(on)X 2908(the)X 3031(complexity)X 3416(of)X 3508(any)X 3649(nontrivial)X 648 2280(monotone)N 990(graph)X 1195(property)X 1489(on)X 1591(any)X 1728(number)X 1994(of)X 2082(nodes)X 2 f 2290(n)X 1 f 2343(.)X 2384(Let)X 2 f 2512(M)X 7 s 2579 2298(n)N 10 s 1 f 2641 2280(and)N 2 f 2778(M)X 7 s 2845 2298(n)N 2854 2247(D)N 1 f 10 s 2915 2280(denote)N 3150(the)X 3269(minimum)X 3600(complexity)X 648 2463(of)N 746(any)X 893(nontrivial)X 1235(monotone)X 1586(graph)X 1800(or)X 1898(digraph)X 2174(property,)X 2497(respectively,)X 2936(on)X 2 f 3047(n)X 1 f 3131(nodes.)X 3369(They)X 3565(showed)X 3840(that)X 2 f 648 2643(M)N 7 s 715 2661(n)N 724 2610(D)N 10 s 9 f 764 2643(\263)N 2 f 808(M)X 7 s 875 2661(n)N 10 s 9 f 916 2643(\263)N 2 f 960(n)X 7 s 1 f 1009 2610(2)N 2 f 10 s 2643(/)Y 1 f 1059(4)X 2 f 9 f (-)S 2 f 1143(o)X 1 f 1196(\()X 2 f 1223(n)X 7 s 1 f 1272 2610(2)N 10 s 2643(\).)Y 848 2859(In)N 942(section)X 1196(2.4,)X 1343(we)X 1464(observe)X 1741(that)X 1888(the)X 2 f 2013(o)X 1 f 2066(\()X 2 f 2093(n)X 7 s 1 f 2142 2826(2)N 10 s 2859(\))Y 2224(term)X 2398(in)X 2487(this)X 2629(lower)X 2839(bound)X 3066(can)X 3205(be)X 3308(made)X 3509(smaller,)X 3791(as)X 3884(an)X 648 3039(easy)N 819(consequence)X 1258(of)X 1353(A.)X 1459(Yao's)X 1679(1986)X 1867(proof)X 2069(that)X 2217(all)X 2324(nontrivial)X 2662(monotone)X 3009(bipartite)X 3303(graph)X 3513(properties)X 3861(are)X 648 3219(evasive)N 922([Y2].)X 1126(Yao's)X 1350(proof)X 1556(demonstrates)X 2011(a)X 2079(nice)X 2245(application)X 2633(of)X 2732(the)X 2862(KSS)X 3040(topological)X 3432(approach)X 3759(and)X 3907(is)X 648 3399(presented)N 976(in)X 1058(section)X 1305(2.4.)X 848 3612(Finally,)N 1114(in)X 1196(section)X 1443(2.5,)X 1603(we)X 1717(improve)X 2004(the)X 2122(lower)X 2325(bound)X 2545(of)X 2 f 2632(M)X 7 s 2699 3630(n)N 2708 3579(D)N 1 f 10 s 2768 3612(to)N 2 f 2850(n)X 7 s 1 f 2899 3579(2)N 2 f 10 s 3612(/)Y 1 f 2949(2)X 2 f 9 f (-)S 2 f 3033(o)X 1 f 3086(\()X 2 f 3113(n)X 7 s 1 f 3162 3579(2)N 10 s 3612(\).)Y 848 3828(The)N 1001(following)X 1340(conjecture)X 1703(of)X 1798(R.)X 1899(Karp)X 2088(remains)X 2370(open,)X 2574(even)X 2754(for)X 2876(graph)X 3087(properties)X 3436(on)X 3544(as)X 3638(few)X 3786(as)X 3880(10)X 648 4008(nodes:)N 3 f 648 4221(Conjecture)N 1052(2.1)X 1172(\(Karp\):)X 2 f 1455(Every)X 1663(nontrivial)X 1998(monotone)X 2334(graph)X 2545(or)X 2636(digraph)X 2909(property)X 3205(is)X 3278(evasive.)X 3 f 648 4497(2.2.)N 808(Early)X 1019(Results)X 1 f 848 4710(Let)N 979(S)X 1047(be)X 1147(any)X 1287(set)X 1400(property)X 1695(with)X 1860(element)X 2137(set)X 2249(X.)X 2370(A)X 2451(key)X 2590(idea)X 2747(of)X 2837(the)X 2958(Rivest-Vuillemin)X 3536(result)X 3737(is)X 3813(their)X 648 4890(observation)N 1050(\(discovered)X 1453(independently)X 1935(by)X 2043(Best,)X 2233(van)X 2377(Emde)X 2592(Boas)X 2779(and)X 2922(H.)X 3027(Lenstra,)X 3315(Jr.)X 3420([BVL]\))X 3688(that)X 3835(in)X 3924(a)X 648 5070(decision)N 939(tree)X 1084(to)X 1170(compute)X 1470(S,)X 1558(every)X 1761(leaf)X 1906(at)X 1987(depth)X 2188(less)X 2331(than)X 9 f 2492(|)X 1 f (X)S 9 f 2566(|)X 1 f 2605(accepts)X 2865(the)X 2986(same)X 3174(number)X 3442(of)X 3532(sets)X 3675(with)X 3840(odd)X 648 5250(cardinality)N 1013(as)X 1102(with)X 1266(even)X 1440(cardinality.)X 1844(Consequently,)X 2325(for)X 2440(a)X 2497(nonevasive)X 2879(set)X 2989(property)X 3282(S,)X 3367(the)X 3486(number)X 3752(of)X 3840(sets)X 648 5430(in)N 730(S)X 794(with)X 956(odd)X 1096(cardinality)X 1459(equals)X 1684(the)X 1802(number)X 2067(of)X 2154(sets)X 2294(in)X 2376(S)X 2440(with)X 2602(even)X 2774(cardinality.)X 6 p %%Page: 6 7 10 s 0 xH 0 xS 1 f 3920 666(6)N 3 f 648 954(Rivest-Vuillemin)N 1246(Theorem)X 1578([RV]:)X 2 f 1795(Let)X 1917(S)X 1977(be)X 2073(a)X 2133(collection)X 2469(of)X 2551(subsets)X 2802(of)X 2884(X,)X 2973(where)X 648 1134(\(i\))N 9 f 744(|)X 2 f (X)S 9 f 809(|)X 2 f 845(is)X 918(a)X 978(prime)X 1185(power)X 1405(p)X 7 s 9 f 1454 1101(a)N 10 s 2 f 1489 1134(,)N 648 1314(\(ii\))N 766(is)X 839(invariant)X 1152(under)X 1359(G,)X 1457(a)X 1517(group)X 1728(which)X 1939(acts)X 2088(transitively)X 2468(on)X 2568(X,)X 648 1494(\(iii\))N 9 f 788(\306)X 2 f 874(or)X 965(X)X 1034(is)X 1107(in)X 1189(S)X 1249(but)X 1371(not)X 1493(both.)X 648 1674(Then)N 828(S)X 888(is)X 961(evasive.)X 3 f 648 1887(Proof:)N 1 f 889(Let)X 2 f 1018(num)X 7 s 1156 1905(k)N 10 s 1 f 1216 1887(be)N 1314(the)X 1434(number)X 1701(of)X 1789(sets)X 1930(in)X 2013(S)X 2078(of)X 2166(size)X 2 f 2312(k)X 1 f 2361(.)X 2422(Let)X 2550(s\()X 2 f 2608(k)X 1 f 2657(\))X 2705(=)X 2 f 15 s 9 f 2771 1911(S)N 10 s 2 f 1 f 9 f 2855 1887(|)N 2 f 2884(A)X 1 f 9 f 2959(|)X 2 f 1 f 3009(over)X 3173(all)X 3274(A)X 9 f 3353(\316)X 1 f 3431(S)X 3496(where)X 9 f 3714(|)X 1 f (A)S 9 f 3788(|)X 1 f 3825(=)X 2 f 3891(k)X 1 f 3940(.)X 648 2076(Since)N 855(G)X 942(acts)X 1096(transitively)X 1485(on)X 1594(X,)X 1700(each)X 2 f 1876(x)X 7 s 1912 2094(i)N 10 s 1 f 1969 2076(appears)N 2243(in)X 2333(the)X 2459(same)X 2652(number)X 2925(of)X 3020(subsets)X 3279(of)X 3374(size)X 2 f 3527(k)X 1 f 3576(.)X 3624(Thus,)X 2 f 3832(p)X 7 s 9 f 3881 2043(a)N 1 f 10 s 9 f 3944 2076(|)N 1 f 648 2259(s\()N 2 f 706(k)X 1 f 755(\).)X 842(But)X 977(s\()X 2 f 1035(k)X 1 f 1084(\))X 1131(=)X 2 f 1196(knum)X 7 s 1370 2277(k)N 10 s 1 f 1408 2259(,)N 1448(so)X 1539(for)X 1653(0<)X 2 f 1738(k)X 1 f 1787(<)X 2 f 1832(p)X 7 s 9 f 1881 2226(a)N 1 f 10 s 1916 2259(,)N 2 f 1956(p)X 1 f 9 f 2009(|)X 2 f (num)S 7 s 2163 2277(k)N 10 s 1 f 2201 2259(.)N 848 2517(Let)N 975(U=)X 7 s 1099 2598(0)N 2 f 15 s 9 f 1078 2541(S)N 7 s 2 f 1087 2436(p)N 4 s 9 f 1120 2406(a)N 1 f 10 s 1149 2517(\()N 2 f 9 f 1176(-)X 1 f 1220(1\))X 2 f 7 s 1287 2484(k)N 10 s 1325 2517(num)N 7 s 1463 2535(k)N 10 s 1 f 1501 2517(.)N 1541(Since)X 9 f 1739(\306)X 1 f 1825(or)X 1912(X)X 1990(but)X 2112(not)X 2234(both)X 2396(are)X 2515(in)X 2597(S,)X 2701(U)X 2 f 9 f 2779 MX (==)186 549 oc 1 f 2843(1)X 2903(mod)X 2 f 3065(p)X 1 f 3118(.)X 848 2796(Since)N 1051(each)X 1224 0.3611(acceptance)AX 1603(leaf)X 1749(of)X 1841(a)X 1902(non-evasive)X 2315(property)X 2611(accepts)X 2872(an)X 2972(equal)X 3170(number)X 3439(of)X 3530(sets)X 3674(with)X 3840(odd)X 648 2976(and)N 784(even)X 956(cardinality,)X 1339(U)X 2 f 9 f 1417 MX (==)186 549 oc 1 f 1481(0)X 1541(mod)X 2 f 1703(p)X 1 f 1776(for)X 1890(non-evasive)X 2298(properties.)X 2659(Then)X 2844(S)X 2908(must)X 3083(be)X 3179(evasive.)X 848 3189(The)N 999(application)X 1380(of)X 1472(this)X 1612(theorem)X 1900(to)X 1987(the)X 2110 0.2279(Aanderaa-Rosenberg)AX 2814(Conjecture)X 3191(is)X 3269(not)X 3396(immediate,)X 3779(for)X 3898(in)X 648 3432(general,)N 2 f 10 f 939 3346(I)N 939 3426(J)N 939 3506(L)N 1 f 3474(2)Y 2 f 959 3393(n)N 10 f 1012 3346(M)N 1012 3426(J)N 1012 3506(O)N 1 f 1053 3432(is)N 1127(not)X 1250(a)X 1307(prime)X 1515(power.)X 1777(Rivest)X 2002(and)X 2139(Vuillemin)X 2484(reduce)X 2720(the)X 2839(computation)X 3260(of)X 3347(a)X 3403(graph)X 3606(property)X 3898(to)X 648 3678(the)N 769(computation)X 1192(of)X 1282(a)X 1340(set)X 1451(property)X 1745(which)X 1963(satis\256es)X 2238(the)X 2358(conditions)X 2713(of)X 2802(their)X 2971(theorem)X 3256(by)X 3358(revealing)X 3679(informa-)X 648 3858(tion)N 799(about)X 1004(some)X 1200(of)X 1293(the)X 1417(edges)X 1626(in)X 1714(the)X 1838(input)X 2028(graph)X 2237(to)X 2325(the)X 2449(algorithm.)X 2806(This)X 2974(technique)X 3312(of)X 3405(reduction)X 3734(is)X 3813(used)X 648 4038(several)N 899(times)X 1095(in)X 1180(proofs)X 1408(presented)X 1739(here.)X 1921(The)X 2069(particular)X 2400(reduction)X 2726(used)X 2896(by)X 2999(Rivest)X 3226(and)X 3365(Vuillemin)X 3712(will)X 3858(not)X 648 4218(be)N 744(described)X 1072(here.)X 848 4431(In)N 939(1975,)X 1143(Kleitman)X 1465(and)X 1605(Kwiatkowski)X 2056(improved)X 2387(the)X 2508(constant)X 2798(in)X 2883(the)X 3004 0.2279(Aanderaa-Rosenberg)AX 3706(Conjec-)X 648 4611(ture)N 797(to)X 2 f 883(n)X 7 s 1 f 932 4578(2)N 2 f 10 s 4611(/)Y 1 f 982(9.)X 1066(Using)X 1281(techniques)X 1648(similar)X 1894(to)X 1980(those)X 2173(of)X 2264(Rivest)X 2492(and)X 2631(Vuillemin,)X 2998(they)X 3159(proved)X 3405(evasiveness)X 3807(for)X 3924(a)X 648 4791(class)N 824(of)X 911(bipartite)X 1198(graph)X 1401(properties.)X 3 f 648 5004(Theorem)N 988(2.2)X 1116([KK]:)X 2 f 1349(Let)X 1479(P)X 1556(be)X 1660(any)X 1804(monotone)X 2148(bipartite)X 2451(graph)X 2670(property)X 2974(on)X 3082(V)X 3159(and)X 3307(W.)X 3422(If)X 9 f 3499(|)X 2 f (W)S 9 f 3582(|)X 2 f 3626(is)X 3706(a)X 3773(prime)X 648 5184(power,)N 888(then)X 1046(P)X 1115(is)X 1188(evasive.)X 1 f 848 5397(Their)N 1050(lower)X 1261(bound)X 1488(for)X 1609(the)X 1734(complexity)X 2121(of)X 2215(graph)X 2425(properties)X 2773(made)X 2974(use)X 3108(of)X 3202(the)X 3327(following)X 3665(recursive)X 648 5577(formula:)N 7 p %%Page: 7 8 10 s 0 xH 0 xS 1 f 3920 666(7)N 3 f 648 954(Theorem)N 980(2.3)X 1100([KK]:)X 2 f 1325(M)X 7 s 1392 972(n)N 10 s 9 f 1433 954(\263)N 2 f 1477(min\(M)X 7 s 1691 972(n)N 9 f 1728(-)X 1 f 1759(1)X 2 f 10 s 954(,)Y 1827(y)X 1 f 1876(\()X 2 f 1903(n)X 9 f 1956(-)X 2 f 2000(y)X 1 f 2049(\))X 2 f 2076(\))X 2123(where)X 2339(y)X 2395(denotes)X 2660(the)X 2778(prime)X 2985(power)X 3205(closest)X 3443(to)X 3525(n.)X 3 f 648 1170(Proof:)N 1 f 893(We)X 1031(sketch)X 1262(the)X 1386(proof.)X 1626(We)X 1764(will)X 1914(reduce)X 2155(the)X 2279(computation)X 2704(of)X 2796(any)X 2937(nontrivial)X 3273(monotone)X 3618(graph)X 3826(pro-)X 648 1350(perty)N 835(P)X 901(on)X 2 f 1003(n)X 1 f 1078(nodes)X 1287(to)X 1371(the)X 1491(computation)X 1913(of)X 2002(a)X 2060(nontrivial)X 2392(monotone)X 2733(graph)X 2937(property)X 3230(on)X 2 f 3331(n)X 1 f 3384(-1)X 3472(nodes)X 3680(\(in)X 3790(cases)X 648 1530(\(i\))N 746(and)X 884(\(ii\)\))X 1031(or)X 1120(a)X 1178(nontrivial)X 1511(monotone)X 1853(bipartite)X 2142(graph)X 2347(property)X 2641(\(case)X 2829(iii\).)X 2964(Let)X 3092(V'={2,3,...,)X 2 f 3460(n)X 1 f 3513(})X 3572(and,)X 3729(for)X 3844(any)X 648 1710(set)N 757(of)X 844(nodes)X 1051(V,)X 1149(let)X 2 f 1249(V)X 1272 1690(\303)N 1 f 1331 1710(be)N 1427(the)X 1545(set)X 1654(of)X 1741(all)X 1841(edges)X 2044(on)X 2144(V.)X 2242(Let)X 2369(T)X 2438(=)X 2503({{1,i})X 9 f 2699(|)X 1 f 2735(for)X 2849(all)X 2949(i)X 9 f 2991(\316)X 1 f 3068(V'})X 648 1923(Case)N 825(\(i\):)X 944(V')X 9 f 1050(\316)X 1 f 1128(P.)X 1233(We)X 1366(reveal)X 1584(that)X 1725(the)X 1844(edges)X 2048(in)X 2131(T)X 2201(are)X 2320(absent)X 2545(from)X 2721(the)X 2839(input)X 3023(graph.)X 3246(Then)X 3431(any)X 3567(algorithm)X 3898(to)X 648 2103(compute)N 944(P)X 1008(must)X 1183(compute)X 1479(P')X 1570(where)X 1787(P')X 1878(is)X 1951(de\256ned)X 2207(as)X 2294(follows:)X 2576(For)X 2707(B)X 9 f 2780(\315)X 2 f 2857(V)X 9 f 2906(\242)X 2 f 2890 2083(\303)N 1 f 2939 2103(,)N 2979(B)X 9 f 3052(\316)X 1 f 3129(P')X 3220(iff)X 3316(B)X 9 f 3389(\316)X 1 f 3466(P.)X 2 f 648 2316(Case)N 830(\(ii\):)X 976(V)X 9 f 1025(\242)X 2 f 1009 2296(\303)N 9 f 1079 2316(\316)N 2 f 1097(/)X 1157(P.)X 1 f 1247(We)X 1380(reveal)X 1598(that)X 1739(the)X 1858(edges)X 2062(in)X 2145(T)X 2215(are)X 2335(in)X 2418(the)X 2537(input)X 2722(graph.)X 2946(Then)X 3132(any)X 3269(algorithm)X 3601(to)X 3684(compute)X 648 2496(P)N 712(must)X 887(compute)X 1183(P')X 1274(where)X 1491(P')X 1582(is)X 1655(de\256ned)X 1911(as)X 1998(follows:)X 2280(For)X 2411(B)X 9 f 2484(\316)X 2 f 2561(V)X 9 f 2610(\242)X 2 f 2630(hat)X 1 f 2745(,)X 2785(B)X 9 f 2858(\316)X 1 f 2935(P')X 3026(iff)X 3122(B)X 9 f 3195(\310)X 1 f 3277(T)X 9 f 3346(\316)X 1 f 3423(P.)X 2 f 648 2709(Case)N 834(\(iii\):)X 1007(T)X 9 f 1077(\316)X 2 f 1095(/)X 1160(P)X 1234(and)X 1379(V)X 9 f 1428(\242)X 2 f 1412 2689(\303)N 9 f 1486 2709(\316)N 2 f 1568(P.)X 1 f 1682(We)X 1819(partition)X 2115(the)X 2 f 2238(n)X 1 f 2316(nodes)X 2528(into)X 2677(set)X 2791(A)X 2874(with)X 2 f 3041(p)X 7 s 9 f 3090 2676(a)N 1 f 10 s 3150 2709(nodes)N 3362(and)X 3503(set)X 3617(B)X 3695(with)X 3862(the)X 648 2889(remaining)N 994(nodes.)X 1222(We)X 1355(reveal)X 1573(that)X 2 f 1714(A)X 1737 2869(\303)N 1 f 1797 2889(is)N 1871(in)X 1954(the)X 2073(input)X 2258(graph)X 2462(and)X 2599(every)X 2799(edge)X 2972(in)X 2 f 3054(B)X 3077 2869(\303)N 1 f 3136 2889(is)N 3209(absent.)X 3474(Then)X 3659(any)X 3795(algo-)X 648 3069(rithm)N 843(to)X 927(compute)X 1225(P)X 1291(must)X 1468(compute)X 1766(P',)X 1879(where)X 2098(P')X 2191(is)X 2266(de\256ned)X 2524(as)X 2613(follows:)X 2897(For)X 3030(any)X 3168(subset)X 3389(C)X 9 f 3463(\315)X 1 f 3541(A)X 2 f 9 f 3599(\264)X 1 f 3643(B,)X 3737(C)X 9 f 3811(\316)X 1 f 3889(P')X 648 3249(iff)N 744(C)X 9 f 817(\310)X 2 f 899(A)X 922 3229(\303)N 1 f 9 f 981 3249(\316)N 1 f 1058(P'.)X 1189(By)X 1302(Theorem)X 1612(2.2,)X 1752(P')X 1843(is)X 1916(evasive.)X 3 f 648 3525(2.3.)N 808(Topological)X 1227(Approach)X 1 f 848 3738(A)N 931(monotone)X 2 f 1276(decreasing)X 1 f 1653(set)X 1766(property)X 2062(is)X 2139(a)X 2199(set)X 2312(property)X 2608(whose)X 2837(complement)X 3257(is)X 3334(monotone)X 3678(\(increas-)X 648 3918(ing\).)N 817(It)X 886(is)X 959(easy)X 1122(to)X 1204(see)X 1327(that)X 1467(the)X 1585(complexity)X 1965(of)X 2052(a)X 2108(set)X 2217(property)X 2509(and)X 2645(its)X 2740(complement)X 3156(are)X 3275(equal.)X 848 4131(Kahn,)N 1068(Saks,)X 1265(Sturtevant)X 1619([KSS])X 1844(developed)X 2199(a)X 2260(technique)X 2597(for)X 2716(proving)X 2990(evasiveness)X 3394(by)X 3499(observing)X 3840(that)X 648 4311(results)N 884(from)X 1066(algebraic)X 1387(topology)X 1697(could)X 1901(be)X 2003(applied.)X 2305(In)X 2398(particular,)X 2752(they)X 2916(observed)X 3232(that)X 3378(for)X 3498(any)X 3640(monotone)X 648 4491(decreasing)N 1022(set)X 1141(property)X 1443(P)X 1517(with)X 1689(set)X 1808(property)X 2110(X,)X 2218(if)X 2297(the)X 2425(sets)X 2575(P)X 2649(could)X 2857(be)X 2962(accepted)X 3273(by)X 3382(a)X 3447(decision)X 3743(tree)X 3893(of)X 648 4671(height)N 868(less)X 1008(than)X 9 f 1166(|)X 1 f (X)S 9 f 1240(|)X 1 f (,)S 1296(then)X 1454(P\\{)X 9 f 1558(\306)X 1 f 1624(})X 1682(is)X 1755(a)X 1811(collapsible)X 2178(abstract)X 2448(simplicial)X 2783(complex.)X 3 f 648 4884(Lemma)N 939(2.4)X 1067(\(KSS\):)X 2 f 1326(A)X 1403(monotone)X 1747(decreasing)X 2126(set)X 2242(property)X 2545(P\\{)X 9 f 2675(\306)X 2 f 2741(})X 2800(is)X 2880(an)X 2987(\(abstract)X 3303(simplicial\))X 3672(complex,)X 648 5064(\(which)N 886(we)X 995(call)X 1135(the)X 1253("complex)X 1575(P"\).)X 1 f 848 5277(This)N 1015(follows)X 1280(from)X 1461(the)X 1584(de\256nition.)X 1935(An)X 2 f 2058(abstract)X 2345(simplicial)X 2685(complex)X 1 f 2978(is)X 3056(a)X 3117(collection)X 2 f 9 f 3458(D)X 1 f 3532(of)X 3624(\256nite)X 3813(non-)X 648 5457(empty)N 868(sets,)X 1028(such)X 1195(that)X 1335(if)X 1404(A)X 1482(is)X 1555(an)X 1651(element)X 1925(of)X 2 f 9 f 2012(D)X 1 f 2081(then)X 2239(so)X 2330(is)X 2403(every)X 2602(non-empty)X 2969(subset)X 3189(of)X 3276(A.)X 8 p %%Page: 8 9 10 s 0 xH 0 xS 1 f 3920 666(8)N 848 954(Each)N 1032(subset)X 1255(of)X 1345(a)X 1404(complex)X 1703(is)X 1779(called)X 1994(a)X 2 f 2053(face.)X 1 f 2250(The)X 2398(dimension)X 2754(of)X 2844(a)X 2903(face)X 3061(A)X 3142(is)X 9 f 3218(|)X 1 f (A)S 9 f 3292(|)X 1 f 3330(-1.)X 3439(Faces)X 3644(of)X 3733(dimen-)X 648 1134(sion)N 801(0)X 861(are)X 980(called)X 2 f 1192(vertices.)X 1 f 1502(The)X 1647(union)X 1849(of)X 1936(the)X 2054(vertices)X 2324(in)X 2 f 9 f 2406(D)X 1 f 2475(is)X 2548(called)X 2760(the)X 2 f 2878(vertex)X 3095(set.)X 1 f 3244(\(See)X 3407([Mu].\))X 888 1347(A)N 2 f 967(free)X 1113(face)X 1 f 1268(is)X 1342(a)X 1399(non-maximal)X 1847(face)X 2003(which)X 2220(is)X 2294(contained)X 2627(in)X 2710(only)X 2873(one)X 3010(maximal)X 3310(face.)X 3485(An)X 2 f 3603(elementary)X 648 1527(collapse)N 1 f 941(of)X 2 f 9 f 1034(D)X 1 f 1109(is)X 1188(the)X 1312(process)X 1578(of)X 1670(removing)X 2002(from)X 2 f 9 f 2183(D)X 1 f 2257(some)X 2451(free)X 2602(face,)X 2782(together)X 3070(with)X 3237(all)X 3342(faces)X 3533(containing)X 3896(it.)X 648 1707(We)N 780(say)X 2 f 9 f 907(D)X 1 f 976(is)X 2 f 1049(collapsible)X 1 f 1420(if)X 2 f 9 f 1489(D)X 1 f 1558(can)X 1690(be)X 1786(reduced)X 2061(to)X 2143(a)X 2199(vertex)X 2420(by)X 2520(a)X 2576(sequence)X 2891(of)X 2978(elementary)X 3355(collapses.)X 3 f 648 1920(Lemma)N 935(2.5)X 1059(\(KSS\):)X 2 f 1314(If)X 1387(a)X 1451(monotone)X 1791(decreasing)X 2167(set)X 2280(property)X 2580(S)X 2644(is)X 2721(nonevasive,)X 3122(then)X 3284(the)X 3405(complex)X 3696(S)X 3759(is)X 3835(col-)X 648 2100(lapsible.)N 3 f 648 2313(Proof:)N 1 f 891(We)X 1026(describe)X 1317(a)X 1376(sequence)X 1694(of)X 1784(elementary)X 2164(collapses)X 2481(to)X 2566(obtain)X 2789(a)X 2848(vertex)X 3072(by)X 3175(considering)X 3572(the)X 3693(decision)X 648 2493(tree)N 789(of)X 876(any)X 1012(algorithm)X 1343(for)X 1457(P)X 1521(with)X 1683(complexity)X 2063(<)X 2 f 1 f 9 f 2141(|)X 2 f 2170(X)X 1 f 9 f 2245(|)X 2 f 1 f 2274(.)X 848 2706(For)N 984(each)X 1157(accepting)X 1490(leaf)X 2 f 1636(L)X 1 f 1693(,)X 1738(let)X 2 f 1843(L)X 7 s 1887 2724(A)N 10 s 1 f 1958 2706(be)N 2058(the)X 2180(set)X 2293(of)X 2384(elements)X 2693(known)X 2935(to)X 3021(be)X 3121(in)X 3207(the)X 3329(sets)X 3473(accepted)X 3779(by)X 2 f 3883(L)X 1 f 3940(.)X 648 2889(Let)N 2 f 782(L)X 7 s 826 2907(N)N 10 s 1 f 903 2889(be)N 1006(the)X 1131(elements)X 1442(not)X 1570(yet)X 1694(asked)X 1903(about)X 2107(on)X 2213(the)X 2337(path)X 2501(to)X 2 f 2589(L)X 1 f 2646(.)X 2712(The)X 2863(leftmost)X 3151(leaf)X 2 f 3298(Left)X 1 f 3461(accepts)X 9 f 3724(\306)X 1 f 3790(.)X 3836(If)X 3916(it)X 648 3072(accepts)N 906(more)X 1092(than)X 1251(one)X 1388(other)X 1574(subset,)X 1815(expand)X 2067(this)X 2202(leaf)X 2343(into)X 2487(a)X 2543(node)X 2719(and)X 2855(two)X 2995(leaves)X 3216(by)X 3316(asking)X 3545(about)X 3743(an)X 3839(ele-)X 648 3252(ment)N 829(in)X 2 f 912(Left)X 7 s 1036 3270(N)N 10 s 1 f 1107 3252(and)N 1244(repeat)X 1462(until)X 1629(the)X 1748(new)X 1903(leftmost)X 2186(leaf)X 2 f 2328(Left)X 1 f 9 f 2465(\242)X 1 f 2506(accepts)X 2764(only)X 9 f 2927(\306)X 1 f 3014(and)X 3150(a)X 3206(subset)X 3426(containing)X 3784(a)X 3840(sin-)X 648 3435(gle)N 766(element,)X 1060(i.e.,)X 1198(a)X 1254(vertex.)X 848 3648(Let)N 2 f 977(Right)X 1 f 1185(be)X 1283(the)X 1403(rightmost)X 1730(accepting)X 2059(leaf.)X 2221(If)X 2 f 2296(Right)X 9 f 2482(\271)X 2 f 2526(Left)X 1 f 2663(',)X 2731(then)X 2 f 2890(Right)X 7 s 3063 3666(A)N 10 s 1 f 3131 3648(is)N 3205(a)X 3262(free)X 3409(face)X 3565(contained)X 3898(in)X 648 3831(the)N 781(maximal)X 1096(face)X 2 f 1266(Right)X 7 s 1439 3849(A)N 10 s 9 f 1486 3831(\310)N 2 f 1548(Right)X 7 s 1721 3849(N)N 10 s 1 f 1805 3831(and)N 1955(the)X 2087(sets)X 2241(accepted)X 2557(by)X 2 f 2671(Right)X 1 f 2891(are)X 3024(exactly)X 3290(the)X 3422(faces)X 3622(containing)X 2 f 648 4014(Right)N 7 s 821 4032(A)N 10 s 1 f 868 4014(.)N 911(Remove)X 1201(these)X 1389(faces)X 1578(from)X 1757(P)X 1824(and)X 2 f 1963(Right)X 1 f 2172(from)X 2351(the)X 2472(tree.)X 2635(Repeat)X 2880(with)X 3044(the)X 3164(next)X 3324(rightmost)X 3652(accepting)X 648 4197(leaf,)N 809(until)X 975(only)X 1137(a)X 1193(vertex)X 1414(remains)X 1688(in)X 1770(P.)X 848 4500(We)N 980(may)X 1138 0.3409(characterize)AX 1548(a)X 1604(complex)X 1900(by)X 2000(studying)X 2295(group)X 2502(actions)X 2749(on)X 2849(the)X 2967(complex.)X 848 4713(Let)N 979(G)X 1061(be)X 1161(a)X 1221(group)X 1432(which)X 1652(acts)X 1801(on)X 1905(X)X 1987(and)X 2127(preserves)X 2 f 9 f 2455(D)X 1 f 2504(.)X 2548(From)X 2745(the)X 2867(induced)X 3145(action)X 3365(of)X 3455(G)X 3536(on)X 2 f 9 f 3639(D)X 1 f 3688(,)X 3731(we)X 3848(can)X 648 4893(de\256ne)N 864(the)X 982(complex)X 1278(of)X 2 f 1365(\256xed)X 1537(points)X 1 f 1752(of)X 2 f 9 f 1839(D)X 1 f 1928(denoted)X 2 f 9 f 2202(D)X 7 s 2 f 2251 4911(G)N 10 s 1 f 2324 4893(as:)N 648 5109(1.)N 728(The)X 873(vertex)X 1094(set)X 1203(Y)X 1281(of)X 2 f 9 f 1368(D)X 7 s 2 f 1417 5127(G)N 10 s 1 f 1490 5109(=)N 1555({)X 2 f 1593(y)X 7 s 1629 5127(A)N 10 s 1 f 9 f 1676 5109(|)N 1 f 1712(A)X 1790(is)X 1863(a)X 1919(minimal)X 2205(G-invariant)X 2595(face)X 2750(of)X 2 f 9 f 2837(D)X 1 f 2886(}.)X 648 5325(2.)N 728(The)X 873(faces)X 1059(of)X 2 f 9 f 1146(D)X 7 s 2 f 1195 5343(G)N 10 s 1 f 1268 5325(are)N 1387(all)X 1487(subsets)X 1738(of)X 1825(Y)X 1903(=)X 1968({)X 2 f 2006(y)X 7 s 2042 5343(A)N 10 s 1 f 2089 5325(,)N 2 f (y)S 7 s 2145 5343(B)N 10 s 2192 5325(,)N 2232(.)X 2272(.)X 2312(.)X 2352(,)X 2385(y)X 7 s 2421 5343(Z)N 10 s 1 f 2465 5325(})N 2523(such)X 2690(that)X 2 f 2830(A)X 9 f 2892(\310)X 2 f 2954(B)X 9 f 3016(\310)X 2 f 3098 5301(.)N 3138(.)X 3178(.)X 9 f 3218 5325(\310)N 2 f 3280(Z)X 1 f 9 f 3357(\316)X 2 f 9 f 3434(D)X 1 f 3483(.)X 848 5541(Let)N 2 f 9 f 978(D)X 1 f 1050(be)X 1149(a)X 1208(complex)X 1507(with)X 1672(vertex)X 1895(set)X 2006(X,)X 9 f 2106(|)X 1 f (X)S 9 f 2180(|)X 1 f (=)S 2 f 2241(n)X 1 f 2294(,)X 2336(and)X 2474(let)X 2 f 2583(f)X 7 s 2618 5559(d)N 10 s 1 f 2681 5541(be)N 2779(the)X 2899(number)X 3166(of)X 3255(faces)X 3443(of)X 3532(dimension)X 2 f 3887(d)X 1 f 3940(.)X 648 5724(Then)N 833(the)X 2 f 951(Euler)X 1149(characteristic)X 1 f 1614(of)X 2 f 9 f 1701(D)X 1 f 1770(is:)X 9 p %%Page: 9 10 10 s 0 xH 0 xS 1 f 3920 666(9)N 2 f 7 s 2125 1077(d)N 9 f 2162(=)X 1 f 2193(0)X 2 f 15 s 9 f 2137 1020(S)N 7 s 2 f 2124 915(n)N 9 f 2161(-)X 1 f 2192(1)X 10 s 996(\()Y 2 f 9 f 2247(-)X 1 f 2291(1\))X 2 f 7 s 2358 963(d)N 10 s 2406 996(f)N 7 s 2441 1014(d)N 10 s 1 f 848 1308(We)N 986(are)X 1111(now)X 1275(ready)X 1480(to)X 1568(state)X 1740(a)X 1801(result)X 2004(from)X 2185(algebraic)X 2505(topology,)X 2834(which)X 3055(provides)X 3356(the)X 3479(main)X 3664(tool)X 3813(used)X 648 1488(here.)N 3 f 648 1701(Lemma)N 936(2.6)X 1061(\(Oliver\):)X 2 f 1385(Let)X 1512(G)X 1595(be)X 1696(a)X 1761(group)X 1977(acting)X 2201(on)X 2305(a)X 2369(collapsible)X 2744(complex)X 9 f 3036(D)X 2 f 3109(and)X 3253(let)X 3357(p)X 3421(be)X 3521(prime.)X 3752(If)X 3825(G)X 3907(is)X 648 1881(cyclic)N 860(or)X 955(G)X 1037(has)X 1171(a)X 1234(normal)X 1488(p-subgroup)X 1880(H)X 1961(such)X 2131(that)X 2278(G/H)X 2439(is)X 2515(cyclic,)X 2746(then)X 2907(the)X 3028(Euler)X 3229(characteristic)X 3697(of)X 9 f 3782(D)X 7 s 2 f 3831 1899(G)N 10 s 3907 1881(is)N 648 2064(1.)N 1 f 848 2277(Oliver)N 1073(proves)X 1307(the)X 1425(lemma)X 1663(for)X 1777(complexes)X 2140(which)X 2356(satisfy)X 2585(even)X 2757(weaker)X 3010(conditions.)X 3383(See)X 3519([O])X 3651(and)X 3787([S].)X 848 2490(From)N 1041(lemmas)X 1310(2.4,)X 1450(2.5,)X 1590(and)X 1726(2.6,)X 1866(we)X 1980(have:)X 3 f 648 2703(Theorem)N 990(2.7)X 1120(\(KSS\):)X 2 f 1381(If)X 1460(the)X 1588(complex)X 1886(S)X 1956(for)X 2079(a)X 2149(monotone)X 2495(decreasing)X 2877(set)X 2995(property)X 3300(is)X 3382(invariant)X 3704(under)X 3920(a)X 648 2883(group)N 862(G)X 942(which)X 1155(is)X 1230(cyclic)X 1440(or)X 1533(has)X 1666(a)X 1728(normal)X 1981(p-subgroup)X 2372(H)X 2452(such)X 2621(that)X 2767(G/H)X 2927(is)X 3002(cyclic)X 3212(and)X 3354(p)X 3416(is)X 3491(prime,)X 3720(and)X 3862(the)X 648 3063(Euler)N 846(characteristic)X 1311(of)X 9 f 1393(D)X 7 s 2 f 1442 3081(G)N 10 s 9 f 1495 3063(\271)N 2 f 1559(1,)X 1639(then)X 1797(the)X 1915(set)X 2024(property)X 2320(is)X 2393(evasive.)X 3 f 648 3279(Theorem)N 990(2.8)X 1120(\(KSS\):)X 2 f 1380(If)X 1458(P)X 1536(is)X 1618(a)X 1687(nontrivial,)X 2051(monotone)X 2396(graph)X 2616(or)X 2716(digraph)X 2998(property)X 3303(on)X 3412(p)X 7 s 9 f 3461 3246(a)N 10 s 2 f 3525 3279(nodes)N 3741(with)X 3907(p)X 648 3459(prime,)N 875(then)X 1033(P)X 1102(is)X 1175(evasive.)X 3 f 648 3672(Proof:)N 1 f 900(Let)X 2 f 1040(P)X 10 f 1056 3598(h)N 1057(h)X 2 f 1 f 1135 3672(be)N 1244(the)X 1375(complement)X 1804(of)X 1904(P,)X 2001(which)X 2230(is)X 2316(monotone)X 2669(decreasing)X 3045(and)X 3193(nontrivial.)X 3576(Identify)X 3862(the)X 648 3852(nodes)N 861(with)X 1029(GF\()X 2 f 1158(p)X 7 s 9 f 1207 3819(a)N 1 f 10 s 1242 3852(\),)N 1315(the)X 1439(\256eld)X 1607(with)X 2 f 1775(p)X 7 s 9 f 1824 3819(a)N 1 f 10 s 1884 3852(elements)N 2194(which)X 2415(has)X 2547(a)X 2608(cyclic)X 2825(multiplicative)X 3294(group.)X 3546(Let)X 3678(G)X 3761(be)X 3862(the)X 648 4032(group)N 862(of)X 956(automorphisms)X 1476(=)X 1548({x)X 1653(->)X 1752(ax)X 1855(+)X 1927(b:)X 2016(a,b)X 9 f 2139(\316)X 1 f 2222(GF\()X 2 f 2351(p)X 7 s 9 f 2400 3999(a)N 1 f 10 s 2435 4032(\),)N 2508(a)X 2 f 9 f 2570(\271)X 1 f 2640(0\))X 2733(}.)X 2817(G)X 2901(has)X 3034(a)X 3096(normal)X 3349(p-group)X 3629(H)X 3713(=)X 3784({x)X 3888(->)X 648 4212(x+b:)N 819(b)X 9 f 883(\316)X 1 f 964(GF\()X 2 f 1093(p)X 7 s 9 f 1142 4179(a)N 1 f 10 s 1177 4212(\)})N 1266(and)X 1405(preserves)X 2 f 1732(P)X 10 f 1748 4138(h)N 1749(h)X 2 f 1 f 1794 4212(,)N 1837(since)X 2 f 2025(P)X 10 f 2041 4138(h)N 2042(h)X 2 f 1 f 2110 4212(is)N 2186(invariant)X 2494(under)X 2700(permutation)X 3110(of)X 3200(the)X 3321(nodes.)X 3571(G)X 3652(maps)X 3844(any)X 648 4392(pair)N 804(of)X 902(nodes)X 1120(to)X 1213(any)X 1360(other)X 1556(pair,)X 1732(and)X 1879(so,)X 2001(maps)X 2201(any)X 2348(edge)X 2531(to)X 2624(any)X 2771(other)X 2966(edge.)X 3168(Then)X 2 f 3363(P)X 10 f 3379 4318(h)N 3380(h)X 7 s 2 f 3421 4356(G)N 10 s 9 f 3474 4392(=\306)N 1 f 3614(with)X 3786(Euler)X 648 4572(characteristic)N 1097(0.)X 3 f 648 4848(2.4.)N 808(Deterministic)X 1292(Complexity)X 1708(of)X 1795(Graph)X 2041(Properties)X 1 f 848 5061(As)N 958(observed)X 1269(by)X 1370(Kahn,)X 1585(Saks)X 1757(and)X 1894(Sturtevant)X 2244([KSS],)X 2485(the)X 2604(recursive)X 2920(formula)X 3195(of)X 3283(Kleitman)X 3601(and)X 3737(Kwiat-)X 648 5241(kowski)N 899(\(Theorem)X 1236(2.3\))X 1383(and)X 1519(the)X 1637(Theorem)X 1947(2.8)X 2067(combine)X 2363(to)X 2445(show)X 2634(that)X 2 f 2774(M)X 7 s 2841 5259(n)N 10 s 9 f 2882 5241(\263)N 2 f 2926(q)X 9 f (\242)S 2 f 1 f 2999(\()X 2 f 3026(q)X 9 f 3079(+)X 1 f 3123(1)X 2 f 9 f (-)S 2 f 3207(q)X 9 f (\242)S 2 f 1 f 3280(\))X 3327(where)X 2 f 3544(q)X 1 f 3617(is)X 3690(the)X 3808(larg-)X 648 5424(est)N 767(prime)X 984(power)X 1214(less)X 1363(than)X 2 f 1530(n)X 1 f 1612(and)X 2 f 1757(q)X 9 f (\242)S 2 f 1 f 1859(is)X 1941(the)X 2068(prime)X 2284(power)X 2514(nearest)X 2771(to)X 2862(\()X 2 f 2889(q)X 9 f 2942(+)X 1 f 2986(1\))X 2 f 3053(/)X 1 f 3075(2.)X 3164(The)X 3318(existence)X 3646(of)X 3742(primes)X 648 5604(suf\256ciently)N 1028(close)X 1213(to)X 2 f 1295(n)X 1 f 1368(imply)X 10 p %%Page: 10 11 10 s 0 xH 0 xS 1 f 3880 666(10)N 3 f 648 954(Theorem)N 980(2.9)X 1100([KSS]:)X 2 f 1351(M)X 7 s 1418 972(n)N 10 s 9 f 1459 954(\263)N 2 f 1503(n)X 7 s 1 f 1552 921(2)N 2 f 10 s 954(/)Y 1 f 1602(4)X 2 f 9 f (+)S 2 f 1686(o)X 1 f 1739(\()X 2 f 1766(n)X 7 s 1 f 1815 921(2)N 10 s 954(\))Y 848 1170(In)N 937(1987,)X 1139(A.)X 1239(Yao)X 1395(used)X 1564(the)X 1684(KSS)X 1852(topological)X 2233(technique)X 2566(to)X 2649(prove)X 2853(that)X 2994(all)X 3095(nontrivial)X 3427(monotone)X 3768(bipar-)X 648 1350(tite)N 797(graph)X 1027(properties)X 1395(were)X 1599(evasive.)X 1907(An)X 2052(easy)X 2242(consequence)X 2700(of)X 2814(his)X 2953(result)X 3177(is)X 3276(that)X 3442(Kleitman's)X 3844(and)X 648 1530(Kwiatkowski's)N 1165(recursive)X 1492(formula)X 1778(and)X 1926(consequently,)X 2401(the)X 2531(KSS)X 2709(lower)X 2924(bound)X 3155(on)X 2 f 3266(M)X 7 s 3333 1548(n)N 10 s 1 f 3405 1530(could)N 3614(be)X 3721(slightly)X 648 1773(improved.)N 996(The)X 1141(modi\256ed)X 1445(recursive)X 1760(formula)X 2034(is)X 2 f 2107(M)X 7 s 2174 1791(n)N 10 s 9 f 2215 1773(\263)N 1 f 2259(min)X 2 f 2383({M)X 7 s 2482 1791(n)N 9 f 2519(-)X 1 f 2550(1)X 10 s 1773(,)Y 2 f 10 f 2611 1690(J)N 2611 1770(J)N 2611 1850(Q)N 1 f 2651 1830(2)N 2 f 2651 1725(n)N 10 f 2639 1749(h)N 2663(h)X 2 f 10 f 2724 1690(J)N 2724 1770(J)N 2724 1850(P)N 1 f 1773(,)Y 2 f 10 f 2777 1690(R)N 2777 1770(J)N 2777 1850(J)N 1 f 2817 1830(2)N 2 f 2817 1725(n)N 10 f 2805 1749(h)N 2829(h)X 2 f 10 f 2890 1690(H)N 2890 1770(J)N 2890 1850(J)N 2 f 1773(})Y 1 f 2962(and)X 3098(the)X 3216(new)X 3370(lower)X 3573(bound)X 3793(is)X 3866(for)X 2 f 648 2022(M)N 7 s 715 2040(n)N 10 s 1 f 776 2022(is)N 2 f 849(q)X 1 f 902(\()X 2 f 929(q)X 9 f 982(+)X 1 f 1026(2\))X 2 f 1093(/)X 1 f 1115(4)X 1175(for)X 2 f 1289(q)X 1 f 1362(the)X 1480(largest)X 1714(prime)X 1921(power)X 2142(less)X 2282(than)X 2 f 2440(n)X 1 f 2493(,)X 2533(which)X 2749(is)X 2822(still)X 2 f 2961(n)X 7 s 1 f 3010 1989(2)N 2 f 10 s 2022(/)Y 1 f 3060(4)X 2 f 9 f (+)S 2 f 3144(o)X 1 f 3197(\()X 2 f 3224(n)X 7 s 1 f 3273 1989(2)N 10 s 2022(\).)Y 3 f 648 2238(Theorem)N 980(2.10)X 1140(\(Yao\):)X 2 f 1379(Every)X 1587(monotone,)X 1943(nontrivial)X 2278(bipartite)X 2573(graph)X 2784(property)X 3080(is)X 3153(evasive.)X 3 f 648 2451(Proof:)N 1 f 889(Let)X 1018(P)X 1084(be)X 1182(a)X 1240(nontrivial)X 1572(monotone)X 1913(decreasing)X 2278(bipartite)X 2566(graph)X 2770(property)X 3063(on)X 3164(node)X 3341(sets)X 3482(V)X 3561(and)X 3698(W.)X 3835(The)X 648 2631(idea)N 803(is)X 877(to)X 960(demonstrate)X 1373(an)X 1470(action)X 1687(by)X 1788(a)X 1845(cyclic)X 2058(group)X 2266(on)X 2367(any)X 2504(monotone,)X 2865(nontrivial)X 3197(bipartite)X 3485(graph)X 3688(property)X 648 2811(P)N 718(whose)X 949(\256xed)X 1135(points)X 1356(do)X 1462(not)X 1590(have)X 1768(Euler)X 1967(characteristic)X 2421(1.)X 2526(Then)X 2716(Theorem)X 3031(2.7)X 3156(implies)X 3416(that)X 3561(P)X 3630(is)X 3708(not)X 3835(col-)X 648 2991(lapsible,)N 937(and)X 1073(therefore,)X 1404(evasive.)X 848 3204(Let)N 981(G)X 1065(be)X 1167(the)X 1291(cyclic)X 1509(group)X 1722(generated)X 2061(by)X 2167(the)X 2290(function)X 2582(which)X 2803(sends)X 3006(i)X 3053(to)X 3140(\(i+1\)mod)X 2 f 1 f 9 f 3456(|)X 2 f 3485(W)X 1 f 9 f 3578(|)X 2 f 1 f 3632(for)X 3751(all)X 3856(i)X 9 f 3903(\316)X 1 f 648 3384(W.)N 773(Then)X 967(the)X 1094(\256xed)X 1283(points)X 1507(of)X 1603(the)X 1730(complex)X 2035(P,)X 2 f 2128(P)X 7 s 2177 3402(G)N 10 s 1 f 2230 3384(,)N 2279(correspond)X 2665(to)X 2756(the)X 2883(collection)X 3227(of)X 3322(all)X 3430(sets)X 3578(V')X 2 f 9 f 3663(\264)X 1 f 3707(W)X 9 f 3811(\316)X 1 f 3896(P.)X 648 3567(That)N 816(is,)X 909(the)X 1027(vertices)X 1297(of)X 2 f 1384(P)X 7 s 1433 3585(G)N 10 s 1 f 1506 3567(correspond)N 1883(to)X 1965(the)X 2083(minimal)X 2369(invariant)X 2674(faces)X 2860({i})X 2 f 9 f 2958(\264)X 1 f 3002(W)X 3098(for)X 3212(all)X 3312(i)X 9 f 3354(\316)X 1 f 3431(V.)X 3529(Similarly,)X 3866(for)X 648 3750(any)N 784(j,)X 846(the)X 964(faces)X 1150(of)X 2 f 1237(P)X 7 s 1286 3768(G)N 10 s 1 f 1359 3750(of)N 1446(dimension)X 1799(j)X 1841(correspond)X 2218(to)X 2300(the)X 2418(sets)X 2558(V')X 2 f 9 f 2643(\264)X 1 f 2687(W)X 2783(for)X 2897(all)X 2997(V')X 9 f 3102(\315)X 1 f 3179(V)X 3257(of)X 3344(cardinality)X 3707(j+1.)X 848 3966(Suppose)N 1140(for)X 1255(some)X 1445(V')X 9 f 1551(\315)X 1 f 1629(V,)X 1728(V')X 2 f 9 f 1813(\264)X 1 f 1857(W)X 9 f 1954(\316)X 1 f 2032(P.)X 2136(The)X 2281(invariance)X 2636(of)X 2723(P)X 2787(under)X 2990(renumbering)X 3420(of)X 3507(V)X 3585(implies)X 3840(that)X 648 4146(for)N 770(every)X 977(U)X 9 f 1063(\315)X 1 f 1148(V)X 1234(with)X 9 f 1404(|)X 1 f (U)S 9 f 1478(|)X 1 f 1522(=)X 9 f 1595(|)X 1 f (V')S 9 f 1696(|)X 1 f (,)S 1760(U)X 2 f 9 f 1818(\264)X 1 f 1862(W)X 9 f 1966(\316)X 1 f 2051(P.)X 2163(Let)X 2298(r)X 2353(be)X 2457(the)X 2583(maximum)X 2935(size)X 3088(of)X 3183(any)X 3327(subset)X 3554(V')X 3666(such)X 3840(that)X 648 4326(V')N 2 f 9 f 733(\264)X 1 f 777(W)X 9 f 873(\316)X 1 f 950(P.)X 1054(Since)X 1252(P)X 1316(is)X 1389(nontrivial,)X 1740(r)X 1787(<)X 9 f 1852(|)X 1 f (V)S 9 f 1926(|)X 1 f (.)S 648 4539(Case)N 824(1:)X 926(r)X 973(=)X 1038(0.)X 1118(Then)X 1303(P)X 1367(has)X 1494(no)X 1594(\256xed)X 1774(points;)X 2011(the)X 2129(Euler)X 2323(character)X 2639(of)X 2 f 2726(P)X 7 s 2775 4557(G)N 10 s 1 f 2848 4539(=0.)N 648 4818(Case)N 826(2:)X 910(r)X 959(>)X 1026(0:)X 1110(Then)X 1297(the)X 1417(number)X 1684(of)X 1773(faces)X 1961(of)X 2050(dimension)X 2405(i,)X 2469(for)X 2585(i)X 2628(<)X 2694(r,)X 2762(in)X 2845(the)X 2964(\256xed)X 3145(point)X 3330(complex)X 3627(is)X 2 f 10 f 3714 4732(I)N 3714 4812(J)N 3714 4892(L)N 1 f 4860(\()Y 2 f 3761(i)X 9 f 3796(+)X 1 f 3840(1\))X 2 f 9 f 3773 4779(|)N 2 f (V)S 9 f 3851(|)X 2 f 10 f 3920 4732(M)N 3920 4812(J)N 3920 4892(O)N 1 f 4818(.)Y 648 5064(For)N 779(i)X 2 f 9 f 821(\263)X 1 f 885(r,)X 952(it)X 1016(is)X 1089(0.)X 848 5277(The)N 993(Euler)X 1187(characteristic)X 1636(of)X 2 f 1723(P)X 7 s 1772 5295(G)N 10 s 1 f 1845 5277(is)N 1918(then:)X 2 f 7 s 2059 5637(i)N 9 f 2084(=)X 1 f 2115(0)X 2 f 15 s 9 f 2065 5580(S)N 7 s 2 f 2055 5475(r)N 9 f 2086(-)X 1 f 2117(1)X 10 s 5556(\()Y 2 f 9 f 2172(-)X 1 f 2216(1\))X 2 f 7 s 2283 5523(i)N 10 s 10 f 2325 5470(I)N 2325 5550(J)N 2325 5630(L)N 1 f 5598(\()Y 2 f 2372(i)X 9 f 2407(+)X 1 f 2451(1\))X 2 f 9 f 2384 5517(|)N 2 f (V)S 9 f 2462(|)X 2 f 10 f 2531 5470(M)N 2531 5550(J)N 2531 5630(O)N 11 p %%Page: 11 12 10 s 0 xH 0 xS 10 f 1 f 3880 666(11)N 648 954(which)N 864(cannot)X 1098(equal)X 1292(1)X 1352([Y2].)X 3 f 648 1230(2.5.)N 808(Deterministic)X 1292(Complexity)X 1708(of)X 1795(Digraph)X 2099(Properties)X 1 f 848 1443(In)N 935(this)X 1070(section,)X 1337(we)X 1451(will)X 1595(improve)X 1882(the)X 2000(asymptotic)X 2371(bound)X 2591(for)X 2 f 2705(M)X 7 s 2772 1461(n)N 2781 1410(D)N 10 s 2012 1659(M)N 7 s 2079 1677(n)N 2088 1626(D)N 10 s 9 f 2128 1659(\263)N 2 f 2172(n)X 7 s 1 f 2221 1626(2)N 2 f 10 s 1659(/)Y 1 f 2271(2)X 2 f 2331(+)X 2405(o\(n)X 7 s 1 f 2521 1626(2)N 2 f 10 s 1659(\).)Y 1 f 648 1908(Thus,)N 857(for)X 980(every)X 1188(nontrivial)X 1528(monotone)X 1877(graph)X 2089(or)X 2185(digraph)X 2459(property)X 2759(almost)X 3000(half)X 3153(the)X 3279(edges)X 3490(must)X 3673(be)X 3777(asked)X 648 2088(about)N 846(in)X 928(the)X 1046(worst)X 1244(case.)X 848 2301(KSS)N 1014(observed)X 1324(that)X 1464(a)X 1520(lower)X 1723(bound)X 1943(for)X 2 f 2057(M)X 7 s 2124 2319(n)N 2133 2268(D)N 1 f 10 s 2193 2301(of)N 2 f 2280(n)X 7 s 1 f 2329 2268(2)N 2 f 10 s 2301(/)Y 1 f 2379(4)X 2 f 9 f (+)S 2 f 2463(o)X 1 f 2516(\()X 2 f 2543(n)X 7 s 1 f 2592 2268(2)N 10 s 2301(\))Y 2667(immediately)X 3087(follows)X 3347(from:)X 3 f 648 2517(Proposition)N 1063(2.11)X 1223([KSS]:)X 1 f 648 2730(\(i\))N 2 f 744(M)X 7 s 811 2748(n)N 10 s 9 f 852 2730(\243)N 2 f 896(M)X 7 s 963 2748(n)N 972 2697(D)N 1 f 10 s 1032 2730(and)N 648 2913(\(ii\))N 2 f 766(M)X 7 s 833 2931(n)N 842 2880(D)N 10 s 9 f 882 2913(\243)N 1 f 926(2)X 2 f (M)S 7 s 1033 2931(n)N 10 s 1 f 1074 2913(.)N 3 f 648 3129(Proof:)N 1 f 648 3342(\(i\))N 752(Let)X 887(P)X 959(be)X 1063(a)X 1127(nontrivial)X 1466(monotone)X 1814(digraph)X 2087(property)X 2387(with)X 2557(complexity)X 2 f 2945(M)X 7 s 3012 3360(n)N 3021 3309(D)N 1 f 10 s 3061 3342(.)N 3129(For)X 3268(any)X 3411(set)X 3527(of)X 3621(undirected)X 648 3525(edges)N 854(S,)X 941(let)X 1044(B\(S\)={)X 1301(\(i,j\))X 9 f 1442(|)X 1 f 1481({i,j})X 9 f 1644(\316)X 1 f 1724(S}.)X 1869(We)X 2004(may)X 2165(de\256ne)X 2384(a)X 2443(nontrivial)X 2777(graph)X 2982(property)X 3276(on)X 2 f 3378(n)X 1 f 3453(nodes)X 3662(P')X 3755(as)X 3844(fol-)X 648 3705(lows:)N 844(for)X 961(any)X 1100(set)X 1212(of)X 1302(undirected)X 1664(edges)X 1870(S,)X 1957(S)X 9 f 2024(\316)X 1 f 2104(P')X 2197(iff)X 2295(B\(S\))X 9 f 2446(\316)X 1 f 2525(P.)X 2631(Let)X 2760(A)X 2840(be)X 2938(an)X 3036(algorithm)X 3369(which)X 3587(computes)X 3916(P)X 648 3885(in)N 734(time)X 2 f 900(M)X 7 s 967 3903(n)N 976 3852(D)N 1 f 10 s 1016 3885(.)N 1060(If)X 1138(we)X 1256(replace)X 1513(every)X 1716(query)X 1923(of)X 2014(\(i,j\))X 2156(or)X 2247({j,i})X 2411(in)X 2497(A)X 2579(by)X 2683(a)X 2743(query)X 2950(of)X 3041({i,j},)X 3225(the)X 3346(resulting)X 3649(algorithm)X 648 4068(computes)N 975(P')X 1066(in)X 1148(time)X 2 f 9 f 1310(\243)X 2 f 1354(M)X 7 s 1421 4086(n)N 1430 4035(D)N 1 f 10 s 1470 4068(.)N 1530(Hence,)X 2 f 1776(M)X 7 s 1843 4086(n)N 10 s 9 f 1884 4068(\243)N 2 f 1928(M)X 7 s 1995 4086(n)N 2004 4035(D)N 1 f 10 s 2044 4068(.)N 648 4284(\(ii\))N 769(Let)X 899(P)X 966(be)X 1064(a)X 1122(monotone)X 1464(nontrivial)X 1797(graph)X 2002(property)X 2296(on)X 2 f 2398(n)X 1 f 2473(nodes)X 2682(with)X 2846(complexity)X 2 f 3228(M)X 7 s 3295 4302(n)N 3304 4251(D)N 1 f 10 s 3344 4284(.)N 3386(Then)X 3573(let)X 3675(P')X 3768(=)X 3835({T)X 9 f 3944(|)X 1 f 648 4467(B\(S\))N 9 f 823(\315)X 1 f 904(T)X 977(for)X 1095(some)X 1288(S)X 9 f 1356(\316)X 1 f 1437(P}.)X 1563(Let)X 1694(A)X 1776(be)X 1876(an)X 1976(algorithm)X 2311(which)X 2531(computes)X 2862(P)X 2930(in)X 3015(time)X 2 f 3180(M)X 7 s 3247 4485(n)N 10 s 1 f 3288 4467(.)N 3331(If)X 3408(we)X 3525(replace)X 3781(every)X 648 4650(query)N 852(of)X 940({i,j})X 1101(by)X 1202(two)X 1343(queries,)X 1616(of)X 1704(\(i,j\))X 1843(and)X 1980(\(j,i\),)X 2139(then)X 2298(A)X 2377(computes)X 2705(P)X 2769(in)X 2851(time)X 2 f 9 f 3013(\243)X 1 f 3057(2)X 2 f (M)S 7 s 3164 4668(n)N 10 s 1 f 3205 4650(.)N 3265(It)X 3334(follows)X 3594(that)X 2 f 3734(M)X 7 s 3801 4668(n)N 3810 4617(D)N 1 f 10 s 3870 4650(<=)N 648 4833(2)N 2 f (M)S 7 s 755 4851(n)N 10 s 1 f 796 4833(.)N 848 5049(Our)N 997(proof)X 1195(of)X 1286(the)X 1408(improved)X 1739(lower)X 1946(bound)X 2170(for)X 2 f 2288(M)X 7 s 2355 5067(n)N 2364 5016(D)N 1 f 10 s 2428 5049(follows)N 2692(the)X 2813(proof)X 3010(of)X 3100(the)X 3221(lower)X 3427(bound)X 3650(for)X 2 f 3767(M)X 7 s 3834 5067(n)N 10 s 1 f 3898 5049(in)N 648 5232(the)N 770(previous)X 1070(section.)X 1360(We)X 1495(use)X 1625(the)X 1746(KSS)X 1915(topological)X 2298(approach)X 2616(to)X 2701(prove)X 2907(evasiveness)X 3309(for)X 3426(a)X 3485(special)X 3731(case)X 3893(of)X 648 5412(nontrivial,)N 1015(monotone)X 1371(bipartite)X 1674(digraph)X 1955(properties,)X 2332(which)X 2564(is)X 2653(then)X 2827(used)X 3009(to)X 3106(prove)X 3324(an)X 3435(analogue)X 3760(of)X 3862(the)X 648 5592(Kleitman's)N 1024(and)X 1160(Kwiatkowski's)X 1665(recursive)X 1980(formula)X 2254(\(Theorem)X 2591(2.3\).)X 12 p %%Page: 12 13 10 s 0 xH 0 xS 1 f 3880 666(12)N 3 f 648 954(Lemma)N 931(2.12:)X 2 f 1118(M)X 7 s 1185 972(n)N 1194 921(D)N 10 s 9 f 1234 954(\263)N 2 f 1278(min)X 1 f 1411(\()X 2 f 1438(M)X 7 s 1505 972(n)N 9 f 1542(-)X 1 f 1573(1)X 2 f 1514 921(D)N 10 s 1 f 1614 954(,2)N 2 f (p)S 7 s 9 f 1723 921(a)N 1 f 10 s 1758 954(\()N 2 f 1785(n)X 9 f 1838(-)X 2 f 1882(p)X 7 s 9 f 1931 921(a)N 1 f 10 s 1966 954(\)\))N 2 f 2020(,)X 2060(where)X 2276(p)X 7 s 9 f 2325 921(a)N 10 s 2 f 2380 954(is)N 2453(the)X 2571(minimum)X 2889(prime)X 3096(power)X 3316(greater)X 3572(than)X 3734(n/2.)X 1 f 648 1170(Lemma)N 913(2.12)X 1073(is)X 1146(proved)X 1389(in)X 1471(section)X 1718(2.5.2.)X 848 1383(Combining)N 1227(Lemma)X 1492(2.12)X 1652(with)X 1814(Theorem)X 2124(2.8,)X 2264(we)X 2378(obtain)X 2598(the)X 2716(following:)X 3 f 648 1596(Theorem)N 980(2.13:)X 2 f 1167(Any)X 1312(nontrivial)X 1647(monotone)X 1983(digraph)X 2256(property)X 2552(on)X 2652(n)X 2712(nodes)X 2919(has)X 3050(complexity)X 9 f 3418(\263)X 2 f 3482(n)X 7 s 1 f 3531 1563(2)N 2 f 10 s 1596(/)Y 1 f 3581(2)X 2 f 9 f (-)S 2 f 3665(o)X 1 f 3718(\()X 2 f 3745(n)X 7 s 1 f 3794 1563(2)N 10 s 1596(\))Y 2 f 3849(.)X 3 f 648 1809(Proof:)N 1 f 889(Theorem)X 1201(2.8)X 1323(implies)X 1580(that)X 2 f 1722(M)X 7 s 1789 1827(n)N 1798 1776(D)N 10 s 9 f 1838 1809(=)N 2 f 1882(n)X 1 f 1935(\()X 2 f 1962(n)X 9 f 2015(-)X 1 f 2059(1\))X 2148(for)X 2 f 2264(n)X 1 f 2339(a)X 2397(prime)X 2605(power.)X 2847(Then,)X 3053(by)X 3154(Lemma)X 3420(2.12,)X 3601(we)X 3716(see)X 3840(that)X 2 f 648 1992(M)N 7 s 715 2010(n)N 724 1959(D)N 10 s 9 f 764 1992(\263)N 1 f 808(2)X 2 f (p)S 7 s 9 f 897 1959(a)N 1 f 10 s 932 1992(\()N 2 f 959(q)X 7 s 9 f 1008 1959(b)N 10 s 1039 1992(+)N 1 f 1083(1)X 2 f 9 f (-)S 2 f 1167(p)X 7 s 9 f 1216 1959(a)N 1 f 10 s 1251 1992(\))N 1299(where)X 2 f 1517(q)X 7 s 9 f 1566 1959(b)N 1 f 10 s 1618 1992(is)N 1692(the)X 1811(largest)X 2046(prime)X 2254(power)X 2476(less)X 2617(than)X 2776(n)X 2837(and)X 2 f 2974(p)X 7 s 9 f 3023 1959(a)N 1 f 10 s 3079 1992(is)N 3152(the)X 3270(smallest)X 3552(prime)X 3759(power)X 648 2175(greater)N 899(than)X 2 f 1064(n)X 1117(/)X 1 f 1139(2.)X 1246(The)X 1398(result)X 1603(now)X 1768(follows)X 2035(from)X 2218(an)X 2321(implication)X 2712(of)X 2806(the)X 2930(Prime)X 3147(Number)X 3436(Theorem)X 3752([HW],)X 648 2355(that)N 788(there)X 969(is)X 1042(a)X 1098(function)X 2 f 9 f 1385(d)X 1 f 1425(\()X 2 f 1452(x)X 1 f 1501(\))X 2 f 9 f 1528(=)X 2 f 1572(o)X 1 f 1625(\()X 2 f 1652(x)X 1 f 1701(\))X 1748(such)X 1915(that)X 2055(for)X 2169(all)X 2 f 2269(x)X 1 f 2338(there)X 2519(is)X 2592(a)X 2648(prime)X 2855(between)X 2 f 3143(x)X 1 f 3212(and)X 2 f 3348(x)X 9 f 3397(+d)X 1 f 3481(\()X 2 f 3508(x)X 1 f 3557(\).)X 3 f 648 2631(2.5.1.)N 868(Deterministic)X 1352(Complexity)X 1768(of)X 1855(Bipartite)X 2182(Digraph)X 2486(Properties)X 1 f 848 2844(A)N 2 f 938(bipartite)X 1245(graph)X 1468(property)X 1 f 1776(is)X 1860(a)X 1927(collection)X 2274(P)X 2349(of)X 2447(subsets)X 2709(of)X 2807(\(V)X 2 f 9 f 2892(\264)X 1 f 2936(W\))X 2 f 9 f 3039(\310)X 1 f 3101(\(W)X 2 f 9 f 3204(\264)X 1 f 3248(V\))X 3364(which)X 3591(is)X 3675(invariant)X 648 3024(under)N 851(renumberings)X 1312(of)X 1399(V)X 1477(and)X 1613(of)X 1700(W.)X 848 3237(Yao)N 1004(showed)X 1271(that)X 1413(every)X 1614(monotone,)X 1976(nontrivial)X 2309(bipartite)X 2598(graph)X 2803(property)X 3097(is)X 3172(evasive)X 3435(\(Theorem)X 3773(2.10\).)X 648 3417(The)N 798(analogous)X 1148(statement)X 1480(for)X 1599(bipartite)X 1891(digraph)X 2161(properties)X 2507(is)X 2585(false.)X 2782(For)X 2917(example,)X 3233(the)X 3355(property)X 3651(of)X 3742(having)X 648 3597(no)N 754(edges)X 963(from)X 1145(V)X 1229(to)X 1317(W)X 1419(can)X 1557(be)X 1659(computed)X 2001(by)X 2107(an)X 2209(algorithm)X 2546(which)X 2768(asks)X 2932(only)X 3100(about)X 3303(the)X 3426(edges)X 3634(from)X 3815(V)X 3898(to)X 648 3777(W.)N 774(It)X 853(need)X 1035(never)X 1244(consider)X 1546(the)X 1674(edges)X 1887(from)X 2073(W)X 2179(to)X 2271(V.)X 2399(We)X 2541(can,)X 2703(however,)X 3030(prove)X 3243(evasiveness)X 3651(for)X 3774(a)X 3839(res-)X 648 3957(tricted)N 873(class)X 1049(of)X 1136(bipartite)X 1423(digraph)X 1688(properties.)X 3 f 648 4170(Theorem)N 990(2.14:)X 2 f 1187(A)X 1266(monotone)X 1612(nontrivial)X 1956(bipartite)X 2260(digraph)X 2542(property)X 2847(on)X 2956(V,)X 3054(W)X 3150(with)X 9 f 3316(|)X 2 f (W)S 9 f 3399(|)X 2 f (=p)S 7 s 9 f 3518 4137(a)N 10 s 2 f 3553 4170(,)N 3602(p)X 3671(prime,)X 3907(is)X 648 4350(evasive)N 905(if)X 969(either:)X 1860 4563(\(i\))N 1956(V)X 9 f 2005(\264)X 2 f 2049(W)X 9 f 2136(\316)X 2 f 2213(P)X 2282(and)X 2422(W)X 9 f 2489(\264)X 2 f 2533(V)X 9 f 2602(\316)X 2 f 2679(P,)X 2268 4653(or)N 1849 4743(\(ii\))N 1967(V)X 9 f 2016(\264)X 2 f 2060(W)X 9 f 2147(\316)X 2 f 2165(/)X 2224(P)X 2293(and)X 2433(W)X 9 f 2500(\264)X 2 f 2544(V)X 9 f 2613(\316)X 2 f 2631(/)X 2690(P.)X 3 f 648 4989(Proof:)N 1 f 888(Let)X 1015(P)X 1079(be)X 1175(any)X 1311(nontrivial)X 1642(monotone)X 1982(decreasing)X 2346(bipartite)X 2633(digraph)X 2898(property)X 3190(on)X 3290(V)X 3368(and)X 3504(W,)X 3620(where)X 3837(V)X 3915(=)X 648 5169({)N 2 f 686(v)X 7 s 1 f 731 5187(1)N 10 s 5169(,)Y 2 f (v)S 7 s 1 f 824 5187(2)N 10 s 5169(,)Y 2 f 892 5145(.)N 932(.)X 972(.)X 1 f 1012 5169(,)N 2 f (v)S 7 s 1 f 9 f 1086 5187(|)N 2 f 1106(V)X 1 f 9 f 1158(|)X 2 f 1 f 10 s 1178 5169(\))N 1225(and)X 1361(W)X 1457(=)X 1522({)X 2 f 1560(w)X 7 s 1 f 1622 5187(1)N 10 s 5169(,)Y 2 f (w)S 7 s 1 f 1732 5187(2)N 10 s 5169(,)Y 2 f 1800 5145(.)N 1840(.)X 1880(.)X 1 f 1920 5169(,)N 2 f (w)S 7 s 1993 5187(p)N 4 s 9 f 2026 5157(a)N 1 f 10 s 2046 5169(}.)N 848 5385(Let)N 975(G)X 1053(be)X 1149(the)X 1267(group)X 1474(generated)X 1807(by)X 1907(two)X 2047(permutations)X 2 f 9 f 2485(t)X 1 f 2540(and)X 2 f 9 f 2676(s)X 1 f 2744(of)X 2831(V)X 2 f 9 f 2889(\310)X 1 f 2951(W,where,)X 3284(for)X 3398(all)X 2 f 3498(i)X 1 f 3533(:)X 2 f 9 f 848 5598(t)N 1 f 883(\()X 2 f 910(v)X 7 s 946 5616(i)N 10 s 1 f 975 5598(\))N 2 f 9 f 1002(=)X 2 f 1046(v)X 7 s 1082 5616(i)N 10 s 1 f 1111 5598(,)N 2 f 9 f 848 5781(t)N 1 f 883(\()X 2 f 910(w)X 7 s 963 5799(i)N 10 s 1 f 992 5781(\))N 2 f 9 f 1019(=)X 2 f 1063(w)X 7 s 1116 5799(i)N 9 f 1141(+)X 1 f 1172(1)X 2 f (modp)S 4 s 9 f 1329 5769(a)N 1 f 10 s 1349 5781(;)N 13 p %%Page: 13 14 10 s 0 xH 0 xS 1 f 3880 666(13)N 2 f 9 f 848 954(s)N 1 f 896(\()X 2 f 923(v)X 7 s 959 972(i)N 10 s 1 f 988 954(\))N 2 f 9 f 1015(=)X 2 f 1059(v)X 7 s 1095 972(i)N 9 f 1120(+)X 1 f 1151(1)X 2 f (mod)S 1 f 9 f 1293(|)X 2 f 1313(V)X 1 f 9 f 1365(|)X 2 f 1 f 10 s 1385 954(,)N 2 f 9 f 848 1137(s)N 1 f 896(\()X 2 f 923(w)X 7 s 976 1155(i)N 10 s 1 f 1005 1137(\))N 2 f 9 f 1032(=)X 2 f 1076(w)X 7 s 1129 1155(i)N 10 s 1 f 1158 1137(.)N 648 1353(The)N 797(action)X 1017(of)X 1108(G)X 1190(on)X 1294(V)X 1375(and)X 1514(W)X 1613(induces)X 1881(an)X 1980(action)X 2199(on)X 2302(the)X 2423(edges)X 2629(between)X 2920(V)X 3001(and)X 3140(W,)X 3259(which)X 3478(in)X 3563(turn)X 3715(induces)X 648 1533(an)N 747(action)X 966(on)X 1068(P,)X 1154(since)X 1341(P)X 1407(is)X 1482(invariant)X 1789(under)X 1994(permutations)X 2434(of)X 2523(V)X 2603(and)X 2741(of)X 2830(W.)X 2968(Since)X 2 f 9 f 3168(t)X 1 f 3225(and)X 2 f 9 f 3363(s)X 1 f 3433(commute,)X 3773(G)X 3853(has)X 648 1713(a)N 704(normal)X 951(p-subgroup)X 1336(\()X 2 f 9 f 1363(t)X 1 f 1398(\))X 1445(such)X 1612(that)X 1752(G/<)X 2 f 9 f 1877(t)X 1 f 1912(>)X 1977(=)X 2042(<)X 2 f 9 f 2087(s)X 1 f 2135(>)X 2200(is)X 2273(cyclic.)X 848 1926(Any)N 1013(G-invariant)X 1410(face)X 1572(of)X 1666(the)X 1791(complex)X 2094(P)X 2165(which)X 2388(contains)X 2682(one)X 2824(edge)X 3002(from)X 3184(V)X 3268(to)X 3356(W)X 3458(\(resp.,)X 3685(W)X 3787(to)X 3875(V\))X 648 2106(must)N 837(contain)X 1107(all)X 1221(of)X 1321(V)X 2 f 9 f 1379(\264)X 1 f 1423(W)X 1532(\(resp.,)X 1766(W)X 2 f 9 f 1842(\264)X 1 f 1886(V\).)X 2024(Then)X 2222(the)X 2353(possible)X 2648(G-invariant)X 3051(faces)X 3250(are)X 3382(V)X 2 f 9 f 3440(\264)X 1 f 3484(W,)X 3613(W)X 2 f 9 f 3689(\264)X 1 f 3733(V,)X 3844(and)X 648 2286(\(V)N 2 f 9 f 733(\264)X 1 f 777(W\))X 9 f 903(\310)X 1 f 988(\(W)X 2 f 9 f 1091(\264)X 1 f 1135(V\).)X 1283(The)X 1431(last)X 1565(is)X 1641(not)X 1766(in)X 1851(P)X 1918(since)X 2106(P)X 2173(is)X 2249(nontrivial.)X 2603(Then,)X 2811(since)X 2999(either)X 3205(the)X 3325(\256rst)X 3471(two)X 3613(are)X 3734(both)X 3898(in)X 648 2466(P)N 712(or)X 799(both)X 961(not)X 1083(in)X 1165(P,)X 1249(the)X 1367(Euler)X 1561(characteristic)X 2010(of)X 2 f 2097(P)X 7 s 2146 2484(G)N 10 s 1 f 2199 2466(=)N 2264(0)X 2324(or)X 2411(2.)X 2491(Hence,)X 2737(P)X 2801(must)X 2976(be)X 3072(evasive.)X 3 f 648 2682(Remark:)N 1 f 982(The)X 1133(theorem)X 1422(can)X 1560(be)X 1662(extended)X 1978(to)X 2066(the)X 2190(cases)X 2386(where)X 9 f 2609(|)X 1 f (W)S 9 f 2701(|)X 1 f 2743(=)X 2 f 2813(p)X 7 s 9 f 2862 2649(a)N 10 s 2 f 2897 2682(q)N 7 s 9 f 2946 2649(b)N 1 f 10 s 3002 2682(and)N 9 f 3143(|)X 1 f (W)S 9 f 3235(|)X 1 f 3276(=)X 3346(2)X 2 f (p)S 7 s 9 f 3435 2649(a)N 10 s 2 f 3470 2682(q)N 7 s 9 f 3519 2649(b)N 1 f 10 s 3550 2682(,)N 3595(for)X 3714(p)X 3779(and)X 3920(q)X 648 2862(primes.)N 906(We)X 1038(sketch)X 1263(the)X 1381(proof)X 1575(for)X 9 f 1689(|)X 1 f (W)S 9 f 1781(|)X 2 f 9 f (=)S 2 f 1841(p)X 7 s 9 f 1890 2829(a)N 10 s 2 f 1925 2862(q)N 7 s 9 f 1974 2829(b)N 1 f 10 s 2005 2862(.)N 868 3075(We)N 1000(use)X 1127(a)X 1183(more)X 1368(general)X 1625(lemma)X 1863(of)X 1950(Oliver's)X 2233([O]:)X 2 f 648 3288(If)N 724(G)X 809(acts)X 965(on)X 1072(a)X 1139(collapsible)X 1517(complex)X 9 f 1812(D)X 2 f 1888(and)X 2035(G)X 2120(has)X 2258(a)X 2325(normal)X 2583(subgroup)X 2912(G')X 3024(with)X 3188(G/G')X 3380(of)X 3469(q-power)X 3762(order,)X 648 3468(and)N 791(G')X 899(has)X 1032(a)X 1094(normal)X 1347(p-subgroup)X 1738(H)X 1818(with)X 1977(G'/H)X 2164(cyclic,)X 2394(for)X 2509(p)X 2571(and)X 2713(q)X 2775(primes,)X 3035(then)X 3195(the)X 3315(Euler)X 3515(characteristic)X 648 3648(of)N 9 f 730(D)X 7 s 2 f 779 3666(G)N 10 s 9 f 832 3648 MXY (==)186 549 oc 1 f 876(1)X 2 f (modq)S 1107(.)X 1 f 848 3864(We)N 983(denote)X 1220(the)X 1341(elements)X 1649(of)X 1739(W)X 1838(by)X 2 f 1941(w)X 7 s 1994 3882(i)N 1 f 2019(,)X 2 f 2038(j)X 10 s 1 f 2067 3864(,)N 2110(where)X 2330(0)X 2 f 9 f (\243)S 2 f 2414(i)X 2449(
)X
2348(ax)X
2445(+)X
2511(b:)X
2594(a,b)X
9 f
2710(\316)X
1 f
2787(GF\()X
2 f
2916(p)X
7 s
9 f
2965 1953(a)N
1 f
10 s
3000 1986(\),)N
3067(a)X
2 f
9 f
3123(\271)X
1 f
3187(0\))X
3274(})X
3332(acts)X
3477(on)X
3577(the)X
3695(edges)X
3898(in)X
648 2166(B)N
732(and)X
879(the)X
1008(edges)X
1222(in)X
1315(\(B)X
2 f
9 f
(\264)S
1 f
1439(A\))X
1554(by)X
1664(permuting)X
2023(the)X
2151(nodes)X
2368(in)X
2460(B.)X
2563(Since)X
2771(P)X
2865(is)X
2948(invariant)X
3263(under)X
3476(permutation)X
3893(of)X
648 2346(nodes,)N
878(and)X
1017(the)X
1138(nodes)X
1348(in)X
1433(B)X
1508(are)X
1629(isomorphic)X
2011(to)X
2095(each)X
2265(other)X
2452(in)X
2536(the)X
2656(graph)X
2861(given)X
3061(by)X
3163(the)X
3283("known")X
3589(edges,)X
3814(P')X
3907(is)X
648 2526(invariant)N
953(under)X
1156(this)X
1291(action.)X
848 2739(G)N
933(has)X
1067(a)X
1130(normal)X
1384(p-group)X
1664(H)X
1748(=)X
1819({x)X
1923(->)X
2021(x+b:)X
2194(b)X
9 f
2260(\316)X
1 f
2343(GF\()X
2 f
2472(p)X
7 s
9 f
2521 2706(a)N
1 f
10 s
2556 2739(\)})N
2647(=)X
2718(GF\()X
2 f
2847(p)X
7 s
9 f
2896 2706(a)N
1 f
10 s
2931 2739(\))N
2984(and)X
3126(G/H)X
3290(=)X
2 f
3361(GF)X
1 f
3481(\()X
2 f
3508(p)X
7 s
9 f
3557 2706(a)N
1 f
10 s
3592 2739(\))N
2 f
7 s
3619 2703(*)N
10 s
1 f
3660 2739(,)N
3706(a)X
3768(cyclic)X
648 2919(multiplicative)N
1112(group.)X
848 3132(Since)N
1052(G)X
1136(maps)X
1331(any)X
1473(two)X
1619(nodes)X
1832(in)X
1920(B)X
1999(to)X
2087(any)X
2229(two)X
2375(other)X
2566(nodes,)X
2798(G)X
2881(maps)X
3075(any)X
3216(edge)X
3393(in)X
2 f
3480(B)X
3503 3112(\303)N
1 f
3567 3132(to)N
3654(any)X
3795(other)X
648 3312(edge)N
823(in)X
2 f
908(B)X
931 3292(\303)N
1 f
970 3312(.)N
1013(Therefore,)X
1374(a)X
1433(G-invariant)X
1826(set)X
1938(must)X
2116(contain)X
2375(either)X
2581(all)X
2684(edges)X
2890(in)X
2 f
2975(B)X
2998 3292(\303)N
1 f
3059 3312(or)N
3148(no)X
3250(edges)X
3455(in)X
2 f
3539(B)X
3562 3292(\303)N
1 f
3601 3312(.)N
3643(Similarly,)X
648 3492(G)N
731(maps)X
925(any)X
1066(edge)X
1243(\()X
2 f
1270(b)X
7 s
3510(i)Y
10 s
1 f
1339 3492(,)N
2 f
1379(a)X
7 s
1424 3510(j)N
10 s
1 f
1453 3492(\))N
1505(to)X
1592(any)X
1733(other)X
1923(edge)X
2100(from)X
2281(a)X
2342(node)X
2523(in)X
2610(B)X
2688(to)X
2 f
2775(a)X
7 s
2820 3510(j)N
10 s
1 f
2849 3492(.)N
2913(Thus,)X
3117(any)X
3257(G-invariant)X
3651(set)X
3764(which)X
648 3675(contains)N
935(\()X
2 f
962(b)X
7 s
3693(i)Y
10 s
1 f
1031 3675(,)N
2 f
1071(a)X
7 s
1116 3693(j)N
10 s
1 f
1145 3675(\))N
1192(must)X
1367(contain)X
2 f
1623(B)X
9 f
1685(\264)X
2 f
1729({a)X
7 s
1806 3693(j)N
10 s
1835 3675(})N
1 f
(.)S
848 3891(By)N
963(assumption,)X
2 f
1369(B)X
1392 3871(\303)N
1 f
9 f
1453 3891(\316)N
1 f
1471(/)X
1532(P')X
1625(and)X
1763(a)X
1821(bidirected)X
2164(star)X
9 f
2302(\316)X
1 f
2320(/)X
2381(P,)X
2467(which)X
2685(implies)X
2941(that)X
2 f
3082(B)X
9 f
3144(\264)X
2 f
3188({a)X
7 s
3265 3909(j)N
10 s
3294 3891(})N
1 f
9 f
3347(\316)X
1 f
3365(/)X
3425(P'.)X
3537(We)X
3670(conclude)X
648 4074(that)N
801(P')X
905(has)X
1045(no)X
1157(G-invariant)X
1559(faces.)X
1777(Then)X
1974(the)X
2104(Euler)X
2310(characteristic)X
2771(of)X
2 f
2870(P)X
7 s
2919 4092(G)N
10 s
1 f
3004 4074(=)N
3081(0)X
2 f
9 f
(\271)S
1 f
3165(1.)X
3277(By)X
3402(lemma)X
3652(2.4,)X
3804(P')X
3907(is)X
648 4257(evasive.)N
848 4470(Hence)N
1074(the)X
1192(complexity)X
1572(of)X
1659(P)X
2 f
9 f
1723(\263)X
1 f
1787(the)X
1905(complexity)X
2285(of)X
2372(P'=)X
2 f
2508(p)X
7 s
9 f
2557 4437(a)N
1 f
10 s
2592 4470(\()N
2 f
2619(n)X
9 f
2672(-)X
2 f
2716(p)X
7 s
9 f
2765 4437(a)N
1 f
10 s
2800 4470(\))N
2 f
9 f
2827(+)X
2 f
2871(p)X
7 s
9 f
2920 4437(a)N
1 f
10 s
2955 4470(\()N
2 f
2982(p)X
7 s
9 f
3031 4437(a)N
10 s
3066 4470(-)N
1 f
3110(1\))X
2 f
9 f
3177(\263)X
1 f
3221(2)X
2 f
(p)S
7 s
9 f
3310 4437(a)N
1 f
10 s
3345 4470(\()N
2 f
3372(n)X
9 f
3425(-)X
2 f
3469(p)X
7 s
9 f
3518 4437(a)N
1 f
10 s
3553 4470(\).)N
2 f
648 4683(Case)N
828(\(ivc\):)X
1023(A)X
1046 4663(\303)N
9 f
1085 4683(\310)N
1 f
1147(\()X
2 f
1174(B)X
9 f
1236(\264)X
2 f
1280(A)X
1 f
1342(\))X
2 f
9 f
1389(\316)X
2 f
1466(P.)X
1 f
848 4896(Similar)N
1103(to)X
1185(Case)X
1361(ivb.)X
848 5109(We)N
980(conclude)X
1290(that)X
2 f
1430(M)X
7 s
1497 5127(n)N
1506 5076(D)N
10 s
9 f
1546 5109(\263)N
1 f
1590(min\()X
2 f
1741(M)X
7 s
1808 5127(n)N
9 f
1845(-)X
1 f
1876(1)X
2 f
1817 5076(D)N
10 s
1 f
1917 5109(,)N
2 f
1 f
1957(2)X
2 f
(p)S
7 s
9 f
2046 5076(a)N
1 f
10 s
2081 5109(\()N
2 f
2108(n)X
9 f
2161(-)X
2 f
2205(p)X
7 s
9 f
2254 5076(a)N
1 f
10 s
2289 5109(\)\).)N
17 p
%%Page: 17 18
10 s 0 xH 0 xS 1 f
3 f
12 s
2021 972(CHAPTER)N
2538(3)X
1796 1296(Randomized)N
2337(Complexity)X
10 s
648 1806(3.1.)N
808(Introduction)X
1 f
848 2019(The)N
1001(randomized)X
1408(complexity)X
1796(of)X
1891(graph)X
2102(properties)X
2451(was)X
2604(\256rst)X
2756(investigated)X
3170(by)X
3277(A.)X
3382(Yao.)X
3583(In)X
3677(1977,)X
3884(he)X
648 2199(observed)N
964(a)X
1026(lower)X
1235(bound)X
1461(of)X
2 f
9 f
1554(W)X
1 f
1616(\()X
2 f
1643(n)X
1 f
1696(\))X
1749(on)X
1855(the)X
1979(randomized)X
2384(complexity)X
2769(of)X
2861(any)X
3002(\(monotone)X
3374(or)X
3466(non-monotone\))X
648 2379(graph)N
851(property)X
1143(on)X
2 f
1243(n)X
1 f
1316(nodes.)X
1563(He)X
1677(posed)X
1884(the)X
2002(following)X
2333(question,)X
2644(which)X
2860(remains)X
3134(open:)X
3 f
648 2592(Open)N
860(Problem)X
1180([Y1]:)X
2 f
1385(Is)X
1469(there)X
1660(a)X
1726(constant)X
9 f
2023(e)X
2 f
2084(such)X
2257(that)X
2407(for)X
2526(all)X
2636(nontrivial)X
2977(monotone)X
3319(graph)X
3536(properties)X
3891(P,)X
648 2772(R\(P\))N
9 f
800(\263e)X
2 f
879(n)X
7 s
1 f
928 2739(2)N
2 f
10 s
2772(?)Y
1 f
848 2985(No)N
973(progress)X
1272(was)X
1424(made)X
1625(on)X
1732(this)X
1874(problem)X
2168(until)X
2341(1987,)X
2548(when)X
2749(Yao)X
2910(improved)X
3244(the)X
3369(lower)X
3578(bound)X
3804(from)X
2 f
9 f
648 3165(W)N
1 f
710(\()X
2 f
737(n)X
1 f
790(\))X
837(to)X
2 f
9 f
919(W)X
1 f
981(\()X
2 f
1008(n)X
1 f
1061(\(log)X
2 f
1190(n)X
1 f
1243(\))X
7 s
1270 3132(1)N
2 f
(/)S
1 f
1314(12)X
10 s
3165(\))Y
1417([Y2].)X
1609(In)X
1696(this)X
1831(chapter,)X
2108(we)X
2222(improve)X
2509(this)X
2644(to)X
2 f
9 f
2726(W)X
1 f
2788(\()X
2 f
2815(n)X
7 s
1 f
2864 3132(5)N
2 f
(/)S
1 f
2908(4)X
10 s
3165(\).)Y
848 3378(The)N
994(gap)X
1131(between)X
1419(the)X
1537(lower)X
1740(bound)X
1960(and)X
2096(upper)X
2299(bound)X
2519(for)X
2633(this)X
2768(problem)X
3055(remains)X
3329(remarkably)X
3715(wide.)X
3911(It)X
648 3558(is)N
732(not)X
865(known)X
1114(whether)X
1404(the)X
1533(randomized)X
1943(complexity)X
2334(of)X
2432(a)X
2499(graph)X
2712(property)X
3014(is)X
3097(ever)X
3266(less)X
3416(than)X
3584(one)X
3730(half)X
3885(its)X
648 3738(deterministic)N
1086(complexity.)X
848 3951(A)N
934(savings)X
1202(of)X
1297(almost)X
1538(a)X
1602(half)X
1755(can)X
1895(be)X
1999(shown)X
2236(for)X
2358(the)X
2484(monotone)X
2831(digraph)X
3103(property)X
3402(of)X
3496(having)X
3741(a)X
3804(node)X
648 4131(with)N
811(out-degree)X
2 f
1176(n)X
9 f
1229(-)X
1 f
1273(1.)X
1354(A)X
1433(simple)X
1667(adversary)X
2001(argument)X
2325(proves)X
2560(that)X
2701(this)X
2837(property)X
3130(is)X
3203(evasive.)X
3504(The)X
3649(following)X
648 4311(randomized)N
1047(algorithm)X
1378(which)X
1594(uses)X
1752(only)X
1914(one)X
2050(random)X
2315(bit)X
2419(has)X
2546(complexity)X
2 f
2926(n)X
7 s
1 f
2975 4278(2)N
2 f
10 s
4311(/)Y
1 f
3025(2.)X
2 f
728 4491(If)N
797(the)X
915(random)X
1184(bit)X
1288(is)X
1361(1,)X
1441(then)X
788 4671(let)N
888(i=1,)X
1044(j=1)X
788 4851(while)N
981(i)X
9 f
1003(\243)X
2 f
1047(n)X
1120(or)X
1211(until)X
1377(a)X
1437(node)X
1613(with)X
1770(out-degree)X
2138(n-1)X
2265(is)X
2338(found,)X
2560(do)X
1016 5031(while)N
1209(j)X
9 f
1231(\243)X
2 f
1275(n)X
1328(,)X
1368(or)X
1459(until)X
1625(a)X
1685(missing)X
1949(edge)X
2121(is)X
2194(found)X
2396(do)X
1136 5211(if)N
1200(i)X
9 f
1222(\271)X
2 f
1266(j)X
1308(then)X
1466(query)X
1669(\(i,j\))X
1136 5391(j=j+1;)N
888 5571(i=)N
984(i+1.)X
1 f
3880 6048(17)N
18 p
%%Page: 18 19
10 s 0 xH 0 xS 1 f
3880 666(18)N
2 f
728 954(else)N
788 1134(let)N
888(i=n,)X
1044(j=n)X
788 1314(while)N
981(i)X
9 f
1003(\263)X
1 f
1047(1)X
2 f
1107(or)X
1198(until)X
1364(a)X
1424(node)X
1600(with)X
1757(out-degree)X
2125(n-1)X
2252(is)X
2325(found,)X
2547(do)X
1016 1494(while)N
1209(j)X
9 f
1231(\263)X
1 f
1275(1)X
2 f
(,)S
1355(or)X
1446(until)X
1612(a)X
1672(missing)X
1936(edge)X
2108(is)X
2181(found)X
2383(do)X
1136 1674(if)N
1200(i)X
9 f
1222(\271)X
2 f
1266(j)X
1308(then)X
1466(query)X
1669(\(i,j\))X
1136 1854(j=j-1;)N
888 2034(i=)N
984(i-1;)X
1 f
648 2247(If)N
725(the)X
846(input)X
1033(graph)X
1239(has)X
1369(a)X
1428(node)X
2 f
1607(k)X
1 f
1679(with)X
1844(out-degree)X
2 f
2211(n)X
9 f
2264(-)X
1 f
2308(1,)X
2391(then)X
2552(it)X
2619(will)X
2766(be)X
2865(found)X
3075(after)X
3246(an)X
3345(average)X
3618(of)X
3707(\()X
2 f
3734(n)X
9 f
3787(+)X
1 f
3831(1\))X
2 f
3898(/)X
1 f
3920(2)X
648 2427(iterations)N
968(of)X
1057(the)X
2 f
1177(i)X
1 f
1234(loops.)X
1469(If)X
1545(the)X
1665(input)X
1851(graph)X
2056(has)X
2185(no)X
2287(node)X
2465(with)X
2629(out-degree)X
2 f
2995(n)X
9 f
3048(-)X
1 f
3092(1,)X
3174(then)X
3334(a)X
3392(missing)X
3662(edge)X
3836(will)X
648 2607(be)N
744(found)X
951(after)X
1119(an)X
1215(average)X
1486(of)X
2 f
1573(n)X
1626(/)X
1 f
1648(2)X
1708(queries)X
1960(for)X
2 f
2074(n)X
1 f
2147(iterations)X
2465(of)X
2552(the)X
2 f
2670(i)X
1 f
2725(loop.)X
848 2820(For)N
983(other)X
1172(evasive)X
1436(monotone)X
1779(set)X
1891(properties,,)X
2275(Saks)X
2449(and)X
2588(Wigderson)X
2963([SW])X
3160(and)X
3299(Snir)X
3455([S])X
3576(have)X
3751(shown)X
648 3000(that)N
788(randomization)X
1271(can)X
1403(achieve)X
1669(savings)X
1929(of)X
2016(more)X
2201(than)X
2359(a)X
2415(constant)X
2702(factor.)X
2950(In)X
3037(particular,)X
3385(Saks)X
3556(and)X
3692(Wigder-)X
648 3180(son)N
783(showed)X
1052(that)X
1196(the)X
1318(family)X
1550(of)X
1640(AND/OR)X
1970(tree)X
2114(functions)X
2435(with)X
2600(input)X
2787(size)X
2 f
2935(m)X
1 f
3029(has)X
3159(deterministic)X
3600(complexity)X
2 f
648 3360(m)N
1 f
745(and)X
887(randomized)X
1292(complexity)X
2 f
9 f
1677(Q)X
1 f
1736(\()X
2 f
1763(m)X
7 s
1830 3327(.)N
1 f
(753...)S
10 s
3360(\).)Y
2042(\(An)X
2192(AND/OR)X
2524(tree)X
2670(function)X
2962(is)X
3040(described)X
3373(by)X
3478(the)X
3601(values)X
3831(out-)X
648 3540(puted)N
847(by)X
948(the)X
1067(root)X
1217(of)X
1305(a)X
1362(complete)X
1677(binary)X
1903(tree)X
2044(in)X
2126(which)X
2342(each)X
2510(input)X
2694(bit)X
2798(is)X
2871(contained)X
3203(in)X
3285(a)X
3341(leaf)X
3482(and)X
3618(each)X
3786(inter-)X
648 3720(nal)N
774(node)X
958(computes)X
1293(either)X
1504(an)X
1608(AND)X
1810(or)X
1905(an)X
2009(OR)X
2147(of)X
2241(its)X
2343(subtrees,)X
2653(depending)X
3014(on)X
3121(whether)X
3407(it)X
3478(is)X
3558(at)X
3643(an)X
3746(odd)X
3893(or)X
648 3900(even)N
820(depth)X
1018(in)X
1100(the)X
1218(tree.\))X
848 4113(The)N
997(AND/OR)X
1328(tree)X
1473(function)X
1764(is)X
1841(invariant)X
2150(under)X
2357(a)X
2417(cyclic)X
2633(group)X
2844(which)X
3064(acts)X
3212(transitively)X
3595(on)X
3698(its)X
3796(input)X
648 4293(bits.)N
809(Thus)X
995(when)X
1195(viewed)X
1453(as)X
1546(a)X
1608(set)X
1723(property,)X
2040(it)X
2109(satis\256es)X
2387(the)X
2510(criteria)X
2763(for)X
2882(evasiveness)X
3286(in)X
3373(Theorem)X
3688(2.7.)X
3833(It)X
3907(is)X
648 4473(still)N
801(not)X
937(known)X
1189(if)X
1272(every)X
1485(set)X
1608(property)X
1914(which)X
2144(meets)X
2365(this)X
2514(criteria)X
2776(has)X
2917(randomized)X
3329(complexity)X
3722(at)X
3813(least)X
2 f
648 4653(m)N
7 s
715 4620(.)N
1 f
(753...)S
10 s
4653(,)Y
899(where)X
2 f
1120(m)X
1 f
1215(is)X
1292(the)X
1414(size)X
1562(of)X
1652(its)X
1750(element)X
2027(set,)X
2159(or)X
2249(even,)X
2444(if)X
2516(every)X
2718(evasive)X
2982(set)X
3094(property)X
3389(has)X
3519(this)X
3657(complex-)X
648 4833(ity.)N
797(A)X
880(bound)X
1105(of)X
2 f
1197(m)X
7 s
1264 4800(.)N
1 f
(5)S
10 s
1331 4833(is)N
1409(known,)X
1672(and)X
1813(follows)X
2078(from)X
2259(lower)X
2466(bounds)X
2721(on)X
2825(the)X
2947(nondeterministic)X
3509(complexity)X
3893(of)X
648 5013(set)N
757(properties.)X
19 p
%%Page: 19 20
10 s 0 xH 0 xS 1 f
3880 666(19)N
3 f
648 954(3.2.)N
808(Nondeterministic)X
1420(Complexity)X
1836(of)X
1923(Set)X
2050(Properties)X
1 f
848 1167(Let)N
978(S)X
1045(be)X
1144(a)X
1203(set)X
1315(property)X
1609(with)X
1773(element)X
2049(set)X
2160(X.)X
2280(Let)X
2409(Y)X
2489(be)X
2587(a)X
2645(set)X
2756(of)X
2845(\(queried)X
3135(element,)X
3431(answer\))X
3708(pairs.)X
3906(If)X
648 1347(every)N
851(input)X
1039(set)X
1152(which)X
1372(is)X
1449(consistent)X
1793(with)X
1959(Y)X
2041(is)X
2118(in)X
2204(S,)X
2292(then)X
2454(Y)X
2535(may)X
2696(considered)X
3067(a)X
3126("proof")X
3389(of)X
3479(membership)X
3898(in)X
648 1527(S.)N
754(Similarly,)X
1093(if)X
1164(every)X
1365(input)X
1551(set)X
1662(consistent)X
2003(with)X
2166(Y)X
2245(is)X
2319(not)X
2442(in)X
2525(S,)X
2610(then)X
2769(Y)X
2848(may)X
3007(be)X
3104(considered)X
3473(a)X
3530(proof)X
3725(of)X
3813(non-)X
648 1707(membership)N
1064(in)X
1146(S.)X
848 1920(We)N
987(call)X
1130(a)X
1193(minimal)X
1486(proof)X
1687(of)X
1781(membership)X
2204(in)X
2293(S)X
2363(a)X
2 f
2425(1-certi\256cate)X
2839(for)X
2958(S)X
1 f
3024(and)X
3166(a)X
3228(minimal)X
3520(proof)X
3720(of)X
3813(non-)X
648 2100(membership)N
1069(in)X
1156(S)X
1225(a)X
2 f
1286(0-certi\256cate)X
1699(for)X
1817(S.)X
1 f
1922(ship)X
2080(in)X
2167(S.)X
2256(I.e.,)X
2404(a)X
2464(proof)X
2662(Y)X
2744(is)X
2821(minimal)X
3111(if)X
3184(any)X
3324(subset)X
3548(of)X
3639(Y)X
3721(is)X
3798(not)X
3924(a)X
648 2280(proof.)N
862(The)X
1007(size)X
1152(of)X
1239(a)X
1295(certi\256cate)X
1632(is)X
1705(the)X
1823(number)X
2088(of)X
2175(query)X
2378(pairs)X
2554(in)X
2636(it.)X
848 2493(We)N
991(may)X
1160(de\256ne)X
1387(the)X
2 f
1515(nondeterministic)X
2083(complexity)X
2461(of)X
2553(any)X
2699(set)X
2818(property)X
3124(S,)X
3214(N\(S\),)X
1 f
3411(as)X
3508(the)X
3636(maximum)X
648 2673(over)N
812(all)X
913(input)X
1098(sets)X
1239(of)X
1327(the)X
1445(minimum)X
1775(size)X
1920(proof)X
2114(consistent)X
2454(with)X
2616(the)X
2734(input)X
2918(set.)X
3067(The)X
3212(following)X
3543(two)X
3683(observa-)X
648 2853(tions)N
823(are)X
942(apparent.)X
3 f
648 3066(Proposition)N
1063(3.1:)X
2 f
648 3279(\(i\))N
744(D\(S\))X
9 f
896(\263)X
2 f
960(R\(S\))X
9 f
1103(\263)X
2 f
1147(N\(S\).)X
648 3459(\(ii\))N
774(Let)X
903(Y)X
974(and)X
1121(N)X
1201(be)X
1304(any)X
1447(proof)X
1647(of)X
1736(membership)X
2155(and)X
2302(proof)X
2502(of)X
2591(non-membership,)X
3177(respectively.)X
3608(Then)X
3795(there)X
648 3639(must)N
820(be)X
917(some)X
1103(query)X
1307(Q)X
1386(on)X
1487(which)X
1699(they)X
1854(disagree.)X
2171(I.e,)X
2295(either)X
2503(\(Q,)X
2629(yes\))X
9 f
2780(\316)X
2 f
2858(Y)X
2923(and)X
3064(\(Q,)X
3190(no\))X
9 f
3317(\316)X
2 f
3394(N,)X
3487(or)X
3578(\(Q,)X
3703(no\))X
9 f
3830(\316)X
2 f
3907(N)X
648 3819(and)N
788(\(Q,)X
913(yes\))X
9 f
1063(\316)X
2 f
1140(Y.)X
1 f
848 4032(Blum)N
1055(has)X
1192(shown)X
1431(that)X
1580(for)X
1703(any)X
1848(set)X
1966(property)X
2 f
2267(N)X
1 f
2333(\()X
2 f
2360(S)X
1 f
2413(\))X
2 f
9 f
2440(\263)X
2 f
2484(D)X
1 f
2555(\()X
2 f
2582(S)X
1 f
2635(\))X
2 f
7 s
2662 3999(.)N
1 f
(5)S
10 s
4032(.)Y
2773(The)X
2927(following)X
3267(theorem)X
3559(may)X
3726(also)X
3884(be)X
648 4212(used)N
822(to)X
911(\256nd)X
1062(lower)X
1272(bounds)X
1530(on)X
1636(N\(S\),)X
1838(in)X
1926(the)X
2050(case)X
2215(where)X
2438(S)X
2508(is)X
2587(invariant)X
2898(under)X
3107(a)X
3169(group)X
3382(which)X
3604(acts)X
3755(transi-)X
648 4392(tively)N
852(on)X
954(its)X
1051(element)X
1326(set.)X
1476(The)X
1622(proof)X
1817(given)X
2016(here)X
2176(is)X
2250(in)X
2333(fact)X
2475(a)X
2532(generalization)X
3008(of)X
3096(an)X
3193(argument)X
3517(used)X
3685(by)X
3786(Kirk-)X
648 4572(patrick)N
891(in)X
973(1974)X
1153(in)X
1235(proving)X
1504(a)X
1560(lower)X
1763(bound)X
1983(on)X
2083(the)X
2201(deterministic)X
2639(complexity)X
3019(of)X
3106(nontrivial)X
3437(monotone)X
3777(graph)X
648 4752(properties)N
989(and)X
1125(by)X
1225(Sauer)X
1428(and)X
1564(Spencer)X
1843(in)X
1925(1978)X
2105(in)X
2187(proving)X
2456(theorems)X
2770(about)X
2968(packing)X
3242(graphs)X
3476(\(see)X
3626(below\).)X
3 f
648 4965(Theorem)N
988(3.2:)X
2 f
1143(Let)X
1273(S)X
1341(be)X
1445(any)X
1589(set)X
1706(property)X
2010(with)X
2175(element)X
2453(set)X
2570(X)X
2647(which)X
2865(is)X
2945(invariant)X
3265(under)X
3479(the)X
3604(action)X
3831(of)X
3920(a)X
648 5145(group)N
871(G)X
961(which)X
1184(acts)X
1345(transitively)X
1737(on)X
1848(X.)X
1948(If)X
2028(Y)X
2103(and)X
2254(N)X
2338(are)X
2476(a)X
2547(1-certi\256cate)X
2966(and)X
3117(a)X
3188(0-certi\256cate)X
3607(for)X
3731(S,)X
3822(then)X
9 f
648 5325(|)N
2 f
(Y)S
9 f
708(||)X
2 f
(N)S
9 f
793(|\263|)X
2 f
869(X)X
9 f
918(|)X
2 f
(.)S
3 f
648 5538(Proof:)N
1 f
889(We)X
1023(prove)X
1228(this)X
1364(by)X
1465(showing)X
1757(that)X
1898(if)X
1968(I)X
2016(and)X
2153(I')X
2228(are)X
2348(any)X
2485(two)X
2626(sets)X
2767(in)X
2850(S)X
2915(such)X
3083(that)X
9 f
3224(|)X
1 f
(I)S
9 f
3267(||)X
1 f
(I')S
9 f
3353(|)X
1 f
3390(<)X
9 f
3435(|)X
1 f
(X)S
9 f
3509(|)X
1 f
(,)S
3566(then)X
3725(there)X
3907(is)X
648 5718(some)N
842(g)X
9 f
(\316)S
1 f
964(G)X
1047(such)X
1219(that)X
1364(gI)X
9 f
1456(\310)X
1 f
1543(I')X
1622(=)X
9 f
1667(\306)X
1 f
1733(.)X
1798(The)X
1947(theorem)X
2234(follows)X
2498(as)X
2589(a)X
2649(consequence)X
3084(of)X
3175(Proposition)X
3567(3.1)X
3691(\(ii\).)X
3853(Let)X
20 p
%%Page: 20 21
10 s 0 xH 0 xS 1 f
3880 666(20)N
648 954(B\(I\))N
805(be)X
904(the)X
1025(orbit)X
1199(of)X
1289(I)X
1339(under)X
1545(G,)X
1646(i.e.,)X
1787(B\(I\))X
1944(=)X
2012({gI)X
9 f
(|)S
1 f
2156(for)X
2272(all)X
2374(g)X
9 f
(\316)S
1 f
2493(G}.)X
2651(Since)X
2851(G)X
2931(acts)X
3078(transitively)X
3460(on)X
3562(X,)X
3662(every)X
3863(x)X
9 f
(\316)S
1 f
648 1134(X)N
730(appears)X
999(in)X
1084(the)X
1205(same)X
1393(number)X
1661(of)X
1751(sets)X
1894(in)X
1979(B\(I\).)X
2156(Thus,)X
9 f
2359(|)X
1 f
(B\(I\))S
9 f
2509(||)X
1 f
(I)S
9 f
2568(|)X
1 f
(=)S
2652(k)X
9 f
(|)S
1 f
(X)S
9 f
2766(|)X
1 f
2805(for)X
2922(some)X
3114(k.)X
3197(In)X
3287(particular,)X
3638(every)X
3840(x)X
9 f
3903(\316)X
1 f
648 1314(I')N
732(appears)X
1008(in)X
1100(B\(I\))X
1264(k)X
1334(times.)X
1557(If)X
1641(every)X
1849(set)X
1967(in)X
2058(B\(I\))X
2221(contains)X
2517(at)X
2604(least)X
2780(one)X
2925(x)X
9 f
2994(\316)X
1 f
3080(I',)X
3183(then)X
9 f
3350(|)X
1 f
(B\(I\))S
9 f
3500(|)X
2 f
9 f
(\243)S
1 f
3589(k)X
9 f
(|)S
1 f
(I')S
9 f
3699(|)X
1 f
(,)S
3764(which)X
648 1494(implies)N
903(that)X
1043(k)X
9 f
(|)S
1 f
(X)S
9 f
1157(|)X
2 f
9 f
(\243)S
1 f
1237(k)X
9 f
(|)S
1 f
(I')S
9 f
1347(||)X
1 f
(I)S
9 f
1406(|)X
1 f
1442(or)X
9 f
1529(|)X
1 f
(X)S
9 f
1603(|)X
2 f
9 f
(\243)S
1 f
9 f
1663(|)X
1 f
(I')S
9 f
1733(||)X
1 f
(I)S
9 f
1792(|)X
1 f
(.)S
3 f
648 1770(Corollary)N
1002(3.3)X
1122(\([Y1],)X
1341([K],)X
1497([SS]\):)X
2 f
1713(For)X
1853(any)X
1989(graph)X
2200(property)X
2496(P)X
2565(on)X
2665(n)X
2725(nodes,)X
2952(N\(P\))X
9 f
3108(\263)X
2 f
10 f
3165 1684(I)N
3165 1764(J)N
3165 1844(L)N
1 f
1812(2)Y
2 f
3185 1731(n)N
10 f
3238 1684(M)N
3238 1764(J)N
3238 1844(O)N
1 f
7 s
1656(1)Y
2 f
(/)S
1 f
3302(2)X
2 f
10 s
1770(.)Y
3 f
648 2112(3.3.)N
808(Previous)X
1126(Lower)X
1369(Bounds)X
1 f
848 2325(The)N
997(\256rst)X
1145(lower)X
1352(bound)X
1576(on)X
1680(the)X
1802(randomized)X
2205(complexity)X
2589(of)X
2680(nontrivial)X
3015(graph)X
3222(properties)X
3567(observed)X
3880(by)X
648 2505(Yao)N
802(in)X
884(1977)X
1064(was)X
1209(a)X
1265(consequence)X
1696(of)X
1783(lower)X
1986(bound)X
2206(for)X
2320(the)X
2438(nondeterministic)X
2996(complexity,)X
3396(given)X
3594(above.)X
848 2718(In)N
936(that)X
1077(same)X
1263(paper,)X
1483(Yao)X
1638(introduced)X
2002(some)X
2192(important)X
2524(techniques)X
2888(for)X
3003(proving)X
3273(lower)X
3477(bounds)X
3729(on)X
3830(ran-)X
648 2898(domized)N
946(complexity.)X
1348(One)X
1504(important)X
1837(result)X
2037(which)X
2255(can)X
2389(be)X
2487(applied)X
2744(to)X
2827(analysis)X
3106(in)X
3189(other)X
3375(models)X
3627(of)X
3715(compu-)X
648 3078(tation)N
850(is)X
3 f
648 3291(Theorem)N
980(3.4)X
1100(\(Yao\))X
1312([Y1]:)X
2 f
1511(Let)X
1633(P)X
1702(be)X
1798(any)X
1934(set)X
2043(property.)X
2359(Then)X
1632 3504(R\(P\))N
1804(=)X
7 s
1940 3561(I)N
10 s
1878 3504(Max)N
7 s
2068 3561(A)N
10 s
2021 3504(Min)N
2170(\(Average)X
2485(Cost)X
2651(of)X
2733(A)X
2802(on)X
2902(I\),)X
750 3636(where)N
966(I)X
1013(is)X
1086(a)X
1146(probability)X
1521(distribution)X
1913(of)X
1995(input)X
2179(sets)X
2319(and)X
2459(A)X
2528(is)X
2601(a)X
2661(deterministic)X
3099(algorithm)X
3434(to)X
3516(compute)X
3808(P.)X
3 f
648 3882(Sketch)N
901(of)X
990(Proof:)X
1 f
1231(An)X
1351(algorithm)X
1684(which)X
1902(\257ips)X
2061(coins)X
2252(to)X
2336(determine)X
2679(its)X
2776(choices)X
3039(is)X
3114(equivalent)X
3469(to)X
3552(an)X
3649(algorithm)X
648 4062(which)N
866(\257ips)X
1025(all)X
1127(coins)X
1317(\256rst)X
1462(and)X
1599(then)X
1758(selects)X
1993(each)X
2162(possible)X
2445(deterministic)X
2884(algorithm)X
3216(with)X
3379(some)X
3569(\256xed)X
3750(proba-)X
648 4242(bility.)N
857(R\(P\))X
1029(may)X
1188(be)X
1285(viewed)X
1537(as)X
1624(the)X
1742(expected)X
2048(pay-off)X
2305(in)X
2387(a)X
2443(mixed)X
2663(strategy)X
2937(game.)X
3151(Player)X
3376(1)X
3436(\(the)X
3581(randomized)X
648 4422(algorithm\))N
1031(selects)X
1270(a)X
1331(vector)X
1557(of)X
1649(p)X
1714(=)X
2 f
1784(p)X
7 s
1 f
1833 4440(1)N
2 f
10 s
4422(p)Y
7 s
1 f
1910 4440(2)N
2 f
10 s
1958 4398(.)N
1998(.)X
2038(.)X
2078 4422(p)N
7 s
4440(z)Y
10 s
1 f
2198 4422(such)N
2369(that)X
2513(deterministic)X
2955(algorithm)X
3290(j)X
3336(is)X
3413(used)X
3584(with)X
3750(proba-)X
648 4605(bility)N
2 f
842(p)X
7 s
887 4623(j)N
10 s
1 f
916 4605(.)N
962(Player)X
1193(2)X
1259(\(the)X
1410(adversary\))X
1776(selects)X
2016(an)X
2118(input)X
2308(distribution)X
2 f
2702(I)X
9 f
2742(=)X
2 f
2786(i)X
7 s
1 f
2817 4623(1)N
2 f
10 s
4605(i)Y
7 s
1 f
2876 4623(2)N
2 f
10 s
2924 4581(.)N
2964(.)X
3004(.)X
3044 4605(i)N
7 s
3066 4623(w)N
10 s
1 f
3142 4605(such)N
3315(that)X
3460(input)X
3649(k)X
3714(appears)X
648 4788(with)N
814(probability)X
2 f
1189(i)X
7 s
1211 4806(k)N
10 s
1 f
1249 4788(.)N
1293(Each)X
1478(entry)X
2 f
1667(a)X
7 s
4806(i)Y
1728(j)X
10 s
1 f
1781 4788(in)N
1867(the)X
1989(game)X
2187(matrix)X
2419(A)X
2500(is)X
2576(the)X
2697(cost)X
2849(of)X
2939(the)X
3060(deterministic)X
3501(algorithm)X
3835(i)X
3880(on)X
648 4971(input)N
832(j.)X
894(The)X
1039(proof)X
1233(of)X
1320(the)X
1438(theorem)X
1721(follows)X
1981(from)X
2157(Von)X
2315(Neumann's)X
2705(Min-Max)X
3032(theorem)X
3315([V].)X
848 5184(Yao)N
1011(used)X
1187(a)X
1252(theorem)X
1544(similar)X
1795(to)X
1886(the)X
2013(following)X
2353(to)X
2444(prove)X
2 f
9 f
2656(W)X
1 f
2718(\()X
2 f
2745(n)X
7 s
1 f
2794 5151(2)N
10 s
5184(\))Y
2877(lower)X
3088(bounds)X
3347(on)X
3455(the)X
3581(randomized)X
648 5364(complexity)N
1037(on)X
1146(the)X
1273(problems)X
1600(of)X
1696(determining)X
2112(whether)X
2400(a)X
2464(graph)X
2675(on)X
2 f
2783(n)X
1 f
2836(nodes)X
3051(contains)X
3346(a)X
3410(perfect)X
3662(matching)X
648 5544(and)N
784(of)X
871(determining)X
1278(if)X
1347(it)X
1411(contains)X
1698(a)X
1754(Hamiltonian)X
2174(cycle.)X
21 p
%%Page: 21 22
10 s 0 xH 0 xS 1 f
3880 666(21)N
3 f
648 954(Theorem)N
980(\(Yao\):)X
2 f
1219(If)X
1288(S)X
1348(is)X
1421(monotone)X
1757(set)X
1866(property)X
2162(and)X
2302(has)X
2433(k)X
2489(1-certi\256cates)X
2928(\(or)X
3046(0-certi\256cates\))X
3512(size)X
3652(s,)X
3723(then)X
10 f
2092 1144(I)N
2092 1224(J)N
2092 1304(L)N
2 f
2201 1272(s)N
1 f
2112 1191(2)N
2 f
(R)S
1 f
2214(\()X
2 f
2241(S)X
1 f
2294(\))X
2 f
10 f
2334 1144(M)N
2334 1224(J)N
2334 1304(O)N
9 f
1230(\263)Y
2 f
2398(k)X
2447(/)X
1 f
2469(2)X
2 f
(.)S
3 f
648 1542(Sketch)N
900(of)X
988(Proof:)X
1 f
1228(Suppose)X
1520(f)X
1568(has)X
1695(k)X
1755(1-certi\256cates.)X
2210(We)X
2342(pick)X
2500(a)X
2556(distribution)X
2944(and)X
3080(prove)X
3283(a)X
3339(lower)X
3542(bound)X
3762(on)X
3862(the)X
648 1722(average)N
921(cost)X
1072(that)X
1214(any)X
1352(deterministic)X
1792(algorithm)X
2125(which)X
2342(computes)X
2670(S)X
2735(incurs)X
2952(on)X
3053(that)X
3194(distribution.)X
3623(The)X
3769(distri-)X
648 1902(bution)N
877(is)X
955(the)X
1078(uniform)X
1361(distribution)X
1754(of)X
1846(the)X
1969(sets)X
2114(of)X
2205(s)X
2260(elements)X
2569(queried)X
2834(in)X
2920(each)X
3092(of)X
3183(the)X
3305(k)X
3369(1-certi\256cates.)X
3848(We)X
648 2082(note)N
821(that)X
976(since)X
1176(each)X
1359(1-certi\256cate)X
1778(is)X
1866(a)X
1937(minimal)X
2238(proof,)X
2467(any)X
2618(decision)X
2920(tree)X
3076(algorithm)X
3422(which)X
3653(computes)X
648 2262(without)N
919(error)X
1103(must)X
1285(have)X
1464(exactly)X
1723(s)X
1781(of)X
1875(its)X
1977(queries)X
2236(on)X
2343(that)X
2490(input)X
2681(set)X
2797(answered)X
3128("yes")X
3328(before)X
3561(it)X
3632(accepts)X
3896(it,)X
648 2442(and,)N
806(no)X
908(two)X
1050(of)X
1139(these)X
1326(sets)X
1468(can)X
1602(be)X
1700(accepted)X
2004(by)X
2106(the)X
2226(same)X
2412(leaf)X
2554(in)X
2637(the)X
2756(decision)X
3044(tree.)X
3226(Then,)X
3432(there)X
3614(are)X
3734(at)X
3813(least)X
648 2622(k)N
715(leaves)X
943(in)X
1032(the)X
1157(decision)X
1451(tree,)X
1619(each)X
1794(corresponding)X
2280(to)X
2369(a)X
2432(different)X
2735(1-certi\256cate,)X
3165(and)X
3307(each)X
3481(at)X
3565(the)X
3689(end)X
3831(of)X
3924(a)X
648 2802(path)N
806(with)X
968(exactly)X
1220(s)X
1271("yes")X
1464(branches.)X
848 3078(A)N
931(binary)X
1161(tree)X
1307(of)X
1399(height)X
1624(h)X
1689(can)X
1826(have)X
2002(at)X
2084(most)X
2 f
10 f
2276 2992(I)N
2276 3072(J)N
2276 3152(L)N
2 f
2300 3120(s)N
2296 3039(h)N
10 f
2349 2992(M)N
2349 3072(J)N
2349 3152(O)N
1 f
2393 3078(paths)N
2586(with)X
2752(exactly)X
3008(m)X
3094("yes")X
3291(branches.)X
3621(If)X
2 f
10 f
3712 2992(I)N
3712 3072(J)N
3712 3152(L)N
2 f
3736 3120(s)N
3732 3039(h)N
10 f
3785 2992(M)N
3785 3072(J)N
3785 3152(O)N
9 f
3078(=)Y
2 f
3849(k)X
3898(/)X
1 f
3920(2)X
648 3324(then)N
807(at)X
886(least)X
1054(half)X
1200(the)X
1319(leaves)X
1541(accepting)X
1870(the)X
1989(inputs)X
2205(in)X
2288(the)X
2407(distribution)X
2796(must)X
2972(lie)X
3073(at)X
3152(depth)X
3351(greater)X
3596(than)X
3755(h.)X
3835(The)X
648 3504(average)N
927(depth)X
1133(of)X
1228(these)X
1421(leaves)X
1650(is)X
1731(at)X
1817(least)X
1992(h/2.)X
2142(By)X
2263(Theorem)X
2581(3.4,)X
2729(R\(P\))X
2908(is)X
2988(at)X
3073(least)X
3247(the)X
3372(minimum)X
3709(average)X
648 3684(cost)N
797(of)X
884(any)X
1020(deterministic)X
1458(algorithm)X
1789(on)X
1889(this)X
2024(input)X
2208(which)X
2424(is)X
2497(at)X
2575(least)X
2742(h/2.)X
848 3897(Yao's)N
1062(lower)X
1267(bound)X
1489(of)X
2 f
9 f
1578(W)X
1 f
1640(\()X
2 f
1667(n)X
1 f
1720(log)X
7 s
1822 3864(1)N
2 f
(/)S
1 f
1866(12)X
2 f
10 s
3897(n)Y
1 f
1975(\))X
2024(was)X
2171(proved)X
2416(in)X
2500(two)X
2641(steps.)X
2842(First,)X
3029(following)X
3361(the)X
3480(technique)X
3813(used)X
648 4077(by)N
761(Rivest)X
998(and)X
1147(Vuillemin,)X
1524(he)X
1633(reduced)X
1921(the)X
2051(computation)X
2483(of)X
2582(a)X
2650(graph)X
2865(property)X
3169(to)X
3263(the)X
3393(computation)X
3825(of)X
3924(a)X
648 4257(bipartite)N
936(graph)X
1140(property,)X
1452(by)X
1552(revealing)X
1871(information)X
2269(about)X
2467(some)X
2656(of)X
2743(the)X
2861(edges.)X
3084(Second,)X
3360(he)X
3456(showed)X
3721(a)X
3777(lower)X
648 4437(bound)N
871(on)X
974(the)X
1095(randomized)X
1497(complexity)X
1880(of)X
1970(nontrivial)X
2304(monotone)X
2647(bipartite)X
2936(graph)X
3141(properties)X
3484(by)X
3586(considering)X
648 4617(two)N
788(cases.)X
848 4830(The)N
1008(improved)X
1350(lower)X
1568(bound)X
1803(presented)X
2145(in)X
2241(the)X
2373(next)X
2545(section)X
2806(follows)X
3080(the)X
3212(basic)X
3411(outline)X
3667(of)X
3768(Yao's)X
648 5010(proof.)N
867(In)X
959(step)X
1113(1,)X
1198(using)X
1396(a)X
1457(different,)X
1779(simpler)X
2044(technique,)X
2401(we)X
2520(show)X
2713(that)X
2857(either)X
3064(a)X
3124(graph)X
3331(property)X
3627(has)X
3758(a)X
3818(high)X
648 5190(nondeterministic)N
1220(complexity)X
1614(or)X
1715(it)X
1793(can)X
1939(be)X
2049(reduced)X
2338(to)X
2434(a)X
2504(bipartite)X
2805(graph)X
3022(property.)X
3347(We)X
3492(prove)X
3708(a)X
3777(lower)X
648 5370(bound)N
871(for)X
988(bipartite)X
1278(graph)X
1484(properties)X
1828(by)X
1931(considering)X
2328(essentially)X
2688(the)X
2808(same)X
2995(two)X
3137(cases.)X
3349(One)X
3505(case)X
3666(is)X
3741(treated)X
648 5550(with)N
810(Yao's)X
1022(technique.)X
1374(However,)X
1709(the)X
1827(other)X
2012(case)X
2171(is)X
2244(handled)X
2518(much)X
2716(differently.)X
22 p
%%Page: 22 23
10 s 0 xH 0 xS 1 f
3880 666(22)N
848 954(In)N
936(both)X
1099(cases,)X
1310(we)X
1425(show)X
1615(that)X
1756(we)X
1871(can)X
2003(reduce)X
2238(a)X
2294(bipartite)X
2581(graph)X
2784(property)X
3076(to)X
3158(a)X
3214(set)X
3323(property)X
3615(with)X
3777(either)X
648 1134(a)N
708(large)X
893(number)X
1162(of)X
1253(1-certi\256cates)X
1692(or)X
1783(a)X
1843(large)X
2028(number)X
2297(of)X
2388(0-certi\256cates)X
2826(of)X
2916(suf\256ciently)X
3299(small)X
3495(size)X
3643(and)X
3782(apply)X
648 1314(Theorem)N
958(3.5)X
1078(above)X
1290(to)X
1372(prove)X
1575(a)X
1631(lower)X
1834(bound)X
2054(on)X
2154(their)X
2321(randomized)X
2720(complexity.)X
3 f
648 1590(3.4.)N
808(A)X
886(New)X
1058(Lower)X
1301(Bound)X
1546(for)X
1669(Graph)X
1915(Properties)X
1 f
848 1803(We)N
980(show:)X
3 f
648 2016(Theorem)N
980(3.6:)X
2 f
1127(For)X
1267(any)X
1403(nontrivial)X
1738(monotone)X
2074(graph)X
2285(property)X
2581(P,)X
2670(R\(P\)>n)X
7 s
1 f
2925 1983(5)N
2 f
(/)S
1 f
2969(4)X
2 f
10 s
2016(/)Y
1 f
3019(44)X
2 f
(,)S
3139(for)X
3252(suf\256ciently)X
3619(large)X
3808(n.)X
1 f
848 2229(In)N
943(Sections)X
1242(3.4.2)X
1430(and)X
1574(3.4.3,)X
1782(we)X
1904(reduce)X
2147(the)X
2273(minimum)X
2610(randomized)X
3016(complexity)X
3403(of)X
3497(any)X
3640(monotone)X
648 2409(nontrivial)N
985(graph)X
1194(property)X
1492(on)X
2 f
1598(n)X
1 f
1677(nodes)X
1890(to)X
2 f
1978(b)X
7 s
2427(k)Y
1 f
2052(,)X
2 f
(l)S
10 s
1 f
2095 2409(,)N
2140(the)X
2263(minimum)X
2598(randomized)X
3002(complexity)X
3387(of)X
3479(any)X
3620(monotone,)X
648 2592(nontrivial)N
979(bipartite)X
1266(graph)X
1469(property)X
1761(on)X
1861(V)X
1939(and)X
2075(W)X
2171(with)X
9 f
2333(|)X
1 f
(V)S
9 f
2407(|)X
1 f
(=k)S
2528(and)X
9 f
2664(|)X
1 f
(W)S
9 f
2756(|)X
1 f
(=l:)S
3 f
648 2805(Theorem)N
993(3.7:)X
2 f
1153(For)X
1306(any)X
1455(q)X
1528(such)X
1708(that)X
1865(1)X
9 f
(\243)S
2 f
1949(q)X
9 f
2002(\243)X
2 f
2046(n)X
2099(/)X
1 f
2121(2)X
2 f
2194(and)X
2347(any)X
2496(monotone)X
2845(nontrivial)X
3193(graph)X
3417(property)X
3726(P)X
3808(on)X
3920(n)X
648 2985(nodes,)N
875(R\(P\))X
9 f
1027(\263)X
1 f
1071(min)X
2 f
1195({n)X
7 s
1 f
1276 2952(2)N
2 f
10 s
2985(/)Y
1 f
1326(3)X
2 f
(q)S
9 f
1419(-)X
1 f
1463(3)X
2 f
(/)S
1 f
1525(2)X
2 f
(n)S
1 f
1618(,)X
2 f
7 s
3042(q)Y
9 f
1675(\243)X
2 f
1706(r)X
9 f
1737(\243)X
2 f
1768(n)X
1805(/)X
1 f
1821(2)X
10 s
1681 2985(min)N
2 f
1848(b)X
7 s
3003(n)Y
9 f
1925(-)X
2 f
1956(r)X
1 f
1987(,)X
2 f
(r)S
10 s
2036 2985(}.)N
3 f
648 3240(Theorem)N
1043(3.8:)X
2 f
1253(For)X
1456(any)X
1655(monotone,)X
2074(nontrivial)X
2472(graph)X
2746(property)X
3104(P)X
3235(on)X
3397(n)X
3519(nodes,)X
3808(R\(P\))X
9 f
648 3420(\263)N
1 f
692(min)X
2 f
816({n)X
7 s
1 f
897 3387(5)N
2 f
(/)S
1 f
941(4)X
2 f
10 s
3420(/)Y
1 f
991(32,)X
2 f
1111(b)X
7 s
10 f
1160 3430(J)N
1160 3486(Q)N
2 f
3465(n)Y
1211(/)X
1 f
1227(2)X
2 f
10 f
1264 3430(J)N
1264 3486(P)N
1 f
3465(,)Y
2 f
10 f
1301 3430(R)N
1301 3486(J)N
2 f
3465(n)Y
1352(/)X
1 f
1368(2)X
2 f
10 f
1405 3430(H)N
1405 3486(J)N
10 s
2 f
3420(})Y
1471(for)X
1584(suf\256ciently)X
1951(large)X
2140(n.)X
1 f
848 3690(In)N
935(Section)X
1195(3.4.4,)X
1395(we)X
1509(prove)X
1712(a)X
1768(lower)X
1971(bound)X
2191(for)X
2305(bipartite)X
2592(graph)X
2795(properties:)X
3 f
648 3903(Theorem)N
980(3.9:)X
2 f
1127(For)X
1267(any)X
1403(k)X
1459(and)X
1599(l,)X
1661(b)X
7 s
3921(k)Y
1 f
1735(,)X
2 f
(l)S
10 s
1778 3903(>k)N
7 s
1 f
1877 3870(3)N
2 f
(/)S
1 f
1921(4)X
2 f
10 s
3903(l)Y
7 s
1 f
1980 3870(1)N
2 f
(/)S
1 f
2024(2)X
2 f
10 s
3903(/)Y
2094(18)X
2194(for)X
2307(suf\256ciently)X
2674(large)X
2863(k)X
2919(and)X
3059(l.)X
1 f
648 4119(ThIs)N
816(improves)X
1135(the)X
1254(lower)X
1458(bound)X
1679(for)X
2 f
1794(b)X
7 s
4137(n)Y
1 f
1871(,)X
2 f
(n)S
10 s
1 f
1947 4119(to)N
2 f
9 f
2030(W)X
1 f
2092(\()X
2 f
2119(n)X
7 s
1 f
2168 4086(5)N
2 f
(/)S
1 f
2212(4)X
10 s
4119(\))Y
2288(from)X
2485(the)X
2604(previously)X
2963(known)X
3202(bound)X
3423(of)X
2 f
9 f
3510(W)X
1 f
3572(\()X
2 f
3599(n)X
1 f
3652(\(log)X
2 f
3781(n)X
1 f
3834(\))X
7 s
3861 4086(1)N
2 f
(/)S
1 f
3905(4)X
10 s
4119(\))Y
648 4302([Y3].)N
848 4515(Theorems)N
1194(3.8)X
1319(and)X
1460(3.9)X
1585(immediately)X
2010(yield)X
2195(Theorem)X
2510(3.6.)X
2655(Theorem)X
2970(3.7)X
3095(is)X
3173(of)X
3264(interest)X
3524(in)X
3610(that)X
3754(it)X
3822(may)X
648 4695(lead)N
810(to)X
900(lower)X
1111(bounds)X
1369(as)X
1463(high)X
1632(as)X
2 f
1726(n)X
7 s
1 f
1775 4662(1.5)N
10 s
4695(,)Y
1892(if)X
1968(improved)X
2302(lower)X
2512(bounds)X
2770(on)X
2877(the)X
3002(complexity)X
3389(of)X
3483(bipartite)X
3777(graph)X
648 4875(properties)N
989(can)X
1121(be)X
1217(shown.)X
848 5088(In)N
935(section)X
1182(3.4.6,)X
1382(we)X
1496(give)X
1654(a)X
1710(technique)X
2042(for)X
2156(proving)X
2425(lower)X
2628(bounds)X
2879(for)X
2993(some)X
3182(graph)X
3385(properties:)X
3 f
648 5301(Theorem)N
987(3.10:)X
2 f
1181(If)X
1257(P)X
1333(is)X
1413(a)X
1480(monotone)X
1823(nontrivial)X
2165(graph)X
2383(property)X
2686(and)X
2833(there)X
3025(is)X
3105(a)X
3172(graph)X
3389(G)X
3473(in)X
3561(P)X
3636(with)X
3799(max-)X
648 5481(imum)N
846(degree)X
1085(d,)X
1165(then)X
1323(R\(P\))X
1495(>)X
1569(n)X
7 s
1 f
1618 5448(2)N
2 f
10 s
5481(/)Y
1 f
1668(512\()X
2 f
1815(d)X
7 s
1 f
1864 5448(3)N
2 f
10 s
9 f
5481(+)Y
2 f
1936(d)X
7 s
1 f
1985 5448(2)N
2 f
10 s
9 f
5481(+)Y
2 f
2057(d)X
9 f
2110(+)X
1 f
2154(1\))X
2 f
2221(.)X
23 p
%%Page: 23 24
10 s 0 xH 0 xS 2 f
1 f
3880 666(23)N
3 f
648 954(3.4.1.)N
868(Preliminaries)X
1 f
848 1167(For)N
995(the)X
1129(purposes)X
1450(of)X
1553(this)X
1704(section,)X
1986(in)X
2083(which)X
2314(only)X
2491(monotone)X
2846(set)X
2970(properties)X
3326(are)X
3460(discussed,)X
3822(a)X
2 f
3893(1-)X
648 1347(certi\256cate)N
992(for)X
1107(P)X
1 f
1178(will)X
1324(refer)X
1499(to)X
2 f
1583(a)X
1645(minimal)X
1929(set)X
2040(of)X
2124(elements)X
2427(whose)X
2649(presence)X
2957(in)X
3041(an)X
3143(input)X
3329(set)X
3440(proves)X
3676(the)X
3796(input)X
648 1527(set)N
766(is)X
848(in)X
939(P.)X
1 f
1056(A)X
2 f
1142(0-certi\256cate)X
1558(for)X
1679(P)X
1 f
1756(is)X
1837(then)X
2 f
2003(a)X
2071(minimal)X
2361(set)X
2478(of)X
2568(elements)X
2877(whose)X
3105(absence)X
3392(from)X
3571(an)X
3679(input)X
3871(set)X
648 1707(proves)N
882(the)X
1000(input)X
1184(set)X
1293(is)X
1366(not)X
1488(in)X
1570(P.)X
1 f
848 1920(Let)N
2 f
9 f
992(p)X
1 f
1073(be)X
1186(a)X
1259(permutation)X
1683(of)X
1787(nodes)X
2011(in)X
2110(V.)X
2225(For)X
2373(any)X
2526(set)X
2652(of)X
2756(edges)X
2975(A)X
3069(on)X
3185(V,)X
3299(let)X
2 f
9 f
3415(p)X
1 f
3459(\(A\))X
3607(by)X
2 f
9 f
3723(p)X
1 f
3767(\(A\))X
3915(=)X
648 2100({{)N
2 f
9 f
724(p)X
1 f
768(\(i\),)X
2 f
9 f
864(p)X
1 f
908(\(j\)})X
9 f
1043(|)X
1 f
1080({i,j})X
9 f
1241(\316)X
1 f
1319(A}.)X
1456(If)X
1531(A)X
1610(and)X
1747(B)X
1821(are)X
1941(sets)X
2082(of)X
2169(edges)X
2372(on)X
2472(V,)X
2570(we)X
2684(say)X
2811(A)X
2889(and)X
3025(B)X
3098(can)X
3230(be)X
2 f
3326(packed)X
1 f
3574(iff)X
3670(there)X
3851(is)X
3924(a)X
648 2280(permutation)N
2 f
9 f
1055(p)X
1 f
1119(of)X
1206(V)X
1284(such)X
1451(that)X
2 f
9 f
1591(p)X
1 f
1635(\(A\))X
1767(and)X
1903(B)X
1976(are)X
2095(disjoint.)X
848 2493(The)N
998(proofs)X
1228(in)X
1315(this)X
1455(section)X
1707(will)X
1855(make)X
2053(frequent)X
2345(use)X
2476(of)X
2567(the)X
2689(following)X
3024(facts)X
3200(which)X
3420(are)X
3543(special)X
3790(cases)X
648 2673(of)N
735(Proposition)X
1123(3.1.)X
1263(Let)X
1390(P)X
1454(be)X
1550(any)X
1686(nontrivial)X
2017(monotone)X
2357(graph)X
2560(property.)X
2 f
648 2886(a.)N
728(R\(P\))X
900(is)X
973(greater)X
1229(than)X
1391(or)X
1482(equal)X
1680(to)X
1762(the)X
1880(size)X
2020(of)X
2102(any)X
2238(1)X
2298(or)X
2389(0-certi\256cate.)X
648 3066(b.)N
748(A)X
817(0-certi\256cate)X
1225(and)X
1365(a)X
1425(1-certi\256cate)X
1833(for)X
1946(P)X
2015(cannot)X
2253(be)X
2349(packed.)X
3 f
648 3279(Proposition)N
1063(3.11:)X
2 f
1250(Let)X
1372(G)X
9 f
1450(\316)X
2 f
1527(P)X
7 s
1585 3246(D)N
10 s
1658 3279(iff)N
1744(G)X
10 f
1760 3205(h)N
1770(h)X
2 f
9 f
1835 3279(\316)N
2 f
1853(/)X
1912(P,)X
2001(for)X
2114(G)X
10 f
2130 3205(h)N
2140(h)X
2 f
2205 3279(the)N
2323(complement)X
2731(of)X
2813(G.)X
2911(P)X
7 s
2969 3246(D)N
10 s
3042 3279(is)N
3115(called)X
3331(the)X
3449("dual")X
3679(of)X
3761(P.)X
648 3492(a.)N
728(P)X
7 s
786 3459(D)N
10 s
859 3492(is)N
932(monotone)X
1268(and)X
1408(nontrivial)X
1743(if)X
1807(P)X
1876(is.)X
648 3705(b.)N
728(The)X
868(0-certi\256cates)X
1307(of)X
1389(P)X
1458(are)X
1585(the)X
1703(1-certi\256cates)X
2142(of)X
2224(P)X
7 s
2282 3672(D)N
10 s
2355 3705(and)N
2495(vice)X
2645(versa.)X
648 3918(c.)N
724(R\(P)X
7 s
858 3885(D)N
10 s
911 3918(\))N
958(=)X
1032(R\(P\).)X
3 f
648 4194(3.4.2.)N
868(Reduction)X
1239(to)X
1326(a)X
1386(Bipartite)X
1713(Graph)X
1959(Property)X
2287(I)X
1 f
848 4407(The)N
993(proof)X
1187(of)X
1274(Theorem)X
1584(3.7)X
1704(uses:)X
3 f
648 4620(Turan's)N
945(Theorem)X
1279(\([T]\):)X
2 f
1489(Let)X
1613(q)X
1674(and)X
1815(n)X
1876(be)X
1973(natural)X
2229(numbers)X
2526(with)X
2684(q)X
2745(>)X
2820(2.)X
2901(Every)X
3110(n-node)X
3354(graph)X
3566(with)X
3724(greater)X
648 4872(than)N
10 f
823 4786(I)N
823 4866(J)N
823 4946(L)N
1 f
4914(2)Y
2 f
843 4833(n)N
10 f
896 4786(M)N
896 4866(J)N
896 4946(O)N
9 f
4872(-)Y
2 f
960(t)X
7 s
982 4890(q)N
9 f
1019(-)X
1 f
1050(1)X
10 s
4872(\()Y
2 f
1105(n)X
1 f
1158(\))X
2 f
1205(edges)X
1408(contains)X
1699(a)X
1759(q-clique,)X
2062(where)X
2278(t)X
7 s
2300 4890(q)N
10 s
2361 4872(=)N
7 s
2469 4953(i)N
9 f
2494(=)X
1 f
2525(0)X
2 f
15 s
9 f
2475 4896(S)N
7 s
2 f
2434 4791(i)N
9 f
2459(=)X
2 f
2490(q)X
9 f
2527(-)X
1 f
2558(1)X
2 f
10 s
10 f
2599 4777(I)N
2599 4857(J)N
2599 4937(L)N
1 f
2633 4914(2)N
2 f
2619 4815(n)N
7 s
4833(i)Y
10 s
10 f
2701 4777(M)N
2701 4857(J)N
2701 4937(O)N
2 f
2741 4872(where)N
2957(n)X
7 s
4890(i)Y
10 s
9 f
3026 4872(=)N
2 f
10 f
3083 4789(J)N
3083 4869(J)N
3083 4949(Q)N
2 f
3162 4929(q)N
3123 4824(n)N
9 f
3176(+)X
2 f
3220(i)X
10 f
3111 4848(h)N
3134(hhh)X
2 f
10 f
3275 4789(J)N
3275 4869(J)N
3275 4949(P)N
2 f
4872(.)Y
1 f
648 5154(Equivalently,)N
2 f
1097(Any)X
1242(n-node)X
1485(graph)X
1696(with)X
1853(less)X
1993(than)X
2155(t)X
7 s
2177 5172(q)N
9 f
2214(-)X
1 f
2245(1)X
10 s
5154(\()Y
2 f
2300(n)X
1 f
2353(\))X
2 f
2400(edges)X
2603(can)X
2739(be)X
2835(packed)X
3083(with)X
3240(a)X
3300(q-clique.)X
3 f
648 5370(Proof)N
870(of)X
967(Theorem)X
1309(3.7:)X
1 f
1466(Let)X
2 f
1603(c)X
7 s
1 f
1648 5388(1)N
10 s
1706 5370(and)N
2 f
1852(c)X
7 s
1 f
1897 5388(0)N
10 s
1955 5370(each)N
2133(be)X
2239(the)X
2367(order)X
2567(of)X
2664(the)X
2791(smallest)X
3082(clique)X
3307(which)X
3532(contains)X
3828(a)X
3893(1-)X
648 5553(certi\256cate)N
986(and)X
1123(0-certi\256cate,)X
1548(respectively,)X
1977(for)X
2092(P.)X
2197(If)X
2 f
2272(c)X
7 s
1 f
2317 5571(1)N
2 f
10 s
9 f
5553(\243)Y
2 f
2389(q)X
1 f
2463(or)X
2 f
2551(c)X
7 s
1 f
2596 5571(0)N
2 f
10 s
9 f
5553(\243)Y
2 f
2668(q)X
1 f
2742(then)X
2901(Turan's)X
3172(Theorem)X
3483(implies)X
3739(that)X
3880(all)X
648 5736(0-certi\256cates,)N
1104(or)X
1192(all)X
1293(1-certi\256cates,)X
1749(resp.)X
1924(must)X
2100(have)X
2273(size)X
2 f
9 f
2419(\263)X
2 f
2463(t)X
7 s
2485 5754(q)N
9 f
2522(-)X
1 f
2553(1)X
10 s
5736(\()Y
2 f
2608(n)X
1 f
2661(\))X
2 f
9 f
2688(\263)X
2 f
2732(n)X
7 s
1 f
2781 5703(2)N
2 f
10 s
5736(/)Y
1 f
2831(3)X
2 f
(q)S
9 f
2924(-)X
1 f
2968(3)X
2 f
(/)S
1 f
3030(2)X
2 f
(n)S
1 f
3123(,)X
3163(giving)X
3387(a)X
3443(lower)X
3646(bound)X
3866(for)X
24 p
%%Page: 24 25
10 s 0 xH 0 xS 1 f
3880 666(24)N
648 954(R\(P\).)N
848 1167(For)N
2 f
983(c)X
7 s
1 f
1028 1185(1)N
2 f
10 s
1167(>q)Y
1 f
1187(and)X
2 f
1327(c)X
7 s
1 f
1372 1185(0)N
2 f
10 s
1167(>q)Y
1 f
1507(,)X
1551(let)X
1655(r)X
1706(=)X
1775(min)X
2 f
1899({c)X
7 s
1 f
1976 1185(1)N
2 f
10 s
9 f
1167(-)Y
1 f
2048(1,)X
2 f
2128(n)X
9 f
2181(-)X
2 f
2225(q)X
2278(})X
1 f
(.)S
2354(Then)X
2 f
2543(q)X
9 f
2596(\243)X
2 f
2640(r)X
9 f
2684(\243)X
2 f
2728(n)X
9 f
2781(-)X
2 f
2825(q)X
1 f
2902(and)X
2 f
3042(r)X
3086(