%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: june00.dvi %%CreationDate: Fri May 05 08:46:41 2000 %%Pages: 11 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips june00 %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2000.05.05:0845 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (june00.dvi) @start %DVIPSBitmapFont: Fa cmbx8 8 3 /Fa 3 89 df69 D80 D<007FB548B512E0A4C6903AE0000FE0006D 6C5C6E495A6D6C49C7FC011F5C6D6C137E6E5B6DEB81F86D13836DEBC7F0EDE7E06DEBFF C06E5B8093C8FC6E5A140F6E7E826E7F5C4A7F4A7F82EC3F3F91387E1FFC02FE7F4A6C7E 49487E49486C7F0107814A6C7F49487E49486D7E013F8149C76C7E017E141F496E7EB5D8 F001B512FCA4362E7DAD3D>88 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmsy8 8 4 /Fb 4 100 df<130C131EA50060EB01800078130739FC0C0FC0007FEB3F80393F8C7F00 3807CCF83801FFE038007F80011EC7FCEB7F803801FFE03807CCF8383F8C7F397F0C3F80 00FCEB0FC039781E078000601301000090C7FCA5130C1A1D7C9E23>3 D<137813FE1201A3120313FCA3EA07F8A313F0A2EA0FE0A313C0121F1380A3EA3F00A312 3E127E127CA35AA35A0F227EA413>48 D<126012E0B3B3B3A9B51280A27E114374B11F> 98 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc msam10 10.95 1 /Fc 1 4 df<007FB912E0BA12F0A300F0CBFCB3B3B2BAFCA36C18E03C3E7BBD47>3 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmmi6 6 4 /Fd 4 117 df<127812FCA4127806067A8513>58 D<1418143C147CA214381400A7EB07 80EB1FE01338EB60F013C0A2EA0180A2380001E0A4EB03C0A4EB0780A4EB0F00A4131EA2 1238EA783CEAF8381378EA70F0EA7FC0001FC7FC162D81A119>106 D<000F017E13FC3A1F81FF83FF3B31C383C707803A61EE03CC039026EC01F813C0D8C1F8 13F013F001E013E00003903903C0078013C0A2EE0F003907800780A2EE1E041706270F00 0F00130C163C1718A2001E011EEB1C70EE1FE0000C010CEB07802F177D9536>109 D<133013785BA4485AA4485AB51280A23803C000485AA448C7FCA4121EA25B1480383C03 001306A25BEA1C38EA0FF0EA07C011217D9F18>116 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmsy10 10.95 12 /Fe 12 107 df<007FB812FEBAFCA26C17FE3804799847>0 D<121EEA7F80A2EAFFC0A4 EA7F80A2EA1E000A0A799B19>I<0203B612FE023F15FF91B8FC010316FED90FFEC9FCEB 1FE0EB7F8001FECAFCEA01F8485A485A485A5B48CBFCA2123EA25AA21278A212F8A25AA8 7EA21278A2127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FE0EB0FFE0103B7 12FE010016FF143F020315FE91CAFCAE001FB812FE4817FFA26C17FE384879B947>18 D<180E183F18FFEF03FEEF0FF8EF3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF80DB03FE C7FCED0FF8ED7FE0913801FF80DA07FEC8FCEC1FF8EC7FC04948C9FCEB07FCEB1FF0EB7F C04848CAFCEA07FCEA1FF0EA7FC048CBFCA2EA7FC0EA1FF0EA07FCEA01FF38007FC0EB1F F0EB07FCEB01FF9038007FC0EC1FF0EC07FE913801FF809138007FE0ED1FF8ED03FE9238 00FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FEEF00FF183F180E1800AE 007FB812FEBAFCA26C17FE384879B947>20 D<19301978A2197C193CA2193E191EA2191F 737EA2737E737EA2737E737E1A7C1A7EF21F80F20FC0F207F0007FBB12FCBDFCA26C1AFC CDEA07F0F20FC0F21F80F27E001A7C624F5A4F5AA24F5A4F5AA24FC7FC191EA2193E193C A2197C1978A2193050307BAE5B>33 D<03F015F0A20201824B15780203167C4B153C0207 163E4A488192C97E4A83023E707E023C1603027C834A707E49B97E498449844984013FCB EA0FC0017E727E49727ED803F8F001FCD80FE0F0007FD83FC0F13FC0B4CDEA0FF0A2D83F C0F13FC0D80FE0F17F00D803F8F001FCC66CF003F0017E4E5A6D4E5A010FBAC7FC6D606D 606D60D900F8C9EA01F0027C4C5A023C5F023E16076E4C5A6E94C8FC6F5D6E6C153E0203 163C6F157C020116786F15F802005EA254327DAF5B>44 D<0203B512F8023F14FC91B6FC 010315F8D90FFEC8FCEB1FE0EB7F8001FEC9FCEA01F8485A485A485A5B48CAFCA2123EA2 5AA21278A212F8A25AA2B812F817FCA217F800F0CAFCA27EA21278A2127CA27EA27EA26C 7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FE0EB0FFE0103B612F8010015FC143F020314F82E 3679B13D>50 D<1718173C177CA217F8A2EE01F0A2EE03E0A2EE07C0160F1780EE1F00A2 163EA25EA25EA24B5AA24B5AA24B5AA24B5AA24BC7FCA2153E157E157C5DA24A5AA24A5A A24A5AA24A5AA24AC8FCA2143EA25CA25C13015C495AA2495AA2495AA249C9FCA2133EA2 5BA25BA2485AA2485AA2485A120F5B48CAFCA2123EA25AA25AA25A12602E5474C000>54 D92 D<153FEC03FFEC0FE0EC3F80EC7E00495A5C49 5AA2495AB3AA130F5C131F495A91C7FC13FEEA03F8EA7FE048C8FCEA7FE0EA03F8EA00FE 133F806D7E130F801307B3AA6D7EA26D7E80EB007EEC3F80EC0FE0EC03FFEC003F205B7A C32D>102 D<12FCEAFFC0EA07F0EA01FCEA007E6D7E131F6D7EA26D7EB3AA801303806D 7E1300147FEC1FC0EC07FEEC00FFEC07FEEC1FC0EC7F0014FC1301495A5C13075CB3AA49 5AA2495A133F017EC7FC485AEA07F0EAFFC000FCC8FC205B7AC32D>I<126012F0B3B3B3 B3B11260045B76C319>106 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff msbm10 10.95 2 /Ff 2 79 df<0203B612FE023F15FF91B8FC010316FED90FFEC9FCEB1FE0EB7F8001FECA FCEA01F8485A485A485A5B48CBFCA2123EA25AA21278A212F8A25AA87EA21278A2127CA2 7EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FE0EB0FFE0103B712FE010016FF143F 020315FE91CAFCA51606161F5E167E5E4B5A4B5A4B5A4B5A001FB812FE4817FFA26C17FE C7D803F0C8FC4A5A4A5A4A5A4AC9FC147E5C5C1460385179B947>40 D78 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmti10 10.95 51 /Fg 51 124 df<933807FF80043F13E09338FE00F8DB01F0133EDB07E0130E4B48131F4C 137F031F14FF4BC7FCA218FE157E1878180015FE5DA31401A25DA414030103B712F0A218 E0903A0003F000070207140F4B14C0A3171F020F15805DA2173F1800141F5D5F177EA214 3F92C712FE5FA34A1301027EECF81CA3160302FEECF03C4A1538A21878187013014A0101 13F018E0933800F1C0EF7F804948EC1F0094C7FCA35C1307A2001E5B127F130F00FF5BA2 49CAFC12FEEAF81EEA703CEA7878EA1FF0EA07C0385383BF33>12 D39 D44 D<387FFFFEA3B5FCA21705799521>I<120FEA3FC0127FA212FFA3 1380EA7F00123C0A0A77891C>I<15FE913807FF8091381F07C091387C01F0ECF0004948 13F8494813780107147C495A49C7FC167E133E137EA25BA2485AA2000315FEA25B000715 FCA2491301120FA34848EB03F8A44848EB07F0A448C7EA0FE0A316C0007E141F12FE1680 153FA2481500A2157EA25DA25D4813015D6C495A127C4A5A4A5A6C49C7FC143E6C5B380F C1F03803FFC0C648C8FC273F76BC2E>48 D<15031507150F151F151E153E157EEC01FEEC 03FC1407141FEB01FF90380FFBF8EB1FC3EB0E07130015F0A2140FA215E0A2141FA215C0 A2143FA21580A2147FA21500A25CA25CA21301A25CA21303A25CA21307A25CA2130FA25C A2131FA25CEB7FE0B612F0A215E0203D77BC2E>I<15FE913803FFC091380F01F091383C 00F84A137C4A7F4948133F49487F4A148049C7FC5BEB0E0C011E15C0EB1C0EEB3C061338 13781370020E133FD9F00C148013E0141C0218137F00011600EBC0384A13FEEC600102E0 5B3A00E3C003F89039FF0007F0013C495A90C7485A5E037FC7FC15FC4A5A4A5AEC0FC04A C8FC147E14F8EB03E0495A011FC9FC133E49141801F0143C48481438485A1678485A48C8 5A120E001E4A5AD83FE0130301FF495A397C3FF01FD8780FB55AD8700391C7FCD8F0015B 486C6C5A6E5AEC07C02A3F79BC2E>II<1638167E16FE16FCA3150116F8A3150316F0A21507 16E0A2ED0FC0A3ED1F80A216005DA2157EA2157C15FC5D14015D14035D4A5AA24A5AA24A C7FC143EED038091387C0FC014F8ECF01F01011480EB03E014C0903807803F010F1400EB 1F00133E495B49137E485A485A484813FE48B46C5A4813F04813FE267C00FF130800F090 380FFFFC00601301C714E0913803F8005DA314075DA3140F5DA3141F5DA3020EC7FC274F 7DBC2E>I<02C0EB018002F0130FD901FEEB7F0091B512FE5E5E4914E016804BC7FCECBF F8D90780C8FC91C9FCA35B130EA3131E131CA3133C9038381FC0ECFFF090383BE07C9038 7F003E017E133F017C7F0178805B498090C7FCA6153FA4001F147F486C5C487EA24913FF 00FF92C7FC90C7FC48495A12E04A5A5D6C495A140F00705C0078495A6C495A003E01FEC8 FC381F03FC380FFFF0000313C0C648C9FC293F77BC2E>I<15FF020713C091381F81E091 383E00F002FC13F84948137C495A4948137E010F143E495A133F4A133F017F147F91C7FC 5BA2485AA216FF12035B16FE150112075B1503A216FC491307A20003140F16F8151F1201 6D133F0000EC7FF015EF90387C01CF90393E079FE090380FFE1FD903F813C090C7123FA2 1680157F160015FEA24A5A001C5C007F1303485C4A5A4A5A4A5A4849C7FC00F8137E00E0 5B6C485A387C07E0383FFFC06C90C8FCEA03F8283F77BC2E>57 D<171C173C177CA217FC A216011603A21607A24C7EA2161DA216391679167116E1A2ED01C1A2ED03811507160115 0EA2031C7FA24B7EA25D15F05D4A5AA24A5AA24AC7FC5C140E5C021FB6FC4A81A20270C7 127FA25C13015C495AA249C8FCA2130E131E131C133C5B01F882487ED807FEEC01FFB500 E0017FEBFF80A25C39417BC044>65 D<9339FF8001C0030F13E0033F9038F803809239FF 807E07913A03FC001F0FDA0FF0EB071FDA1FC0ECBF00DA7F806DB4FC4AC77E495AD903F8 6E5A495A130F4948157E4948157C495A13FF91C9FC4848167812035B1207491670120FA2 485A95C7FC485AA3127F5BA312FF5BA490CCFCA2170FA2170EA2171E171C173C17381778 6C16706D15F04C5A003F5E6D1403001F4B5A6D4AC8FC000F151E6C6C5C6C6C14F86C6C49 5A6C6CEB07C090397FC03F8090261FFFFEC9FC010713F0010013803A4272BF41>67 D<49B712C018F818FE903B0003FE0003FF9438007F804BEC1FC0F00FE0F007F014074BEC 03F8F001FCA2140F4BEC00FEA3141F4B15FFA3143F5DA3027F5D5DA219FE14FF92C81203 A34917FC4A1507A219F813034A150F19F0A20107EE1FE05CF03FC0A2010FEE7F804A1600 6060011F4B5A4A4A5A4D5AA2013F4B5A4AEC3FC04DC7FC017F15FEEE03FC4AEB0FF001FF EC7FE0B8128004FCC8FC16E0403E7BBD45>I<49B812F8A390260003FEC7121F18074B14 031801F000F014075DA3140F5D19E0A2141F4B1338A2EF7801023F027013C04B91C7FCA2 17F0027F5CED80011603160F91B65AA3ED001F49EC07805CA3010392C8FC5CF003804C13 070107020E14005C93C75A180E010F161E4A151C183CA2011F5E5C60A2013F15014A4A5A 1707017F150F4D5A4A147F01FF913807FF80B9FCA295C7FC3D3E7BBD3E>I<49B812F0A3 90260003FEC7123F180F4B1403A2F001E014075DA3140F5D19C0A2141F5D1770EFF00302 3F02E013804B91C7FCA21601027F5CED8003A2160702FFEB1F8092B5FCA349D9003FC8FC 4A7F82A20103140E5CA2161E0107141C5CA293C9FC130F5CA3131F5CA3133F5CA2137FA2 5C497EB612E0A33C3E7BBD3B>I<49B6FC5BA2D9000313005D5DA314075DA3140F5DA314 1F5DA3143F5DA3147F5DA314FF92C7FCA35B5CA313035CA313075CA3130F5CA3131F5CA3 133F5CA2137FA25C497EB67EA3283E7BBD23>73 D<4AB61280A2180091C713C0167F5FA2 16FF94C7FCA35D5EA315035EA315075EA3150F5EA3151F5EA3153F5EA3157FA25EA215FF A293C8FCA25CA25DA2380F8003EA3FC0D87FE05BA21407D8FFC05B140F01805B49485A12 FC0070495A4A5A6C01FEC9FC383C01FC380F07F03807FFC0C648CAFC314079BD30>I<49 B612C0A25FD9000390C8FC5D5DA314075DA3140F5DA3141F5DA3143F5DA3147F5DA314FF 92C9FCA35B5CA313035C18C0EF01E0010716C05C17031880130F4A140718005F131F4A14 1EA2173E013F5D4A14FC1601017F4A5A16074A131F01FFECFFF0B8FCA25F333E7BBD39> 76 D<49B5933807FFFC496062D90003F0FC00505ADBBF805E1A771AEF1407033F923801 CFE0A2F1039F020FEE071F020E606F6C140E1A3F021E161C021C04385BA2F1707F143C02 3804E090C7FCF001C0629126780FE0495A02705FF00700F00E0114F002E0031C5BA2F038 03010116704A6C6C5D18E019070103ED01C00280DA03805BA2943807000F13070200020E 5C5FDB03F8141F495D010E4B5CA24D133F131E011CDAF9C05CEEFB80197F013C6DB4C7FC 013895C8FC5E01784A5C13F8486C4A5CD807FE4C7EB500F04948B512FE16E01500563E7B BD52>I<902601FFFE020FB5FC496D5CA2D900016D010013C04AEE3F00193E70141C193C EC07BFDB3FE01438151F1978020F7FDA0E0F15708219F0EC1E07021C6D5CA20303140102 3C7FDA38015DA2701303EC7800027002805BA2047F130702F014C04A013F91C7FCA2715A 0101141F4AECF00EA2040F131E010315F84A151C1607EFFC3C0107140391C7143817FE04 0113784915FF010E16708218F0131E011C6F5AA2173F133C01385E171F137813F8486C6F 5AEA07FEB500F01407A295C8FC483E7BBD44>I<49B77E18F018FC903B0003FE0003FEEF 00FF4BEC7F80F03FC00207151F19E05DA2020F16F0A25DA2141FF03FE05DA2023F16C018 7F4B1580A2027FEDFF00604B495A4D5A02FF4A5A4D5A92C7EA3FC04CB4C7FC4990B512FC 17E04ACAFCA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA25C49 7EB67EA33C3E7BBD3E>80 D<49B612FCEFFF8018F0903B0003FE000FF8EF03FE4BEB00FF 8419800207ED3FC05DA219E0140F5DA3021FED7FC05DA2F0FF80143F4B15004D5A60027F 4A5A4B495A4D5AEF3F8002FF02FEC7FC92380007F892B512E01780499038000FE04A6D7E 707E707E0103814A130083A213075CA25E130F5C5F1603131F5CA3013F020714404A16E0 5F017F160119C04A01031303496C1680B6D8800113079438FE0F009338007E1ECAEA3FFC EF07F03B407BBD42>82 D<92390FF001C0ED7FFE4AB5EA0380913907F80FC791390FC003 EF91391F8001FF4AC71300027E805C495A4948143EA2495AA2010F153C5CA3011F1538A3 8094C7FC80A214FC6DB4FC15F015FE6DEBFFC06D14F06D14FC6D80143F020F7F020180EC 001F150303007F167F163FA2161FA212075A5F120EA2001E153F94C7FCA2163E003E157E 167C003F15FC4B5A486C5C4B5A6D495AD87DE0EB1F80D8F8F849C8FC017F13FE39F03FFF F8D8E00F13E048C690C9FC32427ABF33>I<48B9FCA25A903AFE001FF00101F89138E000 7FD807E0163E49013F141E5B48C75BA2001E147FA2001C4B131C123C003814FFA2007892 C7FC12704A153C00F01738485CC716001403A25DA21407A25DA2140FA25DA2141FA25DA2 143FA25DA2147FA25DA214FFA292C9FCA25BA25CA21303A25CEB0FFE003FB67E5AA2383D 71BC41>I<147E49B47E903907C1C38090391F80EFC090383F00FF017E137F4914804848 133F485AA248481400120F5B001F5C157E485AA215FE007F5C90C7FCA21401485C5AA214 03EDF0385AA21407EDE078020F1370127C021F13F0007E013F13E0003E137FECF3E1261F 01E313C03A0F8781E3803A03FF00FF00D800FC133E252977A72E>97 DIIII<167C 4BB4FC923807C78092380F83C0ED1F87161FED3F3FA2157EA21780EE0E004BC7FCA41401 5DA414035DA30103B512F8A390260007E0C7FCA3140F5DA5141F5DA4143F92C8FCA45C14 7EA414FE5CA413015CA4495AA4495AA4495A121E127F5C12FF49C9FCA2EAFE1EEAF83C12 70EA7878EA3FE0EA0F802A5383BF1C>III<1478EB01FCA21303A314F8EB00E01400AD137C48B4FC38038F 80EA0707000E13C0121E121CEA3C0F1238A2EA781F00701380A2EAF03F140012005B137E 13FE5BA212015BA212035B1438120713E0000F1378EBC070A214F0EB80E0A2EB81C01383 148038078700EA03FEEA00F8163E79BC1C>I107 DIIII<903903E001F890390F F807FE903A1E7C1E0F80903A1C3E3C07C0013C137801389038E003E0EB783F017001C013 F0ED80019038F07F0001E015F8147E1603000113FEA2C75AA20101140717F05CA2010314 0F17E05CA20107EC1FC0A24A1480163F010F15005E167E5E131F4B5A6E485A4B5A90393F B80F80DA9C1FC7FCEC0FFCEC03E049C9FCA2137EA213FEA25BA21201A25BA21203A2387F FFE0B5FCA22D3A80A72E>I114 DII<137C48B4 141C26038F80137EEA0707000E7F001E15FE121CD83C0F5C12381501EA781F007001805B A2D8F03F1303140000005D5B017E1307A201FE5C5B150F1201495CA2151F0003EDC1C049 1481A2153F1683EE0380A2ED7F07000102FF13005C01F8EBDF0F00009038079F0E90397C 0F0F1C90391FFC07F8903907F001F02A2979A731>I<017CEB01C048B4EB07F038038F80 EA0707000E01C013F8121E001C1403EA3C0F0038EC01F0A2D8781F130000705BA2EAF03F 91C712E012005B017E130116C013FE5B1503000115805BA2ED07001203495B150EA25DA2 5D1578000114706D5B0000495A6D485AD97E0FC7FCEB1FFEEB03F0252979A72A>I<017C 167048B491387001FC3A038F8001F8EA0707000E01C015FE001E1403001CEDF000EA3C0F 0038177C1507D8781F4A133C00701380A2D8F03F130F020049133812005B017E011F1478 4C137013FE5B033F14F0000192C712E05BA2170100034A14C049137E17031880A2EF0700 15FE170E00010101141E01F86D131C0000D9039F5BD9FC076D5A903A3E0F07C1E0903A1F FC03FFC0902703F0007FC7FC372979A73C>I<903903F001F890390FFC07FE90393C1E0E 0F9026780F1C138001F0EBB83FD801E013F89039C007F07FEA0380000714E0D9000F1400 48151C000E4AC7FCA2001E131FA2C75BA2143F92C8FCA35C147EA314FE4A131CA3010114 3C001E1538003F491378D87F811470018314F000FF5D9039077801C039FE0F7C033A7C0E 3C078027783C1E1EC7FC391FF80FFC3907E003F029297CA72A>I<137C48B4143826038F 8013FCEA0707000E7F001E1401001C15F8EA3C0F12381503D8781F14F000701380A2D8F0 3F1307020013E012005B017E130F16C013FE5B151F1201491480A2153F000315005BA25D 157EA315FE5D00011301EBF8030000130790387C1FF8EB3FF9EB07E1EB00035DA2140700 0E5CEA3F80007F495AA24A5AD8FF0090C7FC143E007C137E00705B387801F0383803E038 1E0FC06CB4C8FCEA03F8263B79A72C>III E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmr8 8 14 /Fh 14 112 df10 D<13031307130E131C1338137013F0EA01E013C01203EA0780A2EA0F00A2121EA3 5AA45AA512F8A25AAB7EA21278A57EA47EA37EA2EA0780A2EA03C0120113E0EA00F01370 1338131C130E1307130310437AB11B>40 D<12C07E12707E7E7E120FEA0780120313C0EA 01E0A2EA00F0A21378A3133CA4131EA5131FA2130FAB131FA2131EA5133CA41378A313F0 A2EA01E0A2EA03C013801207EA0F00120E5A5A5A5A5A10437CB11B>I43 D48 D<130C133C137CEA03FC12FFEAFC7C1200B3B113FE387FFFFEA2172C7AAB23>III<140EA2141E143EA2147E14FEA2EB01BE1303143E13 06130E130C131813381330136013E013C0EA0180120313001206120E120C5A123812305A 12E0B612FCA2C7EA3E00A9147F90381FFFFCA21E2D7EAC23>I56 DI<013F13F89038FFC3FE3903E1FF1E3807807C000F 140C391F003E00A2003E7FA76C133EA26C6C5A00071378380FE1F0380CFFC0D81C3FC7FC 90C8FCA3121E121F380FFFF814FF6C14C04814F0391E0007F848130048147C12F848143C A46C147C007C14F86CEB01F06CEB03E03907E01F803901FFFE0038003FF01F2D7E9D23> 103 D108 D111 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmbx12 12 42 /Fi 42 123 df44 D46 D49 DII<163FA25E5E 5D5DA25D5D5D5DA25D92B5FCEC01F7EC03E7140715C7EC0F87EC1F07143E147E147C14F8 EB01F0EB03E0130714C0EB0F80EB1F00133E5BA25B485A485A485A120F5B48C7FC123E5A 12FCB91280A5C8000F90C7FCAC027FB61280A531417DC038>I<0007150301E0143F01FF EB07FF91B6FC5E5E5E5E5E16804BC7FC5D15E092C8FC01C0C9FCAAEC3FF001C1B5FC01C7 14C001DF14F09039FFE03FFC9138000FFE01FC6D7E01F06D13804915C0497F6C4815E0C8 FC6F13F0A317F8A4EA0F80EA3FE0487E12FF7FA317F05B5D6C4815E05B007EC74813C012 3E003F4A1380D81FC0491300D80FF0495AD807FEEBFFFC6CB612F0C65D013F1480010F01 FCC7FC010113C02D427BC038>I<4AB47E021F13F0027F13FC49B6FC01079038807F8090 390FFC001FD93FF014C04948137F4948EBFFE048495A5A1400485A120FA248486D13C0EE 7F80EE1E00003F92C7FCA25B127FA2EC07FC91381FFF8000FF017F13E091B512F89039F9 F01FFC9039FBC007FE9039FF8003FF17804A6C13C05B6F13E0A24915F0A317F85BA4127F A5123FA217F07F121FA2000F4A13E0A26C6C15C06D4913806C018014006C6D485A6C9038 E01FFC6DB55A011F5C010714C0010191C7FC9038003FF02D427BC038>I<903807FFC001 3F13FC48B612804815E0260FF80013F0D81FC0EB3FF848C7EA1FFC4815FE01C0130F486C 14FF7FA66C485B6C4814FE000FC7FCC8EA3FFCED7FF8EDFFF04A13E04A13801600EC07FC 4A5A5D4A5A5D4A5A92C7FCA2147E147CA31478AA91C8FCA814F8EB03FE497E497FA2497F A56D5BA26D90C7FC6D5AEB00F828467AC535>63 D65 D67 DIII72 DI78 D80 D82 DI<003FBA12E0A59026FE000FEB8003D87FE09338003FF049171F90C71607A2007E1803 007C1801A300781800A400F819F8481978A5C81700B3B3A20107B8FCA545437CC24E>I< 903801FFE0011F13FE017F6D7E48B612E03A03FE007FF84848EB1FFC6D6D7E486C6D7EA2 6F7FA36F7F6C5A6C5AEA00F090C7FCA40203B5FC91B6FC1307013F13F19038FFFC010003 13E0000F1380381FFE00485A5B127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE013EEB FFC03A1FFF80FC7F0007EBFFF86CECE01FC66CEB8007D90FFCC9FC322F7DAD36>97 DIIIIIII<137C48 B4FC4813804813C0A24813E0A56C13C0A26C13806C1300EA007C90C7FCAAEB7FC0EA7FFF A512037EB3AFB6FCA518467CC520>I108 D<90277F8007FEEC0FFCB590263FFFC090387FFF8092B5D8F001B512E00281 6E4880913D87F01FFC0FE03FF8913D8FC00FFE1F801FFC0003D99F009026FF3E007F6C01 9E6D013C130F02BC5D02F86D496D7EA24A5D4A5DA34A5DB3A7B60081B60003B512FEA557 2D7CAC5E>I<90397F8007FEB590383FFF8092B512E0028114F8913987F03FFC91388F80 1F000390399F000FFE6C139E14BC02F86D7E5CA25CA35CB3A7B60083B512FEA5372D7CAC 3E>II<90397FC00FF8B590 B57E02C314E002CF14F89139DFC03FFC9139FF001FFE000301FCEB07FF6C496D13804A15 C04A6D13E05C7013F0A2EF7FF8A4EF3FFCACEF7FF8A318F017FFA24C13E06E15C06E5B6E 4913806E4913006E495A9139DFC07FFC02CFB512F002C314C002C091C7FCED1FF092C9FC ADB67EA536407DAC3E>I<90387F807FB53881FFE0028313F0028F13F8ED8FFC91389F1F FE000313BE6C13BC14F8A214F0ED0FFC9138E007F8ED01E092C7FCA35CB3A5B612E0A527 2D7DAC2E>114 D<90391FFC038090B51287000314FF120F381FF003383FC00049133F48 C7121F127E00FE140FA215077EA27F01E090C7FC13FE387FFFF014FF6C14C015F06C14FC 6C800003806C15806C7E010F14C0EB003F020313E0140000F0143FA26C141F150FA27EA2 6C15C06C141FA26DEB3F8001E0EB7F009038F803FE90B55A00FC5CD8F03F13E026E007FE C7FC232F7CAD2C>IIII121 D<001FB71280A49026FC001F130001E0495A5B49495A90C7485A 48495B123E4A5B4A5B003C495BA24A90C7FC4A5A4A5AC7FC4A5A495B495BA2495B499038 800780491300A2495A4948130F49481400A2485B48495B485BA248495B4890C75A48485C 15034848EB1FFEB7FCA4292C7DAB32>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmmi8 8 17 /Fj 17 121 df15 D<123C127E12FFA4127E123C08087A8714>58 D<1670A216F01501A24B7EA2150715 0DA2151915391531ED61FC156015C0EC0180A2EC03005C14064A7F167E5C5CA25C14E05C 4948137F91B6FC5B0106C7123FA25B131C1318491580161F5B5B120112031207000FED3F C0D8FFF8903807FFFEA22F2F7DAE35>65 D79 D97 D<131FEA03FFA2EA003FA2133EA2137EA2137C A213FCA25BA21201143F9038F1FFC09038F3C1F03803FF0001FC7F5BA2485A5BA25B000F 13015D1380A2001F13035D1300140748ECC04016C0003E130F1580007E148191381F0180 007C1403ED070000FCEB0F06151E48EB07F80070EB01E0222F7DAD29>104 D<1307EB0F80EB1FC0A2EB0F80EB070090C7FCA9EA01E0EA07F8EA0E3CEA1C3E12381230 1270EA607EEAE07C12C013FC485A120012015B12035BA21207EBC04014C0120F13801381 381F01801303EB0700EA0F06131EEA07F8EA01F0122E7EAC18>I<15E0EC01F01403A3EC 01C091C7FCA9147CEB03FE9038078F80EB0E07131C013813C01330EB700F0160138013E0 13C0EB801F13001500A25CA2143EA2147EA2147CA214FCA25CA21301A25CA21303A25CA2 130700385BEAFC0F5C49C7FCEAF83EEAF0F8EA7FF0EA1F801C3B81AC1D>I<131FEA03FF A2EA003FA2133EA2137EA2137CA213FCA25BA2120115F89038F003FCEC0F0E0003EB1C1E EC387EEBE07014E03807E1C09038E3803849C7FC13CEEA0FDC13F8A2EBFF80381F9FE0EB 83F0EB01F81300481404150C123EA2007E141C1518007CEBF038ECF83000FC1470EC78E0 48EB3FC00070EB0F801F2F7DAD25>I<27078007F0137E3C1FE01FFC03FF803C18F0781F 0783E03B3878E00F1E01263079C001B87F26707F8013B00060010013F001FE14E000E015 C0485A4914800081021F130300015F491400A200034A13076049133E170F0007027EEC80 80188149017C131F1801000F02FCEB3F03053E130049495C180E001F0101EC1E0C183C01 0049EB0FF0000E6D48EB03E0391F7E9D3E>109 D<3907C007E0391FE03FF83918F8783E 393879E01E39307B801F38707F00126013FEEAE0FC12C05B00815C0001143E5BA2000314 7E157C5B15FC0007ECF8081618EBC00115F0000F1538913803E0300180147016E0001F01 0113C015E390C7EAFF00000E143E251F7E9D2B>II<90387C01F89038FE07FE3901CF8E0F3A03879C0780D907B813 C0000713F000069038E003E0EB0FC0000E1380120CA2D8081F130712001400A249130F16 C0133EA2017EEB1F80A2017C14005D01FC133E5D15FC6D485A3901FF03E09038FB87C0D9 F1FFC7FCEBF0FC000390C8FCA25BA21207A25BA2120FA2EAFFFCA2232B829D24>I<3807 C01F390FF07FC0391CF8E0E0383879C138307B8738707F07EA607E13FC00E0EB03804848 C7FCA2128112015BA21203A25BA21207A25BA2120FA25BA2121FA290C8FC120E1B1F7E9D 20>114 DI<130E131FA25BA213 3EA2137EA2137CA213FCA2B512F8A23801F800A25BA21203A25BA21207A25BA2120FA25B A2001F1310143013001470146014E0381E01C0EB0380381F0700EA0F0EEA07FCEA01F015 2B7EA919>I<013F137C9038FFC1FF3A01C1E383803A0380F703C0390700F60F000E13FE 4813FC12180038EC0700003049C7FCA2EA200100005BA313035CA301075B5D14C000385C D87C0F130600FC140E011F130C011B131C39F03BE038D8707113F0393FE0FFC0260F803F C7FC221F7E9D28>120 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmbx10 10.95 52 /Fk 52 123 df40 D<127012F8127C7EEA3F806C7E6C7E12076C7E7F6C7E6C 7EA2137F80133F806D7EA280130FA280130780A36D7EA4807FA51580B01500A55B5CA449 5AA35C130F5CA2131F5CA2495A5C137F91C7FC13FEA2485A485A5B485A120F485A485A00 3EC8FC5A5A1270195A7AC329>I45 DI<140F143F5C495A130F48B5 FCB6FCA313F7EAFE071200B3B3A8B712F0A5243C78BB34>49 D<903803FF80013F13F890 B512FE00036E7E4881260FF80F7F261FC0037F4848C67F486C6D7E6D6D7E487E6D6D7EA2 6F1380A46C5A6C5A6C5A0007C7FCC8FC4B1300A25E153F5E4B5AA24B5A5E4A5B4A5B4A48 C7FC5D4A5AEC1FE04A5A4A5A9139FF000F80EB01FC495A4948EB1F00495AEB1F8049C7FC 017E5C5B48B7FC485D5A5A5A5A5AB7FC5EA4293C7BBB34>I<903801FFE0010F13FE013F 6D7E90B612E04801817F3A03FC007FF8D807F06D7E82D80FFC131F6D80121F7FA56C5A5E 6C48133FD801F05CC8FC4B5A5E4B5A4A5B020F5B902607FFFEC7FC15F815FEEDFFC0D900 0113F06E6C7E6F7E6F7E6F7E1780A26F13C0A217E0EA0FC0487E487E487E487EA317C0A2 5D491580127F49491300D83FC0495A6C6C495A3A0FFE01FFF86CB65A6C5DC61580013F49 C7FC010313E02B3D7CBB34>II<00071538D80FE0EB01F801FE133F90B6FC5E5E5E5E93C7FC5D15F85D15C04AC8FC 0180C9FCA9ECFFC0018713FC019F13FF90B67E020113E09039F8007FF0496D7E01C06D7E 5B6CC77FC8120F82A31780A21207EA1FC0487E487E12FF7FA21700A25B4B5A6C5A01805C 6CC7123F6D495AD81FE0495A260FFC075B6CB65A6C92C7FCC614FC013F13F0010790C8FC 293D7BBB34>II<121F7F13F8 90B712F0A45A17E017C0178017005E5E5A007EC7EA01F84B5A007C4A5A4B5A4B5A93C7FC 485C157E5DC7485A4A5AA24A5A140F5D141F143F5D147FA214FF92C8FC5BA25BA3495AA3 130FA5131FAA6D5A6D5A6D5A2C3F7ABD34>I58 D<16FCA24B7EA24B7EA34B7FA24B7FA34B7FA24B7FA34B 7F157C03FC7FEDF87FA2020180EDF03F0203804B7E02078115C082020F814B7E021F8115 00824A81023E7F027E81027C7FA202FC814A147F49B77EA34982A2D907E0C7001F7F4A80 010F835C83011F8391C87E4983133E83017E83017C81B500FC91B612FCA5463F7CBE4F> 65 DI< 922607FFC0130E92B500FC131E020702FF133E023FEDC07E91B7EAE1FE01039138803FFB 499039F80003FF4901C01300013F90C8127F4948151FD9FFF8150F48491507485B4A1503 481701485B18004890CAFC197E5A5B193E127FA349170012FFAC127F7F193EA2123FA27F 6C187E197C6C7F19FC6C6D16F86C6D150119F06C6D15036C6DED07E0D97FFEED0FC06D6C ED3F80010F01C0ECFF006D01F8EB03FE6D9039FF801FFC010091B55A023F15E002071580 020002FCC7FC030713C03F407ABE4C>IIII73 D75 DIII80 D<903A03FFC001C0011FEBF803017FEBFE0748B6128F4815DF48010013FF D80FF8130F48481303497F4848EB007F127F49143F161F12FF160FA27F1607A27F7F01FC 91C7FCEBFF806C13F8ECFFC06C14FCEDFF806C15E016F86C816C816C816C16806C6C15C0 7F010715E0EB007F020714F0EC003F1503030013F8167F163F127800F8151FA2160FA27E A217F07E161F6C16E06D143F01E015C001F8EC7F8001FEEB01FF9026FFE00713004890B5 5A486C14F8D8F81F5CD8F00314C027E0003FFEC7FC2D407ABE3A>83 D<003FB912FCA5903BFE003FFE003FD87FF0EE0FFE01C0160349160190C71500197E127E A2007C183EA400FC183F48181FA5C81600B3AF010FB712F8A5403D7CBC49>I86 DI<007FB6013FB512F0A5D8001F01C0D9003FC7FC6D6D147E18 FE6D6D5C6D6D495A6D4B5A6F13076D6D5C6E6C495A4D5A6EEB803F6E01C090C8FC6E147E 705A6E13F16EEBF9F86EEBFBF0EEFFE0806F5B5F816F7F81836F7F81834B7F4B7F5D83DB 3F3F7FED7E1F03FE804B6C7F4A486C7F4A487E0207814B6C7F4A487E4A4880023F6E7E92 C76C7F027E804A8201016F7F4A6E7F495A49486E7F010F6F7F4A80B600C0017F90B5FCA5 483E7DBD4F>I<903807FFC0013F13F848B6FC48812607FE037F260FF8007F6DEB3FF048 6C806F7EA36F7EA26C5A6C5AEA01E0C8FC153F91B5FC130F137F3901FFFE0F4813E0000F 1380381FFE00485A5B485A12FF5BA4151F7F007F143F6D90387BFF806C6C01FB13FE391F FF07F36CEBFFE100031480C6EC003FD91FF890C7FC2F2B7DA933>97 D<13FFB5FCA512077EAFEDFFE0020713FC021FEBFF80027F80DAFF8113F09139FC003FF8 02F06D7E4A6D7E4A13074A80701380A218C082A318E0AA18C0A25E1880A218005E6E5C6E 495A6E495A02FCEB7FF0903AFCFF01FFE0496CB55AD9F01F91C7FCD9E00713FCC7000113 C033407DBE3A>IIIII<903A03FF8007F0 013F9038F83FF8499038FCFFFC48B712FE48018313F93A07FC007FC34848EB3FE1001FED F1FC4990381FF0F81700003F81A7001F5DA26D133F000F5D6C6C495A3A03FF83FF8091B5 C7FC4814FC01BF5BD80F03138090CAFCA2487EA27F13F06CB6FC16F016FC6C15FF17806C 16C06C16E01207001F16F0393FE000034848EB003F49EC1FF800FF150F90C81207A56C6C EC0FF06D141F003F16E001F0147FD81FFC903801FFC02707FF800F13006C90B55AC615F8 013F14E0010101FCC7FC2F3D7DA834>I<13FFB5FCA512077EAFED1FF8EDFFFE02036D7E 4A80DA0FE07F91381F007F023C805C4A6D7E5CA25CA35CB3A4B5D8FE0FB512E0A5333F7C BE3A>II<13FFB5FCA512077EB092380FFFFEA5DB01FEC7FC4B5A ED07F0ED1FE04B5A4B5A4BC8FCEC03FC4A5A4A5A141FEC7FF84A7EA2818102E77F02C37F 148102007F826F7E6F7E151F6F7E826F7F6F7F816F7FB5D8FC07EBFFC0A5323F7DBE37> 107 D<13FFB5FCA512077EB3B3AFB512FCA5163F7CBE1D>I<01FFD91FF8ECFFC0B590B5 010713F80203DAC01F13FE4A6E487FDA0FE09026F07F077F91261F003FEBF8010007013E DAF9F0806C0178ECFBC04A6DB4486C7FA24A92C7FC4A5CA34A5CB3A4B5D8FE07B5D8F03F EBFF80A551297CA858>I<01FFEB1FF8B5EBFFFE02036D7E4A80DA0FE07F91381F007F00 07013C806C5B4A6D7E5CA25CA35CB3A4B5D8FE0FB512E0A533297CA83A>II<01FFEBFFE0B5000713FC021FEBFF80027F80DA FF8113F09139FC007FF8000701F06D7E6C496D7E4A130F4A6D7E1880A27013C0A38218E0 AA4C13C0A318805E18005E6E5C6E495A6E495A02FCEBFFF0DAFF035B92B55A029F91C7FC 028713FC028113C00280C9FCACB512FEA5333B7DA83A>I<3901FE01FE00FF903807FF80 4A13E04A13F0EC3F1F91387C3FF8000713F8000313F0EBFFE0A29138C01FF0ED0FE09138 8007C092C7FCA391C8FCB3A2B6FCA525297DA82B>114 D<90383FFC1E48B512BE000714 FE5A381FF00F383F800148C7FC007E147EA200FE143EA27E7F6D90C7FC13F8EBFFE06C13 FF15C06C14F06C806C806C806C80C61580131F1300020713C014000078147F00F8143F15 1F7EA27E16806C143F6D140001E013FF9038F803FE90B55A15F0D8F87F13C026E00FFEC7 FC222B7DA929>IIIII121 D<003FB612F8A4D9F80113F001C014E0495A494813C04A1380007E15005C4A5A007C5C14 7F4A5A495B5DC65A495B495BA249EB007C495A5C137F494813FC484913F85C5A48EBC001 14804814034813004848130749131F007FECFFF0B7FCA426287DA72E>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmmi10 10.95 26 /Fl 26 121 df<1678A21670A216F0A25EA21501A25EA21503A25EA21507A293C7FCA25D A2150EEDFFC0020F13FC91383F9E3F903A01F81C0FC0D903E0EB03E0903A0FC03C01F0D9 1F00EB00F8017E0138137C5B48480178133E485A48480170133F120F4901F0131F485A5D 48C7FC0201143F5A007E5CA20203147F00FE167E485C17FE020714FC1601007C020013F8 EE03F0007E49EB07E0A2003E010EEB0FC0003FED1F806C011EEB3F00D80F80147C3A07C0 1C01F8D803E0EB03E03A01F03C1F80D8007E01FEC7FC90381FFFF801011380D90078C8FC A21470A214F0A25CA21301A25CA21303A25CA21307A230527CBE36>30 D<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A798919>58 D<121EEA7F8012FF13C0A2 13E0A3127FEA1E601200A413E013C0A312011380120313005A120E5A1218123812300B1C 798919>I<180E183F18FFEF03FEEF0FF8EF3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF 80DB03FEC7FCED1FF8ED7FE0913801FF80DA07FEC8FCEC1FF0EC7FC04948C9FCEB07FCEB 1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFCA2EA7FC0EA1FF0EA07FCEA01FF3800 7FC0EB1FF0EB07FCEB01FF9038007FC0EC1FF0EC07FE913801FF809138007FE0ED1FF8ED 03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FEEF00FF183F18 0E383679B147>I<17075F84171FA2173F177FA217FFA25E5EA24C6C7EA2EE0E3F161E16 1C1638A21670A216E0ED01C084ED0380171FED07005D150E5DA25D157815705D844A5A17 0F4A5A4AC7FC92B6FC5CA2021CC7120F143C14384A81A24A140713015C495AA249C8FC5B 130E131E4982137C13FED807FFED1FFEB500F00107B512FCA219F83E417DC044>65 D<49B712F818FF19E090260001FEC7EA3FF0F007F84B6E7E727E850203815D1A80A20207 167F4B15FFA3020F17004B5C611803021F5E4B4A5A180FF01FE0023F4B5A4B4A5ADD01FE C7FCEF07F8027FEC7FE092B6C8FC18E092C7EA07F84AEC01FE4A6E7E727E727E13014A82 181FA213034A82A301075F4A153FA261010F167F4A5E18FF4D90C7FC011F5E4A14034D5A 013FED1FF04D5A4AECFFC0017F020790C8FCB812FC17F094C9FC413E7DBD45>I<49B9FC A3D9000190C7120718004B157F193F191E14035DA314075D191CA2140F5D17074D133C02 1F020E13384B1500A2171E023F141C4B133C177C17FC027FEB03F892B5FCA39139FF8003 F0ED00011600A2495D5CA2160101035D5CA293C9FC13075CA3130F5CA3131F5CA2133FA2 5C497EB612F8A3403E7DBD3A>70 DI<49B612F0A3D900010180C7FC93C8FC5DA314035DA314075DA3 140F5DA3141F5DA3143F5DA3147F5DA314FF92C9FCA35B5C180C181E0103161C5C183C18 3813074A1578187018F0130F4AEC01E0A21703011FED07C04A140F171F013FED3F8017FF 4A1303017F021F1300B9FCA25F373E7DBD3E>76 D<49B56C93383FFFF05113E098B5FCD9 0001F1E000704B5B03DF933803BF80A2F2077F1403039F040E90C7FC1A1CDB8FE05E0207 5F030F4C5AA21AE1020FEE01C1020E606F6CEC03811A83021EEE0703021C040E5BA2F11C 07023C16380238606F6C1470F1E00F14780270DB01C05BA2953803801F02F0ED07004A6C 6C5E180E4E133F130102C04B5C601A7F01036D6C5B4A95C8FC4D5A4D485B130791C749C7 5A170E047F1401495D010E4B5CA24D1303131E011C4B5C5F013C023F1407017C5D01FE92 C75BD803FF4D7EB500FC013E011FB512F8163C041C5E5C3E7DBD58>I79 D97 D<163EEEFFC0923803E1E0923807C0F0ED0F811687ED1F8F160F153FA2 17E092387E038093C7FCA45DA514015DA30103B512FCA390260003F0C7FCA314075DA414 0F5DA5141F5DA4143F92C8FCA45C147EA414FE5CA413015CA4495AA35CEA1E07127F5C12 FF495AA200FE90C9FCEAF81EEA703EEA7878EA1FF0EA07C02C537CBF2D>102 DII< 143C14FEA21301A314FCEB00701400AD137E3801FF803803C7C0EA0703000F13E0120E12 1C13071238A2EA780F007013C0A2EAF01F14801200133F14005B137EA213FE5BA212015B 0003130E13F0A20007131EEBE01CA2143CEBC0381478147014E013C13803E3C03801FF00 EA007C173E7EBC1F>III109 DII114 DI<147014FC1301A25CA21303A25CA21307A2 5CA2130FA25CA2007FB512F0B6FC15E039001F8000133FA291C7FCA25BA2137EA213FEA2 5BA21201A25BA21203A25BA21207EC01C013E01403000F1480A2EBC0071500140E141E5C 000713385C3803E1E03801FF80D8003EC7FC1C3A7EB821>I<017CEE038048B40207EB0F E02603C7C090391F801FF0EA0703000F7F000E153F001C16000107160F003817074C1303 D8780F027E130100705B1800D8F01F14FE4A4914E01200133FDA000114014C14C05B137E 0303140301FE4A14805BA2F0070000011407494A5B180EA260A2030F5C12006D011F5C01 7C496C5B017E0139495A6D903870F80390281F81E07C0FC7FC903A07FFC01FFE01009038 0007F03C297EA741>119 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmr9 9 40 /Fm 40 122 df<123C127EB4FCA21380A2127F123D1201A412031300A25A1206120E120C 121C5A5A126009177A8715>44 D<123C127E12FFA4127E123C08087A8715>46 D<1530157815F8A215F01401A215E01403A215C01407A21580140FA215005CA2143EA214 3C147CA2147814F8A25C1301A25C1303A25C1307A2495AA291C7FC5BA2131E133EA2133C 137CA2137813F8A25B1201A25B1203A2485AA25B120FA290C8FC5AA2121E123EA2123C12 7CA2127812F8A25A12601D4B7CB726>II<13075B5B137FEA07FFB5FC13BFEAF83F1200B3B3A2497E007FB51280A3 19327AB126>III<123C127E12FFA412 7E123C1200B0123C127E12FFA4127E123C08207A9F15>58 D<15E0A34A7EA24A7EA34A7E A3EC0DFE140CA2EC187FA34A6C7EA202707FEC601FA202E07FECC00FA2D901807F1507A2 49486C7EA301066D7EA2010E80010FB5FCA249800118C77EA24981163FA2496E7EA3496E 7EA20001821607487ED81FF04A7ED8FFFE49B512E0A333367DB53A>65 DIII73 D77 D<90381FE00390387FFC 0748B5FC3907F01FCF390F8003FF48C7FC003E80814880A200788000F880A46C80A27E92 C7FC127F13C0EA3FF013FF6C13F06C13FF6C14C06C14F0C680013F7F01037F9038003FFF 140302001380157F153FED1FC0150F12C0A21507A37EA26CEC0F80A26C15006C5C6C143E 6C147E01C05B39F1FC03F800E0B512E0011F138026C003FEC7FC22377CB42B>83 D<007FB712FEA390398007F001D87C00EC003E0078161E0070160EA20060160600E01607 A3481603A6C71500B3AB4A7E011FB512FCA330337DB237>I87 D 97 DII<153FEC0FFFA3EC007F81AEEB07F0EB3FFCEBFC0F3901F003 BF3907E001FF48487E48487F8148C7FCA25A127E12FEAA127E127FA27E6C6C5BA26C6C5B 6C6C4813803A03F007BFFC3900F81E3FEB3FFCD90FE0130026357DB32B>III<151F90391FC07F809039FFF8E3C03901F07FC73907E03F033A0FC01F 83809039800F8000001F80EB00074880A66C5CEB800F000F5CEBC01F6C6C48C7FCEBF07C 380EFFF8380C1FC0001CC9FCA3121EA2121F380FFFFEECFFC06C14F06C14FC4880381F00 01003EEB007F4880ED1F8048140FA56C141F007C15006C143E6C5C390FC001F83903F007 E0C6B51280D91FFCC7FC22337EA126>IIIIII<2703F01FE013FF00FF90267FF80313C0903BF1E07C0F 03E0903BF3803E1C01F02807F7003F387FD803FE1470496D486C7EA2495CA2495CB3486C 496C487EB53BC7FFFE3FFFF0A33C217EA041>I<3903F01FC000FFEB7FF09038F1E0FC90 38F3807C3907F7007EEA03FE497FA25BA25BB3486CEB7F80B538C7FFFCA326217EA02B> II<3903F03F8000FFEBFFE0 9038F3C0F89038F7007ED807FE7F6C48EB1F804914C049130F16E0ED07F0A3ED03F8A915 0716F0A216E0150F16C06D131F6DEB3F80160001FF13FC9038F381F89038F1FFE0D9F07F C7FC91C8FCAA487EB512C0A325307EA02B>I<3803E07C38FFE1FF9038E38F809038E71F C0EA07EEEA03ECA29038FC0F8049C7FCA35BB2487EB512E0A31A217FA01E>114 DI<1330A51370A313F0A21201 A212031207381FFFFEB5FCA23803F000AF1403A814073801F806A23800FC0EEB7E1CEB1F F8EB07E0182F7FAD1E>IIII<3A7FFF807FF8A33A07F8001FC00003EC0F80 0001EC070015066C6C5BA26D131C017E1318A26D5BA2EC8070011F1360ECC0E0010F5BA2 903807E180A214F3010390C7FC14FBEB01FEA26D5AA31478A21430A25CA214E05CA2495A 1278D8FC03C8FCA21306130EEA701CEA7838EA1FF0EA0FC025307F9F29>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmr6 6 5 /Fn 5 58 df<130C1338137013E0EA01C0EA038013005A120EA25AA25AA312781270A312 F0AB1270A312781238A37EA27EA27E7E1380EA01C0EA00E013701338130C0E317AA418> 40 D<12C012707E7E7E7E7E1380EA01C0A2EA00E0A21370A313781338A3133CAB1338A3 13781370A313E0A2EA01C0A2EA038013005A120E5A5A5A12C00E317CA418>I<13E01201 120712FF12F91201B3A7487EB512C0A212217AA01E>49 DI<13FE3803FFC0380781E0380E0070481378003C133848133CA200F8131EA3 141FA40078133FA26C137F121C380F01DF3807FF9F3803FE1EC7FCA2143E143C001C1338 003E13781470003C13E0381801C0381C0780380FFE00EA03F818227DA01E>57 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmr10 10 26 /Fo 26 123 df45 D<121C127FEAFF80A5EA7F00121C09097988 17>I87 D97 DIIII<147E903803FF8090380FC1E0EB1F8790383F0FF0137EA213 FCA23901F803C091C7FCADB512FCA3D801F8C7FCB3AB487E387FFFF8A31C3B7FBA19>I< ED03F090390FF00FF890393FFC3C3C9039F81F707C3901F00FE03903E007C03A07C003E0 10000FECF000A248486C7EA86C6C485AA200075C6C6C485A6D485A6D48C7FC38073FFC38 060FF0000EC9FCA4120FA213C06CB512C015F86C14FE6CECFF804815C03A0F80007FE048 C7EA0FF0003E140348140116F8481400A56C1401007C15F06CEC03E0003F1407D80F80EB 0F80D807E0EB3F003901FC01FC39007FFFF0010790C7FC26387EA52A>III108 D<2703F00FF0EB1FE000FFD93FFCEB7FF8 913AF03F01E07E903BF1C01F83803F3D0FF3800FC7001F802603F70013CE01FE14DC49D9 07F8EB0FC0A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA340257EA445>I< 3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F70013FE496D7EA25B A35BB3A3486C497EB500C1B51280A329257EA42E>II<3903F01FE000 FFEB7FF89038F1E07E9039F3801F803A0FF7000FC0D803FEEB07E049EB03F04914F84913 0116FC150016FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076DEB0FE001F614C090 39F7803F009038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328357EA42E>I<38 07E01F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE9038EC03E09038FC00 80491300A45BB3A2487EB512F0A31C257EA421>114 DI<1318A51338A31378A313F8120112031207 001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E13006D5AEB0FFEEB01 F81A347FB220>IIIIII<003FB512FCA2EB8003D83E0013F8003CEB07F00038EB0FE012 300070EB1FC0EC3F800060137F150014FE495AA2C6485A495AA2495A495A495AA290387F 000613FEA2485A485A0007140E5B4848130C4848131CA24848133C48C7127C48EB03FC90 B5FCA21F247EA325>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fp cmbx10 10 7 /Fp 7 117 df65 D97 D<13FFB5FCA412077EAF4AB47E020F13F0023F13FC9138FE03FFDAF000 13804AEB7FC00280EB3FE091C713F0EE1FF8A217FC160FA217FEAA17FCA3EE1FF8A217F0 6E133F6EEB7FE06E14C0903AFDF001FF80903AF8FC07FE009039F03FFFF8D9E00F13E0D9 C00390C7FC2F3A7EB935>I<903801FFC0010F13FC017F13FFD9FF8013802603FE0013C0 48485AEA0FF8121F13F0123F6E13804848EB7F00151C92C7FC12FFA9127FA27F123FED01 E06C7E15036C6CEB07C06C6C14806C6C131FC69038C07E006DB45A010F13F00101138023 257DA42A>I<9038FE03F000FFEB0FFEEC3FFF91387C7F809138F8FFC000075B6C6C5A5C A29138807F80ED3F00150C92C7FC91C8FCB3A2B512FEA422257EA427>114 D<90383FF0383903FFFEF8000F13FF381FC00F383F0003007E1301007C130012FC15787E 7E6D130013FCEBFFE06C13FCECFF806C14C06C14F06C14F81203C614FC131F9038007FFE 140700F0130114007E157E7E157C6C14FC6C14F8EB80019038F007F090B512C000F81400 38E01FF81F257DA426>I<130FA55BA45BA25B5BA25A1207001FEBFFE0B6FCA3000390C7 FCB21578A815F86CEB80F014816CEBC3E090383FFFC06D1380903803FE001D357EB425> I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fq cmr12 12 11 /Fq 11 120 df<143014F013011303131F13FFB5FC13E713071200B3B3B0497E497E007F B6FCA3204278C131>49 D70 D76 D97 D99 D101 D<3901FC01FE00FF903807FFC091381E07F091383801F8000701707F0003EBE0 002601FDC07F5C01FF147F91C7FCA25BA35BB3A8486CECFF80B5D8F83F13FEA32F2C7DAB 36>110 DI<3903F803F000FFEB1FFCEC3C 3EEC707F0007EBE0FF3803F9C000015B13FBEC007E153C01FF13005BA45BB3A748B4FCB5 12FEA3202C7DAB26>114 D<1306A5130EA4131EA3133E137EA213FE12011207001FB512 F0B6FCA2C648C7FCB3A4150CAA017E131C017F1318A26D133890381F8030ECC070903807 E0E0903801FFC09038007F001E3E7EBC26>116 D119 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fr cmr17 17.28 9 /Fr 9 123 df68 D97 D103 D<133C13FF487F487FA66C5B6C90C7FC133C90C8FCB3A2EB03C0EA07FF127FA41201EA00 7FA2133FB3B3AC497E497EB612E0A41B5F7DDE23>105 D108 D110 DI<1438A71478A414F8A31301A31303A21307130F131FA213 7F13FF1203000F90B6FCB8FCA3260007F8C8FCB3AE17E0AE6D6CEB01C0A316036D6C1480 16076D6C14006E6C5A91383FC01E91381FF07C6EB45A020313E09138007F802B597FD733 >116 D<001FB81280A391C70001130001F85C01E05D01804A5A160F90C8485A001E5E4C 5A48157F5F4C5A5D94C7FC00384A5A15074B5A5E4B5A153F5EC8485A15FF5E4A90C8FC5C 5D4A5A140F4A5A5D4A5A147F5D4A48EB03805B92C7FC495A13075C4948EC0700131F495A 5C495A13FF4A5C4890C8FC5A495D485A000F5E48485D4915FE48481401007F150749147F B8FCA3313E7DBD3A>122 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fs cmtt10 10.95 15 /Fs 15 120 df<120FEA3FC0EA7FE0A2EAFFF0A4EA7FE0A2EA3FC0EA0F000C0C6E8B30> 46 D64 D97 D99 D<49B4FC010713E0011F13F8017F7F 90B57E488048018113803A07FC007FC04848133FD81FE0EB1FE0150F484814F049130712 7F90C7FCED03F85A5AB7FCA516F048C9FC7E7EA27F003FEC01F06DEB03F86C7E6C7E6D13 07D807FEEB1FF03A03FFC07FE06C90B5FC6C15C0013F14806DEBFE00010713F8010013C0 252A7CA830>101 DI104 D106 D<02FC137E3B7FC3FF01FF80D8FF EF01877F90B500CF7F15DF92B57E6C010F13872607FE07EB03F801FC13FE9039F803FC01 A201F013F8A301E013F0B3A23C7FFE0FFF07FF80B548018F13C0A46C486C010713803228 81A730>109 DI<49B4FC010F13E0013F13F8497F90 B57E0003ECFF8014013A07FC007FC04848EB3FE0D81FE0EB0FF0A24848EB07F849130300 7F15FC90C71201A300FEEC00FEA86C14016C15FCA26D1303003F15F86D13076D130F6C6C EB1FF06C6CEB3FE06D137F3A07FF01FFC06C90B512806C15006C6C13FC6D5B010F13E001 0190C7FC272A7CA830>I114 D<90381FFC1E48B5129F000714FF5A5A5A38 7FF007EB800100FEC7FC4880A46C143E007F91C7FC13E06CB4FC6C13FC6CEBFF806C14E0 000114F86C6C7F01037F9038000FFF02001380007C147F00FEEC1FC0A2150F7EA27F151F 6DEB3F806D137F9039FC03FF0090B6FC5D5D00FC14F0D8F83F13C026780FFEC7FC222A79 A830>II<3B3FFFC01FFFE0486D4813F0B515F8A26C16F06C496C13E0D807E0 C7EA3F00A26D5C0003157EA56D14FE00015DEC0F80EC1FC0EC3FE0A33A00FC7FF1F8A214 7DA2ECFDF9017C5C14F8A3017E13FBA290393FF07FE0A3ECE03FA2011F5C90390F800F80 2D277FA630>119 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ft cmss10 10.95 11 /Ft 11 111 df70 D76 D78 D<4AB47E020F13F0027F13FE91B6FC01 0315C04981011F010013F8D93FF8EB1FFCD97FE0EB07FE4A130349486D7E4890C8138048 48ED7FC049153F4848ED1FE04848ED0FF0A24848ED07F8A2491503003F17FCA249150100 7F17FEA390CAFC4817FFAC6D5D007F17FEA46D1503003F17FCA26D1507001F17F86D150F 000F17F06D151F6C6CED3FE0A26C6CED7FC06C6CEDFF806C6D4913006E5BD97FF0EB0FFE 6D6C495A6DB4EBFFF8010790B512E06D5D010092C7FC6E5B020F13F00201138038437BC0 43>I82 D84 D87 D97 D<49B47E010F13F0013F13FC4913FF90B612805A48 1300D807FCEB1F00D80FF0130748487F4990C7FC123F5B127F90C9FCA312FEAA127FA36C 7EA26C6C14406DEB01C06C6C13036C6C131F01FF13FF6C90B5FC7E6C6C14806DEBFE0001 0F13F001011380222B7DA928>99 D101 D<38FC01FF010713C0011F13F0 017F13F890B512FC12FD39FFF80FFEEBE003EBC00190388000FFA290C7127FA35AB3A920 2979A82F>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fu cmr10 10.95 87 /Fu 87 125 df5 DI<4AB4EB0FE0 021F9038E03FFC913A7F00F8FC1ED901FC90383FF03FD907F090397FE07F80494801FF13 FF4948485BD93F805C137F0200ED7F00EF003E01FE6D91C7FC82ADB97EA3C648C76CC8FC B3AE486C4A7E007FD9FC3FEBFF80A339407FBF35>11 D<4AB4FC021F13C091387F01F090 3901FC0078D907F0131C4948133E494813FF49485A137F1400A213FE6F5A163893C7FCAA 167FB8FCA33900FE00018182B3AC486CECFF80007FD9FC3F13FEA32F407FBF33>I<4AB4 ECFF80021FD9C00F13E0913B7F01F03F80F8903C01F80078FE003CD907F0D93FF8130E49 484948131F49484948EB7F804948484913FF137F02005CA201FE92C7FC6FED7F0070141C 96C7FCAAF13F80BBFCA3C648C76CC7FC197F193FB3AC486C4A6CEB7FC0007FD9FC3FD9FE 1FB5FCA348407FBF4C>14 D<127C12FC7E7EA2EA7F80EA3FC0EA1FE0120FEA07F0EA03F8 1201EA007C133E131F130E1304101176BE2D>18 D<133E133F137F13FFA2EA01FEEA03FC EA07F813F0EA0FE0EA1FC01380EA3E005A5A1270122010116EBE2D>I<00601306007813 1E00FC133F003F13FC381F81F8380FE7F03803FFC06C13806C1300133C1318180B76B92D >I<121EEA7F80EAFFC0A9EA7F80ACEA3F00AC121EAB120CC7FCA8121EEA7F80A2EAFFC0 A4EA7F80A2EA1E000A4179C019>33 D<001E130F397F803FC000FF137F01C013E0A201E0 13F0A3007F133F391E600F3000001300A401E01370491360A3000114E04913C000031301 01001380481303000EEB070048130E0018130C0038131C003013181C1C7DBE2D>I<4B6C 130C4B6C131EA20307143EA24C133CA2030F147CA293C71278A24B14F8A2031E5CA2033E 1301A2033C5CA3037C1303A203785CA203F81307A24B5CA20201140F007FBAFCBB1280A2 6C1900C72707C0003EC8FC4B133CA3020F147CA292C71278A24A14F8A2021E5CA3023E13 01007FBAFCBB1280A26C1900C727F80007C0C8FC4A5CA20101140FA24A91C9FCA301035C A24A131EA20107143EA24A133CA2010F147CA291C71278A34914F8A2011E5CA2013E1301 A2013C5CA201186D5A41517BBE4C>I<121EEA7F8012FF13C0A213E0A3127FEA1E601200 A413E013C0A312011380120313005A120E5A1218123812300B1C79BE19>39 D<1430147014E0EB01C0EB03801307EB0F00131E133E133C5B13F85B12015B1203A2485A A2120F5BA2121F90C7FCA25AA3123E127EA6127C12FCB2127C127EA6123E123FA37EA27F 120FA27F1207A26C7EA212017F12007F13787F133E131E7FEB07801303EB01C0EB00E014 701430145A77C323>I<12C07E12707E7E121E7E6C7E7F12036C7E7F12007F1378137CA2 7FA2133F7FA21480130FA214C0A3130714E0A6130314F0B214E01307A614C0130FA31480 A2131F1400A25B133EA25BA2137813F85B12015B485A12075B48C7FC121E121C5A5A5A5A 145A7BC323>I<1506150FB3A9007FB912E0BA12F0A26C18E0C8000FC9FCB3A915063C3C 7BB447>43 D<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A312011380 120313005A120E5A1218123812300B1C798919>II<121EEA7F80 A2EAFFC0A4EA7F80A2EA1E000A0A798919>I48 DIII<150E15 1E153EA2157EA215FE1401A21403EC077E1406140E141CA214381470A214E0EB01C0A2EB 0380EB0700A2130E5BA25B5BA25B5B1201485A90C7FC5A120E120C121C5AA25A5AB8FCA3 C8EAFE00AC4A7E49B6FCA3283E7EBD2D>I<00061403D80780131F01F813FE90B5FC5D5D 5D15C092C7FC14FCEB3FE090C9FCACEB01FE90380FFF8090383E03E090387001F8496C7E 49137E497F90C713800006141FC813C0A216E0150FA316F0A3120C127F7F12FFA416E090 C7121F12FC007015C012780038EC3F80123C6CEC7F00001F14FE6C6C485A6C6C485A3903 F80FE0C6B55A013F90C7FCEB07F8243F7CBC2D>II<1238123C123F90B612FCA316F85A16F016E00078C712010070EC03C0ED 078016005D48141E151C153C5DC8127015F04A5A5D14034A5A92C7FC5C141EA25CA2147C 147814F8A213015C1303A31307A3130F5CA2131FA6133FAA6D5A0107C8FC26407BBD2D> III<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCB3121E EA7F80A2EAFFC0A4EA7F80A2EA1E000A2779A619>I<007FB912E0BA12F0A26C18E0CDFC AE007FB912E0BA12F0A26C18E03C167BA147>61 D63 D<15074B7EA34B7EA34B7EA3 4B7EA34B7E15E7A2913801C7FC15C3A291380381FEA34AC67EA3020E6D7EA34A6D7EA34A 6D7EA34A6D7EA34A6D7EA349486D7E91B6FCA249819138800001A249C87EA24982010E15 7FA2011E82011C153FA2013C820138151FA2017882170F13FC00034C7ED80FFF4B7EB500 F0010FB512F8A33D417DC044>65 DIIIIII II<011FB512FCA3D9 000713006E5A1401B3B3A6123FEA7F80EAFFC0A44A5A1380D87F005B007C130700385C00 3C495A6C495A6C495A2603E07EC7FC3800FFF8EB3FC026407CBD2F>IIIIIII82 DI<003FB912 80A3903AF0007FE001018090393FC0003F48C7ED1FC0007E1707127C00781703A3007017 01A548EF00E0A5C81600B3B14B7E4B7E0107B612FEA33B3D7DBC42>II II<007FB5D8C003B512E0A3C649C7EBFC00D93FF8EC3FE06D48EC1F806D6C92C7FC17 1E6D6C141C6D6C143C5F6D6C14706D6D13F04C5ADA7FC05B023F13036F485ADA1FF090C8 FC020F5BEDF81E913807FC1C163C6E6C5A913801FF7016F06E5B6F5AA26F7E6F7EA28282 153FED3BFEED71FF15F103E07F913801C07F0203804B6C7EEC07004A6D7E020E6D7E5C02 3C6D7E02386D7E14784A6D7E4A6D7F130149486E7E4A6E7E130749C86C7E496F7E497ED9 FFC04A7E00076DEC7FFFB500FC0103B512FEA33F3E7EBD44>II<003FB712F8A391C7EA1FF013F801E0EC3FE00180EC7FC090 C8FC003EEDFF80A2003C4A1300007C4A5A12784B5A4B5AA200704A5AA24B5A4B5AA2C848 5A4A90C7FCA24A5A4A5AA24A5AA24A5A4A5AA24A5A4A5AA24990C8FCA2495A4948141CA2 495A495AA2495A495A173C495AA24890C8FC485A1778485A484815F8A248481401160348 48140F4848143FED01FFB8FCA32E3E7BBD38>II<486C13C00003130101001380481303000EEB070048130E0018130C0038 131C003013180070133800601330A300E01370481360A400CFEB678039FFC07FE001E013 F0A3007F133FA2003F131F01C013E0390F0007801C1C73BE2D>II97 DI<49B4FC010F13E090383F00F8017C131E4848131F 4848137F0007ECFF80485A5B121FA24848EB7F00151C007F91C7FCA290C9FC5AAB6C7EA3 003FEC01C07F001F140316806C6C13076C6C14000003140E6C6C131E6C6C137890383F01 F090380FFFC0D901FEC7FC222A7DA828>II II<167C903903F801 FF903A1FFF078F8090397E0FDE1F9038F803F83803F001A23B07E000FC0600000F6EC7FC 49137E001F147FA8000F147E6D13FE00075C6C6C485AA23901F803E03903FE0FC026071F FFC8FCEB03F80006CAFC120EA3120FA27F7F6CB512E015FE6C6E7E6C15E06C810003813A 0FC0001FFC48C7EA01FE003E140048157E825A82A46C5D007C153E007E157E6C5D6C6C49 5A6C6C495AD803F0EB0FC0D800FE017FC7FC90383FFFFC010313C0293D7EA82D>III<1478EB01FEA2EB03FFA4EB01FEA2EB00781400AC147FEB7FFFA313 017F147FB3B3A5123E127F38FF807E14FEA214FCEB81F8EA7F01387C03F0381E07C0380F FF803801FC00185185BD1C>II I<2701F801FE14FF00FF902707FFC00313E0913B1E07E00F03F0913B7803F03C01F80007 903BE001F87000FC2603F9C06D487F000101805C01FBD900FF147F91C75B13FF4992C7FC A2495CB3A6486C496CECFF80B5D8F87FD9FC3F13FEA347287DA74C>I<3901F801FE00FF 903807FFC091381E07E091387803F000079038E001F82603F9C07F0001138001FB6D7E91 C7FC13FF5BA25BB3A6486C497EB5D8F87F13FCA32E287DA733>I<14FF010713E090381F 81F890387E007E01F8131F4848EB0F804848EB07C04848EB03E0000F15F04848EB01F8A2 003F15FCA248C812FEA44815FFA96C15FEA36C6CEB01FCA3001F15F86C6CEB03F0A26C6C EB07E06C6CEB0FC06C6CEB1F80D8007EEB7E0090383F81FC90380FFFF0010090C7FC282A 7EA82D>I<3901FC03FC00FF90381FFF8091387C0FE09039FDE003F03A07FFC001FC6C49 6C7E6C90C7127F49EC3F805BEE1FC017E0A2EE0FF0A3EE07F8AAEE0FF0A4EE1FE0A2EE3F C06D1580EE7F007F6E13FE9138C001F89039FDE007F09039FC780FC0DA3FFFC7FCEC07F8 91C9FCAD487EB512F8A32D3A7EA733>I<02FF131C0107EBC03C90381F80F090397F0038 7C01FC131CD803F8130E4848EB0FFC150748481303121F485A1501485AA448C7FCAA6C7E A36C7EA2001F14036C7E15076C6C130F6C7E6C6C133DD8007E137990383F81F190380FFF C1903801FE0190C7FCAD4B7E92B512F8A32D3A7DA730>I<3901F807E000FFEB1FF8EC78 7CECE1FE3807F9C100031381EA01FB1401EC00FC01FF1330491300A35BB3A5487EB512FE A31F287EA724>I<90383FC0603901FFF8E03807C03F381F000F003E1307003C1303127C 0078130112F81400A27E7E7E6D1300EA7FF8EBFFC06C13F86C13FE6C7F6C1480000114C0 D8003F13E0010313F0EB001FEC0FF800E01303A214017E1400A27E15F07E14016C14E06C EB03C0903880078039F3E01F0038E0FFFC38C01FE01D2A7DA824>I<131CA6133CA4137C A213FCA2120112031207001FB512C0B6FCA2D801FCC7FCB3A215E0A912009038FE01C0A2 EB7F03013F138090381F8700EB07FEEB01F81B397EB723>IIIIII<001FB61280A2EBE0000180140049485A001E495A121C4A5A003C 495A141F00385C4A5A147F5D4AC7FCC6485AA2495A495A130F5C495A90393FC00380A2EB 7F80EBFF005A5B484813071207491400485A48485BA248485B4848137F00FF495A90B6FC A221277EA628>III E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fv cmbx12 14.4 35 /Fv 35 123 df<157815FC14031407141F14FF130F0007B5FCB6FCA2147F13F0EAF800C7 FCB3B3B3A6007FB712FEA52F4E76CD43>49 DI<9138 0FFFC091B512FC0107ECFF80011F15E090263FF8077F9026FF800113FC4848C76C7ED803 F86E7E491680D807FC8048B416C080486D15E0A4805CA36C17C06C5B6C90C75AD801FC16 80C9FC4C13005FA24C5A4B5B4B5B4B13C04B5BDBFFFEC7FC91B512F816E016FCEEFF80DA 000713E0030113F89238007FFE707E7013807013C018E07013F0A218F8A27013FCA218FE A2EA03E0EA0FF8487E487E487EB57EA318FCA25E18F891C7FC6C17F0495C6C4816E001F0 4A13C06C484A1380D80FF84A13006CB44A5A6CD9F0075BC690B612F06D5D011F15800103 02FCC7FCD9001F1380374F7ACD43>I<177C17FEA2160116031607160FA2161F163F167F A216FF5D5DA25D5DED1FBFED3F3F153E157C15FCEC01F815F0EC03E01407EC0FC01580EC 1F005C147E147C5C1301495A495A5C495A131F49C7FC133E5B13FC485A5B485A1207485A 485A90C8FC123E127E5ABA12C0A5C96C48C7FCAF020FB712C0A53A4F7CCE43>I<171F4D 7E4D7EA24D7EA34C7FA24C7FA34C7FA34C7FA24C7FA34C8083047F80167E8304FE804C7E 03018116F8830303814C7E03078116E083030F814C7E031F81168083033F8293C77E4B82 157E8403FE824B800201835D840203834B800207835D844AB87EA24A83A3DA3F80C88092 C97E4A84A2027E8202FE844A82010185A24A820103854A82010785A24A82010F855C011F 717FEBFFFCB600F8020FB712E0A55B547BD366>65 D<932601FFFCEC01C0047FD9FFC013 030307B600F81307033F03FE131F92B8EA803F0203DAE003EBC07F020F01FCC7383FF0FF 023F01E0EC0FF94A01800203B5FC494848C9FC4901F88249498249498249498249498249 90CA7E494883A2484983485B1B7F485B481A3FA24849181FA3485B1B0FA25AA298C7FC5C A2B5FCAE7EA280A2F307C07EA36C7FA21B0F6C6D1980A26C1A1F6C7F1C006C6D606C6D18 7EA26D6C606D6D4C5A6D6D16036D6D4C5A6D6D4C5A6D01FC4C5A6D6DEE7F806D6C6C6C4B C7FC6E01E0EC07FE020F01FEEC1FF80203903AFFE001FFF0020091B612C0033F93C8FC03 0715FCDB007F14E0040101FCC9FC525479D261>67 DI73 D76 D78 D80 D82 D<003FBC1280A59126C0 003F9038C0007F49C71607D87FF8060113C001E08449197F49193F90C8171FA2007E1A0F A3007C1A07A500FC1BE0481A03A6C994C7FCB3B3AC91B912F0A553517BD05E>84 D97 D<913801FFF8021FEBFF8091B612F0010315FC010F9038C00FFE903A1FFE0001FFD97FFC 491380D9FFF05B4817C048495B5C5A485BA2486F138091C7FC486F1300705A4892C8FC5B A312FFAD127F7FA27EA2EF03E06C7F17076C6D15C07E6E140F6CEE1F806C6DEC3F006C6D 147ED97FFE5C6D6CEB03F8010F9038E01FF0010390B55A01001580023F49C7FC020113E0 33387CB63C>99 D<4DB47E0407B5FCA5EE001F1707B3A4913801FFE0021F13FC91B6FC01 0315C7010F9038E03FE74990380007F7D97FFC0101B5FC49487F4849143F484980485B83 485B5A91C8FC5AA3485AA412FFAC127FA36C7EA37EA26C7F5F6C6D5C7E6C6D5C6C6D49B5 FC6D6C4914E0D93FFED90FEFEBFF80903A0FFFC07FCF6D90B5128F0101ECFE0FD9003F13 F8020301C049C7FC41547CD24B>I<913803FFC0023F13FC49B6FC010715C04901817F90 3A3FFC007FF849486D7E49486D7E4849130F48496D7E48178048497F18C0488191C7FC48 17E0A248815B18F0A212FFA490B8FCA318E049CAFCA6127FA27F7EA218E06CEE01F06E14 037E6C6DEC07E0A26C6DEC0FC06C6D141F6C6DEC3F806D6CECFF00D91FFEEB03FE903A0F FFC03FF8010390B55A010015C0021F49C7FC020113F034387CB63D>IIII<137F497E000313 E0487FA2487FA76C5BA26C5BC613806DC7FC90C8FCADEB3FF0B5FCA512017EB3B3A6B612 E0A51B547BD325>I107 DIII<913801FFE0021F13FE91B612C0010315F0010F9038807F FC903A1FFC000FFED97FF86D6C7E49486D7F48496D7F48496D7F4A147F48834890C86C7E A24883A248486F7EA3007F1880A400FF18C0AC007F1880A3003F18006D5DA26C5FA26C5F 6E147F6C5F6C6D4A5A6C6D495B6C6D495B6D6C495BD93FFE011F90C7FC903A0FFF807FFC 6D90B55A010015C0023F91C8FC020113E03A387CB643>I<903A3FF001FFE0B5010F13FE 033FEBFFC092B612F002F301017F913AF7F8007FFE0003D9FFE0EB1FFFC602806D7F92C7 6C7F4A824A6E7F4A6E7FA2717FA285187F85A4721380AC1A0060A36118FFA2615F616E4A 5BA26E4A5B6E4A5B6F495B6F4990C7FC03F0EBFFFC9126FBFE075B02F8B612E06F148003 1F01FCC8FC030313C092CBFCB1B612F8A5414D7BB54B>I<90397FE003FEB590380FFF80 033F13E04B13F09238FE1FF89139E1F83FFC0003D9E3E013FEC6ECC07FECE78014EF1500 14EE02FEEB3FFC5CEE1FF8EE0FF04A90C7FCA55CB3AAB612FCA52F367CB537>114 D<903903FFF00F013FEBFE1F90B7FC120348EB003FD80FF81307D81FE0130148487F4980 127F90C87EA24881A27FA27F01F091C7FC13FCEBFFC06C13FF15F86C14FF16C06C15F06C 816C816C81C681013F1580010F15C01300020714E0EC003F030713F015010078EC007F00 F8153F161F7E160FA27E17E07E6D141F17C07F6DEC3F8001F8EC7F0001FEEB01FE9039FF C00FFC6DB55AD8FC1F14E0D8F807148048C601F8C7FC2C387CB635>I<143EA6147EA414 FEA21301A313031307A2130F131F133F13FF5A000F90B6FCB8FCA426003FFEC8FCB3A9EE 07C0AB011FEC0F8080A26DEC1F0015806DEBC03E6DEBF0FC6DEBFFF86D6C5B021F5B0203 13802A4D7ECB34>II119 D<007FB500F090387FFFFEA5C66C48C7000F90C7FC6D6CEC07 F86D6D5C6D6D495A6D4B5A6F495A6D6D91C8FC6D6D137E6D6D5B91387FFE014C5A6E6C48 5A6EEB8FE06EEBCFC06EEBFF806E91C9FCA26E5B6E5B6F7E6F7EA26F7F834B7F4B7F92B5 FCDA01FD7F03F87F4A486C7E4A486C7E020F7FDA1FC0804A486C7F4A486C7F02FE6D7F4A 6D7F495A49486D7F01076F7E49486E7E49486E7FEBFFF0B500FE49B612C0A542357EB447 >II<001FB8FC1880A3912680007F130001FCC7B5FC01F049 5B495D49495B495B4B5B48C75C5D4B5B5F003E4A90C7FC92B5FC4A5B5E4A5B5CC7485B5E 4A5B5C4A5B93C8FC91B5FC495B5D4949EB0F805B495B5D495B49151F4949140092C7FC49 5A485E485B5C485E485B4A5C48495B4815074849495A91C712FFB8FCA37E31357CB43C> I E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%BeginPaperSize: Letter letter %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop 758 91 a Fv(The)45 b(Computational)i(Complexit)l(y)f(Column) 1902 317 y Fu(b)m(y)1599 543 y Ft(Lance)31 b(F)m(ORTNO)m(W)1475 769 y Fu(NEC)f(Researc)m(h)h(Institute)986 882 y(4)g(Indep)s(endence)e (W)-8 b(a)m(y)g(,)33 b(Princeton,)d(NJ)g(08540,)j(USA)1306 995 y Fs(fortnow@research.nj.nec)o(.com)141 1307 y Fu(This)d(summer)h (I)h(tak)m(e)i(o)m(v)m(er)f(t)m(w)m(o)h(p)s(ositions)c(from)i(Eric)f (Allender:)42 b(Editor)31 b(of)i(this)e(column)f(and)i(c)m(hair)g(of)0 1420 y(the)27 b(conference)g(committee)g(of)g(the)g(IEEE)e(Conference)i (on)f(Computational)f(Complexit)m(y)-8 b(.)39 b(While)26 b(these)g(jobs)0 1533 y(ha)m(v)m(e)h(quite)e(di\013eren)m(t)h(resp)s (onsibilities,)c(I)j(b)s(eliev)m(e)g(they)h(share)g(the)g(same)g (goals:)39 b(T)-8 b(o)26 b(promote)g(computational)0 1645 y(complexit)m(y)i(and)f(k)m(eep)h(researc)m(hers)g(informed)e(of)i (the)g(latest)h(happ)s(enings)c(in)h(the)i(area.)41 b(I)28 b(thank)f(Eric)g(for)g(his)0 1758 y(excellen)m(t)k(w)m(ork)f(on)g(b)s (oth)g(this)f(column)h(and)f(the)i(conference.)41 b(His)30 b(sho)s(es)g(will)e(b)s(e)h(hard)h(to)h(\014ll.)141 1871 y(In)37 b(m)m(y)h(\014rst)f(column)f(I)i(giv)m(e)g(a)g(surv)m(ey)f(on)h (\\Diagonalization")g(based)g(on)f(a)h(talk)g(giv)m(en)g(at)g(the)g (recen)m(t)0 1984 y(DIMA)m(CS)31 b(w)m(orkshop.)40 b(I)30 b(hop)s(e)g(y)m(ou)g(\014nd)f(it)h(in)m(teresting.)141 2097 y(This)22 b(column)g(should)f(not)j(b)s(e)f(a)g(one-w)m(a)m(y)i (street.)40 b(Please)23 b(feel)h(free)f(to)h(con)m(tact)i(me)d(if)g(y)m (ou)g(ha)m(v)m(e)i(commen)m(ts)0 2210 y(ab)s(out)30 b(this)f(column)h (\(or)g(the)h(conference\))g(particularly)d(if)i(y)m(ou)g(ha)m(v)m(e)i (ideas)e(for)g(future)f(column)g(topics.)1476 2557 y Fr(Diagonalization)2368 2505 y Fq(1)1633 2670 y(Lance)k(F)-8 b(ortno)m(w)1767 2869 y Fp(Abstract)352 3020 y Fo(W)h(e)22 b(giv)n(e)f(a)g(mo)r(dern)h(historical)e(and)i(philosophical)f (discussion)g(of)g(diagonalization)f(as)h(a)g(to)r(ol)h(to)f(pro)n(v)n (e)227 3120 y(lo)n(w)n(er)k(b)r(ounds)h(in)h(computational)e(complexit) n(y)-7 b(.)36 b(W)-7 b(e)26 b(will)h(giv)n(e)e(sev)n(eral)f(examples)i (and)g(discuss)g(four)f(p)r(os-)227 3220 y(sible)30 b(approac)n(hes)d (to)i(use)g(diagonalization)f(for)h(separating)f(logarithmic-space)f (from)i(nondeterministic)227 3319 y(p)r(olynomial-time.)0 3606 y Fv(1)135 b(In)l(tro)t(duction)0 3809 y Fu(The)20 b(greatest)j(em)m(barrassmen)m(t)e(in)f(computational)h(complexit)m(y)f (theory)h(comes)h(from)e(our)h(inabilit)m(y)d(to)k(ac)m(hiev)m(e)0 3921 y(signi\014can)m(t)41 b(complexit)m(y)i(class)f(separations.)76 b(In)42 b(recen)m(t)i(y)m(ears)f(w)m(e)g(ha)m(v)m(e)g(seen)g(man)m(y)f (in)m(teresting)g(results)0 4034 y(come)31 b(from)f(an)g(old)f(tec)m (hnique|diagonalization.)40 b(Deceptiv)m(ely)31 b(simple,)d (diagonalization,)i(com)m(bined)f(with)0 4147 y(tec)m(hniques)h(for)g (collapsing)f(classes,)h(can)h(yield)e(quite)h(in)m(teresting)f(lo)m(w) m(er)i(b)s(ounds)d(on)i(computation.)141 4260 y(In)f(1874,)i(Can)m(tor) f([Can74])g(\014rst)e(used)g(diagonalization)h(for)g(sho)m(wing)f(the)h (set)h(of)f(reals)g(is)f(not)h(coun)m(table.)0 4373 y(The)h(pro)s(of)h (w)m(ork)m(ed)g(b)m(y)g(assuming)f(an)g(en)m(umeration)h(of)g(the)g (reals)g(and)f(designing)f(a)j(set)f(that)h(one-b)m(y-one)g(is)0 4486 y(di\013eren)m(t)g(from)g(ev)m(ery)i(set)f(in)f(the)h(en)m (umeration.)47 b(Dra)m(wn)33 b(as)g(a)g(table)f(this)g(pro)s(cess)g (considers)g(the)h(diagonal)0 4599 y(set)e(and)f(rev)m(erses)h(it.)40 b(Th)m(us)29 b(the)i(term)f(diagonalization.)141 4712 y(Diagonalization)f(w)m(as)h(\014rst)f(used)f(in)h(computabilit)m(y)e (theory)j(in)e(the)i(1930's)h(b)m(y)e(T)-8 b(uring)28 b([T)-8 b(ur36])30 b(to)g(sho)m(w)0 4825 y(that)d(there)h(existed)e (computably)g(en)m(umerable)g(problems)f(that)j(w)m(ere)f(not)g (computable.)39 b(The)27 b(seminal)e(pap)s(er)0 4938 y(in)k(computational)h(complexit)m(y)g([HS65)q(])h(used)e (diagonalization)g(to)j(giv)m(e)e(time)h(and)e(space)i(hierarc)m(hies.) p 0 4999 1560 4 v 104 5053 a Fn(1)138 5085 y Fm(Based)h(on)e(an)h(in)n (vited)e(talk)i(giv)n(en)f(at)h(the)f(DIMA)n(CS)g(W)-6 b(orkshop)30 b(on)g(Computational)h(In)n(tractabilit)n(y)f(on)h(April)f (13,)j(2000.)0 5176 y(The)26 b(slides)h(of)f(that)f(presen)n(tation)h (can)g(b)r(e)g(found)f(at)h(h)n (ttp://www.neci.nj.nec.com/homepages/fortno)n(w/talks.)p eop %%Page: 2 2 2 1 bop 141 91 a Fu(Diagonalization)30 b(w)m(orks!)41 b(In)29 b(Section)h(2.1)h(w)m(e)g(describ)s(e)d(Allender's)h (diagonalization)g(pro)s(of)g([All99])h(that)0 204 y(the)e(p)s(ermanen) m(t)f(is)g(not)h(computable)f(b)m(y)h(uniform)d(constan)m(t)k(depth)e (threshold)f(circuits.)39 b(Without)27 b(diagonal-)0 317 y(ization,)j(can)h(w)m(e)g(ev)m(en)g(sho)m(w)f(that)h(the)g (halting)e(problem)f(do)s(es)j(not)f(ha)m(v)m(e)i(suc)m(h)e(circuits?) 141 430 y(Razb)s(oro)m(v)35 b(and)e(Rudic)m(h)f([RR97)q(])i(has)g(dev)m (elop)s(ed)f(the)h(concept)h(of)f(\\natural)f(pro)s(ofs")g(that)i (capture)f(the)0 543 y(kno)m(wn)g(tec)m(hniques)g(for)g(pro)m(ving)g (lo)m(w)m(er)h(b)s(ounds)d(in)h(non)m(uniform)g(circuit)g(classes.)53 b(They)34 b(sho)m(w)g(that)h(under)0 656 y(reasonable)k(assumptions,)g (these)h(pro)s(ofs)e(cannot)h(giv)m(e)h(us)e(strong)h(lo)m(w)m(er)g(b)s (ounds)e(for)i(v)-5 b(arious)38 b(in)m(teresting)0 769 y(circuit)28 b(problems.)39 b(Since)28 b(diagonalization)g(w)m(orks)h (against)h(uniform)d(mo)s(dels)h(of)h(computation,)h(these)f(issues)0 882 y(do)h(not)h(apply)-8 b(.)141 995 y(The)32 b(tec)m(hniques)g(for)g (diagonalization)f(remain)h(relativ)m(ely)f(simple.)45 b(T)-8 b(o)33 b(pro)m(v)m(e)g(a)g(separation)f(result,)g(one)0 1108 y(assumes)g(a)h(collapse)f(and)g(deriv)m(es)g(enough)h (consequences)g(un)m(til)e(w)m(e)i(violate)g(a)g(w)m(ell-kno)m(wn)e (time-hierarc)m(h)m(y)0 1220 y(theorem.)41 b(Most)31 b(of)g(the)g(in)m(teresting)e(diagonalization)h(pro)s(ofs)f(do)h(not)h (rely)e(on)i(hard)e(com)m(binatorics.)141 1333 y(Diagonalization)23 b(do)s(es)f(ha)m(v)m(e)i(its)e(limitations.)36 b(Most)24 b(of)e(the)h(results)f(w)m(e)h(ha)m(v)m(e)h(b)m(y)e(diagonalization)g (are)h(still)0 1446 y(far)i(w)m(eak)m(er)i(than)e(w)m(e)h(w)m(ould)e (hop)s(e.)38 b(Diagonalization)25 b(also)g(giv)m(es)h(ev)m(en)g(w)m (eak)m(er)h(results)d(against)h(probabilistic)0 1559 y(and)30 b(non)m(uniform)e(computation.)141 1672 y(Bak)m(er,)42 b(Gill)36 b(and)i(Solo)m(v)-5 b(a)m(y)39 b([BGS75)q(])g(dev)m(elop)f (the)g(notion)g(of)h(\\relativization".)64 b(They)37 b(created)j(a)e(rel-)0 1785 y(ativized)h(w)m(orld)f Fl(A)h Fu(where)f Fk(P)1058 1752 y Fj(A)1156 1785 y Fu(=)h Fk(NP)1419 1749 y Fj(A)1476 1785 y Fu(.)67 b(Since)38 b(all)g(of)i(the)f(kno)m(wn) f(diagonalization)g(pro)s(ofs)h(of)g(the)g(time)0 1898 y(relativize,)34 b(this)f(ga)m(v)m(e)j(a)e(go)s(o)s(d)g(argumen)m(t)g (that)h(diagonalization)d(alone)i(w)m(ould)f(not)h(separate)h Fk(P)f Fu(from)f Fk(NP)q Fu(.)0 2011 y(One)39 b(can)g(get)i(some)e (nonrelativizing)e(separation)i(results.)66 b(W)-8 b(e)41 b(giv)m(e)e(one)h(suc)m(h)f(example)g(in)f(Section)h(2.6.)0 2124 y(Ho)m(w)m(ev)m(er)32 b(these)f(results)e(require)g (nonrelativizing)f(collapses)i(of)h(whic)m(h)e(there)h(are)h(few.)141 2237 y(W)-8 b(e)26 b(will)c(giv)m(e)i(sev)m(eral)h(results)e(sho)m (wing)h(ho)m(w)g(diagonalization)g(has)g(and)g(con)m(tin)m(ues)g(to)h (pla)m(y)f(an)h(imp)s(ortan)m(t)0 2350 y(role)39 b(in)f(computational)i (complexit)m(y)f(theory)-8 b(.)69 b(W)-8 b(e)41 b(also)e(argue)h(that)g (diagonalization)f(ma)m(y)h(ev)m(en)g(help)f(us)0 2462 y(separate)31 b(classes)g(lik)m(e)e Fk(NP)i Fu(from)f Fk(L)p Fu(|w)m(e)h(giv)m(e)f(four)g(approac)m(hes)h(to)m(w)m(ards)g (this)e(goal.)0 2749 y Fv(2)135 b(Diagonalization)48 b(Pro)t(ofs)0 2952 y Fu(In)27 b(this)g(section)h(w)m(e)g(giv)m(e)h(sev) m(eral)f(examples)g(ab)s(out)f(diagonalization)g(results)g(to)i(giv)m (e)f(a)g(taste)i(and)d(history)g(of)0 3065 y(the)k(tec)m(hnique.)0 3308 y Fi(2.1)112 b(P)m(ermanen)m(t)37 b(is)g(not)g(in)g(uniform)f(TC) 1851 3323 y Fh(0)0 3480 y Fu(A)i(w)m(onderful)e(example)i(of)g(the)g (diagonalization)f(tec)m(hnique)h(is)f(the)i(result)d(sho)m(wing)i (that)g(the)h(p)s(ermanen)m(t)0 3593 y(cannot)k(b)s(e)g(computed)f(b)m (y)h(uniform)d(constan)m(t)k(depth)e(threshold)g(circuits.)76 b(This)41 b(result)h(w)m(as)h(pro)m(v)m(en)g(b)m(y)0 3706 y(Allender)35 b([All99])j(building)33 b(on)k(w)m(ork)h(of)f (Caussin)m(us,)g(McKenzie,)j(Th)m(\023)-43 b(erien)37 b(and)f(V)-8 b(ollmer)37 b([CMTV98)q(])h(and)0 3819 y(Allender)28 b(and)i(Gore)h([A)m(G94)r(].)41 b(W)-8 b(e)32 b(sk)m(etc)m(h)g(the)e (pro)s(of)g(in)f(this)g(section.)141 3931 y(Consider)e Fg(thr)-5 b(eshold)32 b Fu(mac)m(hines:)39 b(These)29 b(are)g(lik)m(e)f(alternating)g(mac)m(hines)g(except)i(that)g(instead)e (of)g(asking)0 4044 y(existen)m(tial)j(and)g(univ)m(ersal)f(questions)h (they)h(ask)g(\\Do)h(a)f(ma)5 b(jorit)m(y)32 b(of)g(m)m(y)g (computation)f(paths)g(accept?")47 b(A)0 4157 y Fl(k)s Fu(-threshold)38 b(mac)m(hine)g(can)i(ha)m(v)m(e)g Fl(k)i Fu(threshold)37 b(questions)h(on)h(an)m(y)g(path.)67 b(P)m(olynomial-time)37 b(un)m(b)s(ounded-)0 4270 y(threshold)30 b(mac)m(hines)h(giv)m(e)h(us)f Fk(PSP)-9 b(A)m(CE)q Fu(.)44 b(P)m(olynomial-time)30 b(constan)m(t-threshold)i(mac)m(hines)f(c)m (haracterize)0 4383 y(the)i(coun)m(ting)f(hierarc)m(h)m(y)-8 b(.)47 b(Logarithmic-time)32 b(constan)m(t-threshold)h(mac)m(hines)f (with)f(random-access)i(to)h(the)0 4496 y(input)28 b(c)m(haracterize)k (uniform)d Fk(TC)1235 4510 y Fh(0)1274 4496 y Fu(.)141 4609 y(Supp)s(ose)c(the)j(p)s(ermanen)m(t)e(is)g(in)g(uniform)f Fk(TC)1776 4623 y Fh(0)1842 4609 y Fu(and)i(therefore)g(in)f Fk(P)p Fu(.)40 b(Th)m(us)26 b(w)m(e)h(can)g(coun)m(t)h(computation)0 4722 y(paths)k(in)e(p)s(olynomial-time)f([V)-8 b(al79)r(])32 b(so)g(the)g(en)m(tire)g(coun)m(ting)g(hierarc)m(h)m(y)f(collapses)h (to)g Fk(P)p Fu(.)46 b(The)31 b(pro)s(ofs)g(that)0 4835 y(the)h(p)s(ermanen)m(t)e(is)h(#)p Fk(P)p Fu(-complete)h([V)-8 b(al79)q(,)32 b(Zan92])g(sho)m(w)f(that)h(the)f(p)s(ermanen)m(t)g(is)f (in)g(fact)j(complete)e(under)0 4948 y(reductions)36 b(computable)h(b)m(y)g(constan)m(t)i(depth)d(circuits.)60 b(Since)36 b(the)i(p)s(ermanen)m(t)e(is)h(in)f Fk(TC)3319 4962 y Fh(0)3396 4948 y Fu(the)h(coun)m(ting)0 5061 y(hierarc)m(h)m(y) 30 b(no)m(w)g(collapses)g(to)h Fk(TC)1220 5075 y Fh(0)1260 5061 y Fu(.)141 5173 y(By)g(straigh)m(tforw)m(ard)f(diagonalization)f (one)h(can)h(get)g(that)g(for)f(an)m(y)g(\014xed)g Fl(k)j Fu(there)e(exists)f(a)g(language)h(ac-)0 5286 y(cepted)24 b(b)m(y)g(a)g(p)s(olynomial-time)d Fl(k)s Fu(-threshold)i(mac)m(hine)g (not)h(accepted)h(b)m(y)f(an)m(y)g(logarithmic-time)e Fl(k)s Fu(-threshold)p eop %%Page: 3 3 3 2 bop 0 91 a Fu(mac)m(hine.)57 b(W)-8 b(e)37 b(ha)m(v)m(e)g(not)f(y)m (et)h(reac)m(hed)f(a)g(con)m(tradiction)g(since)f(it)h(is)e(p)s (ossible)g(that)i(a)g(p)s(olynomial-time)e Fl(k)s Fu(-)0 204 y(threshold)29 b(mac)m(hine)h(is)f(accepted)j(b)m(y)e(some)h (logarithmic-time)e Fl(k)24 b Fu(+)19 b(1-threshold)30 b(mac)m(hine.)141 317 y(No)m(w)40 b Fk(SA)-9 b(T)38 b Fu(is)g(accepted)i(b)m(y)f(a)g(log-time)g Fl(k)s Fu(-threshold)f(mac)m (hine)g(for)h(some)g(\014xed)f Fl(k)s Fu(.)66 b(All)37 b(of)i Fk(NP)p Fu(,)j(and)0 430 y(th)m(us)27 b(the)h(coun)m(ting)f (hierarc)m(h)m(y)g(is)g(reducible)e(to)j Fk(SA)-9 b(T)27 b Fu(via)h(simple)d(pro)5 b(jections.)39 b(All)26 b(of)i(the)g(p)s (olynomial-time)0 543 y(constan)m(t)g(threshold)d(mac)m(hines)i(can)g (b)s(e)f(sim)m(ulated)f(b)m(y)i(a)g(logarithmic-time)f Fl(k)s Fu(-threshold)g(mac)m(hine)g(giving)g(us)0 656 y(the)31 b(con)m(tradiction.)141 769 y(This)h(pro)s(of)h(is)g(a)h (great)h(example)f(of)f(the)h(diagonalization)f(metho)s(d:)47 b(W)-8 b(e)35 b(w)m(an)m(t)g(to)f(pro)m(v)m(e)h(a)f(separation.)0 882 y(First)k(w)m(e)h(assume)g(the)g(collapse.)65 b(Then)37 b(w)m(e)j(get)f(other)g(collapses)f(and)h(k)m(eep)g(on)f(collapsing)g (un)m(til)e(w)m(e)k(can)0 995 y(apply)29 b(a)i(straigh)m(tforw)m(ard)f (diagonalization.)0 1235 y Fi(2.2)112 b(Time)36 b(and)j(Space)f (Hierarc)m(hies)0 1407 y Fu(The)21 b(\014rst)g(uses)f(of)i (diagonalization)e(in)g(complexit)m(y)i(theory)f(came)h(in)f(the)g(v)m (ery)h(\014rst)e(pap)s(ers.)37 b(The)21 b(main)f(results)0 1520 y(of)k(the)g(seminal)e(pap)s(er)h(in)g(complexit)m(y)h(theory)g(b) m(y)f(Hartmanis)h(and)f(Stearns)g([HS65)q(])h(ga)m(v)m(e)i (deterministic)c(time)0 1633 y(and)30 b(space)h(hierarc)m(h)m(y)f (results)f(using)g(straigh)m(tforw)m(ard)h(diagonalization.)141 1745 y(Nondeterministic)38 b(hierarc)m(h)m(y)i(results)e(are)j(not)f (so)g(straigh)m(tforw)m(ard)g(b)s(ecause)g(of)g(the)g(need)g(to)h(do)f (the)0 1858 y(opp)s(osite)28 b(in)f(the)i(diagonalization)e(step.)40 b(Ibarra)28 b([Iba72)q(])h(sho)m(w)m(ed)f(ho)m(w)h(to)g(get)h(go)s(o)s (d)e(b)s(ounds)e(for)j(the)f(nonde-)0 1971 y(terministic)23 b(space)i(hierarc)m(h)m(y)f(b)m(y)h(making)f(man)m(y)h(collapses)f(and) g(then)g(applying)f(Sa)m(vitc)m(h's)i(Theorem)f([Sa)m(v70)r(])0 2084 y(to)31 b(get)h(the)f(determinism)d(needed)j(for)f (diagonalization.)41 b(Immerman)29 b([Imm88)q(])i(and)f(Szelep)s(cs)m (\023)-43 b(en)m(yi)30 b([Sze88)r(]'s)0 2197 y(results)38 b(that)i(nondeterministic)d(space)j(is)f(closed)g(under)f(complemen)m (t)i(remo)m(v)m(ed)g(this)f(problem)f(and)h(ga)m(v)m(e)0 2310 y(tigh)m(t)31 b(hierarc)m(hies.)141 2423 y(W)-8 b(e)34 b(do)e(not)g(b)s(eliev)m(e)g(nondeterministic)d(time)j(is)g (closed)g(under)f(complemen)m(t)h(and)g(w)m(e)h(also)f(do)g(not)h(ha)m (v)m(e)0 2536 y(an)m(y)e(deterministic)d(sim)m(ulation)h(nearly)h(as)h (nice)f(as)g(Sa)m(vitc)m(h's)i(theorem)f(for)f(space.)42 b(Ho)m(w)m(ev)m(er,)33 b(using)c(a)i(large)0 2649 y(n)m(um)m(b)s(er)e (of)i(collapses)e(w)m(e)i(can)g(ac)m(hiev)m(e)h(quite)d(a)i(tigh)m(t)g (hierarc)m(h)m(y)f(for)g(nondeterministic)e(time.)141 2762 y(Co)s(ok)36 b([Co)s(o73)r(])g(\014rst)g(sho)m(w)m(ed)g(that)h Fk(NTIME)o Fu(\()p Fl(n)1889 2729 y Fj(r)1927 2762 y Fu(\))f Ff(\()f Fk(NTIME)o Fu(\()p Fl(n)2556 2729 y Fj(s)2593 2762 y Fu(\))h(if)g(1)f Fe(\024)g Fl(r)j(<)d(s)p Fu(.)58 b(Seiferas,)37 b(Fisc)m(her)0 2875 y(and)30 b(Mey)m(er)h([SFM78)r(])f (giv)m(e)h(a)g(signi\014can)m(tly)d(stronger)j(v)m(ersion.)0 3046 y Fk(Theorem)j(2.1)h(\(Seiferas-Fisc)m(her-Mey)m(er\))46 b Fg(F)-7 b(or)30 b(any)g(time-c)-5 b(onstructible)29 b(functions)g Fl(s)g Fg(and)h Fl(t)f Fg(such)g(that)0 3159 y Fl(s)p Fu(\()p Fl(n)19 b Fu(+)g(1\))26 b(=)f Fl(o)p Fu(\()p Fl(t)p Fu(\()p Fl(n)p Fu(\)\))p Fg(,)33 b(ther)-5 b(e)33 b(exists)g(a)f(language)h(ac)-5 b(c)g(epte)g(d)34 b(in)e(nondeterministic)i(time)e Fl(t)p Fu(\()p Fl(n)p Fu(\))g Fg(but)g(not)h(ac)-5 b(c)g(epte)g(d)0 3272 y(in)33 b(nondeterministic)h(time)e Fl(s)p Fu(\()p Fl(n)p Fu(\))p Fg(.)0 3444 y Fu(W)-8 b(e)32 b(sk)m(etc)m(h)f(a)g(simple)d(pro)s(of)i (of)h(Theorem)f(2.1)h(due)f(to)1951 3421 y(\024)1946 3444 y(Z\022)-45 b(ak)30 b([)2155 3421 y(\024)2150 3444 y(Z\022)-45 b(ak83)q(].)0 3638 y Fk(Sk)m(etc)m(h)31 b(of)f(Pro)s(of:)62 b Fu(Let)27 b Fl(M)1036 3652 y Fh(1)1075 3638 y Fl(;)15 b(:)g(:)g(:)28 b Fu(b)s(e)e(an)g(en)m(umeration)g(of)h (nondeterministic)c(T)-8 b(uring)25 b(mac)m(hines.)39 b(W)-8 b(e)28 b(de\014ne)0 3751 y(a)39 b(nondeterministic)d(mac)m(hine) i Fl(M)49 b Fu(that)39 b(acts)g(as)g(follo)m(ws)f(on)g(input)f Fl(w)k Fu(=)e(1)2759 3718 y Fj(i)2787 3751 y Fu(01)2877 3718 y Fj(m)2945 3751 y Fu(01)3035 3718 y Fj(k)3078 3751 y Fu(:)57 b(If)38 b Fl(k)k(<)d(m)3538 3718 y Fj(t)p Fh(\()p Fj(m)p Fh(\))3723 3751 y Fu(then)0 3863 y(sim)m(ulate)27 b Fl(M)447 3877 y Fj(i)504 3863 y Fu(on)h(input)e(1)913 3830 y Fj(i)942 3863 y Fu(01)1032 3830 y Fj(m)1099 3863 y Fu(01)1189 3830 y Fj(k)r Fh(+1)1351 3863 y Fu(for)i Fl(t)p Fu(\()p Fe(j)p Fl(w)r Fe(j)p Fu(\))h(steps.)40 b(If)28 b Fl(k)g Fu(=)d Fl(m)2340 3830 y Fj(t)p Fh(\()p Fj(m)p Fh(\))2515 3863 y Fu(then)j(accept)i(if)d(1)3127 3830 y Fj(i)3155 3863 y Fu(01)3245 3830 y Fj(m)3313 3863 y Fu(0)h(rejects)h(whic)m(h)0 3976 y(w)m(e)i(can)g(do)f(quic)m(kly)f (as)i(a)f(function)f(of)i(the)f(curren)m(t)h(input)d(size.)141 4089 y(This)g(mac)m(hine)i(uses)g(time)f Fl(t)p Fu(\()p Fl(n)p Fu(\))h(so)h(b)m(y)f(assumption)e(can)i(b)s(e)g(sim)m(ulated)f (in)f(time)i Fl(s)p Fu(\()p Fl(n)p Fu(\))g(b)m(y)g(some)g(mac)m(hine)0 4202 y Fl(M)88 4216 y Fj(i)116 4202 y Fu(.)41 b(Since)29 b Fl(s)p Fu(\()p Fl(n)20 b Fu(+)g(1\))26 b(=)f Fl(o)p Fu(\()p Fl(t)p Fu(\()p Fl(n)p Fu(\)\))31 b(w)m(e)g(ha)m(v)m(e)h(for)e (su\016cien)m(tly)f(large)h Fl(m)p Fu(,)234 4404 y(1)279 4366 y Fj(i)307 4404 y Fu(01)397 4366 y Fj(m)465 4404 y Fu(0)25 b Fe(2)g Fl(L)p Fu(\()p Fl(M)10 b Fu(\))26 b Fe(,)f Fu(1)1038 4366 y Fj(i)1067 4404 y Fu(01)1157 4366 y Fj(m)1224 4404 y Fu(01)i Fe(2)d Fl(L)p Fu(\()p Fl(M)10 b Fu(\))26 b Fe(,)g(\001)15 b(\001)g(\001)26 b(,)f Fu(1)2091 4366 y Fj(i)2120 4404 y Fu(01)2210 4366 y Fj(m)2277 4404 y Fu(01)2367 4366 y Fj(m)2429 4343 y Fd(t)p Fn(\()p Fd(m)p Fn(\))2590 4404 y Fe(2)g Fl(L)p Fu(\()p Fl(M)10 b Fu(\))26 b Fe(,)f Fu(1)3093 4366 y Fj(i)3122 4404 y Fu(01)3212 4366 y Fj(m)3279 4404 y Fu(0)h Fe(62)f Fl(L)p Fu(\()p Fl(M)10 b Fu(\))0 4589 y(a)31 b(con)m(tradiction.)40 b Fc(\003)0 4830 y Fi(2.3)112 b(Dela)m(y)m(ed)38 b(Diagonalization)0 5001 y Fu(In)d(1975,)40 b(Ladner)35 b([Lad75)q(])h(sho)m(w)m(ed)g(that)h(if)d Fk(P)h Fe(6)p Fu(=)g Fk(NP)h Fu(there)g(m)m(ust)g(an)g(incomplete)f (set)h(in)f Fk(NP)24 b Fe(\000)g Fk(P)p Fu(.)58 b(His)0 5114 y(pro)s(of)26 b(creates)i(a)f(set)g(that)g(is)e(sometimes)i Fk(SA)-9 b(T)27 b Fu(to)g(k)m(eep)g(it)f(out)h(of)g Fk(P)g Fu(and)f(sometimes)g(the)h(empt)m(y)g(set)g(to)g(k)m(eep)0 5227 y(it)k(incomplete.)44 b(The)31 b(tric)m(ky)g(part)g(is)g(to)h(k)m (eep)h(the)e(set)h(in)f Fk(NP)p Fu(.)44 b(W)-8 b(e)33 b(need)e(to)h(b)s(e)f(patien)m(t)h(and)f(w)m(ait)h(un)m(til)d(w)m(e)0 5340 y(actually)h(see)h(a)g(diagonalization)e(o)s(ccur.)p eop %%Page: 4 4 4 3 bop 0 91 a Fk(Theorem)34 b(2.2)h(\(Ladner\))45 b Fg(If)32 b Fk(P)26 b Fe(6)p Fu(=)f Fk(NP)33 b Fg(then)g(ther)-5 b(e)34 b(exists)e(a)h(set)g Fl(A)g Fg(such)g(that)107 279 y(1.)46 b Fl(A)26 b Fe(2)f Fk(NP)p Fg(,)107 467 y(2.)46 b Fl(A)26 b Fe(62)f Fk(P)p Fg(,)32 b(and)107 654 y(3.)46 b Fl(A)33 b Fg(is)g(not)g Fk(NP)p Fg(-c)-5 b(omplete.)0 867 y Fk(Pro)s(of:)65 b Fu(W)-8 b(e)29 b(will)c(create)k(a)f(p)s (olynomial-time)e(computable)h(function)f Fl(f)35 b Fu(:)25 b(1)2698 834 y Fb(\003)2764 867 y Fe(!)g Ff(N)6 b Fu(.)46 b(W)-8 b(e)29 b(de\014ne)e(our)g(set)i Fl(A)f Fu(as)1176 1071 y Fl(A)e Fu(=)f Fe(f)p Fl(\036)31 b Fe(j)f Fl(\036)c Fe(2)f Fk(SA)-9 b(T)30 b Fu(and)g Fl(f)10 b Fu(\()p Fe(j)p Fl(\036)p Fe(j)p Fu(\))31 b(is)e(ev)m(en)q Fe(g)p Fl(:)0 1275 y Fu(Clearly)c Fl(A)h Fu(is)g(in)f Fk(NP)p Fu(.)39 b(W)-8 b(e)28 b(will)c(use)i Fl(f)35 b Fu(to)27 b(indicate)f(our)g (curren)m(t)g(stage.)41 b(When)26 b Fl(f)35 b Fu(is)26 b(equal)g(to)h(2)p Fl(i)g Fu(then)f(w)m(e)h(will)0 1388 y(try)f(to)h(prev)m(en)m(t)g Fl(A)f Fu(from)g(b)s(eing)f(accepted)i(b)m (y)g(the)f Fl(i)p Fu(th)g(p)s(olynomial-time)e(T)-8 b(uring)25 b(mac)m(hine.)39 b(When)26 b Fl(f)35 b Fu(is)25 b(equal)0 1501 y(to)e(2)p Fl(i)t Fu(+)t(1)h(w)m(e)f(will)d(prev)m(en)m(t)j Fk(SA)-9 b(T)23 b Fu(from)f(reducing)f(to)i Fl(A)g Fu(via)f(the)g Fl(i)p Fu(th)h(p)s(olynomial-time)d(computable)i(reduction.)0 1614 y(T)-8 b(o)38 b(k)m(eep)h Fl(f)47 b Fu(p)s(olynomial-time)35 b(computable)i(w)m(e)h(will)d(need)j(to)g(w)m(ait)g(not)g(only)f(for)h (the)g(diagonalization)e(to)0 1727 y(o)s(ccur)25 b(but)f(for)h(there)g (to)g(b)s(e)g(enough)f(time)h(for)f(us)h(to)g(see)h(it.)38 b(Th)m(us)24 b(the)h(notion)f(of)i(\\dela)m(y)m(ed)f(diagonalization.") 141 1840 y(Let)k Fl(M)390 1854 y Fh(1)430 1840 y Fl(;)15 b(:)g(:)g(:)29 b Fu(b)s(e)f(an)g(en)m(umeration)g(of)h(the)f(p)s (olynomial-time)e(computable)i(T)-8 b(uring)26 b(mac)m(hines.)40 b(Let)29 b Fl(g)3714 1854 y Fh(1)3754 1840 y Fl(;)15 b(:)g(:)g(:)0 1953 y Fu(b)s(e)30 b(an)g(en)m(umeration)g(of)h(p)s (olynomial-time)c(computable)j(functions.)141 2066 y(Initially)e(let)i Fl(f)10 b Fu(\(0\))26 b(=)f(2.)41 b(W)-8 b(e)31 b(will)d(start)j(in)e (stage)j Fl(n)25 b Fu(=)g(1.)0 2278 y(ST)-8 b(A)m(GE)31 b Fl(n)p Fu(:)141 2491 y(Let)e Fl(j)h Fu(=)25 b Fl(f)10 b Fu(\()p Fl(n)15 b Fe(\000)g Fu(1\).)41 b(If)27 b Fl(j)34 b Fu(is)27 b(ev)m(en)h(w)m(e)h(will)c(w)m(ork)j(against)g Fl(A)e Fu(=)f Fl(L)p Fu(\()p Fl(M)2527 2493 y Fd(j)p 2526 2508 31 3 v 2526 2549 a Fn(2)2571 2491 y Fu(\).)40 b(If)27 b Fl(j)34 b Fu(is)27 b(o)s(dd)g(w)m(e)h(will)e(w)m(ork)i (against)0 2621 y Fl(g)43 2653 y Fb(b)85 2622 y Fd(j)p 85 2638 V 85 2679 a Fn(2)125 2653 y Fb(c)191 2621 y Fu(reducing)h Fk(SA)-9 b(T)30 b Fu(to)h Fl(A)p Fu(.)0 2850 y(CASE)f Fl(j)g Fu(=)25 b(2)p Fl(k)s Fu(:)141 3063 y(See)38 b(if)f(there)h (exists)g(a)g(form)m(ula)f Fl(\036)h Fu(suc)m(h)g(that)g Fe(j)p Fl(\036)p Fe(j)h(\024)e Fu(log)17 b Fl(n)37 b Fu(and)h Fl(\036)g Fu(is)f(in)f(the)i(symmetric)f(di\013erence)h(of)0 3176 y Fl(L)p Fu(\()p Fl(M)185 3191 y Fj(k)228 3176 y Fu(\))31 b(and)f Fl(A)g Fu(as)h(de\014ned)e(so)h(far.)41 b(If)30 b(so)g(let)h Fl(f)10 b Fu(\()p Fl(n)p Fu(\))25 b(=)f Fl(j)i Fu(+)20 b(1)31 b(otherwise)f(let)g Fl(f)10 b Fu(\()p Fl(n)p Fu(\))25 b(=)g Fl(j)5 b Fu(.)0 3388 y(CASE)30 b Fl(j)g Fu(=)25 b(2)p Fl(k)f Fu(+)c(1:)141 3601 y(See)31 b(if)e(there)i(exists)f(a)g(form)m(ula)g Fl(\036)g Fu(suc)m(h)h(that)g Fe(j)p Fl(\036)p Fe(j)25 b(\024)g Fu(log)17 b Fl(n)30 b Fu(and)g(either)111 3788 y(1.)46 b Fl(\036)26 b Fe(2)f Fk(SA)-9 b(T)30 b Fu(and)g Fl(g)844 3803 y Fj(k)887 3788 y Fu(\()p Fl(\036)p Fu(\))c Fe(62)f Fl(A)p Fu(,)31 b(or)111 3976 y(2.)46 b Fl(\036)26 b Fe(62)f Fk(SA)-9 b(T)30 b Fu(and)g Fl(g)844 3991 y Fj(k)887 3976 y Fu(\()p Fl(\036)p Fu(\))c Fe(2)f Fl(A)p Fu(.)0 4164 y(If)30 b(so)h(then)f(let)g Fl(f)10 b Fu(\()p Fl(n)p Fu(\))25 b(=)g Fl(j)h Fu(+)19 b(1)31 b(otherwise)f(let)g Fl(f)10 b Fu(\()p Fl(n)p Fu(\))25 b(=)g Fl(j)5 b Fu(.)141 4326 y(If)36 b Fl(f)10 b Fu(\()p Fl(n)p Fu(\))35 b(go)s(es)h(to)h (in\014nit)m(y)d(then)h(w)m(e)i(ha)m(v)m(e)g(ful\014lled)32 b(the)k(conditions)e(for)i Fl(A)p Fu(.)57 b(If)36 b Fl(f)10 b Fu(\()p Fl(n)p Fu(\))35 b(reac)m(hes)i(a)f(limit)e(of)0 4439 y(2)p Fl(k)43 b Fu(then)d Fl(A)f Fu(will)e(b)s(e)i(equal)h(to)g Fl(L)p Fu(\()p Fl(M)1328 4454 y Fj(k)1371 4439 y Fu(\))g(and)f(also)h (\014nitely)e(di\013eren)m(t)h(from)g Fk(SA)-9 b(T)40 b Fu(violating)e(the)i Fk(P)h Fe(6)p Fu(=)g Fk(NP)0 4552 y Fu(assumption.)e(Lik)m(ewise)28 b(if)g Fl(f)10 b Fu(\()p Fl(n)p Fu(\))29 b(reac)m(hes)h(a)g(limit)d(of)j(2)p Fl(k)21 b Fu(+)d(1)29 b(then)g Fl(g)2405 4567 y Fj(k)2478 4552 y Fu(will)d(reduce)j Fk(SA)-9 b(T)30 b Fu(to)g Fl(A)f Fu(but)g Fl(A)g Fu(will)e(b)s(e)0 4665 y(\014nite)i(again)i(violating)e (the)i Fk(P)25 b Fe(6)p Fu(=)g Fk(NP)31 b Fu(assumption.)39 b Fc(\003)p eop %%Page: 5 5 5 4 bop 0 91 a Fi(2.4)112 b(Ev)m(ery)37 b(separation)h(is)f (diagonalization?)0 263 y Fu(P)m(artly)e(in)f(resp)s(onse)h(to)h(the)f (relativization)g(w)m(ork)g(of)g(Bak)m(er,)k(Gill)33 b(and)i(Solo)m(v)-5 b(a)m(y)36 b([BGS75)q(],)h(Kozen)f([Koz80)r(])0 376 y(to)s(ok)25 b(a)g(di\013eren)m(t)e(tact.)41 b(He)25 b(argued)f(that)h(an)m(y)f(pro)s(of)g(of)g(sa)m(y)h Fk(P)h Fe(6)p Fu(=)f Fk(NP)g Fu(w)m(ould)e(b)s(e)g(a)i(pro)s(of)f(b)m(y)g (diagonalization.)141 489 y(Let)f Fl(M)384 503 y Fh(1)424 489 y Fl(;)15 b(:)g(:)g(:)23 b Fu(b)s(e)f(an)h(en)m(umeration)f(of)g (the)h(p)s(olynomial-time)d(computable)h(mac)m(hines.)38 b(Let)23 b Fl(h)g Fu(b)s(e)e(a)i(function)0 602 y(mapping)29 b(\006)440 569 y Fb(\003)509 602 y Fu(to)i(the)g(natural)e(n)m(um)m(b)s (ers.)40 b(W)-8 b(e)31 b(de\014ne)f Fk(diag)2108 624 y Fj(h)2183 602 y Fu(as)1326 806 y Fk(diag)1518 828 y Fj(h)1588 806 y Fu(=)25 b Fe(f)p Fl(x)30 b Fe(j)h Fl(M)1955 824 y Fj(h)p Fh(\()p Fj(x)p Fh(\))2095 806 y Fu(\()p Fl(x)p Fu(\))g(rejects)p Fe(g)p Fl(:)0 1010 y Fu(Kozen)g(notes)g(that)g (either)e(of)i(the)g(follo)m(wing)d(t)m(w)m(o)k(conditions)d(guaran)m (tee)j(that)f Fk(diag)3027 1032 y Fj(h)3102 1010 y Fu(is)e(not)i(in)e Fk(P)p Fu(.)111 1198 y(1.)46 b(F)-8 b(or)31 b(all)f Fl(L)g Fu(in)f Fk(P)i Fu(there)f(is)g(some)g Fl(x)h Fu(suc)m(h)f(that)h Fl(L)25 b Fu(=)g Fl(L)p Fu(\()p Fl(M)2221 1216 y Fj(h)p Fh(\()p Fj(x)p Fh(\))2361 1198 y Fu(\).)111 1385 y(2.)46 b(F)-8 b(or)33 b(all)d Fl(L)i Fu(in)f Fk(P)h Fu(there)g(is)f Fl(L)1213 1352 y Fb(0)1267 1385 y Fu(suc)m(h)h(that)g Fl(L)1734 1352 y Fb(0)1789 1385 y Fu(and)f Fl(L)h Fu(di\013er)e(in)h (\014nitely)f(man)m(y)i(places)f(and)g(for)h(in\014nitely)227 1498 y(man)m(y)f Fl(x)p Fu(,)f Fl(L)644 1465 y Fb(0)693 1498 y Fu(=)25 b Fl(L)p Fu(\()p Fl(M)974 1517 y Fj(h)p Fh(\()p Fj(x)p Fh(\))1113 1498 y Fu(\).)0 1711 y Fk(Theorem)34 b(2.3)h(\(Kozen\))46 b Fg(F)-7 b(or)31 b(any)g(c)-5 b(omputable)32 b(set)f Fl(B)k Fg(not)c(in)f Fk(P)h Fg(ther)-5 b(e)31 b(exists)g(a)f(c)-5 b(omputable)32 b Fl(h)f Fg(such)g(that)0 1824 y Fl(B)f Fu(=)25 b Fk(diag)386 1846 y Fj(h)431 1824 y Fg(.)42 b(Mor)-5 b(e)g(over,)34 b Fl(h)e Fg(c)-5 b(an)34 b(b)-5 b(e)32 b(chosen)i(to)f(me)-5 b(et)33 b(b)-5 b(oth)34 b(of)f(the)g(c)-5 b(onditions)34 b(ab)-5 b(ove.)0 2036 y Fu(In)34 b(particular)g(if)g Fk(P)g Fe(6)p Fu(=)f Fk(NP)i Fu(then)g(w)m(e)h(can)f(tak)m(e)i Fl(B)h Fu(=)32 b Fk(SA)-9 b(T)36 b Fu(in)e(Theorem)g(2.3.)57 b(An)m(y)35 b(pro)s(of)f(that)i Fk(P)e Fe(6)p Fu(=)f Fk(NP)0 2149 y Fu(w)m(ould)24 b(imply)f(a)i(pro)s (of)g(of)g(the)g(existence)h(of)f(an)g Fl(h)g Fu(ful\014lling)c(the)26 b(conditions)d(ab)s(o)m(v)m(e)j(suc)m(h)f(that)h Fk(SA)-9 b(T)25 b Fu(=)g Fk(diag)3830 2171 y Fj(h)3875 2149 y Fu(.)141 2262 y(I)30 b(b)s(eliev)m(e)g(this)f(result)g(sa)m(ys)i(more)f (ab)s(out)g(the)h(di\016cult)m(y)d(of)j(exactly)g(formalizing)d(the)j (notion)e(of)i(a)g(\\diag-)0 2375 y(onalization)e(pro)s(of)7 b(")30 b(than)g(of)h(actually)f(arguing)f(the)h(diagonalization)g(tec)m (hnique)g(is)f(the)h(only)g(tec)m(hnique)f(w)m(e)0 2488 y(ha)m(v)m(e)j(for)e(class)g(separation.)0 2731 y Fi(2.5)112 b(Separations)38 b(against)g(non)m(uniform)f(classes)0 2903 y Fu(Diagonalizing)k(against)i(non)m(uniform)d(classes)i(app)s (ears)f(quite)h(di\016cult.)74 b(One)41 b(could)h(use)f(some)i(input)d (to)0 3016 y(diagonalize)30 b(against)g(a)h(particular)e(circuit.)39 b(Unfortunately)30 b(w)m(e)h(usually)d(ha)m(v)m(e)j(more)g(circuits)e (than)h(inputs.)141 3129 y(Kannan)h([Kan82)q(])h(giv)m(es)h(an)f(in)m (teresting)f(strategy)j(for)d(sho)m(wing)h(that)g(some)h(classes)f(do)g (not)g(ha)m(v)m(e)h(small)0 3242 y(circuits.)0 3429 y Fk(Theorem)h(2.4)h(\(Kannan\))107 3617 y Fg(1.)46 b(F)-7 b(or)34 b(any)f(\014xe)-5 b(d)34 b Fl(k)s Fg(,)e(ther)-5 b(e)34 b(is)e(a)h(language)g(in)g Fu(\006)1846 3573 y Fj(p)1846 3643 y Fh(2)1905 3617 y Fe(\\)20 b Fu(\005)2054 3573 y Fj(p)2054 3643 y Fh(2)2127 3617 y Fg(not)33 b(c)-5 b(omputable)34 b(in)f Fl(n)2923 3584 y Fj(k)2965 3617 y Fg(-size)f(cir)-5 b(cuits.)107 3805 y(2.)46 b(Ther)-5 b(e)34 b(is)e(a)h(language)g(in)g Fu(\006)1217 3772 y Fa(E)1217 3829 y Fh(4)1294 3805 y Fe(\\)20 b Fu(\005)1443 3772 y Fa(E)1443 3829 y Fh(4)1533 3805 y Fg(not)33 b(c)-5 b(omputable)35 b(by)d Fu(2)2326 3772 y Fj(o)p Fh(\()p Fj(n)p Fh(\))2463 3805 y Fg(-size)g(cir)-5 b(cuits.)107 3992 y(3.)46 b(Ther)-5 b(e)34 b(is)e(a)h(language)g(in)g Fu(\006)1217 3959 y Fa(E)1217 4017 y Fh(2)1294 3992 y Fe(\\)20 b Fu(\005)1443 3959 y Fa(E)1443 4017 y Fh(2)1533 3992 y Fg(not)33 b(c)-5 b(omputable)35 b(by)d(p)-5 b(olynomial-size)35 b(cir)-5 b(cuits.)0 4180 y Fu(The)30 b(class)g(\006)466 4147 y Fa(E)466 4208 y Fj(k)553 4180 y Fu(represen)m(ts)h(the)f(2)1183 4147 y Fj(O)r Fh(\()p Fj(n)p Fh(\))1371 4180 y Fu(v)m(ersion)g(of)h (\006)1850 4136 y Fj(p)1850 4209 y(k)1892 4180 y Fu(.)0 4392 y Fk(Pro)s(of:)71 b Fu(W)-8 b(e)31 b(will)d(giv)m(e)j(the)f(pro)s (of)g(for)g(the)h(\014rst.)40 b(The)30 b(other)g(t)m(w)m(o)i(are)f (similar.)141 4505 y(Fix)40 b Fl(k)s Fu(.)72 b(Consider)39 b(the)i(set)g(of)g(strings)e Fl(L)i Fu(consisting)e(of)i Fl(x)g Fu(accepted)h(b)m(y)e(the)h(lexicographically)e(least)0 4618 y(circuit)33 b(of)h(size)h Fl(n)626 4585 y Fj(k)r Fh(+1)792 4618 y Fu(that)g(is)e(di\013eren)m(t)h(from)g(all)f(circuits) g(of)i(size)f Fl(n)2462 4585 y Fj(k)2504 4618 y Fu(.)52 b(Simple)32 b(coun)m(ting)i(argumen)m(ts)h(sho)m(w)0 4731 y(that)c(suc)m(h)f(circuits)f(m)m(ust)h(exist.)41 b(This)28 b(expression)h(can)i(b)s(e)f(form)m(ulated)g(in)f(\006)2765 4687 y Fj(p)2765 4757 y Fh(4)2804 4731 y Fu(.)141 4844 y(T)-8 b(o)31 b(get)h(a)f(separation)g(at)g(the)g(second)g(lev)m(el)f (of)h(the)g(hierarc)m(h)m(y)f(w)m(e)h(use)g(a)g(nonconstructiv)m(e)f (argumen)m(t.)42 b(If)0 4957 y Fk(SA)-9 b(T)30 b Fu(do)s(es)f(not)h(ha) m(v)m(e)h Fl(n)860 4924 y Fj(k)932 4957 y Fu(size)e(circuits)f(than)i (the)g(result)e(follo)m(ws.)40 b(Otherwise)28 b(b)m(y)i(Karp)f(and)g (Lipton)f([KL80)q(])0 5070 y(the)j(en)m(tire)f(p)s(olynomial-time)e (hierarc)m(h)m(y)i(and)f(th)m(us)h Fl(L)h Fu(is)e(con)m(tained)i(in)e (\006)2630 5026 y Fj(p)2630 5096 y Fh(2)2689 5070 y Fe(\\)20 b Fu(\005)2838 5026 y Fj(p)2838 5096 y Fh(2)2878 5070 y Fu(.)40 b Fc(\003)141 5183 y Fu(Is)34 b(this)e(pro)s(of)h(a)i (diagonalization)e(argumen)m(t)h(or)g(really)e(a)j(simple)d(com)m (binatorial)g(argumen)m(t?)52 b(It)34 b(is)f(not)0 5296 y(clear)d(and)g(an)g(informal)f(surv)m(ey)h(of)g(fello)m(w)g(complexit) m(y)g(theorists)g(ga)m(v)m(e)j(a)d(mixed)g(resp)s(onse.)p eop %%Page: 6 6 6 5 bop 0 91 a Fi(2.6)112 b(Nonrelativizing)34 b(Separations)0 263 y Fu(Buhrman,)e(F)-8 b(ortno)m(w)34 b(and)e(Thierauf)f([BFT98)q(])i (giv)m(e)g(the)g(\014rst)f(separation)g(result)g(that)h(do)s(es)f(not)h (relativize.)0 376 y(Consider)25 b(the)i(class)g Fk(MA)917 390 y Fa(EXP)1118 376 y Fu(that)g(consists)g(of)g(languages)g(pro)m(v)m (en)g(b)m(y)g(an)g(in)m(teractiv)m(e)g(pro)s(of)f(system)h(where)0 489 y(the)k(pro)m(v)m(er)f(sends)g(a)h(single)e(message)i(to)g(a)g (probabilistic)c(exp)s(onen)m(tial-time)i(v)m(eri\014er.)0 701 y Fk(Theorem)34 b(2.5)h(\(Buhrman-F)-9 b(ortno)m(w-Thierauf)10 b(\))107 889 y Fg(1.)46 b(Ther)-5 b(e)34 b(exists)f(a)g(language)g(in)f Fk(MA)1480 903 y Fa(EXP)1687 889 y Fg(that)i(do)-5 b(es)34 b(not)f(have)g(p)-5 b(olynomial-size)35 b(cir)-5 b(cuits.)107 1077 y(2.)46 b(Ther)-5 b(e)28 b(exists)f(a)g(r)-5 b(elativize)g(d)28 b(world)g(wher)-5 b(e)28 b(every)e(language)h(in)g Fk(MA)2597 1091 y Fa(EXP)2798 1077 y Fg(has)h(p)-5 b(olynomial-size)29 b(cir)-5 b(cuits.)0 1289 y Fk(Pro)s(of)29 b(of)g(Theorem)e(2.5\(1\):)57 b Fu(Assume)24 b(that)h Fk(MA)1885 1303 y Fa(EXP)2084 1289 y Fu(has)f(p)s(olynomial-size)e(circuits.)38 b(This)23 b(implies)e(that)0 1402 y Fk(EXP)32 b Fu(has)g(p)s(olynomial-size)e (circuits)h(and)h(th)m(us)g(that)g Fk(EXP)d Fu(=)f Fk(MA)33 b Fu([BFL91)q(].)47 b(W)-8 b(e)33 b(then)f(ha)m(v)m(e)i(\006)3555 1358 y Fj(p)3555 1428 y Fh(2)3623 1402 y Fe(\022)28 b Fk(MA)0 1515 y Fu(and)33 b(b)m(y)g(translation)g(that)h(\006)1039 1482 y Fa(EXP)1039 1539 y Fh(2)1243 1515 y Fe(\022)d Fk(MA)1523 1529 y Fa(EXP)1697 1515 y Fu(.)50 b(This)32 b(con)m(tradicts)i(Kannan's)f(result)f([Kan82)q(])i(that)g(\006)3726 1482 y Fa(EXP)3726 1539 y Fh(2)0 1628 y Fu(do)s(es)c(not)h(ha)m(v)m(e)g (p)s(olynomial-size)d(circuits.)39 b Fc(\003)141 1741 y Fu(The)23 b(pro)s(of)g(do)s(es)h(not)g(relativize)f(b)s(ecause)g(it)g (relies)g(on)g(the)h(result)f(of)h(Babai,)h(F)-8 b(ortno)m(w)25 b(and)e(Lund)f([BFL91)r(])0 1854 y(that)f Fk(EXP)g Fu(has)g(p)s (olynomial-size)d(circuits)h(implies)f Fk(EXP)25 b Fu(=)g Fk(MA)c Fu(whic)m(h)f(follo)m(ws)f(from)i(their)e(nonrelativizing)0 1967 y(pro)s(of)30 b(of)g Fk(MIP)c Fu(=)f Fk(NEXP)p Fu(.)141 2079 y(This)j(pro)s(of)h(sho)m(ws)g(that)h(one)g(can)g(get)h (nonrelativizing)c(diagonalization)h(argumen)m(ts)i(b)m(y)f(using)g (nonrela-)0 2192 y(tivizing)g(collapses.)0 2479 y Fv(3)135 b(Approac)l(hes)44 b(to)i(separating)g(L)f(from)g(NP)0 2682 y Fu(While)37 b(the)h Fk(P)h Fe(6)p Fu(=)e Fk(NP)i Fu(question)e(remains)g(quite)g(formidable,)i(the)f Fk(L)g Fe(6)p Fu(=)g Fk(NP)g Fu(question)f(seem)i(m)m(uc)m(h)f(more)0 2795 y(tractable.)62 b(W)-8 b(e)39 b(ha)m(v)m(e)f(no)g(reason)f(to)h (think)e(this)g(question)h(is)f(di\016cult.)60 b(The)37 b(lac)m(k)g(of)h(go)s(o)s(d)f(relativization)0 2908 y(mo)s(dels)27 b(for)i(space)g(means)g(w)m(e)g(ha)m(v)m(e)h(no)f(meaningful)e(oracle)i (mo)s(del)e(where)i Fk(L)f Fu(and)g Fk(NP)h Fu(collapse.)40 b(Also)29 b(since)0 3020 y Fk(L)h Fu(is)g(a)g(uniform)f(class,)h(the)g (Razb)s(oro)m(v-Rudic)m(h)g([RR97)q(])h(limitations)d(do)i(not)h(apply) -8 b(.)141 3133 y(In)30 b(this)f(section)i(w)m(e)f(giv)m(e)h(four)f (di\013eren)m(t)g(approac)m(hes)h(to)g(attac)m(k)i(this)c(problem.)0 3377 y Fi(3.1)112 b(Autoreducibilit)m(y)0 3548 y Fu(T)-8 b(rakh)m(ten)m(brot)30 b([T)-8 b(ra70a)r(])30 b(\014rst)f(lo)s(ok)m(ed) g(at)i(autoreducibilit)m(y)c(in)h(the)i(computabilit)m(y)e(setting)h (as)h(a)g(measure)g(of)0 3661 y(redundancy)h(in)h(a)i(set.)49 b(Buhrman,)33 b(F)-8 b(ortno)m(w,)35 b(v)-5 b(an)33 b(Melk)m(eb)s(eek)h (and)e(T)-8 b(oren)m(vliet)33 b([BFvMT00)r(])g(sho)m(w)m(ed)g(that)0 3774 y(in)c(the)i(complexit)m(y)f(setting)g(autoreducibilit)m(y)e(ma)m (y)j(help)e(separate)i(complexit)m(y)f(classes.)141 3887 y(A)43 b(set)h Fl(A)e Fu(is)g(autoreducible)g(if)g(there)h(exists)f(an) h(oracle)g(p)s(olynomial-time)e(T)-8 b(uring)41 b(mac)m(hine)h Fl(M)53 b Fu(suc)m(h)0 4000 y(that)40 b Fl(L)p Fu(\()p Fl(M)401 3967 y Fj(A)458 4000 y Fu(\))g(=)f Fl(A)g Fu(with)f(the)h (restriction)f(that)i(for)e(all)g Fl(x)p Fu(,)k Fl(M)2280 3967 y Fj(A)2337 4000 y Fu(\()p Fl(x)p Fu(\))d(do)s(es)g(not)g(query)g (whether)f Fl(x)h Fu(is)f(in)g Fl(A)p Fu(.)0 4113 y(Buhrman,)30 b(F)-8 b(ortno)m(w,)33 b(v)-5 b(an)31 b(Melk)m(eb)s(eek)g(and)g(T)-8 b(oren)m(vliet)30 b(sho)m(w)h(a)h(relationship)c(b)s(et)m(w)m(een)k (complete)f(sets)h(and)0 4226 y(autoreducibilit)m(y)-8 b(.)0 4438 y Fk(Theorem)34 b(3.1)h(\(Buhrman-F)-9 b(ortno)m(w-v)j(an)34 b(Melk)m(eb)s(eek-T)-9 b(oren)m(vliet\))107 4626 y Fg(1.)46 b(If)33 b(every)f(T)-7 b(uring-c)i(omplete)34 b(set)e(for)i Fk(EXPSP)-9 b(A)m(CE)33 b Fg(is)f(autor)-5 b(e)g(ducible)34 b(then)f Fk(NL)25 b Fe(6)p Fu(=)g Fk(NP)q Fg(.)107 4814 y(2.)46 b(If)29 b(every)g(nonadaptively-T)-7 b(uring-c)i(omplete)31 b(set)e(for)h Fk(PSP)-9 b(A)m(CE)29 b Fg(is)g(nonadaptively)i(autor)-5 b(e)g(ducible)30 b(then)227 4927 y Fk(NL)25 b Fe(6)p Fu(=)g Fk(NP)p Fg(.)141 5139 y Fu(Assuming)42 b Fk(NL)47 b Fu(=)g Fk(NP)c Fu(Buhrman,)j(F)-8 b(ortno)m(w,)48 b(v)-5 b(an)44 b(Melk)m(eb)s(eek)g(and)f(T)-8 b(oren)m(vliet)43 b(create)i(a)f(series)f(of)0 5252 y(constructions)30 b(to)h(get)g(an)g Fl(A)f Fu(suc)m(h)g(that)p eop %%Page: 7 7 7 6 bop 111 91 a Fu(1.)46 b Fl(A)31 b Fu(is)e(in)g Fk(EXPSP)-9 b(A)m(CE)q Fu(,)111 279 y(2.)46 b Fl(A)31 b Fu(is)e(T)-8 b(uring-hard)28 b(for)i Fk(EXPSP)-9 b(A)m(CE)31 b Fu(and)111 467 y(3.)46 b Fl(A)31 b Fu(\\diagonalizes")f(against)h(all)e(p)s (ossible)f(autoreductions.)141 654 y(They)f(also)h(giv)m(e)g (autoreductions)f(for)g(the)h Fk(EXP)p Fu(-complete)g(sets)g(and)f (complete)h(sets)g(for)g(some)g(classes)f(in)0 767 y(the)d(exp)s(onen)m (tial-time)f(hierarc)m(h)m(y)-8 b(.)38 b(These)24 b(autoreductions)f (use)g(game)i(c)m(haracterizations)g(of)f(classes)g(creating)0 880 y(a)30 b(con)m(test)h(b)s(et)m(w)m(een)g(a)e(pla)m(y)m(er)h(trying) f(to)h(sho)m(w)g(a)g(string)e Fl(x)i Fu(is)e(in)g(a)i(set)h Fl(A)e Fu(and)g(a)h(pla)m(y)m(er)g(trying)f(to)h(sho)m(w)f(that)0 993 y Fl(x)h Fu(is)f(not)h(in)f Fl(A)p Fu(.)41 b(Earlier)28 b(Beigel)i(and)f(F)-8 b(eigen)m(baum)31 b([BF92)r(])f(used)f(a)h (di\013eren)m(t)g(tec)m(hnique)g(to)g(sho)m(w)g(that)h(all)e(of)0 1106 y(the)i(T)-8 b(uring-complete)29 b(sets)i(for)f Fk(PSP)-9 b(A)m(CE)31 b Fu(are)g(autoreducible.)0 1349 y Fi(3.2)112 b(In)m(tersecting)36 b(Finite)g(Automata)0 1521 y Fu(Karak)m(ostas,)h(Lipton)c(and)g(Viglas)h([KL)-10 b(V00)q(])34 b(giv)m(e)h(an)f(in)m(teresting)f(approac)m(h)h(to)h(the)g Fk(L)c Fe(6)p Fu(=)g Fk(NP)k Fu(problem)d(b)m(y)0 1634 y(lo)s(oking)c(at)h(the)g(complexit)m(y)g(of)g(determining)d(whether)i (a)i(collection)e(of)h(\014nite)f(automata)i(accept)g(a)g(common)0 1747 y(string.)141 1860 y(Giv)m(en)25 b(a)g(\014nite)f(automaton)j(of)e Fl(s)f Fu(states)i(one)g(can)f(determine)f(whether)h(the)g(mac)m(hine)f (accepts)j(an)m(y)e(strings)0 1973 y(at)34 b(all)e(in)h Fl(O)s Fu(\()p Fl(s)p Fu(\))g(time)g(b)m(y)g(using)f(depth-\014rst)h (searc)m(h)h(to)g(determine)e(if)h(there)g(exists)g(a)h(path)f(from)g (the)h(initial)0 2085 y(state)42 b(to)f(an)f(accept)i(state.)73 b(If)40 b(w)m(e)h(are)g(giv)m(en)f Fl(k)k Fu(suc)m(h)c(automata,)45 b(w)m(e)c(can)g(\014rst)e(create)j(the)f(in)m(tersecting)0 2198 y(automaton)d(b)m(y)f(using)e(cross)i(pro)s(ducts)e(and)h(then)h (apply)e(depth-\014rst)h(searc)m(h)h(to)h(this)d(automata)k(in)c Fl(O)s Fu(\()p Fl(s)3822 2165 y Fj(k)3865 2198 y Fu(\))0 2311 y(time.)k(Karak)m(ostas,)27 b(Lipton)d(and)g(Vigas)h(sho)m(w)g (that)g(ev)m(en)h(small)d(impro)m(v)m(emen)m(ts)i(in)f(this)g(running)e (time)i(w)m(ould)0 2424 y(yield)29 b(complexit)m(y)h(class)g (separations.)0 2637 y Fk(Theorem)k(3.2)h(\(Karak)m (ostas-Lipton-Viglas\))45 b Fg(Supp)-5 b(ose)25 b(we)f(ar)-5 b(e)24 b(given)f Fl(k)j Fg(\014nite)d(automata)j(with)e Fl(s)f Fg(states)0 2750 y(and)34 b(one)e(additional)k(automaton)f(with) e Fl(t)f Fg(states.)43 b(L)-5 b(et)33 b Fl(L)f Fg(b)-5 b(e)33 b(the)g(interse)-5 b(ction)34 b(of)e(the)h(languages)h(ac)-5 b(c)g(epte)g(d)34 b(by)0 2863 y(these)f(automata.)107 3050 y(1.)46 b(If)33 b(we)f(c)-5 b(an)34 b(determine)f(whether)h Fl(L)e Fg(is)h(not)g(empty)h(in)e Fl(s)2165 3017 y Fj(o)p Fh(\()p Fj(k)r Fh(\))2297 3050 y Fl(t)g Fg(time)h(then)g Fk(L)25 b Fe(6)p Fu(=)g Fk(P)p Fg(.)107 3238 y(2.)46 b(If)33 b(we)f(c)-5 b(an)34 b(determine)f(whether)h Fl(L)e Fg(is)h(not)g(empty)h(with)f Fl(s)2251 3205 y Fj(o)p Fh(\()p Fj(k)r Fh(\))2383 3238 y Fl(t)p Fg(-size)f(cir)-5 b(cuits)32 b(then)h Fk(L)26 b Fe(6)p Fu(=)e Fk(NP)q Fg(.)0 3450 y Fu(The)h(pro)s(of)g(w)m(orks)g(b)m(y)h(assigning)e(\014nite)h (automata)i Fl(F)1865 3464 y Fh(1)1905 3450 y Fl(;)15 b(:)g(:)g(:)h(;)f(F)2164 3465 y Fj(k)2233 3450 y Fu(to)27 b(di\013eren)m(t)e(regions)g(of)h(the)f(w)m(ork)h(tap)s(e.)39 b(Eac)m(h)0 3563 y Fl(F)58 3577 y Fj(i)117 3563 y Fu(is)29 b(resp)s(onsible)e(for)j(c)m(hec)m(king)g(the)h(computation)f(when)f (the)h(head)g(is)f(in)g(its)g(region.)40 b(Eac)m(h)31 b Fl(F)3392 3577 y Fj(i)3451 3563 y Fu(has)e(to)i(k)m(eep)0 3676 y(trac)m(k)39 b(of)f(its)g(region)f(of)i(the)f(tap)s(e)g(and)f (the)i(curren)m(t)e(tap)s(e)i(head)e(lo)s(cation.)64 b(An)37 b(additional)f(automaton)k Fl(G)0 3789 y Fu(k)m(eeps)27 b(trac)m(k)g(of)g(the)f(input)e(tap)s(e.)40 b(With)26 b(appropriate)f(c)m(hoices)i(of)f Fl(s)g Fu(for)g(the)g(sizes)g(of)h (the)f Fl(F)3184 3803 y Fj(i)3239 3789 y Fu(and)g Fl(t)g Fu(for)g(the)g(size)0 3902 y(of)g Fl(G)p Fu(,)h(if)e(w)m(e)i(can)f (determine)g(that)g Fl(L)g Fu(is)g(not)g(empt)m(y)h(in)d Fl(s)1958 3869 y Fj(o)p Fh(\()p Fj(k)r Fh(\))2090 3902 y Fl(t)i Fu(time)f(then)h(w)m(e)h(ha)m(v)m(e)g Fk(L)f Fe(\022)e Fk(DTIME)p Fu(\()p Fl(n)3524 3869 y Fh(1+)p Fj(\017)3647 3902 y Fu(\))h Ff(\()g Fk(P)p Fu(.)141 4015 y(A)k(similar)e(pro)s(of)h(sho)m(ws)h(that)h(if)e(w)m(e)i(can)f (determine)f(whether)h Fl(L)g Fu(is)f(not)i(empt)m(y)f(with)f Fl(s)3246 3982 y Fj(o)p Fh(\()p Fj(k)r Fh(\))3377 4015 y Fl(t)p Fu(-size)h(circuits)0 4128 y(then)h Fk(L)g Fu(has)g Fl(n)517 4095 y Fh(1+)p Fj(\017)670 4128 y Fu(size)g(circuits.)39 b(If)30 b Fk(L)25 b Fu(=)g Fk(NP)31 b Fu(then)f Fk(L)25 b Fu(=)g(\006)2112 4084 y Fj(p)2112 4154 y Fh(2)2181 4128 y Fu(and)30 b(\006)2424 4084 y Fj(p)2424 4154 y Fh(2)2494 4128 y Fu(cannot)h(ha)m(v)m(e)g Fl(n)3056 4095 y Fj(k)3128 4128 y Fu(size)g(circuits)e(for)h(an)m(y)0 4241 y(\014xed)g Fl(k)j Fu([Kan82)q(].)141 4354 y(W)-8 b(e)23 b(ma)m(y)f(ha)m(v)m(e)h(trouble)d(applying)g(Theorem)h(3.2)h (directly)f(to)h(separate)g Fk(L)g Fu(from)f Fk(NP)g Fu(b)s(ecause)h(determining)0 4467 y(whether)k Fl(L)g Fu(is)g(not)h(empt)m(y)f(ma)m(y)i(just)e(b)s(e)f(a)i(di\016cult)e (problem.)38 b(Ho)m(w)m(ev)m(er,)29 b(to)f(separate)f Fk(L)f Fu(from)g Fk(NP)q Fu(,)h(w)m(e)g(need)0 4579 y(only)g(sho)m(w)h (a)h(quic)m(k)f(algorithm)f(for)h(c)m(hec)m(king)h(that)g Fl(L)f Fu(is)f(not)h(empt)m(y)h(under)e(the)h(assumption)f(that)h Fk(L)e Fu(=)e Fk(NP)q Fu(.)0 4692 y(There)30 b(w)m(e)h(ma)m(y)g(ha)m(v) m(e)g(more)g(hop)s(e.)0 4936 y Fi(3.3)112 b(Hardness)39 b(v)m(ersus)f(Randomness)0 5107 y Fu(Impagliazzo)43 b(and)f(Wigderson)g ([IW97)q(])h(sho)m(w)g(ho)m(w)f(to)i(completely)e(derandomize)g Fk(BPP)i Fu(using)d(a)i(strong)0 5220 y(hardness)22 b(assumption.)37 b(T)-8 b(rying)22 b(to)i(sho)m(w)f(this)f(or)i(ev)m(en)g(stronger)f (assumptions)f(false)h(can)g(lead)g(to)h(complexit)m(y)0 5333 y(separations.)p eop %%Page: 8 8 8 7 bop 0 91 a Fk(Theorem)34 b(3.3)h(\(Impagliazzo-Wigderson\))46 b Fg(If)30 b(ther)-5 b(e)31 b(exist)f(languages)h(in)f Fk(E)f Fg(that)j(c)-5 b(annot)31 b(b)-5 b(e)30 b(c)-5 b(ompute)g(d)0 204 y(by)32 b Fu(2)163 171 y Fj(o)p Fh(\()p Fj(n)p Fh(\))300 204 y Fg(-size)g(cir)-5 b(cuits)33 b(then)g Fk(P)26 b Fu(=)f Fk(BPP)q Fg(.)0 380 y Fu(This)34 b(is)h(a)h(w)m (onderful)e(derandomization)h(result|but)f(that)i(is)f(the)h(topic)g (of)g(another)g(surv)m(ey)-8 b(.)57 b(Instead)36 b(let)0 493 y(us)31 b(fo)s(cus)g(on)h(the)g(an)m(teceden)m(t.)47 b(The)31 b(an)m(teceden)m(t)j(seems)e(a)m(wfully)f(strong|It)h(is)e (imp)s(ossible)f(to)j(ha)m(v)m(e)h(a)g(v)m(ery)0 606 y(large)26 b(amoun)m(t)g(of)g(advice)g(to)g(giv)m(e)h(a)f(small)e (impro)m(v)m(emen)m(t)i(on)g(time.)39 b(Ho)m(w)m(ev)m(er,)29 b(pro)m(ving)c(it)g(false)h(w)m(ould)e(imply)0 719 y Fk(P)i Fe(6)p Fu(=)f Fk(NP)p Fu(.)0 895 y Fk(Theorem)34 b(3.4)46 b Fg(If)37 b Fk(P)c Fu(=)g Fk(NP)k Fg(then)g(ther)-5 b(e)38 b(exist)f(languages)g(in)g Fk(E)f Fg(that)i(c)-5 b(annot)39 b(b)-5 b(e)36 b(c)-5 b(ompute)g(d)39 b(by)e Fu(2)3587 862 y Fj(o)p Fh(\()p Fj(n)p Fh(\))3723 895 y Fg(-size)0 1008 y(cir)-5 b(cuits.)0 1184 y Fk(Pro)s(of:)78 b Fu(If)32 b Fk(P)f Fu(=)f Fk(NP)k Fu(then)f Fk(P)e Fu(=)f(\006)1322 1140 y Fj(p)1322 1210 y Fh(4)1394 1184 y Fu(and)j(b)m(y)g(translation)g Fk(E)d Fu(=)g(\006)2433 1151 y Fa(E)2433 1208 y Fh(4)2490 1184 y Fu(.)49 b(Ho)m(w)m(ev)m(er)36 b(b)m(y)d(Kannan)f([Kan82)q(],)j (\006)3843 1151 y Fa(E)3843 1208 y Fh(4)0 1297 y Fu(has)30 b(languages)h(that)g(require)e(2)1125 1264 y Fh(\012\()p Fj(n)p Fh(\))1278 1297 y Fu(-size)i(circuits.)39 b Fc(\003)141 1410 y Fu(A)29 b(similar)d(argumen)m(t)j(sho)m(ws)g(that)g(if)f(linear) f(space)i(has)f(small)g(circuits)f(w)m(e)i(can)g(get)h(w)m(eak)m(er)g (separations.)0 1586 y Fk(Theorem)k(3.5)46 b Fg(If)34 b Fk(L)29 b Fu(=)g Fk(NP)34 b Fg(then)h(ther)-5 b(e)36 b(exist)f(languages)g(in)f Fk(DSP)-9 b(A)m(CE)q Fu(\()p Fl(n)p Fu(\))34 b Fg(that)i(do)g(not)f(have)g Fu(2)3587 1553 y Fj(o)p Fh(\()p Fj(n)p Fh(\))3723 1586 y Fg(-size)0 1699 y(cir)-5 b(cuits.)0 1875 y Fu(It)30 b(remains)g(op)s(en)f(whether) h(ev)m(en)h Fk(SA)-9 b(T)25 b Fe(2)g Fk(NTIME)o Fu(\()p Fl(n)p Fu(\))h Fe(\022)f Fk(DSP)-9 b(A)m(CE)p Fu(\()p Fl(n)p Fu(\))31 b(can)f(b)s(e)g(computed)g(b)m(y)g(2)3591 1842 y Fj(o)p Fh(\()p Fj(n)p Fh(\))3728 1875 y Fu(-size)0 1988 y(circuits.)39 b(Ho)m(w)m(ev)m(er,)33 b(if)c Fk(SA)-9 b(T)30 b Fu(do)s(es)g(not)h(ha)m(v)m(e)g(small)e(circuits)g(then)h(w)m (e)h(already)f(kno)m(w)g Fk(L)25 b Fe(6)p Fu(=)g Fk(NP)p Fu(.)41 b(This)29 b(leads)0 2101 y(to)i(the)g(follo)m(wing)e(approac)m (h)h(to)h(separating)f(those)h(classes.)0 2277 y Fk(Theorem)j(3.6)46 b Fg(If)37 b(every)g(language)h(in)f Fk(DSP)-9 b(A)m(CE)p Fu(\()p Fl(n)p Fu(\))37 b Fg(has)h Fu(2)2258 2244 y Fj(o)p Fh(\()p Fj(n)p Fh(\))2395 2277 y Fg(-size)f(cir)-5 b(cuits)37 b(assuming)h(that)g Fk(SA)-9 b(T)37 b Fg(c)-5 b(an)0 2390 y(b)g(e)33 b(c)-5 b(ompute)g(d)34 b(in)f(p)-5 b(olynomial-size)35 b(cir)-5 b(cuits)33 b(then)g Fk(L)25 b Fe(6)p Fu(=)g Fk(NP)p Fg(.)0 2566 y Fu(One)31 b(can)g(think)e(of)j Fk(DSP)-9 b(A)m(CE)p Fu(\()p Fl(n)p Fu(\))31 b(as)g(linear)f (alternating)g(time.)43 b(W)-8 b(e)32 b(w)m(an)m(t)g(to)g(sim)m(ulate)e (linear)f(alternating)0 2679 y(time)24 b(with)f(sligh)m(tly)g(sub)s (exp)s(onen)m(tial)e(circuits)i(on)i(the)f(assumption)f(that)i(w)m(e)g (can)f(do)g(one)h(la)m(y)m(er)g(of)f(alternation)0 2792 y(in)29 b(p)s(olynomial-size)f(circuits.)0 3029 y Fi(3.4)112 b(Alternation,)36 b(Time)g(and)i(Space)0 3201 y Fu(A)c(recen)m(t)h (approac)m(h)f(lo)s(oks)f(at)i(using)d(collapses)i(on)f(mac)m(hines)h (of)g(small)e(alternations.)51 b(This)32 b(approac)m(h)i(has)0 3314 y(led)42 b(to)h(in)m(teresting)f(time-space)h(tradeo\013s)g(for)g (satis\014abilit)m(y)-8 b(.)75 b(Kannan)42 b([Kan84)q(])h(had)f(lo)s (ok)m(ed)g(at)i(similar)0 3427 y(tec)m(hniques)37 b(in)f(1984)j(follo)m (w)m(ed)d(b)m(y)i(more)f(recen)m(t)h(w)m(ork)f(b)m(y)h(F)-8 b(ortno)m(w)38 b([F)-8 b(or00)r(],)39 b(Lipton)d(and)h(Viglas)f([L)-10 b(V99)q(],)0 3540 y(T)i(ourlakis)29 b([T)-8 b(ou00)q(])31 b(and)e(F)-8 b(ortno)m(w)32 b(and)e(v)-5 b(an)30 b(Melk)m(eb)s(eek)h ([FvM00)r(].)141 3653 y(W)-8 b(e)32 b(giv)m(e)f(an)f(easy)h(example)f (sho)m(wing)f(time-space)i(trade-o\013s)h(on)e(\006)2558 3620 y Fj(n)2558 3677 y Fh(2)2635 3653 y Fu(time.)0 3810 y Fk(Theorem)k(3.7)h(\(F)-9 b(ortno)m(w-v)j(an)35 b(Melk)m(eb)s(eek\)) 45 b Fg(Ther)-5 b(e)41 b(exists)f(a)h(language)f(in)g Fu(\006)3009 3777 y Fj(n)3009 3834 y Fh(2)3095 3810 y Fg(that)h(c)-5 b(annot)42 b(b)-5 b(e)39 b(c)-5 b(om-)0 3923 y(pute)g(d)34 b(by)e(any)h(deterministic)h(r)-5 b(andom-ac)g(c)g(ess)35 b(T)-7 b(uring-machine)33 b(using)g Fl(n)2640 3890 y Fh(1)p Fj(:)p Fh(99)2801 3923 y Fg(time)g(and)h Fl(O)s Fu(\(log)16 b Fl(n)p Fu(\))33 b Fg(sp)-5 b(ac)g(e.)0 4080 y Fk(Pro)s(of)42 b(Sk)m(etc)m(h:)83 b Fu(Supp)s(ose)34 b(the)i(theorem)h(is)e(false.)57 b(By)36 b(translation)f(w)m(e)h(ha)m (v)m(e)h(ev)m(ery)g(language)f Fl(L)g Fu(in)f(\006)3819 4047 y Fj(n)3862 4024 y Fn(2)3819 4104 y Fh(2)0 4193 y Fu(accepted)d(b)m(y)e(a)h(deterministic)d(T)-8 b(uring-mac)m(hine)29 b Fl(M)40 b Fu(using)29 b Fl(n)2195 4160 y Fh(3)p Fj(:)p Fh(98)2355 4193 y Fu(time)h(and)f Fl(O)s Fu(\(log)17 b Fl(n)p Fu(\))30 b(space.)141 4324 y(W)-8 b(e)37 b(will)d(sim)m(ulate) h Fl(M)46 b Fu(b)m(y)36 b(a)g(\006)1261 4280 y Fj(n)1304 4256 y Fn(1)p Fd(:)p Fn(99)1430 4280 y Fh(log)13 b Fj(n)1261 4350 y Fh(2)1616 4324 y Fu(mac)m(hine)35 b(violating)g(the)h(\006)2587 4338 y Fh(2)2626 4324 y Fu(-time)g(hierarc)m(h)m(y)g(whic)m(h)f(is)g (pro)m(v)m(en)0 4437 y(similarly)20 b(to)j(Theorem)g(2.1.)39 b(Nondeterministically)20 b(guess)j(the)g(con\014gurations)f(of)h Fl(M)33 b Fu(at)24 b(the)f(time)g(step)g Fl(in)3771 4404 y Fh(1)p Fj(:)p Fh(99)0 4550 y Fu(for)32 b(0)d Fe(\024)f Fl(i)h Fe(\024)f Fl(n)528 4517 y Fh(1)p Fj(:)p Fh(99)658 4550 y Fu(.)46 b(Univ)m(ersally)31 b(pic)m(k)h(an)g Fl(i)d(<)f(n)1743 4517 y Fh(1)p Fj(:)p Fh(99)1904 4550 y Fu(and)k(deterministically)d(c)m (hec)m(k)34 b(that)f(the)g(con\014guration)0 4663 y(at)e(time)f Fl(in)404 4630 y Fh(1)p Fj(:)p Fh(99)564 4663 y Fu(can)h(go)g(to)g (con\014guration)f(\()p Fl(i)21 b Fu(+)f(1\))p Fl(n)1827 4630 y Fh(1)p Fj(:)p Fh(99)1956 4663 y Fu(.)41 b Fc(\003)141 4775 y Fu(Similar)26 b(tec)m(hniques)i(sho)m(w)g(that)h(\006)1380 4742 y Fj(n)1380 4803 y(k)1455 4775 y Fu(requires)e(nearly)g Fl(n)2123 4742 y Fj(k)2194 4775 y Fu(deterministic)f(time)i(for)g (small)f(space-b)s(ounded)0 4888 y(mac)m(hines.)67 b(If)38 b(one)i(could)e(sho)m(w)h(that)h(for)f(some)g(\014xed)g Fl(k)s Fu(,)i(\006)2215 4855 y Fj(n)2215 4916 y(k)2301 4888 y Fu(requires)d Fl(n)2707 4855 y Fj(j)2782 4888 y Fu(time)h(for)g(all)f Fl(j)44 b Fu(then)39 b(w)m(e)h(ha)m(v)m(e)0 5001 y(separated)31 b Fk(L)f Fu(from)g Fk(NP)p Fu(.)141 5114 y(W)-8 b(e)44 b(can)f(also)g(use)g(these)g(ideas)f(to)i(get)g (time-space)f(tradeo\013s)h(for)e(satis\014abilit)m(y)-8 b(.)77 b(F)-8 b(ortno)m(w)44 b(and)e(v)-5 b(an)0 5227 y(Melk)m(eb)s(eek)33 b(building)c(on)j(the)h(earlier)f(pap)s(ers)f(sho) m(w)h(that)i(satis\014abilit)m(y)c(cannot)j(b)s(e)f(solv)m(ed)g(in)g Fl(n)3471 5194 y Fj(a)3544 5227 y Fu(time)h(and)0 5340 y Fl(n)55 5307 y Fj(o)p Fh(\(1\))213 5340 y Fu(space)e(for)f (random-access)i(T)-8 b(uring)28 b(mac)m(hines)i(for)g(an)m(y)h Fl(a)f Fu(less)g(than)g(the)h(golden)f(ration,)g(ab)s(out)g(1.618.)p eop %%Page: 9 9 9 8 bop 0 91 a Fv(4)135 b(Conclusions)0 294 y Fu(Diagonalization,)44 b(once)d(giv)m(en)g(up)f(for)h(dead,)i(has)e(returned)f(still)f(giving) g(us)i(new)f(and)g(in)m(teresting)h(lo)m(w)m(er)0 407 y(b)s(ounds.)c(While)26 b(the)h(actual)g(diagonalization)f(step)h (still)e(remains)h(easy)-8 b(,)28 b(w)m(e)g(ha)m(v)m(e)g(new)e(to)s (ols)h(and)f(tec)m(hniques)0 520 y(for)k(collapsing)f(classes.)41 b(As)30 b(w)m(e)h(ha)m(v)m(e)g(seen)g(in)e(this)g(surv)m(ey)-8 b(,)31 b(b)s(etter)f(collapses)g(lead)g(to)h(b)s(etter)g(separations.)0 807 y Fv(Ac)l(kno)l(w)l(eledgmen)l(ts)0 1009 y Fu(I)g(wish)e(to)i (thank)g(the)g(organizers)g(of)g(the)g(DIMA)m(CS)h(w)m(orkshop,)e(P)m (aul)h(Beame,)h(Stev)m(e)g(Rudic)m(h)e(and)g(Andrew)0 1122 y(Y)-8 b(ao,)38 b(for)c(in)m(viting)f(me)i(to)g(giv)m(e)g(the)g (talk.)54 b(I)35 b(also)g(thank)f(the)h(man)m(y)g(participan)m(ts)f(of) g(the)h(w)m(orkshop)g(whom)0 1235 y(I)d(had)g(commen)m(ts)h(and)f (discussions)d(relating)j(to)h(diagonalization.)46 b(I)32 b(also)g(thank)g(Bill)e(Gasarc)m(h)k(and)e(Dieter)0 1348 y(v)-5 b(an)30 b(Melk)m(eb)s(eek)h(for)f(man)m(y)h(helpful)c(commen)m (ts)32 b(on)e(this)f(man)m(uscript.)0 1635 y Fv(References)0 1838 y Fu([A)m(G94])232 b(E.)35 b(Allender)f(and)h(V.)h(Gore.)57 b(A)35 b(uniform)f(circuit)g(lo)m(w)m(er)i(b)s(ound)d(for)i(the)h(p)s (ermanen)m(t.)56 b Fg(SIAM)508 1950 y(Journal)33 b(on)g(Computing)p Fu(,)f(23:1026{1049,)k(1994.)0 2138 y([All99])248 b(E.)23 b(Allender.)28 b(The)c(p)s(ermanen)m(t)f(requires)f(large)i(uniform)e (threshold)g(circuits.)28 b Fg(Chic)-5 b(ago)28 b(Journal)508 2251 y(of)k(The)-5 b(or)g(etic)g(al)36 b(Computer)e(Scienc)-5 b(e)p Fu(,)30 b(1999\(7\),)j(August)e(1999.)0 2439 y([BF92])245 b(R.)30 b(Beigel)g(and)g(J.)g(F)-8 b(eigen)m(baum.)41 b(On)29 b(b)s(eing)g(incoheren)m(t)h(without)f(b)s(eing)g(v)m(ery)h (hard.)39 b Fg(Compu-)508 2552 y(tational)34 b(Complexity)p Fu(,)e(2\(1\):1{17,)j(1992.)0 2739 y([BFL91])188 b(L.)22 b(Babai,)i(L.)e(F)-8 b(ortno)m(w,)25 b(and)c(C.)h(Lund.)k (Non-deterministic)20 b(exp)s(onen)m(tial)h(time)h(has)g(t)m(w)m(o-pro) m(v)m(er)508 2852 y(in)m(teractiv)m(e)31 b(proto)s(cols.)40 b Fg(Computational)c(Complexity)p Fu(,)c(1\(1\):3{40,)i(1991.)0 3040 y([BFT98])179 b(H.)23 b(Buhrman,)h(L.)g(F)-8 b(ortno)m(w,)26 b(and)d(T.)h(Thierauf.)j(Nonrelativizing)22 b(separations.)29 b(In)23 b Fg(Pr)-5 b(o)g(c)g(e)g(e)g(dings)508 3153 y(of)35 b(the)h(13th)h(IEEE)d(Confer)-5 b(enc)g(e)37 b(on)f(Computational)i (Complexity)p Fu(,)e(pages)e(8{12.)i(IEEE,)d(New)508 3266 y(Y)-8 b(ork,)31 b(1998.)0 3453 y([BFvMT00])48 b(H.)25 b(Buhrman,)g(L.)g(F)-8 b(ortno)m(w,)27 b(D.)f(v)-5 b(an)25 b(Melk)m(eb)s(eek,)i(and)d(L.)h(T)-8 b(oren)m(vliet.)31 b(Using)24 b(autoreducibilit)m(y)508 3566 y(to)31 b(separate)g (complexit)m(y)f(classes.)41 b Fg(SIAM)32 b(Journal)h(on)g(Computing)p Fu(,)f(29\(5\):1497{1520,)37 b(2000.)0 3754 y([BGS75])182 b(T.)38 b(Bak)m(er,)43 b(J.)c(Gill,)g(and)f(R.)h(Solo)m(v)-5 b(a)m(y)d(.)68 b(Relativizations)38 b(of)h(the)g(P)g(=)f(NP)h (question.)66 b Fg(SIAM)508 3867 y(Journal)33 b(on)g(Computing)p Fu(,)f(4\(4\):431{442,)k(1975.)0 4054 y([Can74])206 b(G.)34 b(Can)m(tor.)52 b(Ueb)s(er)34 b(eine)f(Eigensc)m(haft)h(des)g(In)m(b)s (egri\013es)f(aller)g(reellen)g(algebraisc)m(hen)g(Zahlen.)508 4167 y Fg(Cr)-5 b(el)5 b(le's)33 b(Journal)p Fu(,)e(77:258{262,)k (1874.)0 4355 y([CMTV98])85 b(H.)30 b(Caussin)m(us,)e(P)-8 b(.)30 b(McKenzie,)h(D.)f(Th)m(\023)-43 b(erien,)30 b(and)f(H.)h(V)-8 b(ollmer.)39 b(Nondeterministic)28 b(NC)3639 4322 y Fh(1)3708 4355 y Fu(com-)508 4468 y(putation.)40 b Fg(Journal)33 b(of)g(Computer)h(and)g(System)f(Scienc)-5 b(es)p Fu(,)30 b(57\(2\):200{212,)36 b(Octob)s(er)31 b(1998.)0 4655 y([Co)s(o73])209 b(S.)28 b(Co)s(ok.)38 b(A)29 b(hierarc)m(h)m(y)f(for)h (nondeterministic)d(time)i(complexit)m(y)-8 b(.)38 b Fg(Journal)32 b(of)f(Computer)i(and)508 4768 y(System)g(Scienc)-5 b(es)p Fu(,)30 b(7\(4\):343{353,)36 b(August)30 b(1973.)0 4956 y([F)-8 b(or00])236 b(L.)33 b(F)-8 b(ortno)m(w.)49 b(Time-space)33 b(tradeo\013s)h(for)f(satis\014abilit)m(y)-8 b(.)46 b Fg(Journal)36 b(of)g(Computer)g(and)g(System)508 5069 y(Scienc)-5 b(es)p Fu(,)30 b(60\(2\):337{353,)36 b(April)28 b(2000.)p eop %%Page: 10 10 10 9 bop 0 91 a Fu([FvM00])178 b(L.)38 b(F)-8 b(ortno)m(w)39 b(and)f(D.)g(v)-5 b(an)38 b(Melk)m(eb)s(eek.)65 b(Time-space)38 b(tradeo\013s)h(for)f(nondeterministic)d(com-)508 204 y(putation.)j(In)29 b Fg(Pr)-5 b(o)g(c)g(e)g(e)g(dings)34 b(of)f(the)f(15th)i(IEEE)d(Confer)-5 b(enc)g(e)32 b(on)h(Computational) i(Complexity)p Fu(.)508 317 y(IEEE)29 b(Computer)h(So)s(ciet)m(y)-8 b(,)31 b(Los)g(Alamitos,)f(2000.)42 b(T)-8 b(o)31 b(app)s(ear.)0 505 y([HS65])249 b(J.)27 b(Hartmanis)g(and)g(R.)g(Stearns.)36 b(On)26 b(the)i(computational)f(complexit)m(y)h(of)f(algorithms.)35 b Fg(T)-7 b(r)i(ans-)508 618 y(actions)33 b(of)g(the)g(A)n(meric)-5 b(an)33 b(Mathematic)-5 b(al)35 b(So)-5 b(ciety)p Fu(,)31 b(117:285{306,)k(1965.)0 805 y([Iba72])239 b(O.)23 b(Ibarra.)29 b(A)24 b(note)g(concerning)f(nondeterministic)e(tap)s(e)j (complexities.)29 b Fg(Journal)e(of)g(the)g(A)n(CM)p Fu(,)508 918 y(19\(4\):608{612,)36 b(1972.)0 1106 y([Imm88])183 b(N.)28 b(Immerman.)35 b(Nondeterministic)26 b(space)i(is)f(closed)h (under)e(complemen)m(tation.)37 b Fg(SIAM)29 b(Jour-)508 1219 y(nal)k(on)g(Computing)p Fu(,)f(17\(5\):935{938,)k(1988.)0 1406 y([IW97])242 b(R.)25 b(Impagliazzo)h(and)f(A.)h(Wigderson.)32 b(P)25 b(=)g(BPP)h(if)e(E)i(requires)e(exp)s(onen)m(tial)g(circuits:)37 b(Deran-)508 1519 y(domizing)24 b(the)i(X)m(OR)h(lemma.)33 b(In)25 b Fg(Pr)-5 b(o)g(c)g(e)g(e)g(dings)31 b(of)e(the)g(29th)h(A)n (CM)e(Symp)-5 b(osium)30 b(on)f(the)g(The)-5 b(ory)508 1632 y(of)32 b(Computing)p Fu(,)g(pages)f(220{229.)j(A)m(CM,)d(New)g(Y) -8 b(ork,)31 b(1997.)0 1820 y([Kan82])201 b(R.)26 b(Kannan.)32 b(Circuit-size)24 b(lo)m(w)m(er)i(b)s(ounds)e(and)h(non-reducibilit)m (y)e(to)j(sparse)g(sets.)34 b Fg(Information)508 1933 y(and)f(Contr)-5 b(ol)p Fu(,)33 b(55:40{56,)h(1982.)0 2120 y([Kan84])201 b(R.)41 b(Kannan.)72 b(T)-8 b(o)m(w)m(ards)41 b(separating)g(nondeterminism)e(from)h(determinism.)71 b Fg(Mathematic)-5 b(al)508 2233 y(Systems)33 b(The)-5 b(ory)p Fu(,)32 b(17\(1\):29{45,)j(April)28 b(1984.)0 2421 y([KL80])240 b(R.)21 b(Karp)f(and)g(R.)h(Lipton.)j(Some)d (connections)g(b)s(et)m(w)m(een)h(non)m(uniform)c(and)i(uniform)f (complexit)m(y)508 2534 y(classes.)25 b(In)20 b Fg(Pr)-5 b(o)g(c)g(e)g(e)g(dings)26 b(of)f(the)f(12th)i(A)n(CM)c(Symp)-5 b(osium)26 b(on)f(the)f(The)-5 b(ory)26 b(of)e(Computing)p Fu(,)g(pages)508 2647 y(302{309.)33 b(A)m(CM,)f(New)e(Y)-8 b(ork,)31 b(1980.)0 2834 y([KL)-10 b(V00])182 b(G.)25 b(Karak)m(ostas,)j(R.)d(Lipton,)g(and)g(A.)g(Viglas.)31 b(On)25 b(the)g(complexit)m(y)g(of)g(in)m(tersecting)g(\014nite)f (state)508 2947 y(automata.)34 b(In)25 b Fg(Pr)-5 b(o)g(c)g(e)g(e)g (dings)31 b(of)d(the)h(15th)h(IEEE)d(Confer)-5 b(enc)g(e)29 b(on)g(Computational)i(Complexity)p Fu(.)508 3060 y(IEEE)e(Computer)h (So)s(ciet)m(y)-8 b(,)31 b(Los)g(Alamitos,)f(2000.)42 b(T)-8 b(o)31 b(app)s(ear.)0 3248 y([Koz80])212 b(D.)35 b(Kozen.)55 b(Indexings)34 b(of)h(subrecursiv)m(e)e(classes.)55 b Fg(The)-5 b(or)g(etic)g(al)40 b(Computer)e(Scienc)-5 b(e)p Fu(,)36 b(11:277{)508 3361 y(301,)31 b(1980.)0 3548 y([Lad75])215 b(R.)37 b(Ladner.)61 b(On)36 b(the)i(structure)f(of) g(p)s(olynomial)e(time)i(reducibilit)m(y)-8 b(.)58 b Fg(Journal)40 b(of)g(the)f(A)n(CM)p Fu(,)508 3661 y(22:155{171,)34 b(1975.)0 3849 y([L)-10 b(V99])253 b(R.)28 b(Lipton)f(and)h(A.)h (Viglas.)37 b(On)27 b(the)i(complexit)m(y)f(of)h(SA)-8 b(T.)37 b(In)27 b Fg(Pr)-5 b(o)g(c)g(e)g(e)g(dings)33 b(of)e(the)h(40th)g(IEEE)508 3962 y(Symp)-5 b(osium)41 b(on)f(F)-7 b(oundations)42 b(of)d(Computer)i(Scienc)-5 b(e)p Fu(,)39 b(pages)g(459{464.)i(IEEE,)c(New)h(Y)-8 b(ork,)508 4075 y(1999.)0 4262 y([RR97])234 b(A.)21 b(Razb)s(oro)m(v)g (and)g(S.)f(Rudic)m(h.)k(Natural)c(pro)s(ofs.)k Fg(Journal)h(of)f (Computer)i(and)e(System)h(Scienc)-5 b(es)p Fu(,)508 4375 y(55\(1\):24{35,)35 b(August)30 b(1997.)0 4563 y([Sa)m(v70])227 b(W.)41 b(Sa)m(vitc)m(h.)72 b(Relationship)39 b(b)s(et)m(w)m(een)i (nondeterministic)e(and)h(deterministic)f(tap)s(e)i(classes.)508 4676 y Fg(Journal)33 b(of)g(Computer)h(and)g(System)f(Scienc)-5 b(es)p Fu(,)30 b(4:177{192,)35 b(1970.)0 4863 y([SFM78])175 b(J.)34 b(Seiferas,)i(M.)f(Fisc)m(her,)h(and)f(A.)g(Mey)m(er.)55 b(Separating)34 b(nondeterministic)f(time)h(complexit)m(y)508 4976 y(classes.)40 b Fg(Journal)34 b(of)f(the)g(A)n(CM)p Fu(,)c(25\(1\):146{167,)36 b(1978.)0 5164 y([Sze88])237 b(R.)36 b(Szelep)s(cs)m(\023)-43 b(en)m(yi.)58 b(The)36 b(metho)s(d)g(of)h(forced)f(en)m(umeration)g(for)g(nondeterministic)e (automata.)508 5277 y Fg(A)-5 b(cta)33 b(Informatic)-5 b(a)p Fu(,)32 b(26:279{284,)j(1988.)p eop %%Page: 11 11 11 10 bop 0 91 a Fu([T)-8 b(ou00])214 b(I.)43 b(T)-8 b(ourlakis.)80 b(Time-space)43 b(lo)m(w)m(er)i(b)s(ounds)c(for)j(SA)-8 b(T)43 b(on)h(uniform)e(and)h(non-uniform)e(ma-)508 204 y(c)m(hines.)64 b(In)37 b Fg(Pr)-5 b(o)g(c)g(e)g(e)g(dings)42 b(of)f(the)f(15th)i(IEEE)d(Confer)-5 b(enc)g(e)40 b(on)h(Computational) i(Complexity)p Fu(.)508 317 y(IEEE)29 b(Computer)h(So)s(ciet)m(y)-8 b(,)31 b(Los)g(Alamitos,)f(2000.)42 b(T)-8 b(o)31 b(app)s(ear.)0 505 y([T)-8 b(ra70a])184 b(B.)29 b(T)-8 b(rakh)m(ten)m(brot.)38 b(On)27 b(autoreducibilit)m(y)-8 b(.)36 b Fg(Doklady)c(A)n(kademii)e (Nauk)h(SSSR)p Fu(,)e(192:1224{1227,)508 618 y(1970.)42 b(In)30 b(Russian.)e(English)g(T)-8 b(ranslation)30 b(in)f([T)-8 b(ra70b].)0 805 y([T)g(ra70b])178 b(B.)24 b(T)-8 b(rakh)m(ten)m(brot.) 32 b(On)23 b(autoreducibilit)m(y)-8 b(.)29 b Fg(Soviet)e (Mathematics{Doklady)p Fu(,)i(11:814{817,)h(1970.)0 993 y([T)-8 b(ur36])223 b(A.)25 b(T)-8 b(uring.)29 b(On)24 b(computable)g(n)m(um)m(b)s(ers,)h(with)e(an)i(application)e(to)i(the)g (Etsc)m(heidungs)e(problem.)508 1106 y Fg(Pr)-5 b(o)g(c)g(e)g(e)g (dings)34 b(of)f(the)g(L)-5 b(ondon)35 b(Mathematic)-5 b(al)34 b(So)-5 b(ciety)p Fu(,)32 b(42:230{265,)j(1936.)0 1293 y([V)-8 b(al79])237 b(L.)32 b(V)-8 b(alian)m(t.)49 b(The)32 b(complexit)m(y)h(of)g(computing)f(the)h(p)s(ermanen)m(t.)48 b Fg(The)-5 b(or)g(etic)g(al)37 b(Computer)g(Sci-)508 1406 y(enc)-5 b(e)p Fu(,)30 b(8:189{201,)k(1979.)0 1594 y([)30 1571 y(\024)25 1594 y(Z\022)-45 b(ak83])219 b(S.)621 1571 y(\024)616 1594 y(Z\022)-45 b(ak.)48 b(A)33 b(T)-8 b(uring)31 b(mac)m(hine)i(time)g(hierarc)m(h)m(y)-8 b(.)48 b Fg(The)-5 b(or)g(etic)g(al)37 b(Computer)f(Scienc)-5 b(e)p Fu(,)34 b(26\(3\):327{)508 1707 y(333,)d(1983.)0 1895 y([Zan92])216 b(V.)28 b(Zank\023)-45 b(o.)38 b(#P-completeness)28 b(via)g(man)m(y-one)h(reductions.)37 b Fg(International)c(Journal)f(of) f(F)-7 b(oun-)508 2007 y(dations)34 b(of)f(Computer)h(Scienc)-5 b(e)p Fu(,)30 b(2:77{82,)k(1992.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF