%!PS-Adobe-2.0 %%Creator: dvips 5.528 Copyright 1986, 1994 Radical Eye Software %%Title: revised.eatcs2.dvi %%CreationDate: Wed Oct 29 18:16:36 1997 %%Pages: 15 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips -o wagner.eatcs.ps revised.eatcs2.dvi %DVIPSParameters: dpi=300, comments removed %DVIPSSource: TeX output 1997.10.29:1815 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}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 dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put 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 /IE 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 IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /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 dup definefont setfont}B /ch-width{ch-data dup length 5 sub get} B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup 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 /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{ ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 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 dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 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 /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /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 300 300 (/tmp_mnt/fac/u22/allender/papers/journals.appeared/columns.eatcs/40/revised.eatcs2.dvi) @start /Fa 7 116 df82 D<000FFE00007FFFC001FFFFE003FC07F007F00FF80FE0 0FF81FE00FF83FC00FF83FC007F07F8003E07F8000807F800000FF800000FF800000FF80 0000FF800000FF800000FF800000FF800000FF8000007F8000007F8000007FC000003FC0 003C3FC0003C1FE000780FF0007807F800F003FE07E001FFFFC0007FFF00000FF8001E20 7D9F24>99 D<000FFC00007FFF8001FFFFC003FC0FE007F003F00FE001F81FC001FC3FC0 00FE3FC000FE7F80007E7F80007F7F80007FFF80007FFFFFFFFFFFFFFFFFFFFFFFFFFF80 0000FF800000FF800000FF8000007F8000007F8000007FC000003FC0000F1FC0000F1FE0 001E0FF0001E07F8007C03FF01F800FFFFE0003FFFC00007FE0020207E9F25>101 D<0000FF000007FFC0001FFFE0003FC7F0007F0FF800FE0FF801FE0FF801FC0FF803FC07 F003FC03E003FC01C003FC000003FC000003FC000003FC000003FC000003FC000003FC00 00FFFFFC00FFFFFC00FFFFFC00FFFFFC0003FC000003FC000003FC000003FC000003FC00 0003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC00 0003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC00 0003FC00007FFFF0007FFFF0007FFFF0007FFFF0001D327EB119>I<03F007F800FFF03F FE00FFF07FFF00FFF0F07F80FFF1803FC00FF3001FC007F6001FE007FE001FE007FC001F E007FC001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE0 07F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007F8001FE007 F8001FE007F8001FE007F8001FE007F8001FE007F8001FE0FFFFC3FFFFFFFFC3FFFFFFFF C3FFFFFFFFC3FFFF28207D9F2D>110 D<03F07E00FFF0FF80FFF1FFC0FFF38FE0FFF71F F00FF61FF007FE1FF007FC1FF007FC0FE007FC07C007F8010007F8000007F8000007F800 0007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F800 0007F8000007F8000007F8000007F8000007F80000FFFFE000FFFFE000FFFFE000FFFFE0 001C207E9F21>114 D<01FF8E0007FFFE001FFFFE003F00FE007C003E0078003E00F800 1E00F8001E00F8001E00FC000000FF000000FFF800007FFF80007FFFE0003FFFF8001FFF FC0007FFFE0001FFFF00003FFF000001FF8000003F8070001F80F0000F80F0000F80F800 0F80F8000F00FC001F00FE001E00FF807C00FFFFF800F3FFF000C07F800019207D9F20> I E /Fb 1 84 df83 D E /Fc 4 81 df<020408183030606060E0E0E0E0E0E0E0E06060603030180804 02071A7F920C>40 D<8040203018180C0C0C0E0E0E0E0E0E0E0E0C0C0C18183020408007 1A7E920C>I<0C003C00DC001C001C001C001C001C001C001C001C001C001C001C001C00 FF8009107E8F0F>49 D80 D E /Fd 2 9 df<40E04003037D8709>1 D<03F0000C4C00104200204100404080404080404080804040804040FFFFC08040408040 408040404040804040804040802041001042000C4C0003F00012147D8F18>8 D E /Fe 2 116 df<00C001E001C001800000000000000000000000000E003300238063 80C700C70007000E000E000E001C001C4038C038C038C0398039001E000B1C7D9B0D> 105 D<01F006180C180C3C18781C301F001FC00FF007F0007820387030F030F030C06060 C01F000E127D9111>115 D E /Ff 1 4 df<040004000400C460E4E03F800E003F80E4E0 C4600400040004000B0D7E8D11>3 D E /Fg 1 68 df<0003F0000FF8003FF800F07801 C0780380700700F00F00F00E00E01C01C03C01803C0000380000780000780000700000F0 0000F00000F00000F00000F00000F00000F00060F800E0F801C07C03807F07003FFC001F F80007E000151E7F9C16>67 D E /Fh 5 107 df0 D<60F0F06004047D890A>I<00FC0003FF000733800C30C0183060303030303030603018 603018C0300CC0300CFFFFFCFFFFFCC0300CC0300C603018603018303030303030183060 0C30C007338003FF0000FC0016187E931B>8 D<001F80007F8000FF800387800707000E 07001C0E001C0C00380000380000700000700000700000F00000F00000F00000F80000F8 0300FC07007E1E007FF8003FF0001F80001117809613>67 D106 D E /Fi 1 68 df<007F8101FFE707E03F0F801F1F000F3E00077E00037C0003FC0003FC 0000FC0000FC0000FC0000FC0000FC00037C00037E00033E00061F00060F800C07E03801 FFF0007F8018177E961D>67 D E /Fj 15 122 df<70F8FCFC7404040404080810102040 060F7C840E>59 D<00008000018000018000030000030000030000060000060000060000 0C00000C00000C0000180000180000180000300000300000300000600000600000600000 C00000C00000C00001800001800001800001800003000003000003000006000006000006 00000C00000C00000C000018000018000018000030000030000030000060000060000060 0000C00000C00000C0000011317DA418>61 DI<000001C00000 0001C000000003C000000003C000000007C00000000FC00000000FC00000001BC0000000 1BE000000031E000000031E000000061E0000000C1E0000000C1E000000181E000000181 E000000301E000000701E000000601E000000C01F000000C01F000001800F000003FFFF0 00003FFFF000006000F000006000F00000C000F00000C000F000018000F000030000F000 030000F000070000F8001F0000F800FFC00FFF80FFC00FFF8021237EA225>65 D<007FFFF80000FFFFFF000007800F8000078007C0000F0007C0000F0003C0000F0003E0 000F0003E0001E0003C0001E0007C0001E0007C0001E000F80003C000F00003C003E0000 3C007C00003C01F000007FFFE00000780078000078003C000078003E0000F0001E0000F0 001E0000F0001F0000F0001F0001E0003E0001E0003E0001E0003E0001E0007C0003C000 780003C000F80003C003F00007C00FC0007FFFFF8000FFFFFC000023227EA125>I<0000 7F01800003FF8300000FC0E700003E0067000078003F0000F0001E0001E0001E0003C000 1E000780001E000F80000C000F00000C001F00000C003E00000C003E000018007C000000 007C000000007C00000000F800000000F800000000F800000000F800000000F800000000 F000000000F000006000F000006000F00000C000F00000C000F800018000780001800078 000300003C000600001E000C00001F0038000007C0F0000003FFC0000000FE0000002124 7DA223>I<007FFE0000FFFE000007800000078000000F0000000F0000000F0000000F00 00001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C0000007800 0000780000007800000078000000F0000000F0003000F0003000F0006001E0006001E000 6001E000C001E000C003C001C003C0038003C0078007C03F807FFFFF00FFFFFF001C227E A121>76 D<007FE00003FF00FFE00003FF0007E00007E00007E0000DE0000DE0000FC000 0DE0001BC0000DE0001BC0000DE00033C00019E00067800019E00067800018F000C78000 18F000C7800030F0018F000030F0030F000030F0030F000030F0060F000060F0061E0000 60F00C1E000060F0181E00006078181E0000C078303C0000C078303C0000C078603C0000 C078C03C00018078C0780001807980780001807980780001807B00780003007E00F00003 003E00F00003003C00F0000F803C01F0007FF0381FFF00FFF0303FFF0030227EA12F>I< 00007F00000381C0000E00E0003C00780070003800E0003C01C0001E03C0001E0780001E 0F00001F0F00001F1E00001F3E00001F3E00001F7C00001F7C00001F7C00001FF800003E F800003EF800003EF800003CF800007CF000007CF00000F8F00000F8F00001F0F00001E0 F00003E0F80003C07800078078000F003C001E001C0038000E00F0000783C00000FE0000 20247DA225>79 D<007FFFF00000FFFFFC000007803E000007800F00000F000F80000F00 0780000F000780000F000780001E000F80001E000F80001E000F80001E000F00003C001F 00003C001E00003C003C00003C007800007801E000007FFF800000780000000078000000 00F000000000F000000000F000000000F000000001E000000001E000000001E000000001 E000000003C000000003C000000003C000000007C00000007FFC000000FFFC0000002122 7EA11F>I<00F8000FF0000FF00000F00000F00001E00001E00001E00001E00003C00003 C00003C00003C0000780000780F007810C07821C0F043C0F087C0F107C0F60381E80001F 00001FF0001E3C003C1E003C1E003C0F083C0F0C781E18781E18781E10780E30F0066060 03C016237EA219>107 D<1E03E000338C300063D0380063E03C00C3E03C00C3C03C00C3 C03C00078078000780780007807800078078000F00F0000F00F0000F01E0800F01E0C01E 01E1801E03C1801E03C3001E01C2003C01C400180078001A157F941D>110 D<03C0F006730C0C7E0E0C7C0E18780718780718780F00F00F00F00F00F00F00F00F01E0 1E01E01E01E01E01E03C03C03803C03803C07003E0E007B180079F000780000780000F00 000F00000F00000F00001E00001E0000FFE000FFE000181F819418>112 D<03E0F00C3318183E1C303E3C203C7C603C7C603C3800780000780000780000780000F0 0000F00000F00830F00C79E018F9E018F9E030F360606230C03C1F0016157E941C>120 D<0F801819C03C31E03C61E078C1E078C1E078C3C07803C0F00780F00780F00780F00F01 E00F01E00F01E00F01E00F03C00E03C00F03C00707C0070F8001F780000780000780000F 003C0F007C1E007C1C0078380060700030E0001F8000161F7F9418>I E /Fk 3 113 df<00FC000387000E01801C01C03801C07000C07000C0E001C0E001C0E0 01C0E00380E00380E00700600E00701C003838000FC00012117D9017>79 D<3E000E000E001C001C001C001C6039B03A703C6038007F00738073907390E3A061C00C 117E9010>107 D<0E70178C270C270E070E0E1C0E1C0E1C0E381E301DC01C001C003800 3800FE000F10808A10>112 D E /Fl 10 121 df<0000C00001C00001E00003E00003E0 0006E0000CE0000CE00018E00018E00030E00070E00060E000C0F000FFF001FFF0038070 0300700600700600700E00707F83FEFF03FE17177F961A>65 D<07FFF807FFFE00E01F00 E00F00E00701C00701C00F01C00F01C01E03803C03FFF003FFF803803C07001C07001E07 001E07001E0E003C0E003C0E00780E01F0FFFFE0FFFF0018177F961B>I<07FE1FF807FE 1FF800E0038000E0038000E0038001C0070001C0070001C0070001C0070003800E0003FF FE0003FFFE0003800E0007001C0007001C0007001C0007001C000E0038000E0038000E00 38000E003800FFC3FF00FF83FE001D177F961D>72 D<001FC000707001C03803801C0700 1C0E001E1E000E1C000E3C001E38001E78001E78001E78001E70003CF0003C7000787000 787000F07800E03801C01C07800E0E0003F00017177F961B>79 D<07FFF807FFFC00E01E 00E00F00E00F01C00F01C00F01C00F01C01E03801C03807803FFE0038000070000070000 0700000700000E00000E00000E00000E0000FFC000FF800018177F9616>I<1FFFFE3FFF FE381C1C701C0C601C0C60380CC0380CC0380C00380000700000700000700000700000E0 0000E00000E00000E00001C00001C00001C00001C0003FFC007FFC0017177F9615>84 D<1F801F000700070007000E000E000E000E001C1E1C271C4F1C8F3B0E3C003F8039C070 E070E370E370E6E064603810177F9612>107 D<1C3E00266380678180670180CF03800E 03800E03800E07001C07001C07301C0E301C0E60380640180380140E808D15>110 D<0E1E0013630033C1803381C06701C00701C00701C00701C00E03800E03800E07000E06 001F1C001CF0001C00001C0000380000380000FF0000FE00001214818D12>112 D<0F1E0031B30060E78060E780C1C70001C00001C00001C000038000638300F38300F386 00E78C0078F800110E7F8D14>120 D E /Fm 25 108 df0 D<78FCFCFCFC7806067C8E0E>I<0007E000003FFC0000F99F0001C18380030180C0 060180600C01803018018018180180183001800C600180066001800660018006C0018003 C0018003C0018003FFFFFFFFFFFFFFFFC0018003C0018003C00180036001800660018006 600180063001800C18018018180180180C01803006018060030180C001C1838000F99F00 003FFC000007E00020227D9C27>8 D<03F0000FFC001FFE003FFF007FFF807FFF80FFFF C0FFFFC0FFFFC0FFFFC0FFFFC0FFFFC0FFFFC0FFFFC07FFF807FFF803FFF001FFE000FFC 0003F00012147D9519>15 D<000FFFFC007FFFFC01F0000003800000060000000C000000 1800000030000000300000006000000060000000C0000000C0000000C0000000C0000000 C0000000C0000000C000000060000000600000003000000030000000180000000C000000 060000000380000001F00000007FFFFC000FFFFC00000000000000000000000000000000 000000000000000000000000000000007FFFFFFC7FFFFFFC1E277C9F27>18 D<0000000C0000003C000000F0000003C000000F0000003C000000F0000007C000001F00 000078000001E00000078000001E00000078000000E0000000780000001E000000078000 0001E0000000780000001F00000007C0000000F00000003C0000000F00000003C0000000 F00000003C0000000C000000000000000000000000000000000000000000000000000000 00000000007FFFFFF8FFFFFFFC1E277C9F27>20 DI<000FFFFC007FFFFC01F0000003800000060000000C0000001800000030000000 300000006000000060000000C0000000C0000000C0000000C0000000C0000000C0000000 C0000000C000000060000000600000003000000030000000180000000C00000006000000 0380000001E00000007FFFFC001FFFFC1E1E7C9A27>26 D<000000006000000000003000 000000003000000000001800000000001800000000000C00000000000600000000000380 FFFFFFFFFFE0FFFFFFFFFFC0000000000380000000000600000000000C00000000001800 0000000018000000000030000000000030000000000060002B127D9432>33 D<0000C00000000000C00000000001800000000003000000000003000000000006000000 00000C00000000001800000000003FFFFFFFE0007FFFFFFFE001C0000000000700000000 003E0000000000F800000000003C00000000000F000000000003800000000000C0000000 00007FFFFFFFE0003FFFFFFFE0001C00000000000C000000000006000000000003000000 000001800000000001800000000000C00000000000C00000002B1C7D9932>40 D<0000006000000000006000000000003000000000001800000000001800000000000C00 00000000060000000000030000FFFFFFFF8000FFFFFFFFC000000000007000000000001C 00000000000F800000000003E0000000000780000000001E000000000038000000000060 00FFFFFFFFC000FFFFFFFF80000000000700000000000600000000000C00000000001800 000000003000000000003000000000006000000000006000002B1C7D9932>I<001FFF00 7FFF01E0000380000600000C0000180000300000300000600000600000600000C00000C0 0000FFFFFFFFFFFFC00000C000006000006000006000003000003000001800000C000006 000003800001E000007FFF001FFF181E7C9A21>50 D<0000030000030000060000060000 0C00000C0000180000180000300000300000600000600000C00000C00000C00001800001 80000300000300000600000600000C00000C000018000018000030000030000060000060 0000C00000C0000180000180000300000300000300000600000600000C00000C00001800 00180000300000300000600000600000C00000400000183079A300>54 DI<40000010C00000306000 00606000006060000060300000C0300000C0300000C018000180180001800C0003000C00 03000C00030007FFFE0007FFFE0003000C0003000C0003000C0001801800018018000180 180000C0300000C030000060600000606000006060000030C0000030C000001980000019 800000198000000F0000000F0000000F000000060000000600001C2480A21D>I I<00007F000003FF80000FFFC0001E07C0007003C000E003C001C0038003800780078007 0007000F000E000E001E001C001C0010003C0000003C0000003800000078000000780000 007800000070000000F0000000F0000000F0000000F0000000F0000000F0000000F00000 00F8000700F8000E0078001C007C0038007E0070003F81C0001FFF80000FFE000003F800 001A2480A21A>67 D<40000040C00000C0C00000C0C00000C0C00000C0C00000C0C00000 C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000 C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C060000180600001 8030000300180006000E001C000780780001FFE000007F80001A1F7D9D21>91 D<007F800001FFE000078078000E001C0018000600300003006000018060000180C00000 C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000 C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000C0C00000 C0C00000C0C00000C0C00000C0400000401A1F7D9D21>I<0007C0003FC0007C0000F000 01E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E000 01E00001E00001E00001E00003C00003C0000F8000FE0000F80000FE00000F800003C000 03C00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E00001E000 01E00001E00001E00001E00001E00000F000007C00003FC00007C012317DA419>102 DI<004000C000C0018001800180030003000300060006000C000C 000C00180018001800300030003000600060006000C000C000C000C00060006000600030 00300030001800180018000C000C000C000600060003000300030001800180018000C000 C000400A327BA413>III<8010C030C030C0 30C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C0 30C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C030C0 30C030C030C030C030C030C030C030C030C03080100C327AA419>I E /Fn 66 123 df<007E1F0001C1B1800303E3C00703C3C00E03C1800E01C0000E01C000 0E01C0000E01C0000E01C0000E01C000FFFFFC00FFFFFC000E01C0000E01C0000E01C000 0E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C000 0E01C0000E01C0007F87FC007F87FC001A1D809C18>11 D<007E0001C1800301800703C0 0E03C00E01800E00000E00000E00000E00000E0000FFFFC0FFFFC00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F8 7F87F8151D809C17>I<7070F8F8FCFCFCFC747404040404040408080808101020204040 0E0D7F9C15>34 D<004000800100020006000C000C001800180030003000700070006000 6000E000E000E000E000E000E000E000E000E000E000E000E00060006000700070003000 3000180018000C000C00060002000100008000400A2A7D9E10>40 D<800040002000100018000C000C000600060003000300038003800180018001C001C001 C001C001C001C001C001C001C001C001C001C0018001800380038003000300060006000C 000C00180010002000400080000A2A7E9E10>I<70F0F8F8780808081010202040050D7D 840C>44 DI<70F8F8F87005057D840C>I<03C00C30181838 1C300C700E700E700EF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00F70 0E700E700E300C381C18180C3007E0101D7E9B15>48 D<030007003F00FF00C700070007 000700070007000700070007000700070007000700070007000700070007000700070007 000700FFF8FFF80D1C7C9B15>I<07C01FF0387C603C601EF01FF81FF80FF80F700F001F 001E001E003C0038007000E000C00180030006000C031803100320067FFEFFFEFFFE101C 7E9B15>I<000C00001C00001C00003C00007C00005C0000DC00019C00031C00031C0006 1C000C1C00081C00181C00301C00201C00601C00C01C00FFFFC0FFFFC0001C00001C0000 1C00001C00001C00001C0001FFC001FFC0121C7F9B15>52 D<00F003FC070C0E0E1C1E38 1E380C780070007000F3E0F430F818F81CF80EF00EF00FF00FF00FF00FF00F700F700F70 0E380E381C1C380FF003E0101D7E9B15>54 D<6000007FFF807FFF807FFF00600300C006 00C00C00C00C0000180000300000300000600000600000C00000C00001C00001C0000380 00038000038000038000078000078000078000078000078000078000078000030000111D 7E9B15>I<03E00FF01C38381C300E700E700E700E780E781C3E183FB01FE007F007F818 FC307E701E600FE00FE007E007E007E007700E700C3C3C1FF007E0101D7E9B15>I<03C0 0FF01C38381C781C700EF00EF00EF00FF00FF00FF00FF00F700F701F381F181F0C2F07CF 000E000E000E301C781C7838703030F03FC00F80101D7E9B15>I<70F8F8F87000000000 0000000070F8F8F87005127D910C>I<70F8F8F870000000000000000070F0F8F8780808 081010202040051A7D910C>I<7FFFFFC0FFFFFFE0000000000000000000000000000000 0000000000000000000000000000000000FFFFFFE07FFFFFC01B0C7E8F20>61 D<00060000000F0000000F0000000F0000001F8000001F8000001F8000001F80000033C0 000033C0000033C0000061E0000061E0000061E00000C0F00000C0F00000C0F000018078 000180780001FFF80003FFFC0003003C0003003C0006001E0006001E0006001E001F001F 00FFC0FFF0FFC0FFF01C1D7F9C1F>65 DI< 001F808000FFE18001F03B8007C00F800F0007801F0007801E0003803C0003807C000180 7C00018078000180F8000000F8000000F8000000F8000000F8000000F8000000F8000000 F8000000780001807C0001807C0001803C0001801E0003001F0003000F00060007C00C00 01F0380000FFF000001FC000191E7E9C1E>I69 DI<001F808000FFE18001F03B8007C0 0F800F0007801F0007801E0003803C0003807C0001807C00018078000180F8000000F800 0000F8000000F8000000F8000000F8000000F800FFF0F800FFF0780007807C0007807C00 07803C0007801E0007801F0007800F00078007C00F8001F0398000FFF080001FC0001C1E 7E9C21>III<1FFF1FFF00780078007800780078007800780078007800780078007800 780078007800780078007800787078F878F878F87870F060E031C00F80101D7F9B15>I< FFF07FE0FFF07FE00F003E000F0018000F0030000F0060000F00C0000F01C0000F038000 0F0700000F0E00000F1E00000F1F00000F3F00000F6780000FC780000F83C0000F01E000 0F01E0000F00F0000F00F8000F0078000F003C000F003C000F001E000F001F00FFF07FF0 FFF07FF01C1C7E9B20>II78 D<003F800000E0E0000380380007001C000E000E001E000F003C0007803C00 07807C0007C0780003C0780003C0F80003E0F80003E0F80003E0F80003E0F80003E0F800 03E0F80003E0F80003E0780003C07C0007C07C0007C03C0007803E000F801E000F000F00 1E0007001C000380380000E0E000003F80001B1E7E9C20>II82 D<07E0801FF9803C1F80700780 700380E00380E00180E00180E00180F00000F000007C00007FC0003FF8001FFE0007FF00 00FF80000F800003C00003C00001C0C001C0C001C0C001C0E00180E00380F00300FC0E00 CFFC0083F800121E7E9C17>I<7FFFFFC07FFFFFC0780F03C0700F01C0600F00C0E00F00 E0C00F0060C00F0060C00F0060C00F0060000F0000000F0000000F0000000F0000000F00 00000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F00 00000F0000000F000003FFFC0003FFFC001B1C7F9B1E>I87 D89 D91 D<08081010202040404040 808080808080B8B8FCFCFCFC7C7C38380E0D7B9C15>II<0F E0001838003C1C003C0E00180E00000E00000E0001FE000F8E003C0E00780E00700E00F0 0E60F00E60F00E60701E603827C00FC38013127F9115>97 DI<03F00E181C3C383C78187000F000F000F000F000F000F00070 00780638061C0C0E1803E00F127F9112>I<001F80001F80000380000380000380000380 00038000038000038000038000038003F3800E0F801C0780380380780380700380F00380 F00380F00380F00380F00380F003807003807803803803801C07800E1BF003F3F0141D7F 9C17>I<03E00C301818381C701E700EF00EFFFEF000F000F000F000700070063806180C 0E1803E00F127F9112>I<00F8018C071E061E0E0C0E000E000E000E000E000E00FFE0FF E00E000E000E000E000E000E000E000E000E000E000E000E000E000E007FE07FE00F1D80 9C0D>I<00038007E4C00C39C0381DC0381C00781E00781E00781E00781E00381C00381C 001C300037E0002000003000003000003FF8001FFF001FFF803003806001C0C000C0C000 C0C000C06001803003001C0E0007F800121C7F9215>II<18003C007C003C001800000000000000000000000000FC00FC001C 001C001C001C001C001C001C001C001C001C001C001C001C001C00FF80FF80091D7F9C0C >I107 DIII<03F000 0E1C00180600380700700380700380F003C0F003C0F003C0F003C0F003C0F003C0700380 7003803807001C0E000E1C0003F00012127F9115>II<03 F1800E19801C0780380780780380780380F00380F00380F00380F00380F00380F0038070 03807803803807801C07800E1B8003E38000038000038000038000038000038000038000 1FF0001FF0141A7F9116>II<1F9030F04070C030C030E030F8007F803F E00FF000F8C038C018C018E018E010D0608FC00D127F9110>I<0C000C000C000C000C00 0C001C001C003FE0FFE01C001C001C001C001C001C001C001C001C301C301C301C301C30 0C200E6003C00C1A7F9910>IIII<7F8F F07F8FF00F0780070600038E0001DC0001D80000F00000700000780000F80001DC00038E 00030E000607000F0380FF8FF8FF8FF81512809116>II< 7FFC78387038607060F060E061C003C0038007000F0C0E0C1C0C3C1C381870187078FFF8 0E127F9112>I E /Fo 7 81 df<06001E00FE00EE000E000E000E000E000E000E000E00 0E000E000E000E000E000E00FFE0FFE00B137D9211>49 D<1F003FC041E0C0F0E070E070 00F000E000E001C00380030004000810101020307FE0FFE0FFE00C137E9211>I<1FC03F E07070707820380078007000E00FC000700038003C003C403CE03CE03840707FE01FC00E 137F9211>I<006000E001E001E002E004E008E010E030E060E0C0E0FFFCFFFC00E000E0 00E000E007FC07FC0E137F9211>I<60607FC07F807F004000400040004F0070C0406000 6000700070E070E070C0E061C03F801F000C137E9211>I78 D80 D E /Fp 6 117 df<00F18003FDC0078F800E0780 1C07803C07803C0700780700780700780700F00E00F00E00F00E00F00E30F01C60F03C60 707C6078FCC03FCFC00F078014147C9317>97 D<007C0001FF000783000F01801E01803C 01803C0300780E007FFC007FE000F00000F00000F00000F000007000007002007807003C 1E001FF80007E00011147C9315>101 D<007C0001FF000383800F01C01E01C01C01E03C 01E07801E07801E07801E0F003C0F003C0F003C0F00780F00700700F00701E003838001F F00007C00013147C9317>111 D<03C1E007E7F8067E3C0C7C1C0C781E0C701E18E01E00 E01E00E01E00E01E01C03C01C03C01C03C01C07803C07803C07003C0E003E3C0077F8007 1E000700000700000E00000E00000E00000E00001C0000FFC000FFC000171D809317>I< 1E0F003F3F8033F1C063C1C063C3C06383C0C783800700000700000700000E00000E0000 0E00000E00001C00001C00001C00001C000038000018000012147D9313>114 D<018001C0038003800380038007000700FFF0FFF00E000E000E000E001C001C001C001C 0038003800380038307060706070C071803F001E000C1C7C9B0F>116 D E /Fq 51 122 df<001F8000FFC001E0E003C0F00781F00F01F00F00E00F00000F0000 0F00000F00000F0000FFFFF0FFFFF00F00F00F00F00F00F00F00F00F00F00F00F00F00F0 0F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F0FFC3FFFFC3FF182080 9F19>12 D<001FB000FFF001E1F003C1F00781F00F00F00F00F00F00F00F00F00F00F00F 00F00F00F0FFFFF0FFFFF00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F 00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F0FFE7FFFFE7FF1820809F19>I< 7038F87CFC7EFC7E7C3E0C060C060C06180C180C381C3018603040200F0E7E9F17>34 D<70F8FCFC7C0C0C0C181838306040060E7C9F0D>39 D<70F8FCFC7C0C0C0C1818383060 40060E7C840D>44 DI<70F8F8F87005057C840D>I<00C001 C00FC0FFC0F3C003C003C003C003C003C003C003C003C003C003C003C003C003C003C003 C003C003C003C003C003C003C003C003C07FFF7FFF101E7D9D17>49 D<03F0000FFC001E1E003807003007007003807003807003807803807C07007E07003F8E 001FFC000FF80007FC0007FE001EFF00387F80701F807007C0E003C0E003C0E001C0E001 C0E001C0F001807003803807001E0E000FFC0003F000121F7E9D17>56 D<03F00007F8001E1C00380E00380700700700700380F00380F00380F003C0F003C0F003 C0F003C0F003C07007C07007C0380FC01C0BC01FF3C007E3C00003800003800007800007 003807007C0E007C0E00781C003078001FF0000FC000121F7E9D17>I<70F8F8F8700000 000000000000000070F8F8F878181818183030606040051D7C930D>59 D<0003800000038000000380000007C0000007C0000007C000000FE000000FE000000FE0 000019F0000019F0000019F0000030F8000030F8000030F8000060FC0000607C0000607C 0000E07E0000C03E0000C03E0001FFFF0001FFFF0001801F0003801F8003000F8003000F 8007000FC0070007C00F8007C0FFE07FFEFFE07FFE1F207F9F22>65 D<001FC040007FF0C001F839C003C00DC0078007C00F0003C01E0003C03E0001C03C0001 C07C0001C07C0000C0780000C0F80000C0F8000000F8000000F8000000F8000000F80000 00F8000000F8000000F8000000780000C07C0000C07C0000C03C0000C03E0001801E0001 800F0003000780030003C00E0001F81C00007FF000001FC0001A217D9F21>67 D69 D72 DI<0FFFE00FFFE0003E00003E00003E00003E00003E00003E00003E 00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E 00003E00003E00783E00FC3E00FC3E00FC3E00F83C00707C0070F8001FF0000FC0001320 7F9E17>I77 D<001F800000FFF00001E07800 07C03E000F801F000F000F001E0007803C0003C03C0003C07C0003E07C0003E0780001E0 F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0 780001E07C0003E07C0003E03C0003C03E0007C01E0007800F000F000F801F0007C03E00 01F0F80000FFF000001F80001C217D9F23>79 DI82 D<07E0800FF9801C1F80380F80780780700380F00380F00180F00180F00180F80000F800 007E00007FE0003FFC003FFE001FFF0007FF0000FF80000F800007C00007C00003C0C003 C0C003C0C003C0C003C0E00380F00780F80700FE0E00CFFC0081F80012217D9F19>I<7F FFFFE07FFFFFE07C0F81E0700F80E0600F8060600F8060E00F8070C00F8030C00F8030C0 0F8030C00F8030000F8000000F8000000F8000000F8000000F8000000F8000000F800000 0F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F800000 0F8000000F800007FFFF0007FFFF001C1F7E9E21>II89 D91 D<0804180C3018703860306030C060C060C060 F87CFC7EFC7E7C3E381C0F0E7B9F17>II<0FE000 3FF8007C3C007C1E007C0F00380F00000F00000F0001FF000FCF003E0F00780F00780F00 F00F30F00F30F00F30F01F30783FF03FC7E00F83C014147E9317>97 D<0F0000FF0000FF00000F00000F00000F00000F00000F00000F00000F00000F00000F00 000F1F800F7FC00FE1E00F80700F00780F00380F003C0F003C0F003C0F003C0F003C0F00 3C0F003C0F00380F00780F00780F80F00EC1E00E7FC00C1F001620809F19>I<03F00FFC 1E3E3C3E383E781C7000F000F000F000F000F000F0007000780038033C031F0E0FFC03F0 10147E9314>I<0003C0003FC0003FC00003C00003C00003C00003C00003C00003C00003 C00003C00003C003E3C00FFBC01E0FC03C07C07803C07003C07003C0F003C0F003C0F003 C0F003C0F003C0F003C07003C07003C07803C03807C01E1FC00FFBFC03E3FC16207E9F19 >I<03F0000FFC001E1E003C0F00380700780700700380F00380FFFF80FFFF80F00000F0 0000F000007000007800003801801C03800F070007FE0001F80011147F9314>I<003E00 00FF0003CF80078F80078F800F07000F00000F00000F00000F00000F00000F0000FFF000 FFF0000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F0000 0F00000F00000F00000F00000F0000FFF000FFF0001120809F0E>I<0000E003E3F00FFE 701C1C70380E60780F00780F00780F00780F00780F00380E001C1C001FF80033E0002000 003000003000003FFE003FFF801FFFC01FFFE07001E06000F0E00070E00070E000707000 E07801E03E07C00FFF0003FC00141F7F9417>I<0F0000FF0000FF00000F00000F00000F 00000F00000F00000F00000F00000F00000F00000F0F800F3FC00F61E00FC0F00F80F00F 00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F 00F0FFF3FFFFF3FF1820809F19>I<0E001F001F001F000E000000000000000000000000 000F007F007F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F 00FFE0FFE00B1F809E0D>I<0F0000FF0000FF00000F00000F00000F00000F00000F0000 0F00000F00000F00000F00000F0FF80F0FF80F07C00F07000F06000F0C000F18000F3800 0F78000FFC000FBC000F1E000F1F000F0F000F0F800F07C00F03C00F03E0FFE7FCFFE7FC 1620809F18>107 D<0F00FF00FF000F000F000F000F000F000F000F000F000F000F000F 000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F00FFF0FF F00C20809F0D>I<0F0FC07E00FF3FE1FF00FF60F307800FC07E03C00F807C03C00F0078 03C00F007803C00F007803C00F007803C00F007803C00F007803C00F007803C00F007803 C00F007803C00F007803C00F007803C00F007803C00F007803C0FFF3FF9FFCFFF3FF9FFC 2614809327>I<0F0F80FF3FC0FF61E00FC0F00F80F00F00F00F00F00F00F00F00F00F00 F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F0FFF3FFFFF3FF1814809319 >I<01F80007FE001E07803C03C03801C07000E07000E0F000F0F000F0F000F0F000F0F0 00F0F000F07000E07801E03801C03C03C01E078007FE0001F80014147F9317>I<0F1F80 FF7FC0FFE1E00F80F00F00780F00780F003C0F003C0F003C0F003C0F003C0F003C0F003C 0F00380F00780F00780F80F00FC1E00F7FC00F1F000F00000F00000F00000F00000F0000 0F00000F0000FFF000FFF000161D809319>I<0F3CFF7EFFCF0F8F0F860F800F000F000F 000F000F000F000F000F000F000F000F000F00FFF0FFF01014809312>114 D<0F903FF07070E030E030E030F000FF007FC03FE01FF003F80078C038C038E038E030F0 70DFE08F800D147E9312>I<06000600060006000E000E001E003E00FFF8FFF81E001E00 1E001E001E001E001E001E001E001E001E181E181E181E181E180F3007E003C00D1C7F9B 12>I<0F00F0FF0FF0FF0FF00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F0 0F00F00F00F00F00F00F00F00F01F00F01F00706F003FCFF01F8FF1814809319>III<7FE7FC7FE7FC0783E007838003C30001E60001EE0000FC0000780000 7800003C00007E0000FE0001CF000187800387800703C00F03E0FFCFFEFFCFFE17148093 18>II E /Fr 21 122 df<3C7EFFFFFFFF7E3C000000003C7EFFFFFFFF7E3C08147D930F>58 D<0000E000000001F000000001F000000003F800000003F800000003F800000007FC0000 0007FC0000000FFE0000000EFE0000000EFE0000001CFF0000001C7F0000003C7F800000 383F800000383F800000703FC00000701FC00000F01FE00000E00FE00000FFFFE00001FF FFF00001FFFFF00003C007F800038003F800038003F800070001FC00070001FC00FFF01F FFE0FFF01FFFE0FFF01FFFE0231F7E9E28>65 D<0007F806007FFF0E01FFFFDE03FE03FE 07F000FE0FC0007E1F80003E3F80001E3F00001E7F00000E7E00000E7E00000EFE000000 FE000000FE000000FE000000FE000000FE000000FE0000007E0000007E00000E7F00000E 3F00000E3F80001C1F80001C0FC0003807F0007803FE03F001FFFFC0007FFF800007FC00 1F1F7D9E26>67 D72 D<7FFFFFFC7FFFFFFC7F FFFFFC7E0FE0FC780FE03C700FE01CF00FE01EF00FE01EE00FE00EE00FE00EE00FE00EE0 0FE00E000FE000000FE000000FE000000FE000000FE000000FE000000FE000000FE00000 0FE000000FE000000FE000000FE000000FE000000FE000000FE00007FFFFC007FFFFC007 FFFFC01F1E7E9D24>84 D<07FC001FFF803F0FC03F07E03F03F03F03F00C03F00003F000 FFF00FFFF01F83F07E03F07C03F0F803F0F803F0F803F0FC07F07E0DFE3FF8FE07E07E17 147F9319>97 DI<01FE 0007FF801F0FC03E0FC03E0FC07C0FC07C0300FC0000FC0000FC0000FC0000FC0000FC00 007C00007E00003E00E03F01C01F83C007FF8001FC0013147E9317>I<0007FC000007FC 000007FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC000000FC 000000FC0001FCFC000FFFFC001F83FC003E00FC007E00FC007C00FC007C00FC00FC00FC 00FC00FC00FC00FC00FC00FC00FC00FC00FC00FC007C00FC007C00FC007E00FC003E01FC 001F07FF800FFFFF8003F8FF8019207E9F1D>I<01FE0007FF800F83C01E01E03E00F07C 00F07C00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00003E00381E00380F 80F007FFE000FF8015147F9318>I<01FC7C07FFFE0F07DE1E03DE3E03EC3E03E03E03E0 3E03E03E03E01E03C00F07800FFF0019FC001800003800003C00003FFF801FFFF01FFFF8 0FFFFC3FFFFC7C00FEF8003EF8003EF8003EF8003E7C007C3F01F80FFFE003FF80171E7F 931A>103 DI<0E001F 003F807F807F803F801F000E0000000000000000000000FF80FF80FF801F801F801F801F 801F801F801F801F801F801F801F801F801F801F80FFF0FFF0FFF00C217EA00F>I108 D110 D<01FF0007FFC01F83F03E00F83E00F87C007C 7C007CFC007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F83E00F81F83F0 07FFC001FF0017147F931A>I114 D<0FE63FFE783E700EF00EF00EFE00FFE07FF83FFC1FFE0FFF007F E01FE00FF00FF00EFC1EFFFCC7F010147E9315>I<03800380038003800780078007800F 801F803FFCFFFCFFFC1F801F801F801F801F801F801F801F801F801F8E1F8E1F8E1F8E1F 8E0F9C07F803F00F1D7F9C14>II121 D E /Fs 85 128 df6 D<001FC3F000786F1800E07C3C01C0FC7C03C0 F87C0780F838078078000780780007807800078078000780780007807800078078000780 7800FFFFFFC0FFFFFFC00780780007807800078078000780780007807800078078000780 780007807800078078000780780007807800078078000780780007807800078078000780 7800078078007FE1FFC07FE1FFC01E2380A21C>11 D<001FC0000078600000E0300001C0 780003C0F8000780F8000780F80007807000078000000780000007800000078000000780 000007800000FFFFF800FFFFF8000780F800078078000780780007807800078078000780 780007807800078078000780780007807800078078000780780007807800078078000780 780007807800078078007FE1FF807FE1FF80192380A21B>I<001FD8000078780000E0F8 0001C0F80003C0F800078078000780780007807800078078000780780007807800078078 000780780007807800FFFFF800FFFFF80007807800078078000780780007807800078078 000780780007807800078078000780780007807800078078000780780007807800078078 000780780007807800078078007FF3FF807FF3FF80192380A21B>I<000FC07E00007833 C18000E01F00C001C03E01E003C07E03E007807C03E007807C03E007803C01C007803C00 0007803C000007803C000007803C000007803C000007803C0000FFFFFFFFE0FFFFFFFFE0 07803C03E007803C01E007803C01E007803C01E007803C01E007803C01E007803C01E007 803C01E007803C01E007803C01E007803C01E007803C01E007803C01E007803C01E00780 3C01E007803C01E007803C01E07FF1FF8FFE7FF1FF8FFE272380A229>I18 D<038007800F800F001E003C003800 7000E0004000090A77A218>I<1E0061804080C0C0C0C0C0C0408061801E000A0973A325> 23 D<7038F87CFC7EFC7E743A04020402040204020804080410081008201040200F0F7E A218>34 D<70F8FCFC7404040404080810102040060F7CA20E>39 D<00200040008001800300060006000E000C001C00180038003800380070007000700070 00F000F000F000F000F000F000F000F000F000F000F000F000F000F00070007000700070 0038003800380018001C000C000E0006000600030001800080004000200B327CA413>I< 800040002000300018000C000C000E0006000700030003800380038001C001C001C001C0 01E001E001E001E001E001E001E001E001E001E001E001E001E001E001C001C001C001C0 0380038003800300070006000E000C000C00180030002000400080000B327DA413>I<70 F8FCFC7404040404080810102040060F7C840E>44 DI<70 F8F8F87005057C840E>I<00008000018000018000030000030000030000060000060000 0600000C00000C00000C0000180000180000180000300000300000300000600000600000 600000C00000C00000C00001800001800001800001800003000003000003000006000006 00000600000C00000C00000C000018000018000018000030000030000030000060000060 0000600000C00000C00000C0000011317DA418>I<01F000071C000C0600180300380380 3803807001C07001C07001C07001C0F001E0F001E0F001E0F001E0F001E0F001E0F001E0 F001E0F001E0F001E0F001E0F001E0F001E0F001E07001C07001C07001C07803C0380380 3803801C07000C0600071C0001F00013227EA018>I<00C001C007C0FFC0FBC003C003C0 03C003C003C003C003C003C003C003C003C003C003C003C003C003C003C003C003C003C0 03C003C003C003C003C003C0FFFFFFFF10217CA018>I<03F0000FFC001C1F00300F8060 07C06003C0F803E0FC03E0FC01E0FC01E07801E03003E00003E00003C00003C000078000 0F00000E00001C0000380000300000600000C0000180000300600600600C00600800E010 00C03FFFC07FFFC0FFFFC0FFFFC013217EA018>I<03F0000FFC001C1F00380780380780 7C07C07C07C07C03C03C07C01807C0000780000780000F00000E0000380003F000001E00 000F000007800007C00003C00003E00003E03003E07803E0FC03E0FC03E0FC03C0F807C0 600780300F801C1F000FFC0003F00013227EA018>I<000300000700000700000F00001F 00001F00003F00006F00004F0000CF00018F00018F00030F00020F00060F000C0F00080F 00180F00300F00200F00600F00C00F00FFFFF8FFFFF8000F00000F00000F00000F00000F 00000F00000F0001FFF801FFF815217FA018>I<1000801C07001FFF001FFE001FF8001F E00018000018000018000018000018000018000019F8001A0C001C070018078010038000 03C00003C00003E00003E00003E07003E0F803E0F803E0F803E0F803C0C003C060078060 0780300F001C1E000FFC0003F00013227EA018>I<007E0001FF0003C3800701C00E03C0 1C07C01C07C0380380380000780000700000700000F0F800F30C00F40700F40300F80380 F801C0F001C0F001E0F001E0F001E0F001E0F001E07001E07001E07001E03801C03803C0 1803801C07000E0E0007FC0001F00013227EA018>I<6000007000007FFFE07FFFE07FFF C07FFFC0600180E00300C00300C00600C00C00000C000018000038000030000070000060 0000E00000E00001E00001E00001C00003C00003C00003C00003C00003C00007C00007C0 0007C00007C00007C00007C00007C00003800013237DA118>I<01F00007FC000E0F0018 07803803803001C07001C07001C07001C07801C07C03803E03803F87001FEE000FF80007 FC0003FE0006FF000C7F80381FC0300FC07003E0E001E0E001E0E000E0E000E0E000E0E0 00C07001C07001803803801E0F000FFC0003F00013227EA018>I<01F00007FC000E0E00 1C0700380380780380700380F001C0F001C0F001C0F001E0F001E0F001E0F001E0F001E0 7001E07003E03803E01805E01C05E00619E003E1E00001C00001C00003C0000380380380 7C07007C0700780E00301C003838001FF00007C00013227EA018>I<70F8F8F870000000 000000000000000070F8F8F87005157C940E>I<70F8F8F8700000000000000000000000 70F8F8F87808080808101010204040051F7C940E>I61 D<07E01838301C600EF00FF80FF80FF80F700F000E001C00380030006000E0 00C001C00180018001800180018001800180018000000000000000000000038007C007C0 07C0038010237DA217>63 D<000180000003C0000003C0000003C0000007E0000007E000 0007E000000FF000000DF000000DF000001DF8000018F8000018F8000038FC0000307C00 00307C0000607E0000603E0000603E0000C03F0000C01F0000C01F0001801F8001FFFF80 01FFFF80030007C0030007C0030007C0060003E0060003E0060003E00E0001F01F0003F0 FFC01FFFFFC01FFF20237EA225>65 DI<000FE010003FF83000F80E7001E0077003C001F007 8001F00F0000F01E0000F03E0000703C0000707C0000707C0000307800003078000030F8 000000F8000000F8000000F8000000F8000000F8000000F8000000F80000007800000078 0000307C0000307C0000303C0000303E0000601E0000600F0000C0078000C003C0018001 E0030000FC0E00003FFC00000FE0001C247DA223>IIII<0007F008003FFC1800FC0E3801F0033803 C001F8078000F80F0000781E0000781E0000383C0000383C0000387C0000187800001878 000018F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8003FFF78 003FFF7C0000F87C0000F83C0000F83C0000F81E0000F81E0000F80F0000F8078000F803 C001F801F003B800FC0718003FFC080007F00020247DA226>III<03FFF803FFF8000F 80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F 80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80300F80780F 80FC0F80FC0F80FC0F00F81F00601E00303C0018780007E00015237FA119>IIIII<000FE00000783C0000E00E00 03C00780078003C00F0001E00E0000E01E0000F03C0000783C0000787C00007C7C00007C 7800003C7800003CF800003EF800003EF800003EF800003EF800003EF800003EF800003E F800003EF800003E7800003C7C00007C7C00007C3C0000783E0000F81E0000F00F0001E0 0F0001E0078003C003C0078000E00E0000783C00000FE0001F247DA226>II82 D<03F0200FFC601E0EE03803E07801E07001E07000E0F000E0F00060F00060F00060F800 00F800007E00007FC0003FFC001FFF000FFF8007FFC000FFC0000FE00003E00001F00001 F00000F0C000F0C000F0C000F0C000F0E000E0E001E0F001C0F803C0EF0780C7FF0081FC 0014247DA21B>I<7FFFFFF87FFFFFF87C07C0F87007C0386007C0186007C018E007C01C E007C00CC007C00CC007C00CC007C00CC007C00C0007C0000007C0000007C0000007C000 0007C0000007C0000007C0000007C0000007C0000007C0000007C0000007C0000007C000 0007C0000007C0000007C0000007C0000007C0000007C0000007C00003FFFF8003FFFF80 1E227EA123>IIII89 D<7FFFFE7FFFFE7F007C7C007C7000F87001F8E001F0E003E0C0 03E0C007C0C007C0C00F80001F80001F00003E00003E00007C00007C0000F80000F80001 F00303F00303E00307C00307C0030F80070F80071F00063F000E3E001E7C003E7C00FEFF FFFEFFFFFE18227DA11E>II<08041008 20102010402040208040804080408040B85CFC7EFC7E7C3E381C0F0F7AA218>II<1FE0003838007C1C007C0E007C0F00380F0000 0F00000F0000FF00078F001E0F003C0F00780F00700F00F00F18F00F18F00F18F01F1878 1F183C27F00FC3E015157E9418>97 D<0F0000FF0000FF00001F00000F00000F00000F00 000F00000F00000F00000F00000F00000F00000F00000F1F000F61C00F80600F00300F00 380F003C0F001C0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001C0F003C0F00 380F00700F80600E61C00C3F0017237FA21B>I<01FE000707000C0F801C0F80380F8078 0700700000F00000F00000F00000F00000F00000F00000F000007000007800C03800C01C 01800C030007060001F80012157E9416>I<0001E0001FE0001FE00003E00001E00001E0 0001E00001E00001E00001E00001E00001E00001E00001E001F9E00707E00C03E01C01E0 3801E07801E07001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E07001E07801E0 3801E01801E00C03F0070DFE01F1FE17237EA21B>I<01FC000707000C03801C01C03801 C07801E07000E0F000E0FFFFE0F00000F00000F00000F00000F000007000007800603800 601C00C00E018007070000FC0013157F9416>I<003E0000E30001C78003CF80038F8007 8700078000078000078000078000078000078000078000078000FFF800FFF80007800007 800007800007800007800007800007800007800007800007800007800007800007800007 80000780000780000780007FFC007FFC00112380A20F>I<00007001F198071E380E0E38 1C07301C07003C07803C07803C07803C07801C07001C07000E0E000F1C0019F000100000 1000001800001800001FFE000FFFC00FFFE03801F0700070600038E00038E00038E00038 6000307000703800E00E038003FE0015217F9518>I<0F0000FF0000FF00001F00000F00 000F00000F00000F00000F00000F00000F00000F00000F00000F00000F0F800F31C00F40 E00F80F00F80F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00 F00F00F00F00F00F00F00F00F0FFF3FFFFF3FF18237FA21B>I<0E001F001F001F000E00 000000000000000000000000000000000F00FF00FF001F000F000F000F000F000F000F00 0F000F000F000F000F000F000F000F000F00FFE0FFE00B2280A10D>I<007000F800F800 F8007000000000000000000000000000000000007807F807F800F8007800780078007800 7800780078007800780078007800780078007800780078007800780078007800787078F8 70F870F8E071C01F000D2C83A10F>I<0F0000FF0000FF00001F00000F00000F00000F00 000F00000F00000F00000F00000F00000F00000F00000F0FFC0F0FFC0F03E00F03800F07 000F0E000F1C000F38000F78000FFC000FBE000F1E000F1F000F0F800F07800F07C00F03 C00F03E00F03F0FFE7FEFFE7FE17237FA21A>I<0F00FF00FF001F000F000F000F000F00 0F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F000F00 0F000F000F000F000F000F000F00FFF0FFF00C2380A20D>I<0F0FC07E00FF30E18700FF 407203801F807C03C00F807C03C00F007803C00F007803C00F007803C00F007803C00F00 7803C00F007803C00F007803C00F007803C00F007803C00F007803C00F007803C00F0078 03C00F007803C00F007803C0FFF3FF9FFCFFF3FF9FFC26157F9429>I<0F0F80FF31C0FF 40E01F80F00F80F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F 00F00F00F00F00F00F00F00F00F0FFF3FFFFF3FF18157F941B>I<01FC000707000C0180 1800C03800E0700070700070F00078F00078F00078F00078F00078F00078F00078700070 7800F03800E01C01C00E038007070001FC0015157F9418>I<0F1F00FF61C0FF80600F00 700F00380F003C0F001C0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F003C0F00 3C0F00380F00700F80E00F61C00F3F000F00000F00000F00000F00000F00000F00000F00 000F0000FFF000FFF000171F7F941B>I<01F860070CE00E02E01C03E03801E07801E078 01E0F001E0F001E0F001E0F001E0F001E0F001E0F001E07001E07801E03801E01C03E00C 03E0070DE001F1E00001E00001E00001E00001E00001E00001E00001E00001E0001FFE00 1FFE171F7E941A>I<0F3CFF46FF8F1F8F0F860F000F000F000F000F000F000F000F000F 000F000F000F000F000F00FFF8FFF810157F9413>I<0FC8307860386018E018E018F000 FC007FC03FE01FF007F8007CC03CC01CC01CE01CE018F038D8708FC00E157E9413>I<03 0003000300030003000700070007000F001F003FF8FFF80F000F000F000F000F000F000F 000F000F000F000F0C0F0C0F0C0F0C0F0C0F0C0708039801F00E1F7F9E13>I<0F00F0FF 0FF0FF0FF01F01F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F 00F00F00F00F00F00F01F00F01F00702F80386FF00F8FF18157F941B>III<7FE3FF007FE3FF0007C1F00003C0E00003E1C00001E3800000 F3000000FF0000007E0000003C0000003E0000003E0000007F00000067800000C7C00001 C3C0000181E0000381F0000F81F800FFC3FF80FFC3FF80191580941A>II<3FFFC03C0780380F80300F00701E 00603E00603C0060780000F80000F00001E00003C00007C0C00780C00F00C01F01C01E01 803C01807C0380780780FFFF8012157F9416>II<7070F8F8F8F8F8 F870700D057BA118>127 D E /Ft 63 128 df<00001FC0F8000070718E0000E0F31E00 01C0F71E0001C0660C0003800E000003800E000003800E000003800E000007001C000007 001C000007001C000007001C000007001C0000FFFFFFC000FFFFFFC0000E003800000E00 3800000E003800001C007000001C007000001C007000001C007000001C007000001C00E0 00003800E000003800E000003800E000003800E000003801C000007001C000007001C000 007001C000007001C00000E003800000E003800000E003800000E003800001C007000001 C007000071CE060000F19E0E0000F31E1C0000620C3000003C07E00000272D82A21E>11 D<00001FE0000078380000E01C0001C03C0001803C000380380003800000038000000700 0000070000000700000007000000070000000E000000FFFFE000FFFFE0000E00E0000E01 C0001C01C0001C01C0001C01C0001C0380001C0380003803800038038000380700003807 00003807080070070C00700E1800700E1800700E1800700E3000E0062000E003C000E000 0000E0000001C0000001C0000001C0000071800000F1800000F3000000620000003C0000 001E2D82A21B>I<0E1E1E1E1E02020404080810204080070F7D840F>44 DI<70F8F8F0E005057A840F>I<000F800030C000E06001C0 700380700300700700700F00700E00701E00701E00701C00F03C00F03C00F03C00F07801 E07801E07801E07801E0F003C0F003C0F003C0F00380E00780E00780E00700E00F00E00E 00E01C00E01C00E0380060700030E0001F000014227AA019>48 D<000100030007000E00 1E003E03EE039C001C001C001C0038003800380038007000700070007000E000E000E000 E001C001C001C001C00380038003800780FFFCFFFC10217AA019>I<000FC00030600060 3800801801801C03001C02201E06101E0C101E0C101E0C101E18203C18203C18403C1840 781880F00F00E00001C0000780000E00003C0000700001E0000380000600000C00181800 381800303000707F80E063FFC0E0FF80C07F00C01E0017227CA019>I<000FC000307000 C01801801C03001C06000C06401C0C201C0C201C0C201C0C40380C40380780700000E000 01C0007F8000FE00000E000003000003800001C00001C00003C00003C06003C0F003C0F0 0380E00780800700C00E00C01C0040380020F0001F800016227BA019>I<063C0306FE06 07FE060FFE0C0F861C1E02381C01F83800303000707000606000E0C001C00001C0000380 000380000700000700000F00000E00001E00001E00003C00003C00003C00007800007800 00F80000F00000F00000F00001F00001E00001E00000C00018227AA019>55 D<000FC0003FE000707000E03801C03803801C03801C07003807003807003807807007C0 E007E0C003F38001FE0000FC0000FE0003BF00061F800C07C01803C03803C07001C07001 C0E001C0E001C0E00180E00380E00300E00600700E007838003FF0000FC00016227BA019 >I<000FC0003FE000787000E03001C0380380380780380780380F00380F00380F00381E 00781E00781E00781E00F81E00F01C00F00C01F00E02F00605E00309E001F1E00003C000 03C0000380000700000700600E00F01C00F03800E07000E0E0007FC0003F000015227BA0 19>I<07000F800F800F000E000000000000000000000000000000000000000000000070 00F800F800F000E00009157A940F>I<1FFFFFFF1FFFFFFF000000000000000000000000 0000000000000000000000000000000000000000FFFFFFF8FFFFFFF8200C7B9125>61 D<007C000182000301000401800C0180180180100180300180600180600380400300E007 00F01E00F03C00E0780000F00001E0000780000F00001E00001C00001830001060001060 0019C0000F00000000000000000000000000000000001C00003E00003E00003C00003800 00112477A319>63 D<00000300000007000000070000000F0000000F8000001F8000001F 800000378000007780000067800000C7800000C780000187800001878000030780000307 8000060780000E0780000C0780001807800018078000300780003FFFC0007FFFC0006003 C000C003C001C003C0018003C0030003C0030003C0060003C0060003C01E0003C0FFC03F FCFF803FFC1E237DA224>65 D<00FFFFE000FFFFF8000F007C000F003E001E001E001E00 1E001E001F001E001F003C001E003C003E003C003E003C007C00780078007800F0007801 E0007807C000FFFF8000F001E000F000F000F000F801E0007801E0007801E0007C01E000 7C03C000F803C000F803C000F803C001F0078001E0078003E007800FC007801F00FFFFFE 00FFFFF00020227DA122>I<00007F01800003FF8300000FC0E700003E0067000078003F 0000F0001E0001E0001E0003C0001E000780001E000F80000C000F00000C001F00000C00 3E00000C003E000018007C000000007C000000007C00000000F800000000F800000000F8 00000000F800000000F800000000F000000000F000006000F000006000F00000C000F000 00C000F800018000780001800078000300003C000600001E000C00001F0038000007C0F0 000003FFC0000000FE000000212479A223>I<00FFFFF00000FFFFFC00000F003E00000F 000F00001E000780001E000780001E0003C0001E0003C0003C0003C0003C0003E0003C00 03E0003C0003E000780003E000780003E000780003E000780003E000F00007C000F00007 C000F00007C000F00007C001E0000F8001E0000F8001E0000F0001E0001F0003C0001E00 03C0003C0003C0007C0003C0007800078000F000078001E000078007800007801F0000FF FFFC0000FFFFF0000023227DA125>I<00FFFFFF8000FFFFFF80000F000F80000F000780 001E000380001E000380001E000300001E000300003C000300003C030300003C03030000 3C0303000078060000007806000000781E0000007FFE000000FFFC000000F01C000000F0 1C000000F01C000001E018000001E0180C0001E0180C0001E000180003C000180003C000 300003C000300003C00070000780006000078000E000078003C00007800FC000FFFFFFC0 00FFFFFF800021227DA121>I<00FFFFFF00FFFFFF000F001F000F0007001E0007001E00 07001E0006001E0006003C0006003C0006003C0306003C0306007806000078060000780E 0000781E0000FFFC0000FFFC0000F01C0000F01C0001E0180001E0180001E0180001E018 0003C0000003C0000003C0000003C0000007800000078000000780000007800000FFFC00 00FFFC000020227DA120>I<00007F01800003FF8300000FC0E700003E0067000078003F 0000F0001E0001E0001E0003C0001E000780001E000F80000C000F00000C001F00000C00 3E00000C003E000018007C000000007C000000007C00000000F800000000F800000000F8 00000000F800000000F8003FFC00F0003FFC00F00001E000F00001E000F00003C000F000 03C000F80003C000780003C00078000780003C000780001E000F80001F001B800007C073 000003FFE1000000FF000000212479A226>I<00FFF87FFC00FFF87FFC000F000780000F 000780001E000F00001E000F00001E000F00001E000F00003C001E00003C001E00003C00 1E00003C001E000078003C000078003C000078003C00007FFFFC0000FFFFF80000F00078 0000F000780000F000780001E000F00001E000F00001E000F00001E000F00003C001E000 03C001E00003C001E00003C001E000078003C000078003C000078003C000078003C000FF F87FFC00FFF87FFC0026227DA124>I<00FFF800FFF8000F00000F00001E00001E00001E 00001E00003C00003C00003C00003C0000780000780000780000780000F00000F00000F0 0000F00001E00001E00001E00001E00003C00003C00003C00003C0000780000780000780 00078000FFF800FFF80015227DA113>I<0007FFC0000FFF8000003C0000003C00000078 000000780000007800000078000000F0000000F0000000F0000000F0000001E0000001E0 000001E0000001E0000003C0000003C0000003C0000003C0000007800000078000000780 0000078000000F0000000F0000380F0000780F0000F81E0000F81E0000F03C0000403800 006070000030E000001F8000001A237CA11A>I<00FFF80FFC00FFF80FFC000F0007C000 0F000700001E000E00001E001C00001E003800001E006000003C00C000003C018000003C 030000003C0E000000781C0000007838000000787800000078FC000000F1BC000000F33C 000000FE1E000000FC1E000001F01F000001E00F000001E00F000001E00F800003C00780 0003C007800003C003C00003C003C000078003C000078001E000078001E000078001F000 FFF80FFE00FFF80FFE0026227DA125>I<00FFFC0000FFFC00000F0000000F0000001E00 00001E0000001E0000001E0000003C0000003C0000003C0000003C000000780000007800 00007800000078000000F0000000F0000000F0000000F0000001E0000001E0006001E000 6001E000C003C000C003C000C003C0018003C00180078003800780070007800F0007807F 00FFFFFE00FFFFFE001B227DA11F>I<00FFC0000FFC00FFC0000FFC000FC0001F80000F C0003780001BC0003F00001BC0006F00001BC0006F00001BC000CF000033C0019E000033 C0019E000033C0031E000031E0031E000061E0063C000061E0063C000061E00C3C000061 E0183C0000C1E018780000C1E030780000C1E030780000C1E06078000181E0C0F0000181 E0C0F0000181E180F0000180F180F0000300F301E0000300F601E0000300F601E0000300 FC01E0000600FC03C0000600F803C0000600F803C0001F00F003C000FFE0E07FFC00FFE0 E07FFC002E227DA12C>I<00FF001FFC00FF801FFC000F8003C0000F800380001BC00300 001BC00300001BC003000019E003000031E006000031E006000030F006000030F0060000 60F00C000060780C000060780C000060780C0000C03C180000C03C180000C03C180000C0 1E180001801E300001801E300001800F300001800F300003000F6000030007E000030007 E000030007E000060007C000060003C000060003C0001F0003C000FFE0018000FFE00180 0026227DA124>I<0000FE0000078380000E00E0003800F00070007800E0003801C0003C 03C0003C0780003C0F00003E1F00003E1E00003E3E00003E3E00003E7C00003E7C00003E 7C00003EF800007CF800007CF800007CF8000078F80000F8F00000F8F00001F0F00001F0 F00003E0F00003C0F00007C0F800078078000F0078001E003C003C001C0078000E00E000 0783800001FC00001F2479A225>I<00FFFFE000FFFFF8000F007C000F001E001E001F00 1E000F001E000F001E000F003C001F003C001F003C001F003C001E0078003E0078003C00 780078007800F000F003C000FFFF0000F0000000F0000001E0000001E0000001E0000001 E0000003C0000003C0000003C0000003C0000007800000078000000780000007800000FF F80000FFF8000020227DA121>I<0000FE0000078380000E01E0003800F00070007800E0 007801C0003C03C0003C0780003C0F00003E1F00003E1E00003E3E00003E3E00003E7C00 003E7C00003E7C00003EF800007CF800007CF800007CF8000078F80000F8F00000F8F000 00F0F00001F0F00001E0F00003C0F00007C0F01C078078610F0078811E0038813C001C81 78000E81E0000783804001FD8040000180C000018080000181800001C3000003FF000001 FE000001FE000001FC000000F0001F2D79A225>I<00FFFFC000FFFFF0000F00F8000F00 3C001E001E001E001E001E001E001E001E003C003E003C003E003C003E003C007C007800 78007800F0007801E00078078000FFFC0000F00C0000F0060000F0070001E0070001E007 8001E0078001E0078003C00F8003C00F8003C00F8003C00F8007801F8007801F8307801F 8307800F86FFF80F86FFF8078C000001F020237DA124>I<0001F060000FFCC0001E0FC0 003807C0007003C000E0038000C0038001C0038001C00380038003000380030003C00000 03C0000003E0000001F8000001FF000000FFE000007FF000001FF8000003FC0000007C00 00003C0000001E0000001E0000001E0030001C0030001C0030001C003000180070003800 70007000780060007C01C000EF038000C7FF000081FC00001B247DA21B>I<1FFFFFF81F FFFFF81E03C0783803C03838078038300780386007803060078030600F0030C00F0030C0 0F0030C00F0030001E0000001E0000001E0000001E0000003C0000003C0000003C000000 3C00000078000000780000007800000078000000F0000000F0000000F0000000F0000001 E0000001E0000001E0000003E00000FFFF8000FFFF00001D2277A123>I<3FFE07FF3FFE 07FF03C000F003C000E0078000C0078000C0078000C0078000C00F0001800F0001800F00 01800F0001801E0003001E0003001E0003001E0003003C0006003C0006003C0006003C00 060078000C0078000C0078000C0078000C00F0001800F0001800F0003000700030007000 60007000C00038018000380300001E0E00000FFC000003F00000202377A124>I87 D<00F8C0018DC00707C00E07800E03801C03803C0380380700780700780700780700F00E 00F00E00F00E10F00E18F01C30701C30703C30307C6030CC400F078015157B9419>97 D<03C03F803F800380038007000700070007000E000E000E000E001C001CF81D8C1E0E3C 063C073807380F700F700F700F700FE01EE01EE01EE03CE038E038607060E031C01F0010 237BA216>I<007E0001C3000301800703800E07801C07803C0000380000780000780000 780000F00000F00000F00000F00000F00100700300700600301C001838000FC00011157B 9416>I<00003C0003F80003F80000380000380000700000700000700000700000E00000 E00000E00000E00001C000F9C0018DC00707C00E07800E03801C03803C03803807007807 00780700780700F00E00F00E00F00E10F00E18F01C30701C30703C30307C6030CC400F07 8016237BA219>I<00F803840E061C063C063806780CF038FFE0F000F000E000E000E000 E000E002E006600C703830700F800F157A9416>I<00003C0000C70001CF0001CF000386 000380000380000380000700000700000700000700000700000E0000FFF000FFF0000E00 000E00001C00001C00001C00001C00001C00003800003800003800003800003800007000 00700000700000700000700000E00000E00000E00000E00001C00001C00001C000718000 F38000F300006200003C0000182D82A20F>I<001F180031B800E0F801C0F001C0700380 700780700700E00F00E00F00E00F00E01E01C01E01C01E01C01E01C01E03800E03800E07 80060F80061F0001E700000700000700000E00000E00000E00701C00F01800F0300060E0 003F8000151F7E9416>I<00F0000FE0000FE00000E00000E00001C00001C00001C00001 C000038000038000038000038000070000071F0007618007C0C00F80E00F00E00F00E00E 00E01E01C01C01C01C01C01C01C038038038038038038438070670070C700E0C700E1870 0610E006206003C017237DA219>I<006000F000E000E000000000000000000000000000 0000000E00118021806180C380C380C380070007000E000E000E001C001C201C30386038 60384038C019800E000C217CA00F>I<00F0000FE0000FE00000E00000E00001C00001C0 0001C00001C0000380000380000380000380000700000701E0070230070C700E10F00E10 F00E20600E40001D80001E00001FC0001C7000383800383800381C20381C307038607038 607038407018C0E01880600F0014237DA216>107 D<01E01FC01FC001C001C003800380 0380038007000700070007000E000E000E000E001C001C001C001C003800380038003800 7000700071007180E300E300E300E20066003C000B237CA20C>I<1E07C07C0033186186 0063B033030063E03E0380C3C03C0380C3C03C0380C38038038007807807000700700700 070070070007007007000E00E00E000E00E00E000E00E00E100E00E01C181C01C01C301C 01C038301C01C038601C01C0184038038018801801800F0025157C9428>I<1E07803318 E063B06063E070C3C070C38070C380700700E00700E00700E00700E00E01C00E01C00E01 C20E03831C03861C07061C070C1C03083803101801E018157C941B>I<007E0001C30003 81800701C00E01C01C01E03C01E03801E07801E07801E07801E0F003C0F003C0F00380F0 0780700700700E00700C0030180018700007C00013157B9419>I<03C1F00663180C741C 0C780C18780E18700E18701E00E01E00E01E00E01E00E01E01C03C01C03C01C03C01C078 03C07003C07003C0E003C1C0076380071E000700000700000E00000E00000E00000E0000 1C00001C0000FFC000FFC000171F7F9419>I<00F840018CC00707C00E07800E03801C03 803C0380380700780700780700780700F00E00F00E00F00E00F00E00F01C00701C00703C 00307C0030F8000F380000380000380000700000700000700000700000E00000E0000FFE 000FFE00121F7B9416>I<1E0F8033184063A0E063C1E0C3C1E0C380C0C3800007000007 00000700000700000E00000E00000E00000E00001C00001C00001C00001C000038000018 000013157C9415>I<00FC000183000201800403800C07800C07800C02000F00000FF000 07FC0003FE00003E00000F00000700700700F00600F00600E004006008003030001FC000 11157D9414>I<00C001C001C001C001C003800380038003800700FFF8FFF807000E000E 000E000E001C001C001C001C00380038003810381870307030706070C031801E000D1F7C 9E10>I<0F003011807021C07061C0E0C1C0E0C380E0C380E00381C00701C00701C00701 C00E03800E03800E03840E03860E070C0C070C0E070C0E0F1806131003E1E017157C941A >I<0F01C01183E021C3E061C1E0C1C0E0C380E0C380E00380C00700C00700C00700C00E 01800E01800E01800E03000E03000E02000E04000E0C0006180001E00013157C9416>I< 0F003070118070F821C070F861C0E078C1C0E038C380E038C380E0380381C0300701C030 0701C0300701C0300E0380600E0380600E0380600E0380C00E0380C00E0780800E078180 060F83000319C60001F078001D157C9420>I<03C1C00C6630183C70303CF02038F06038 6060380000700000700000700000700000E00000E00000E02000E03061C060F1C060F1C0 C0E3C0804663003C3E0014157D9416>I<0F001811803821C03861C070C1C070C38070C3 80700380E00700E00700E00700E00E01C00E01C00E01C00E01C00E03800E03800E07800E 0780061F0001E700000700000700000E00300E00781C0078180070300060600021C0001F 0000151F7C9418>I<00F03003F83007FC60060FC00C01800C0300000600000C00001800 00300000600000C0000180000300400600600C00C01801C03F838070FF00607E00C03800 14157E9414>I<3038787CF87CF87870700E0573A119>127 D E /Fu 22 122 df6 D<0102040C1818303070606060E0E0E0E0E0E0E0E0E0E060606070 303018180C04020108227D980E>40 D<8040203018180C0C0E0606060707070707070707 07070606060E0C0C18183020408008227E980E>I<003000003000003000003000003000 003000003000003000003000003000003000FFFFFCFFFFFC003000003000003000003000 00300000300000300000300000300000300000300016187E931B>43 D<07C018303018701C600C600CE00EE00EE00EE00EE00EE00EE00EE00EE00E600C600C70 1C30181C7007C00F157F9412>48 D<03000F00FF00F70007000700070007000700070007 00070007000700070007000700070007007FF07FF00C157E9412>I<1F803FE071F0F870 F878F838703800780070007000E001C00180030006000C18101820387FF0FFF0FFF00D15 7E9412>I<0FC01FF03038783C781C783C103C0038007007E00070003C001C001E701EF8 1EF81EF83C70783FF00FC00F157F9412>I<0030007000F001F00170037006700C700870 187030706070C070FFFEFFFE007000700070007003FE03FE0F157F9412>I<60307FE07F C07F8060006000600060006F8070E060700070007800787078F078F078E07060E03FC01F 000D157E9412>I61 D66 D72 D78 D80 D91 D93 D<0F9E18E73067707070707070306018C02F80200060003FE03F F83FFC600EC006C006C006600C38380FE010157F8D12>103 D108 D<07C018303018600C600CE00EE00EE00EE00EE00E701C3018183007 C00F0E7F8D12>111 DI121 D E /Fv 47 122 df<000FF000007FFC0001FC 1E0003F03E0007E07F000FC07F000FC07F000FC07F000FC03E000FC008000FC000000FC0 00000FC00000FFFFFF00FFFFFF00FFFFFF000FC03F000FC03F000FC03F000FC03F000FC0 3F000FC03F000FC03F000FC03F000FC03F000FC03F000FC03F000FC03F000FC03F000FC0 3F000FC03F000FC03F007FF0FFE07FF0FFE07FF0FFE01B237FA21F>12 D<00180030006000E001C00380078007000F001F001E003E003E003C007C007C007C007C 00FC00F800F800F800F800F800F800F800F800F800F800F800FC007C007C007C007C003C 003E003E001E001F000F0007000780038001C000E00060003000180D317BA416>40 DI<3C00 7E00FF00FF00FF80FF807F803D800180018003000300070006000C001C00380020000912 7C8710>44 D<3C7EFFFFFFFF7E3C08087C8710>46 D<00180000780003F800FFF800FFF8 00FDF80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8 0001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8 007FFFE07FFFE07FFFE013207C9F1C>49 D<03FC000FFF003FFFC0783FE07C0FF0FE07F0 FE03F8FE03F8FE03F87C03F83803F80003F80003F00007F00007E0000FC0001F80001F00 003C0000780000F00001E03803C0380700380600380C00781FFFF03FFFF07FFFF0FFFFF0 FFFFF0FFFFF015207D9F1C>I<01FE0007FF800FFFE01F07F03F03F03F03F83F83F83F03 F81F03F80C03F80003F00007E00007C0001F8001FE0001FF000007E00003F00001F80001 FC0001FE0001FE7C01FE7C01FEFE01FEFE01FCFE01FC7C03F87C07F03FFFE00FFFC003FE 0017207E9F1C>I<3C7EFFFFFFFF7E3C0000000000003C7EFFFFFFFF7E3C08167C9510> 58 D<00007000000000F800000000F800000000F800000001FC00000001FC00000003FE 00000003FE00000003FE000000077F000000077F0000000F7F8000000E3F8000000E3F80 00001E3FC000001C1FC000001C1FC00000380FE00000380FE00000780FF000007007F000 007007F00000FFFFF80000FFFFF80001FFFFFC0001C001FC0001C001FC0003C001FE0003 8000FE00038000FE000700007F00FFF00FFFF8FFF00FFFF8FFF00FFFF825227EA12A>65 D<0003FE0180001FFF838000FFFFE78001FF00FF8003F8003F8007F0001F800FE0000F80 1FC0000F803F800007803F800007807F800003807F000003807F00000380FF00000000FF 00000000FF00000000FF00000000FF00000000FF00000000FF00000000FF000000007F00 0000007F000003807F800003803F800003803F800007801FC00007000FE0000F0007F000 1E0003F8003C0001FF00F80000FFFFF000001FFFC0000003FE000021227DA128>67 DII<0003FE 00C0001FFFC1C0007FFFF3C001FF80FFC003FC003FC007F0000FC00FE00007C01FC00007 C03FC00003C03F800003C07F800001C07F000001C07F000001C0FF00000000FF00000000 FF00000000FF00000000FF00000000FF00000000FF00000000FF000FFFFC7F000FFFFC7F 000FFFFC7F80001FC03F80001FC03FC0001FC01FC0001FC00FE0001FC007F0001FC003FC 001FC001FF807FC0007FFFF7C0001FFFE3C00003FF00C026227DA12C>71 DII75 DI< FFF800001FFFFFF800001FFFFFFC00003FFF07FC00003FE007FC00003FE0077E000077E0 077E000077E0073F0000E7E0073F0000E7E0071F8001C7E0071F8001C7E0071F8001C7E0 070FC00387E0070FC00387E00707E00707E00707E00707E00703F00E07E00703F00E07E0 0703F00E07E00701F81C07E00701F81C07E00700FC3807E00700FC3807E007007E7007E0 07007E7007E007007E7007E007003FE007E007003FE007E007001FC007E007001FC007E0 07000F8007E0FFF80F80FFFFFFF80F80FFFFFFF80700FFFF30227EA135>II<0007FC0000003FFF 800000FE0FE00003F803F80007E000FC000FC0007E001FC0007F001F80003F003F80003F 803F80003F807F00001FC07F00001FC07F00001FC0FF00001FE0FF00001FE0FF00001FE0 FF00001FE0FF00001FE0FF00001FE0FF00001FE0FF00001FE0FF00001FE07F00001FC07F 80003FC07F80003FC03F80003F803FC0007F801FC0007F000FE000FE0007F001FC0003F8 03F80000FE0FE000003FFF80000007FC000023227DA12A>II82 D<01FC0C07FF9C1FFFFC3F03FC7C00 FC78007C78003CF8001CF8001CF8001CFC0000FF0000FFE0007FFF007FFFC03FFFF01FFF F80FFFFC03FFFE003FFE0003FF00007F00003F00001FE0001FE0001FE0001FF0001EF000 3EFC003CFF00FCFFFFF8E7FFE0C0FF8018227DA11F>I<7FFFFFFF807FFFFFFF807FFFFF FF807E03F81F807C03F807807803F807807003F80380F003F803C0F003F803C0E003F801 C0E003F801C0E003F801C0E003F801C00003F800000003F800000003F800000003F80000 0003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F800000003F800000003F8000003FF FFF80003FFFFF80003FFFFF80022227EA127>II87 D89 D<07FC001FFF803F0FC03F07E03F03E03F03F01E03F00003F00003F0 00FFF007FFF01FC3F03F03F07E03F0FC03F0FC03F0FC03F0FC03F07E07F07E1DFF1FF8FF 07E07F18167E951B>97 D<00FF8007FFE00F83F01F03F03E03F07E03F07C01E07C0000FC 0000FC0000FC0000FC0000FC0000FC00007C00007E00007E00003E00701F00E00FC1E007 FFC000FE0014167E9519>99 D<0003FE000003FE000003FE0000007E0000007E0000007E 0000007E0000007E0000007E0000007E0000007E0000007E0000007E0001FE7E0007FFFE 000F81FE001F00FE003E007E007E007E007C007E00FC007E00FC007E00FC007E00FC007E 00FC007E00FC007E00FC007E00FC007E007C007E007C007E003E007E001E00FE000F83FF C007FF7FC001FC7FC01A237EA21F>I<00FE0007FF800F87C01E01E03E01F07C00F07C00 F8FC00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E00381F00 700FC0F003FFC000FF0015167E951A>I<003F8000FFC001F3E003E7E007C7E00FC7E00F C3C00FC0000FC0000FC0000FC0000FC0000FC000FFFC00FFFC00FFFC000FC0000FC0000F C0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000F C0000FC0007FFC007FFC007FFC0013237FA211>I<01FE1F0007FFFF800F87E7801F03E7 801E01E7003E01F0003E01F0003E01F0003E01F0003E01F0001E01E0001F03E0000F87C0 000FFF800019FE0000180000001C0000001C0000001FFFE0001FFFF8000FFFFE000FFFFF 003FFFFF007C003F80F8001F80F8000F80F8000F80F8000F807C001F007E003F001F80FC 000FFFF80001FFC00019217F951C>II<0E003F003F807F807F803F803F000E0000 0000000000000000000000FF80FF80FF801F801F801F801F801F801F801F801F801F801F 801F801F801F801F801F801F80FFF0FFF0FFF00C247FA30F>I108 DII<00FE0007FFC00F83E01E00F03E00F87C00 7C7C007C7C007CFC007EFC007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00 F81F01F00F83E007FFC000FE0017167E951C>II114 D<07F3001FFF00781F00700F00F00700F00700F80000FF 0000FFF0007FFC003FFE001FFF0007FF00003F80E00F80E00780F00780F00780F80700FC 1E00FFFC00C7F00011167E9516>I<01C00001C00001C00001C00003C00003C00003C000 07C00007C0000FC0003FFF00FFFF00FFFF000FC0000FC0000FC0000FC0000FC0000FC000 0FC0000FC0000FC0000FC0000FC3800FC3800FC3800FC3800FC3800FC30007E70003FE00 00FC0011207F9F16>II120 DI E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 600 53 a Fv(COUNTING)19 b(HIERAR)n(CHIES:)198 114 y(POL)-5 b(YNOMIAL)19 b(TIME)g(AND)g(CONST)-5 b(ANT)19 b(DEPTH)g(CIR)n(CUITS)684 415 y(ERIC)f(W.)h(ALLENDER)1248 396 y Fu(1)406 475 y Ft(Dep)n(artment)e(of)h(Computer)f(Scienc)n(e,)i (R)o(utgers)f(University)626 535 y(New)h(Brunswick,)g(NJ)e(08903,)g (USA)936 655 y Fs(and)694 776 y Fv(KLA)n(US)i(W.)f(W)-6 b(A)n(GNER)491 836 y Ft(Institut)19 b(f)q(\177)-26 b(ur)17 b(Informatik,)g(Universit\177)-25 b(at)18 b(W)q(\177)-26 b(urzbur)n(g)719 896 y(D-8700)17 b(W)q(\177)-26 b(urzbur)n(g,)17 b(FR)o(G)875 1097 y Fr(Abstract)265 1221 y Fq(In)e(the)g(spring)f(of)g (1989,)g(Seinosuk)o(e)g(T)l(o)q(da)h(of)f(the)h(Univ)o(ersit)o(y)e(of)h (Electro-Comm)o(u-)197 1277 y(nications)i(in)h(T)l(oky)o(o,)f(Japan,)i (pro)o(v)o(ed)f(that)f(the)i(p)q(olynomial)c(hierarc)o(h)o(y)j(is)f (con)o(tained)197 1334 y(in)h(P)283 1317 y Fu(PP)350 1334 y Fq([T)l(o-89].)24 b(In)18 b(this)e(Structural)g(Complexit)o(y)f (Column,)h(w)o(e)h(will)e(brie\015y)i(review)197 1390 y(T)l(o)q(da's)c(result,)g(and)h(explore)f(ho)o(w)g(it)g(relates)f(to)h (other)g(topics)g(of)g(in)o(terest)g(in)g(computer)197 1447 y(science.)20 b(In)c(particular,)e(w)o(e)h(will)e(in)o(tro)q(duce) j(the)f(reader)g(to)197 1523 y Fr(The)j(Coun)o(ting)f(Hierarc)o(h)o(y:) k Fq(a)j(hierarc)o(h)o(y)e(of)i(complexit)o(y)d(classes)i(con)o(tained) g(in)304 1580 y(PSP)l(A)o(CE)15 b(and)h(con)o(taining)e(the)h(P)o (olynomial)d(Hierarc)o(h)o(y)l(.)197 1655 y Fr(Threshold)17 b(Circuits:)22 b Fq(circuits)c(constructed)g(of)g(MAJORITY)i(gates;)f (this)f(notion)304 1712 y(of)e(circuit)g(is)g(b)q(eing)g(studied)h(not) f(only)g(b)o(y)g(complexit)o(y)e(theoreticians,)i(but)g(also)304 1768 y(b)o(y)f(researc)o(hers)g(in)g(an)g(activ)o(e)g(sub\014eld)h(of)e (AI)i(studying)f(\\neural)g(net)o(w)o(orks".)265 1844 y(Along)g(the)h(w)o(a)o(y)l(,)e(w)o(e'll)g(review)h(the)h(imp)q(ortan)o (t)d(notion)i(of)g(an)g Fp(op)n(er)n(ator)h Fq(on)g(a)f(com-)197 1901 y(plexit)o(y)f(class.)75 2055 y Fv(1.)24 b(The)19 b(Coun)n(ting)h(Hierarc)n(h)n(y)-5 b(,)19 b(and)g(Op)r(erators)f(on)h (Complexit)n(y)g(Classes)148 2165 y Fs(The)i(coun)o(ting)i(hierarc)o(h) o(y)d(w)o(as)i(de\014ned)f(in)h([W)l(a-86])g(and)g(indep)q(enden)o(tly) f(b)o(y)g(P)o(arb)q(erry)75 2225 y(and)j(Sc)o(hnitger)f(in)h([PS-88].) 43 b(\(The)24 b(motiv)m(ation)h(for)f([W)l(a-86])g(w)o(as)f(the)g (desire)h(to)g(classify)75 2285 y(precisely)19 b(the)g(complexit)o(y)f (of)i(certain)f(com)o(binatorial)i(problems)f(on)f(graphs)h(with)g (succinct)75 2345 y(descriptions.)26 b(P)o(arb)q(erry)17 b(and)h(Sc)o(hnitger)g(w)o(ere)f(studying)h(\\threshold)h(T)l(uring)g (mac)o(hines")e(in)75 2406 y(connection)h(with)h(parallel)h (computation.\))26 b(One)18 b(w)o(a)o(y)f(to)h(de\014ne)f(the)h(coun)o (ting)g(hierarc)o(h)o(y)f(is)75 2466 y(to)g(tak)o(e)e(the)h(usual)i (de\014nition)g(of)e(the)g(p)q(olynomial)j(hierarc)o(h)o(y:)p 75 2508 720 2 v 131 2539 a Fo(1)150 2554 y Fn(Supp)q(orted)c(in)e(part) h(b)o(y)g(National)e(Science)k(F)m(oundation)c(Gran)o(ts)i(CCR-8810467) e(and)h(CCR-9204874)p eop %%Page: 2 2 2 1 bop 148 53 a Fm(\017)24 b Fs(\006)232 30 y Fl(p)232 64 y Fu(0)268 53 y Fs(=)16 b(P)148 151 y Fm(\017)24 b Fs(\006)232 128 y Fl(p)232 164 y(k)q Fu(+1)315 151 y Fs(=)16 b(NP)439 133 y Fu(\006)464 117 y Fk(p)464 146 y(k)502 151 y Fs(for)g Fj(k)g Fm(\025)e Fs(0.)75 301 y(and)k(replace)f(\\NP")h(with)g(\\PP".)f(\(Recall)h(that)g(PP)f(is)h (\\probabilis)q(tic)i(p)q(olynomial)g(time")d(as)75 361 y(de\014ned)h(b)o(y)g(Gill)i([Gi-77])f(and)g(Simon)g([Si-77];)g Fj(L)f Fs(is)h(in)g(PP)1214 343 y Fl(A)1261 361 y Fs(if)g(there)f(is)h (a)f(p)q(olynomial-ti)q(me)75 421 y(nondeterministic)g(oracle)f(T)l (uring)g(mac)o(hine)f Fj(M)22 b Fs(suc)o(h)16 b(that)h Fj(x)d Fm(2)g Fj(L)j Fs(i\013)g(more)f(than)h(half)h(of)e(the)75 482 y(computation)i(paths)f(of)g Fj(M)22 b Fs(on)17 b(input)g Fj(x)f Fs(with)h(oracle)h Fj(A)e Fs(are)g(accepting.\))23 b(That)17 b(giv)o(es)f(us)h(the)75 542 y(de\014nition:)148 682 y Fm(\017)24 b Fv(C)237 659 y Fl(p)237 693 y Fu(0)274 682 y Fs(=)16 b(P)148 780 y Fm(\017)24 b Fv(C)237 757 y Fl(p)237 793 y(k)q Fu(+1)320 780 y Fs(=)16 b(PP)440 762 y Fi(C)469 746 y Fk(p)469 775 y(k)507 780 y Fs(for)h Fj(k)f Fm(\025)d Fs(0.)75 921 y(Th)o(us)k Fv(C)239 897 y Fl(p)239 932 y Fu(1)275 921 y Fs(=)f(PP)l(,)g Fv(C)461 897 y Fl(p)461 932 y Fu(2)498 921 y Fs(=)g(PP)618 903 y Fu(PP)669 921 y Fs(,)f(and)i(so)g(on.)148 1031 y(This)i(c)o (haracterization)f(of)g(the)f(coun)o(ting)h(hierarc)o(h)o(y)f(is)h(due) f(to)g(Jacob)q(o)i(T)l(or\023)-24 b(an,)18 b(who)g(has)75 1091 y(studied)i(the)f(coun)o(ting)h(hierarc)o(h)o(y)f(in)h(depth)f([T) l(or-88,)i(T)l(or-91].)31 b(Although)21 b(this)f(is)g(p)q(erhaps)75 1151 y(the)14 b(simplest)g(w)o(a)o(y)g(to)g(de\014ne)g(the)f(coun)o (ting)i(hierarc)o(h)o(y)l(,)e(it)i(is)f(not)h(the)e(original)k (de\014nition,)e(and)75 1212 y(the)f(pro)q(of)h(that)f(this)h(c)o (haracterization)f(\(in)h(terms)e(of)h(oracle)h(T)l(uring)g(mac)o (hines\))f(is)h(equiv)m(alen)o(t)75 1272 y(to)i(the)f(one)g(giv)o(en)g (b)q(elo)o(w)i(\(in)e(terms)g(of)h(generalized)g(quan)o(ti\014ers\))f (is)i(not)e(ob)o(vious.)148 1382 y(Recall)f(that)f(an)h(alternativ)o(e) f(c)o(haracterization)h(of)f(the)g(p)q(olynomial)i(hierarc)o(h)o(y)e (is)h(giv)o(en)f(b)o(y)75 1442 y(applying)h(b)q(ounded)g(existen)o (tial)f(and)g(univ)o(ersal)h(quan)o(ti\014ers)f(to)g(p)q (olynomial-time)i(predicates.)75 1502 y(One)g(w)o(a)o(y)g(to)g (formalize)h(this)h(is)f(to)f(de\014ne)g Ft(op)n(er)n(ators)f Fs(acting)i(on)g(classes)g(of)g(sets.)k(That)c(is:)148 1612 y Fv(De\014nition:)32 b Fs(Let)21 b Fm(C)j Fs(b)q(e)d(a)h(class)g (of)f(languages.)38 b(Then)21 b(de\014ne)g Fm(9)14 b(\001)g(C)24 b Fs(to)e(b)q(e)f(the)g(set)g(of)75 1672 y(all)e(languages)g Fj(L)f Fs(suc)o(h)f(that)h(there)f(is)h(some)f(p)q(olynomial)j Fj(p)e Fs(and)g(some)f(set)h Fj(A)d Fm(2)h(C)k Fs(suc)o(h)e(that)75 1733 y Fj(x)c Fm(2)g Fj(L)g Fm(\()-8 b(\))13 b(9)p Fj(y)k Fs(\()p Fm(j)p Fj(y)q Fm(j)d(\024)f Fj(p)p Fs(\()p Fm(j)p Fj(x)p Fm(j)o Fs(\))k(and)f Fm(h)p Fj(x;)8 b(y)q Fm(i)14 b(2)h Fj(A)p Fs(\).)20 b(In)c(a)h(similar)h(w)o(a)o(y)l(,)d(one)i(can)f (de\014ne)g Fm(8)10 b(\001)h(C)s Fs(.)148 1843 y(It)20 b(is)h(a)f(familiar)i(fact)e([St-77,)i(W)l(r-77])e(that)h(NP)f(=)g Fm(9\001)p Fs(P)l(,)f(\006)1306 1819 y Fl(p)1306 1854 y Fu(2)1346 1843 y Fs(=)i Fm(9)13 b(\001)h(8\001)p Fs(P)l(,)k(and)i(so) h(on.)33 b(It)75 1903 y(has)19 b(turned)g(out)g(to)g(b)q(e)f(useful)h (to)g(consider)h(other)e(op)q(erators,)i(in)g(addition)g(to)f Fm(9)f Fs(and)i Fm(8)p Fs(.)26 b(In)75 1963 y(particular,)17 b(the)f(op)q(erators)i Fv(C)p Fs(,)e Fj(B)s(P)7 b Fs(,)16 b(and)h Fm(\010)f Fs(will)i(b)q(e)e(imp)q(ortan)o(t)i(for)e(this)h (surv)o(ey)l(.)148 2073 y Fv(De\014nition:)22 b Fs(Let)17 b Fm(C)i Fs(b)q(e)d(a)h(class)g(of)g(languages.)23 b(De\014ne)148 2214 y Fm(\017)h Fv(C)p Fm(\001C)d Fs(to)c(b)q(e)g(the)g(set)g(of)h (all)g(languages)i Fj(L)d Fs(suc)o(h)g(that)g(there)g(is)h(some)f(p)q (olynomial)j Fj(p)d Fs(and)197 2274 y(some)f(set)g Fj(A)e Fm(2)g(C)19 b Fs(suc)o(h)d(that)h Fj(x)c Fm(2)h Fj(L)g Fm(\()-8 b(\))523 2384 y(kf)p Fj(y)15 b Fs(:)f Fm(j)p Fj(y)q Fm(j)f(\024)h Fj(p)p Fs(\()p Fm(j)p Fj(x)p Fm(j)o Fs(\))i(and)h Fm(h)p Fj(x;)8 b(y)q Fm(i)14 b(2)g Fj(A)p Fm(gk)f Fj(=)p Fs(2)1309 2366 y Fl(p)p Fu(\()p Fh(j)p Fl(x)p Fh(j)p Fu(\))1410 2384 y Fj(>)h Fs(1)p Fj(=)p Fs(2.)148 2493 y Fm(\017)24 b Fj(B)s(P)c Fm(\001)13 b(C)22 b Fs(to)e(b)q(e)f(the)g(set)g(of)h(all)h(languages)g Fj(L)f Fs(suc)o(h)f(that)h(there)e(is)i(some)f(p)q(olynomial)k Fj(p)197 2554 y Fs(and)17 b(some)f(set)g Fj(A)e Fm(2)g(C)19 b Fs(suc)o(h)d(that)p eop %%Page: 3 3 3 2 bop 381 53 a Fm(kf)p Fj(y)15 b Fs(:)f Fm(j)p Fj(y)q Fm(j)f(\024)h Fj(p)p Fs(\()p Fm(j)p Fj(x)p Fm(j)o Fs(\))i(and)h([)p Fm(h)p Fj(x;)8 b(y)q Fm(i)13 b(2)h Fj(A)30 b Fm(\()-8 b(\))13 b Fj(x)h Fm(2)g Fj(L)p Fs(])p Fm(gk)f Fj(=)p Fs(2)1451 35 y Fl(p)p Fu(\()p Fh(j)p Fl(x)p Fh(j)p Fu(\))1553 53 y Fj(>)g Fs(3)p Fj(=)p Fs(4.)148 176 y Fm(\017)24 b(\010)10 b(\001)g(C)19 b Fs(to)e(b)q(e)f(the)g(set)f(of)i(all)g (languages)h Fj(L)e Fs(suc)o(h)g(that)g(there)g(is)g(some)g(p)q (olynomial)j Fj(p)d Fs(and)197 236 y(some)g(set)g Fj(A)e Fm(2)g(C)19 b Fs(suc)o(h)d(that)h Fj(x)c Fm(2)h Fj(L)g Fm(\()-8 b(\))594 359 y(kf)p Fj(y)16 b Fs(:)d Fm(j)p Fj(y)q Fm(j)g(\024)h Fj(p)p Fs(\()p Fm(j)p Fj(x)p Fm(j)o Fs(\))i(and)h Fm(h)p Fj(x;)8 b(y)q Fm(i)14 b(2)g Fj(A)p Fm(gk)i Fs(is)h(o)q(dd.)148 510 y(\(The)c(original)j(de\014nition)e(of) f([W)l(a-86,)h(W)l(a-86a])g(actually)g(used)f(a)g(more)g(general)g (de\014nition)75 570 y(of)g(the)g(op)q(erator)h Fv(C)p Fs(;)e(ho)o(w)o(ev)o(er)g(it)h(turns)g(out)h(that)f(the)f(complexit)o (y)h(classes)h(de\014ned)e(in)i(this)f(w)o(a)o(y)75 630 y(are)f(quite)h(robust)g(to)g(small)h(c)o(hanges)e(to)h(the)f (de\014nitions,)j(and)e(for)f(an)o(y)g(reasonable)i(complexit)o(y)75 691 y(class)20 b Fm(C)s Fs(,)g(the)f(de\014nition)i(giv)o(en)e(ab)q(o)o (v)o(e)g(is)i(equiv)m(alen)o(t)e(to)h(the)f(de\014nition)i(giv)o(en)e (in)h([W)l(a-86].\))75 751 y(The)c(original)j(de\014nition)f(of)f(the)f (coun)o(ting)h(hierarc)o(h)o(y)f(is)h(th)o(us:)148 902 y Fm(\017)24 b Fv(C)237 879 y Fl(p)237 913 y Fu(0)274 902 y Fs(=)16 b(P)148 1004 y Fm(\017)24 b Fv(C)237 980 y Fl(p)237 1017 y(k)q Fu(+1)320 1004 y Fs(=)16 b Fv(C)p Fm(\001)p Fv(C)468 980 y Fl(p)468 1017 y(k)490 1004 y Fs(.)148 1156 y(Using)23 b(the)e(op)q(erators)i Fm(8)p Fj(;)8 b Fm(9)p Fj(;)g Fm(\010)p Fj(;)19 b Fv(C)p Fs(,)i(and)h Fj(B)s(P)29 b Fs(in)22 b(di\013eren)o(t)f(com)o(binations,)k(one)c (obtains)75 1216 y(other)16 b(in)o(teresting)g(complexit)o(y)f (classes.)22 b(\(This)17 b(list)f(of)g(op)q(erators)h(is)f(b)o(y)f(no)h (means)g(exclusiv)o(e.)75 1276 y(F)l(or)j(example,)h(T)l(or\023)-24 b(an)20 b(has)g(sho)o(wn)g(that)f(an)h(\\exact)f(coun)o(ting")h(v)o (ersion)g(of)f(the)g Fv(C)h Fs(op)q(erator)75 1336 y(\(whic)o(h)e(he)g (denotes)f(b)o(y)h Fv(C)589 1343 y Fu(=)619 1336 y Fs(\))f(is)i(v)o (ery)d(useful)j(to)q(ol)g(for)f(pro)o(ving)h(results)f(ab)q(out)h (other)f(classes)75 1396 y(in)f(the)f(coun)o(ting)h(hierarc)o(h)o(y)f ([T)l(or-88,)h(T)l(or-91].\))148 1506 y(The)24 b Fj(B)s(P)31 b Fs(op)q(erator)25 b(is)g(ob)o(viously)g(a)g(w)o(a)o(y)e(to)i (generalize)f(the)g(notion)i(of)e(probabilistic)75 1566 y(computation)d(to)f(other)f(complexit)o(y)h(classes.)32 b(F)l(or)19 b(example,)h Fj(B)s(P)g Fm(\001)13 b(9\001)p Fs(P)20 b(is)g(the)f(complexit)o(y)75 1627 y(class)e(AM)f ([BM-89,Sc-87].)21 b(The)16 b Fm(\010)g Fs(op)q(erator)h(is)g(a)g(w)o (a)o(y)f(to)g(generalize)h(the)f(complexit)o(y)g(class)75 1687 y(P)o(arit)o(y-P)h(of)f([PZ-83,GP-86].)148 1797 y(W)l(e)d(should)i(men)o(tion)f(that)g(Stathis)h(Zac)o(hos)e(has)i(an)f (alternativ)o(e)g(logic-based)h(form)o(ulation)75 1857 y(for)j(de\014ning)i(complexit)o(y)d(classes)i(of)g(this)g(sort.)27 b(His)19 b(approac)o(h)g(has)g(also)g(b)q(een)f(quite)g(useful)75 1917 y(in)f(pro)o(ving)g(results)g(ab)q(out)h(these)d(classes;)i(see)f ([HZ-84,)g(Za-88,)h(ZH-86,)f(BHZ-87,)g(ZF-87].)148 2027 y(W)l(e)k(w)o(ould)g(no)o(w)g(lik)o(e)g(to)g(brie\015y)g(catalogue)h (some)e(of)h(the)g(kno)o(wn)g(relationships)i(among)75 2087 y(the)f(complexit)o(y)f(classes)i(de\014ned)e(using)j(these)d(op)q (erators.)36 b(Some)21 b(of)g(these)g(inclusions)i(are)75 2148 y(kno)o(wn)18 b(to)g(hold)h(for)f Ft(al)r(l)h Fs(classes)f(of)g (sets)g Fm(C)s Fs(,)g(but)f(some)h(of)g(the)f(other)h(inclusions)i (only)f(hold)g(if)75 2208 y Fm(C)k Fs(is)e(su\016cien)o(tly)e(\\nice".) 33 b(F)l(or)20 b(the)g(sak)o(e)f(of)i(simplicit)o(y)l(,)g(w)o(e)e(will) j(assume)e(here)g(that)g Fm(C)j Fs(is)e(a)75 2268 y(complexit)o(y)c (class)h(de\014ned)f(b)o(y)g(applying)i(the)d(op)q(erators)j(from)e (the)g(set)g Fm(f9)p Fj(;)8 b Fm(8)p Fj(;)g Fm(\010)p Fj(;)g(B)s(P)f Fs(,)14 b Fv(C)p Fm(g)k Fs(to)75 2328 y(the)e(class)h(P)l(.)f(All)h(suc)o(h)f(classes)h(satisfy)h(the)e (appropriate)i(\\niceness")f(conditions.)1642 2310 y Fu(2)p 75 2372 720 2 v 131 2403 a Fo(2)150 2418 y Fn(Note,)12 b(ho)o(w)o(ev)o(er,)g(that)g(one)g(m)o(ust)f(b)q(e)i(careful)f(what)g (one)g(assumes)g(ab)q(out)g(the)g(classes)i Fg(C)r Fn(.)j(Some)11 b(sub)q(classes)75 2467 y(of)17 b(the)h(coun)o(ting)f(hierarc)o(h)o(y)h (\(suc)o(h)g(as)g(PP\))g(seem)f(not)h(to)f(b)q(e)h(closed)g(under)h (union)d(or)i(in)o(tersection)1743 2452 y Ff(\003)1780 2467 y Fn(while)75 2517 y(other)f(classes)h(\(suc)o(h)f(as)g(NP\))g (seem)f(not)g(to)h(b)q(e)g(closed)g(under)g(complemen)o(tation.)23 b(Information)14 b(ab)q(out)i(the)p eop %%Page: 4 4 4 3 bop 148 53 a Fv(Theorem:)20 b Ft(A)e(c)n(atalo)n(g)g(of)f(facts)h (ab)n(out)f(sub)n(classes)i(of)e(the)h(Counting)h(Hier)n(ar)n(chy.)135 205 y Fs(1.)24 b Fm(9)12 b(\001)h(C)22 b([)d(8)12 b(\001)g(C)22 b([)p Fj(B)s(P)e Fm(\001)13 b(C)22 b(\022)c Fv(C)p Fm(\001C)s Fs(.)30 b(\(This)20 b(is)g(a)f(generalization)i(of)e(Gill's)i(result)e ([Gi-77])197 265 y(that)g(NP)e(and)i(coNP)f(are)g(con)o(tained)h(in)g (PP)l(,)f(and)h(also)g(of)g(the)f(trivial)i(inclusion)g(BPP)197 325 y Fm(\022)c Fs(PP)l(.\))135 427 y(2.)24 b Fm(\010)11 b(\001)g(C)17 b(\022)f Fs(P)403 409 y Fi(C)p Fh(\001C)135 529 y Fs(3.)24 b Fm(9)11 b(\001)g(C)19 b Fs(=)d(NP)430 511 y Fh(C)135 630 y Fs(4.)24 b Fv(C)p Fm(\001C)c Fs(=)c(PP)417 612 y Fh(C)456 630 y Fs([T)l(or-91])135 732 y(5.)24 b Fj(B)s(P)18 b Fm(\001)11 b(C)19 b(\022)d Fs(BPP)512 714 y Fh(C)135 834 y Fs(6.)24 b Fm(\010)11 b(\001)g(C)17 b(\022)f(\010\001)p Fs(P)456 816 y Fh(C)135 936 y Fs(7.)24 b(NP)17 b Fm(\022)f Fj(B)s(P)i Fm(\001)12 b(\010\001)p Fs(P)l(.)k(\(This)i(follo)o(ws)g(from)f(the)g(pro)q(of)h(of)f([VV-86],) f(sho)o(wing)i(that)g(SA)l(T)e(is)197 996 y(reducible)h(via)g (probabilistic)i(reductions)e(to)g(the)f(\\unique)g(satis\014abili)q(t) o(y)j(problem".\))135 1097 y(8.)24 b Fm(\010)11 b(\001)g(\010\001)k(C) 20 b Fs(=)c Fm(\010\001)g(C)s Fs(.)135 1199 y(9.)24 b Fm(\010\001)p Fs(P)283 1181 y Fh(\010\001)p Fu(P)362 1199 y Fs(=)16 b Fm(\010\001)p Fs(P)l(.)g([PZ-83])g(\(Th)o(us)h Fm(\010\001)p Fs(P)f(is)h(closed)g(under)f Fm(\024)1314 1175 y Fl(p)1314 1211 y(T)1341 1199 y Fs(.\))110 1301 y(10.)25 b(PP)263 1283 y Fu(BPP)355 1301 y Fs(=)16 b(PP)l(.)g ([KSTT-89])148 1452 y(If)g(the)h(underlying)h(class)g Fm(C)h Fs(is)f(closed)f(under)g(\\p)q(ositiv)o(e)h(reducibilit)o(y")g (\(see)f([Sc-87]\))f(then)75 1513 y(the)f(usual)h(tec)o(hniques)e(of)h (\\ampli\014cation")k(can)c(b)q(e)g(used)g(to)g(exp)q(onen)o(tially)h (reduce)e(the)h(error)75 1573 y(probabilit)o(y)f(for)f(sets)f(in)h(the) e(class)j Fj(B)s(P)9 b Fm(\001)s(C)s Fs(.)19 b(Th)o(us)13 b(for)f(suc)o(h)g(classes)h Fm(C)s Fs(,)g(the)f(follo)o(wing)j (inclusions)75 1633 y(and)21 b(equalities)g(hold.)34 b(\(It)19 b(should)j(b)q(e)e(noted)g(that)g(classes)h(de\014ned)f (using)i(the)d Fv(C)i Fs(op)q(erator)75 1693 y(are)f(not)h(kno)o(wn)f (to)g(b)q(e)h(closed)f(under)h(this)f(sort)h(of)g(\\p)q(ositiv)o(e)g (reducibilit)o(y)l(,")h(and)f(th)o(us)f(the)75 1753 y(follo)o(wing)f (inclusions)g(ma)o(y)c(not)i(hold)g(for)g(suc)o(h)f(classes.\))148 1863 y Fv(Theorem:)k Fs(F)l(or)d(classes)g Fm(C)i Fs(closed)e(under)f (p)q(ositiv)o(e)i(reducibilit)o(y)l(,)135 2015 y(1.)24 b(P)230 1997 y Fl(B)r(P)5 b Fh(\001C)332 2015 y Fm(\022)13 b Fj(B)s(P)7 b Fm(\001)p Fs(P)509 1997 y Fh(C)532 2015 y Fs(.)135 2117 y(2.)24 b Fj(B)s(P)18 b Fm(\001)11 b Fj(B)s(P)18 b Fm(\001)10 b(C)20 b Fs(=)c Fj(B)s(P)i Fm(\001)11 b(C)s Fs(.)p 75 2151 720 2 v 75 2196 a Fn(closure)k(prop)q(erties)g(of) e(classes)i(in)f(the)g(Coun)o(ting)f(Hierarc)o(h)o(y)i(ma)o(y)d(b)q(e)i (found)g(in)f([T)m(or-88].)117 2231 y Ff(\003)136 2246 y Fn(In)h(the)h(brief)f(p)q(erio)q(d)h(that)f(has)g(elapsed)h(b)q(et)o (w)o(een)h(the)f(time)e(when)i(this)f(article)g(w)o(as)h(\014rst)g (written)f(for)g(the)75 2296 y(EA)m(TCS)e(Bulletin)g(\(Jan)o(uary)m(,)f (1990\))g(and)h(the)h(time)e(of)g(the)i(compilation)c(of)i(the)i (presen)o(t)h(v)o(olume)c(\(Septem)o(b)q(er,)75 2346 y(1992\),)15 b(m)o(uc)o(h)f(has)h(b)q(een)i(learned)f(ab)q(out)f(the)i (coun)o(ting)e(hierarc)o(h)o(y)m(.)22 b(It)16 b(w)o(as)f(sho)o(wn)h(in) f([BRS-91])f(that)h(PP)h Fe(is)75 2395 y Fn(closed)h(under)h(union)e (and)h(in)o(tersection.)27 b(This)17 b(b)q(eautiful)f(and)g(surprising) h(result)h(has)f(b)q(een)h(generalized)f(to)75 2445 y(the)d(en)o(tire)h (coun)o(ting)f(hierarc)o(h)o(y)g([Gu-90].)p eop %%Page: 5 5 5 4 bop 135 53 a Fs(3.)24 b Fj(B)s(P)19 b Fm(\001)13 b(C)21 b(\022)d(9)12 b(\001)h(8)e(\001)h(C)22 b(\\)d(8)11 b(\001)h(9)g(\001)h(C)s Fs(.)27 b([Sc-87])19 b(\(This)g(is)g(a)g (generalization)i(of)e(the)f(result)h(of)197 114 y([Si-83a,)e(La-83],)h (sho)o(wing)f(that)g(BPP)f(is)h(in)g(the)f(p)q(olynomial)j(hierarc)o(h) o(y)l(.\))135 208 y(4.)24 b Fm(\010)11 b(\001)g Fj(B)s(P)18 b Fm(\001)10 b(C)20 b(\022)13 b Fj(B)s(P)18 b Fm(\001)11 b(\010)g(\001)g(C)s Fs(.)21 b(\(This)d(is)f(the)f(\\op)q(erator)h(sw)o (apping")i(lemma)d(of)h([T)l(o-89].\))148 338 y(Some)k(of)g(the)f (inclusions)k(and)d(equalities)h(listed)g(ab)q(o)o(v)o(e)f(are)g(quite) g(easy)g(to)g(pro)o(v)o(e,)f(and)75 399 y(others)15 b(are)h(not)f(at)h (all)g(ob)o(vious.)22 b(It)15 b(is)h(imp)q(ortan)o(t)g(to)g(note)f (that)h(all)g(of)g(the)f(facts)g(listed)h(ab)q(o)o(v)o(e)75 459 y Ft(r)n(elativize)p Fs(,)g(so)h(that)g(the)f(same)g(relationships) j(hold)f(relativ)o(e)e(to)h(an)o(y)f(oracle.)148 569 y(Armed)i(with)j(this)f(list)g(of)g(facts,)g(w)o(e)e(can)i(no)o(w)g (giv)o(e)f(a)h(short)f(pro)q(of)i(of)e(the)g(\014rst)h(part)g(of)75 629 y(T)l(o)q(da's)d(pro)q(of.)148 739 y Fv(Theorem:)j Fs([T)l(o-89])d(The)f(p)q(olynomial)j(hierarc)o(h)o(y)d(is)h(con)o (tained)g(in)g Fj(B)s(P)h Fm(\001)11 b(\010\001)p Fs(P)l(.)148 849 y Fv(Pro)r(of:)22 b Fs(W)l(e)16 b(ha)o(v)o(e)g(already)i(observ)o (ed)e(that)h(\006)1034 825 y Fl(p)1034 860 y Fu(1)1068 849 y Fm(\022)e Fj(B)s(P)j Fm(\001)11 b(\010\001)p Fs(P)l(.)16 b(Th)o(us)h(assume)g(inductiv)o(ely)75 909 y(that)g(\006)216 886 y Fl(p)216 922 y(k)251 909 y Fm(\022)d Fj(B)s(P)k Fm(\001)10 b(\010\001)p Fs(P)l(,)16 b(and)h(note)f(that)658 999 y(\006)693 975 y Fl(p)693 1011 y(k)q Fu(+1)802 999 y Fs(=)42 b(NP)951 978 y Fu(\006)976 962 y Fk(p)976 990 y(k)801 1071 y Fm(\022)g Fj(B)s(P)17 b Fm(\001)11 b(\010)g(\001)g Fs(P)1103 1051 y Fl(B)r(P)5 b Fh(\001\010\001)p Fu(P)801 1144 y Fm(\022)42 b Fj(B)s(P)17 b Fm(\001)11 b(\010)g(\001)g Fj(B)s(P)18 b Fm(\001)11 b Fs(P)1217 1124 y Fh(\010\001)p Fu(P)802 1217 y Fs(=)42 b Fj(B)s(P)17 b Fm(\001)11 b(\010)g(\001)g Fj(B)s(P)18 b Fm(\001)11 b(\010)g(\001)g Fs(P)801 1289 y Fm(\022)42 b Fj(B)s(P)17 b Fm(\001)11 b Fj(B)s(P)18 b Fm(\001)11 b(\010)g(\001)g(\010)g(\001)g Fs(P)802 1362 y(=)42 b Fj(B)s(P)17 b Fm(\001)11 b(\010)g(\001)g Fs(P)148 1497 y(Ha)o(ving)23 b(no)o(w)g(sho)o(wn)g(that)f(the)g(p)q(olynomial)j (hierarc)o(h)o(y)d(is)h(con)o(tained)g(in)g Fj(B)s(P)f Fm(\001)15 b(\010\001)p Fs(P)22 b Fm(\022)75 1557 y Fv(C)p Fm(\001)16 b(\010)g(\001)p Fs(P)l(,)23 b(T)l(o)q(da's)h(theorem)f (follo)o(ws)i(from)e(the)g(follo)o(wing)j(inclusion)g(\(the)d(pro)q(of) h(of)g(whic)o(h)75 1617 y(in)o(v)o(olv)o(es)17 b(a)g(detailed)h (manipulation)i(of)d(the)g(computation)h(tree)e(of)h(a)g(mac)o(hine,)g (whic)o(h)g(w)o(e)g(do)75 1678 y(not)g(ha)o(v)o(e)e(su\016cien)o(t)h (space)g(to)h(presen)o(t)f(here\).)148 1788 y Fv(Theorem:)k Fs([T)l(o-89])d Fv(C)p Fm(\001)12 b(\010)e(\001)p Fs(P)17 b Fm(\022)f Fs(P)835 1770 y Fu(PP)885 1788 y Fs(.)148 1898 y(T)l(o)q(da)g(in)f(fact)g(sho)o(ws)g(that)h(P)697 1880 y Fu(PP)761 1898 y Fs(con)o(tains)g(a)f(seemingly)g(larger)h (class.)22 b(Let)14 b(PH)h(denote)f(the)75 1958 y(p)q(olynomial)19 b(hierarc)o(h)o(y)l(.)148 2068 y Fv(Theorem:)h Fs([T)l(o-89])d(PP)634 2050 y Fu(PH)703 2068 y Fm(\022)f Fs(P)791 2050 y Fu(PP)842 2068 y Fs(.)148 2178 y Fv(Pro)r(of:)756 2263 y Fs(PP)822 2242 y Fu(PH)916 2263 y Fm(\022)42 b Fs(PP)1063 2242 y Fl(B)r(P)5 b Fh(\001\010\001)p Fu(P)916 2336 y Fm(\022)42 b Fs(PP)1063 2315 y Fu(BPP)1136 2303 y Fd(\010\001)p Fc(P)917 2408 y Fs(=)g(PP)1063 2388 y Fh(\010\001)p Fu(P)917 2481 y Fs(=)g Fv(C)11 b Fm(\001)g(\010)g(\001)g Fs(P)916 2554 y Fm(\022)42 b Fs(P)1030 2533 y Fu(PP)p eop %%Page: 6 6 6 5 bop 148 53 a Fs(An)20 b(ob)o(vious)g(op)q(en)h(question)f(is)h (whether)e(or)h(not)g(PH)f(is)i(con)o(tained)f(in)h(PP)f(itself.)32 b(It)19 b(is)75 114 y(not)g(ev)o(en)e(kno)o(wn)h(if)g(P)512 96 y Fu(NP)583 114 y Fs(is)h(con)o(tained)g(in)g(PP)l(.)e(The)i (largest)g(sub)q(class)h(of)e(PH)g(kno)o(wn)g(to)h(b)q(e)75 174 y(con)o(tained)h(in)g(PP)g(is)h(the)e(class)i(P)736 156 y Fu(NP[log])873 174 y Fs(\(the)e(class)i(of)f(languages)h(that)f (can)g(b)q(e)g(recognized)75 234 y(with)d Fj(O)q Fs(\(log)11 b Fj(n)p Fs(\))16 b(queries)h(to)f(SA)l(T\))g([BHW-91].)961 216 y Fu(3)75 344 y Fv(2.)24 b(Circuits)d(\(and)e(Neural)f(Nets\))148 454 y Fs(T)l(o)q(da's)24 b(theorem)f(has)h(some)f(v)o(ery)f(in)o (teresting)i(consequences)e(for)h(circuit)h(complexit)o(y)l(.)75 514 y(Before)15 b(w)o(e)g(can)h(presen)o(t)f(these)h(consequences,)f (it)h(will)i(b)q(e)e(instructiv)o(e)g(to)g(review)f(some)h(basic)75 574 y(notions)i(from)e(circuit)h(complexit)o(y)l(.)148 684 y(A)j Ft(cir)n(cuit)i(family)e Fs(is)h(a)g(set)f Fm(f)p Fj(C)751 691 y Fl(n)796 684 y Fs(:)g Fj(n)h Fm(2)g Fv(N)p Fm(g)f Fs(of)h(circuits,)h(where)e(eac)o(h)g(circuit)h Fj(C)1723 691 y Fl(n)1766 684 y Fs(tak)o(es)75 745 y(\(binary\))e (inputs)g(of)f(length)h Fj(n)p Fs(,)g(and)f(pro)q(duces)h(a)f(single)i (output.)27 b(Eac)o(h)18 b(circuit)h(family)g(th)o(us)75 805 y(de\014nes)k(a)g(language.)43 b(A)22 b(circuit)i(family)f(is)h Ft(uniform)e Fs(if)i(the)e(function)i Fj(n)h Fm(7!)g Fj(C)1655 812 y Fl(n)1701 805 y Fs(is)f(easily)75 865 y(computable)19 b(in)h(some)e(sense.)29 b(F)l(or)18 b(the)h(v)o(ery)e (small)j(circuit)g(complexit)o(y)e(classes)i(w)o(e)e(discuss)75 925 y(here,)d(a)i(v)o(ery)e(strong)i(notion)h(of)f(uniformit)o(y)f(is)h (appropriate.)23 b(This)18 b(is)f(discussed)g(in)g(detail)g(in)75 985 y([BIS-90];)e(w)o(e)h(will)i(not)f(giv)o(e)f(detailed)h (de\014nitions)h(concerning)f(uniformit)o(y)g(here.)148 1095 y(Tw)o(o)24 b(imp)q(ortan)o(t)g(circuit)g(complexit)o(y)f(classes) i(are)e(NC)1239 1077 y Fu(1)1282 1095 y Fs(and)h(A)o(C)1455 1077 y Fu(0)1474 1095 y Fs(;)j(NC)1587 1077 y Fu(1)1630 1095 y Fs(is)d(the)f(class)75 1156 y(of)f(languages)i(accepted)e(b)o(y) f(\(uniform\))i(circuits)f(of)h(AND)e(and)h(OR)g(gates)h(of)f(fan-in)h (2,)h(of)75 1216 y(p)q(olynomial)f(size)e(and)h(logarithmic)g(depth.)35 b(A)o(C)1031 1198 y Fu(0)1071 1216 y Fs(is)21 b(the)g(class)h(of)f (languages)i(accepted)d(b)o(y)75 1276 y(\(uniform\))15 b(circuits)g(of)g(AND)f(and)h(OR)f(gates)h(of)g(un)o(b)q(ounded)g (fan-in,)h(of)f(p)q(olynomial)i(size)d(and)75 1336 y Fj(O)q Fs(\(1\))21 b(depth.)33 b(\(A)o(C)455 1318 y Fu(0)455 1348 y Fl(k)496 1336 y Fs(denotes)21 b(the)f(languages)i(in)f(A)o(C) 1123 1318 y Fu(0)1162 1336 y Fs(accepted)f(b)o(y)g(circuits)h(of)f (depth)g Fj(k)r Fs(.\))75 1396 y(Clearly)l(,)d(A)o(C)325 1378 y Fu(0)358 1396 y Fm(\022)f Fs(NC)485 1378 y Fu(1)504 1396 y Fs(,)g(and)h(b)q(oth)g(classes)g(are)g(con)o(tained)g(in)f(P)l (.)148 1506 y(In)e(some)h(sense,)f(A)o(C)536 1488 y Fu(0)569 1506 y Fs(and)h(NC)734 1488 y Fu(1)768 1506 y Fs(represen)o(t)f(the)g (extremes)f(of)i(our)f(kno)o(wledge)h(ab)q(out)h(com-)75 1566 y(plexit)o(y)g(classes.)22 b(On)17 b(the)f(one)g(hand,)g(man)o(y)g (com)o(binatorial)j(metho)q(ds)d(ha)o(v)o(e)g(b)q(een)g(dev)o(elop)q (ed)75 1627 y(that)j(enable)g(us)f(to)h(sho)o(w)g(that)g(man)o(y)e (problems)i(in)g(NC)1170 1609 y Fu(1)1208 1627 y Fs(are)g(not)f(in)h(A) o(C)1510 1609 y Fu(0)1548 1627 y Fs([FSS-84,)g(Aj-83,)75 1687 y(Y)l(a-85,)f(H)-6 b(\027)-30 b(a-86].)24 b(On)17 b(the)h(other)f(hand,)h(it)g(is)g(still)h(an)f(op)q(en)g(problem)f (whether)h(or)f(not)h(NP)f(=)75 1747 y(NC)147 1729 y Fu(1)167 1747 y Fs(.)k(Th)o(us)16 b(w)o(e)g(kno)o(w)g(a)h(great)g(deal) g(ab)q(out)g(A)o(C)1003 1729 y Fu(0)1022 1747 y Fs(,)f(but)h(really)g (quite)f(little)i(ab)q(out)f(NC)1727 1729 y Fu(1)1747 1747 y Fs(.)148 1857 y(Th)o(us)f(a)f(go)q(o)q(d)j(place)d(to)h(try)f (to)h(mak)o(e)e(progress)i(is)g(in)g(the)f(range)h(b)q(et)o(w)o(een)f (A)o(C)1642 1839 y Fu(0)1676 1857 y Fs(and)h(NC)1842 1839 y Fu(1)1861 1857 y Fs(.)75 1917 y(Among)g(the)g(v)m(arious)i (complexit)o(y)d(classes)i(that)g(ha)o(v)o(e)e(b)q(een)h(studied)g(in)h (this)g(range,)f(TC)1768 1899 y Fu(0)1804 1917 y Fs(has)75 1977 y(attracted)g(a)h(great)g(deal)g(of)f(atten)o(tion.)148 2087 y Fv(De\014nition:)25 b Fs(A)18 b Ft(thr)n(eshold)g(cir)n(cuit)g Fs(is)h(a)f(circuit)g(comp)q(osed)g(en)o(tirely)g(of)g(ma)s(jorit)o(y)g (gates.)75 2148 y(\(A)h(ma)s(jorit)o(y)f(gate)i(outputs)g(1)f(i\013)h (the)f(ma)s(jorit)o(y)g(of)g(its)h(inputs)g(ha)o(v)o(e)e(v)m(alue)i (1.\))29 b(TC)1716 2130 y Fu(0)1755 2148 y Fs(is)20 b(the)75 2208 y(class)e(of)f(languages)i(accepted)d(b)o(y)g(threshold)i (circuits)g(of)f(p)q(olynomial)i(size)e(and)h(depth)e Fj(O)q Fs(\(1\).)75 2268 y(TC)145 2250 y Fu(0)145 2280 y Fl(k)183 2268 y Fs(denotes)g(the)g(class)i(of)e(languages)j(accepted) c(b)o(y)h(threshold)h(circuits)g(of)g(depth)f Fj(k)r Fs(.)p 75 2314 720 2 v 131 2345 a Fo(3)150 2360 y Fn(In)11 b(the)g(mean)o(time,)e(this)i(question)g(has)h(b)q(een)g(addressed)h(b) o(y)e(Ric)o(hard)f(Beigel.)17 b(In)11 b([Be-92],)g(Beigel)g(presen)o (ts)75 2410 y(an)16 b(oracle)g(relativ)o(e)g(to)g(whic)o(h)g(P)609 2395 y Fo(NP)674 2410 y Fn(is)f(not)h(con)o(tained)g(in)g(PP)m(.)g(In)g (fact,)g(he)g(sho)o(ws)g(the)h(stronger)g(result)g(that)75 2460 y(the)d(inclusion)g(presen)o(ted)i(in)d([BHW-91])g(can)h(not)f(b)q (e)i(impro)o(v)o(ed)d(using)i(relativizable)f(pro)q(of)g(tec)o (hniques.)p eop %%Page: 7 7 7 6 bop 148 53 a Fs(The)16 b(follo)o(wing)j(p)q(oin)o(ts)f(explain)f (in)g(part)g(wh)o(y)f(TC)1106 35 y Fu(0)1142 53 y Fs(has)h(b)q(een)f (the)g(fo)q(cus)h(of)g(atten)o(tion.)148 205 y Fm(\017)24 b Fs(The)c(ma)s(jorit)o(y)f(gate)h(is)h(of)f(essen)o(tially)h(the)e (same)h(p)q(o)o(w)o(er)g(as)g(a)g(gate)g(for)g(in)o(teger)g(m)o(ul-)197 265 y(tiplication)i([CSV-84].)31 b(Th)o(us)20 b(TC)866 247 y Fu(0)906 265 y Fs(c)o(haracterizes)f(the)g(p)q(o)o(w)o(er)h(of)g (certain)g(arithmetic)197 325 y(circuits.)148 427 y Fm(\017)k Fs(TC)267 409 y Fu(0)303 427 y Fs(exactly)16 b(c)o(haracterizes)g(the)g (complexit)o(y)g(of)h(symmetric)e(functions)i([FKPS-85].)148 529 y Fm(\017)24 b Fs(Division)f(is)f(in)g(P-uniform)g(TC)815 511 y Fu(0)856 529 y Fs([Re-87,R)l(T-90].)36 b(This)22 b(is)g(one)f(of)g(the)g(few)g(cases)g(in)197 589 y(whic)o(h)14 b(uniformit)o(y)g(considerations)i(come)d(in)o(to)h(pla)o(y)g(when)f (classifying)j(the)d(complexit)o(y)197 649 y(of)j(natural)i(problems.) 148 751 y Fm(\017)24 b Fs(Man)o(y)e(computer)g(scien)o(tists)i(ha)o(v)o (e)e(b)q(een)g(studying)i(\\connectionist")h(mo)q(dels)e(of)g(the)197 811 y(brain,)18 b(also)h(kno)o(wn)f(as)g(\\neural)h(nets".)25 b(It)17 b(turns)h(out)g(that)g(one)f(of)h(the)f(most)h(p)q(opular)197 871 y(mo)q(dels)c(studied)h(b)o(y)e(connectionists)i(is)g (computationally)h(equiv)m(alen)o(t)e(to)g(the)f(threshold)197 931 y(circuit)j(mo)q(del)h([PS-88,)f(PS-89].)22 b(Ian)16 b(P)o(arb)q(erry)g(has)g(written)h(quite)f(elo)q(quen)o(tly)g(on)g(the) 197 992 y(relationship)j(b)q(et)o(w)o(een)c(computational)j(complexit)o (y)e(theory)g(and)h(the)f(study)g(of)g(neural)197 1052 y(net)o(w)o(orks)k([P)o(a-90,PS-89].)36 b(An)o(y)19 b(complexit)o (y-theoretic)i(w)o(ork)f(on)i(threshold)f(circuits)197 1112 y(th)o(us)15 b(is)h(of)f(some)g(in)o(terest)f(to)i(the)e(neural)i (net)o(w)o(ork)e(comm)o(unit)o(y)l(,)g(and)h(con)o(v)o(ersely)l(,)f (some)197 1172 y(theoretical)g(w)o(ork)f(of)h(in)o(terest)f(to)g (complexit)o(y)g(theoreticians)i(w)o(as)f(motiv)m(ated)g(primarily)197 1232 y(b)o(y)i(the)g(study)g(of)h(neural)g(net)o(w)o(orks)f([Go-89,)h (Bru-90,)f(BS-92].)148 1334 y Fm(\017)24 b Fs(A)19 b(large)i(b)q(o)q (dy)g(of)f(w)o(ork)f(on)i(threshold)f(logic)i(and)e(threshold)h (circuits)f(already)h(exists)197 1394 y(\(e.g.,)16 b([Mu-71]\).)25 b(Muc)o(h)17 b(of)h(this)g(w)o(ork)g(w)o(as)g(motiv)m(ated)g(b)o(y)f (in)o(terest)g(in)h(building)i(com-)197 1454 y(puters)c(with)h (threshold)h(logic)f(comp)q(onen)o(ts.)148 1556 y Fm(\017)24 b Fs(As)16 b(w)o(e)g(shall)i(see,)d(TC)617 1538 y Fu(0)654 1556 y Fs(is)i(in)o(timately)g(connected)e(with)j(the)e(coun)o(ting)h (hierarc)o(h)o(y)l(.)148 1708 y(No)o(w)i(that)h(w)o(e)f(ha)o(v)o(e)g (established)i(that)f(there)f(is)h(su\016cien)o(t)g(in)o(terest)f(for)h (studying)g(TC)1841 1690 y Fu(0)1861 1708 y Fs(,)75 1768 y(it)d(is)g(unfortunate)g(that)g(w)o(e)f(m)o(ust)g(rep)q(ort)g(that)h (w)o(e)f(kno)o(w)g(ab)o(ysmally)i(little)f(ab)q(out)h(threshold)75 1828 y(circuits.)k(With)17 b(some)f(e\013ort,)g(Ha)s(jnal)h(et.)k(al.)h (ha)o(v)o(e)16 b(sho)o(wn)h(the)f(follo)o(wing)j(result:)148 1938 y Fv(Theorem:)h Fs([HM-87])c(TC)664 1920 y Fu(0)664 1950 y(1)698 1938 y Fm(\032)g Fs(TC)823 1920 y Fu(0)823 1950 y(2)857 1938 y Fm(\032)g Fs(TC)982 1920 y Fu(0)982 1950 y(3)1002 1938 y Fs(.)148 2048 y(Ho)o(w)o(ev)o(er)f(it)h(is)h (still)i(an)d(op)q(en)h(question)g(if)g(TC)1032 2030 y Fu(0)1032 2060 y(3)1068 2048 y Fs(=)g(NP)l(.)e(\(Ev)o(en)h(w)o(orse,) g(it)g(is)h(not)g(kno)o(wn)g(if)75 2108 y(NP)f(is)g(equal)h(to)f(the)f (class)i(of)f(languages)j(accepted)c(b)o(y)g(uniform)i(circuits)f(of)g (p)q(olynomial)j(size)75 2168 y(and)e(depth)f(three,)f(comp)q(osed)i (of)g(AND,)e(OR)h(and)h(MOD)f(6)h(gates.\))148 2278 y(It)12 b(is)i(fairly)g(natural)g(to)f(conjecture)f(that)h(the)f(TC)1073 2260 y Fu(0)1106 2278 y Fs(hierarc)o(h)o(y)g(is)i(in\014nite)g(\(i.e.,) e(that)h(TC)1803 2260 y Fu(0)1837 2278 y Fm(6)p Fs(=)75 2339 y(TC)145 2321 y Fu(0)145 2351 y Fl(k)182 2339 y Fs(for)j(an)o(y)f Fj(k)r Fs(\),)h(and)g(indeed)g(this)g(conjecture)f (is)h(men)o(tioned)f(in)h([BIS-90,Y)l(a-89].)21 b(Ho)o(w)o(ev)o(er,)75 2399 y(it)g(has)f(also)i(b)q(een)e(conjectured)f(that)h(TC)883 2381 y Fu(0)924 2399 y Fs(=)g(NC)1054 2381 y Fu(1)1093 2399 y Fs([IL-89],)h(whic)o(h)f(w)o(ould)h(imply)g(that)f(the)75 2459 y(TC)145 2441 y Fu(0)181 2459 y Fs(hierarc)o(h)o(y)c(collapses.)p eop %%Page: 8 8 8 7 bop 148 53 a Fs(Y)l(ao)14 b(has)f(sho)o(wn)h(that)g(when)f(one)g (considers)i Ft(monotone)f Fs(circuits,)g(the)f(corresp)q(onding)i(TC) 1855 35 y Fu(0)75 114 y Fs(hierarc)o(h)o(y)j Ft(is)h Fs(in\014nite.)29 b(In)19 b(fact,)g(he)f(sho)o(ws)i(the)e(stronger)i (result)f(that)g(for)g(ev)o(ery)e Fj(k)r Fs(,)i(there)f(is)75 174 y(a)h(set)f(in)h Fj(AC)331 156 y Fu(0)327 186 y Fl(k)q Fu(+1)411 174 y Fs(that)g(requires)g Ft(exp)n(onential)h Fs(size)e(on)h(threshold)h(circuits)f(of)f(size)h Fj(k)h Fs([Y)l(a-89].)75 234 y(As)h(w)o(e)g(shall)j(see,)e(one)g(of)f(the)h (surprising)i(consequences)c(of)i(T)l(o)q(da's)h(theorem)e(is)h(that)g (the)75 294 y(corresp)q(onding)c(result)f(is)g Ft(not)g Fs(true)f(when)g(one)h(considers)g(non-monotone)g(circuits.)75 404 y Ft(2.1.)22 b(R)n(elating)c(Cir)n(cuits)f(to)h(the)g(Counting)g (Hier)n(ar)n(chy)148 514 y Fs(When)d(the)h(alternating)h(T)l(uring)f (mac)o(hine)f(\(A)l(TM\))g(w)o(as)h(in)o(tro)q(duced)g(in)g([CKS-81],)f (one)h(of)75 574 y(the)c(motiv)m(ations)i(w)o(as)f(to)f(ha)o(v)o(e)g(a) g(T)l(uring)i(mac)o(hine)e(mo)q(del)g(suitable)i(for)f(studying)g (parallelism.)75 635 y(Results)i(relating)h(circuit)g(size)e(and)h (depth)g(to)g(alternating)i(T)l(uring)e(mac)o(hine)g(space)f(and)i (time,)75 695 y(resp)q(ectiv)o(ely)l(,)e(can)g(b)q(e)g(found)h(in)g ([Ru-81].)20 b(In)14 b(order)g(to)h(mo)q(del)f(circuits)h(of)g (sublinear)g(depth,)f(it)75 755 y(is)g(necessary)f(to)h(ha)o(v)o(e)e(T) l(uring)j(mac)o(hines)e(with)i(sublinear)g(running)f(times;)g(th)o(us)g (a)f(mec)o(hanism)75 815 y(is)20 b(pro)o(vided)g(for)g(\\random)g (access")g(to)g(an)o(y)f(bit)h(of)g(the)f(input.)32 b(\(Details)21 b(ma)o(y)e(b)q(e)g(found)h(in)75 875 y([Ru-81].\))h(NC)356 857 y Fu(1)392 875 y Fs(is)c(alternating)h(log)g(time,)e(in)h(this)g (mo)q(del)g(of)f(computation.)148 985 y(Sipser)24 b(studied)f(the)g (sub)q(class)h(of)f(NC)896 967 y Fu(1)939 985 y Fs(de\014ned)f(b)o(y)g (log-time)j(A)l(TMs)d(that)h(mak)o(e)f(only)75 1046 y Fj(O)q Fs(\(1\))i(alternations;)k(this)c(is)g(called)g(the)f(log-time)i (hierarc)o(h)o(y)d([Si-83].)43 b(The)23 b(lev)o(els)g(of)g(this)75 1106 y(hierarc)o(h)o(y)c(are)i(denoted)f(\006)600 1113 y Fl(k)621 1106 y Fs(-logtime.)34 b(An)20 b(analogous)j(extension,)e (called)g(the)f(logarithmic-)75 1166 y(time)h(coun)o(ting)h(hierarc)o (h)o(y)f(\(LCH\))h(w)o(as)f(de\014ned)g(in)h([T)l(or-88];)i(the)d(lev)o (els)h(of)f(the)g(LCH)h(are)75 1226 y(de\014ned)d(using)h(logarithmic)h (v)o(ersions)f(of)f(the)g Fm(9)p Fj(;)8 b Fm(8)17 b Fs(and)j Fv(C)g Fs(op)q(erators.)31 b(W)l(e)18 b(will)j(denote)e(the)75 1286 y Fj(k)r Fs(-th)e(lev)o(el)f(of)g(the)g(LCH)h(b)o(y)f Fv(C)658 1293 y Fl(k)679 1286 y Fs(-logtime.)148 1396 y(Lev)o(els)h(of)g(the)f(LCH)h(corresp)q(ond)g(roughly)h(to)f(circuit)g (depth.)22 b(It)16 b(w)o(as)h(sho)o(wn)g(in)h([BIS-90])75 1456 y(that)182 1423 y Fb(S)217 1467 y Fl(k)246 1456 y Fs(\006)281 1463 y Fl(k)303 1456 y Fs(-logtime)h(=)e(\(uniform\))i(A) o(C)843 1438 y Fu(0)862 1456 y Fs(,)e(and)h(the)g(same)f(tec)o(hniques) g(can)h(b)q(e)g(used)f(to)h(sho)o(w)75 1517 y(that)h(LCH)f(=)g (\(uniform\))h(TC)652 1499 y Fu(0)672 1517 y Fs(.)27 b(Ho)o(w)o(ev)o(er,)16 b(the)i(corresp)q(ondence)h(is)g(not)f(exact.)27 b(Dep)q(ending)75 1577 y(somewhat)17 b(on)g(the)f(precise)h(w)o(a)o(y)f (that)h(the)f(uniformit)o(y)h(condition)i(is)e(de\014ned,)f(one)h(can)f (sho)o(w)75 1637 y(that)i Fv(C)222 1644 y Fl(k)244 1637 y Fs(-logtime)g Fm(\022)g Fs(TC)561 1619 y Fu(0)561 1649 y Fl(k)q Fu(+1)628 1637 y Fs(,)f(and)h(TC)825 1619 y Fu(0)825 1649 y Fl(k)864 1637 y Fm(\022)f Fv(C)960 1644 y Fl(k)q Fu(+1)1027 1637 y Fs(-logtime,)i(but)e(no)h(tigh)o(ter)g (corresp)q(ondence)75 1697 y(is)f(kno)o(wn.)148 1807 y(On)e(the)g(other)g(hand,)g(lev)o(els)g(of)g(the)g(LCH)g(corresp)q (ond)h(exactly)f(to)g(lev)o(els)g(of)g(the)g(coun)o(ting)75 1867 y(hierarc)o(h)o(y)l(.)28 b(Generalizing)21 b(a)e(result)g(of)g ([Si-83],)h(T)l(or\023)-24 b(an)19 b(sho)o(w)o(ed)g(in)g([T)l(or-88])h (that)f(if)g(there)f(is)75 1928 y(an)e(oracle)g(separating)h(t)o(w)o(o) e(lev)o(els)g(of)g(the)g(coun)o(ting)i(hierarc)o(h)o(y)l(,)d(then)h (the)g(corresp)q(onding)i(t)o(w)o(o)75 1988 y(lev)o(els)d(of)f(LCH)h (are)g(distinct.)21 b(\(The)14 b(in)o(tuition)h(here)e(is)h(that)g (there)f(is)h(essen)o(tially)h(no)f(di\013erence)75 2048 y(b)q(et)o(w)o(een)h(an)i(oracle)g(T)l(uring)h(mac)o(hine)e(writing)i (an)f(oracle)f(query)g(on)h(its)g(query)e(tap)q(e,)i(and)g(an)75 2108 y(A)l(TM)f(writing)i(an)g(address)f(on)g(its)h(address)f(tap)q(e)g (giving)h(it)g(\\random)f(access")g(to)g(the)g(input.)75 2168 y(That)d(is,)h(the)e(c)o(haracteristic)h(sequence)f(of)h(an)g (oracle)g(to)g(a)g(p)q(olynomial-time)i(T)l(uring)f(mac)o(hine)75 2229 y(can)g(b)q(e)f(view)o(ed)g(as)h Ft(input)g Fs(to)g(a)g(log-time)h (A)l(TM.\))d(Th)o(us)i(an)g(oracle)g(result)g(ab)q(out)h(the)e(coun)o (ting)75 2289 y(hierarc)o(h)o(y)i(implies)h(a)g(real)g(separation)h(in) f(LCH.)148 2399 y(There)k(is)h(a)f(partial)i(con)o(v)o(erse,)e(as)h(w)o (ell.)36 b(It)21 b(w)o(as)h(p)q(oin)o(ted)g(out)f([FSS-84,)i(Si-83])f (that)g(if)75 2465 y(there)c(is)h(a)f(language)j(in)e(\006)595 2472 y Fl(k)616 2465 y Fs(-logtime)h(that)f(requires)f(more)g(than)h (size)f(2)1459 2447 y Fu(log)1505 2434 y Fk(O)q Fc(\(1\))1576 2447 y Fl(n)1618 2465 y Fs(to)h(recognize)75 2525 y(on)14 b(depth)f Fj(k)6 b Fm(\000)f Fs(1)14 b(circuits)g(of)f(AND)g(and)h(OR)f (gates,)h(then)f(there)f(is)i(an)g(oracle)g(relativ)o(e)f(to)h(whic)o (h)p eop %%Page: 9 9 9 8 bop 75 53 a Fs(\006)110 30 y Fl(p)110 66 y(k)q Fh(\000)p Fu(1)190 53 y Fm(6)p Fs(=)14 b(\006)277 30 y Fl(p)277 66 y(k)299 53 y Fs(.)21 b(Circuit)c(lo)o(w)o(er)f(b)q(ounds)i(of)e (this)h(sort)g(w)o(ere)e(ac)o(hiev)o(ed)g(\014rst)i(b)o(y)e(Y)l(ao)i ([Y)l(a-85],)e(and)75 114 y(further)i(dev)o(elopmen)o(ts)f(ma)o(y)h(b)q (e)g(found)h(in)g([H)-6 b(\027)-30 b(a-86)16 b(,)h(Ko-89].)25 b(Along)18 b(the)f(same)g(lines,)h(if)g(one)75 180 y(can)g(sho)o(w)h (that)f(for)h(ev)o(ery)d Fj(k)k Fs(there)e(is)g(a)h(set)f(in)h Fv(C)1045 187 y Fl(k)1084 180 y Fs(that)g(requires)f(more)g(than)g (size)g(2)1734 162 y Fu(log)1780 149 y Fk(O)q Fc(\(1\))1852 162 y Fl(n)75 240 y Fs(to)d(recognize)g(on)g(depth)g Fj(k)10 b Fm(\000)e Fs(1)15 b(threshold)h(circuits,)g(then)e(the)h (coun)o(ting)h(hierarc)o(h)o(y)e(is)h(in\014nite.)148 350 y(Circuit)23 b(lo)o(w)o(er)f(b)q(ounds)h(\(or)f(equiv)m(alen)o(tly) l(,)h(oracles)g(separating)h(lev)o(els)e(of)g(the)f(coun)o(ting)75 410 y(hierarc)o(h)o(y\))16 b(ha)o(v)o(e)f(b)q(een)i(quite)f(di\016cult) h(to)g(construct.)22 b(T)l(or\023)-24 b(an)17 b(reviews)g(the)f (separations)j(that)75 470 y(are)d(curren)o(tly)g(kno)o(wn)g(in)h([T)l (or-91].)22 b(\(See)16 b(also)i([Be-92,)d(Gr-90].\))148 580 y(Seen)h(in)i(this)f(setting,)h(it)f(is)h(clear)f(that)g(T)l(o)q (da's)h(result)f(that)g(PH)f Fm(\022)h Fs(P)1487 562 y Fu(PP)1554 580 y Fs(sa)o(ys)g(something)75 641 y(ab)q(out)c(the)f (threshold)i(circuit)e(complexit)o(y)g(of)h(A)o(C)1015 622 y Fu(0)1034 641 y Fs(.)20 b(Ho)o(w)o(ev)o(er,)10 b(b)q(ecause)j(as)g(men)o(tioned)f(ab)q(o)o(v)o(e,)75 701 y(the)17 b(mapping)h(b)q(et)o(w)o(een)e(the)h(lev)o(els)g(of)h(LCH) f(and)h(circuit)f(depth)h(is)f(only)h(appro)o(ximate;)g(th)o(us)75 761 y(a)f(direct)f(pro)q(of)h(is)g(necessary)f(if)h(one)f(w)o(an)o(ts)h (to)f(ac)o(hiev)o(e)g(the)g(sharp)q(est)h(p)q(ossible)i(result.)148 871 y(In)e([Al-89],)f(a)h(v)o(ery)f(simple)h(pro)q(of)h(w)o(as)f (presen)o(ted)f(of)h(the)f(fact)h(that)g(\(non-uniform\))h(A)o(C)1854 853 y Fu(0)1854 883 y Fl(k)75 936 y Fs(can)13 b(b)q(e)g(recognized)h(b) o(y)e(\(non-uniform\))j(depth)e(three)f(threshold)j(circuits)1459 918 y Fu(4)1492 936 y Fs(of)e(size)h Fj(n)1663 918 y Fu(log)1708 905 y Fk(k)1733 918 y Fl(n)1757 936 y Fs(.)20 b(The)75 996 y(pro)q(of)d(in)g([Al-89])f(w)o(as)h(inspired)g(b)o(y)f(T) l(o)q(da's)h(theorem,)f(but)g(it)g(do)q(es)h(not)g(follo)o(w)h (directly)e(from)75 1056 y([T)l(o-89].)24 b(In)17 b(fact)f(the)h (circuit)h(complexit)o(y)e(result)i(of)f([Al-89])g(app)q(ears)h(to)f(b) q(e)g(m)o(uc)o(h)f(easier)i(to)75 1116 y(pro)o(v)o(e)i(than)h(T)l(o)q (da's)g(theorem;)h(the)e(pro)q(of)h(of)g([Al-89])g(mak)o(es)f(use)g(of) h(some)f(imp)q(ortan)o(t)i(but)75 1176 y(elemen)o(tary)15 b(observ)m(ations)k(of)d(Razb)q(oro)o(v)h(and)g(Smolensky)f([Ra-87,)h (Sm-87].)148 1286 y(It)k(is)g(also)i(true)d(that)i(\(uniform\))f(A)o(C) 876 1268 y Fu(0)876 1299 y Fl(k)918 1286 y Fs(can)g(b)q(e)g(recognized) g(b)o(y)f(\(uniform\))i(depth)f(three)75 1351 y(threshold)i(circuits)g (of)f(size)g Fj(n)660 1333 y Fu(log)705 1320 y Fk(k)730 1333 y Fl(n)754 1351 y Fs(,)h(although)g(the)f(pro)q(of)h(is)g(sligh)o (tly)g(more)f(complex)f(than)75 1411 y(that)h(of)f([Al-89].)36 b(\(The)21 b(pro)q(of)i(of)e(the)g(uniform)h(v)o(ersion)f(still)i(do)q (es)f(not)g(app)q(eal)g(to)g(T)l(o)q(da's)75 1472 y(theorem.\))f(The)16 b(pro)q(of)h(of)g(the)f(theorem)f(for)i(uniform)g(circuits)g(is)g (found)g(in)g([AH-90].)75 1582 y Fv(3.)24 b(Conclusion)148 1692 y Fs(W)l(e)15 b(hop)q(e)h(that)g(this)g(will)h(serv)o(e)d(as)i(a)g (useful)f(surv)o(ey)g(of)g(an)h(area)g(of)f(researc)o(h)g(w)o(e)g (\014nd)g(v)o(ery)75 1752 y(exciting.)32 b(There)20 b(are)g(a)g(great)g (man)o(y)f(op)q(en)h(problems,)h(and)g(w)o(e)e(feel)h(con\014den)o(t)f (that)h(m)o(uc)o(h)75 1812 y(progress)e(on)f(these)f(problems)h(will)i (b)q(e)e(made)f(in)h(the)g(next)f(few)g(y)o(ears.)23 b(T)l(o)17 b(close)g(this)g(surv)o(ey)l(,)75 1872 y(w)o(e)f(men)o(tion) g(a)h(few)f(problems)h(that)f(seem)g(w)o(orth)o(y)g(of)g(study:)148 2020 y Fm(\017)24 b Fs(What)f(inclusions)i(can)d(b)q(e)h(sho)o(wn)g (among)g(the)f(complexit)o(y)g(classes)h(de\014ned)f(b)o(y)g(the)197 2081 y(op)q(erators)16 b Fm(9)p Fj(;)8 b Fm(8)p Fj(;)g Fm(\010)p Fj(;)g(B)s(P)f Fs(,)12 b Fv(C)p Fs(?)k(Man)o(y)e(of)h(the)g (relationships)j(ha)o(v)o(e)c(y)o(et)g(to)h(b)q(e)g(w)o(ork)o(ed)f (out.)148 2181 y Fm(\017)24 b Fs(Are)d(there)g(other)h(op)q(erators)h (that)f(w)o(ould)h(b)q(e)f(more)f(useful)i(for)f(study?)38 b(\(Note)22 b(that)197 2242 y(b)q(efore)17 b(T)l(o)q(da's)h(w)o(ork)f (it)g(w)o(as)h(not)f(widely)h(susp)q(ected)f(that)g Fj(B)s(P)i Fm(\001)11 b(\010\001)p Fs(P)17 b(w)o(ould)h(turn)f(out)197 2302 y(to)g(b)q(e)f(so)h(in)o(teresting.\))148 2402 y Fm(\017)24 b Fs(Is)13 b(IP)h(\(or)g(IP\(log\)\))h(con)o(tained)f(in)g (the)g(coun)o(ting)g(hierarc)o(h)o(y?)21 b(\(IP)13 b(\(IP\(log\)\))i (is)f(the)g(class)197 2463 y(of)i(languages)j(accepted)c(b)o(y)h(in)o (teractiv)o(e)f(pro)q(of)i(systems)f(with)h Fj(n)1430 2444 y Fl(O)q Fu(\(1\))1521 2463 y Fs(\(log)11 b Fj(n)p Fs(\))16 b(rounds)h(of)p 75 2508 720 2 v 131 2539 a Fo(4)150 2554 y Fn(In)d(the)g(mean)o(time,)d(Y)m(ao)i(has)h(sho)o(wn)g(stronger) h(inclusions)e(of)h(this)g(sort)g([Y)m(a-90].)p eop %%Page: 10 10 10 9 bop 197 53 a Fs(comm)o(unication.\))23 b(Is)16 b(there)g(an)i(in)o (teresting)f(circuit)g(complexit)o(y)f(class)i(corresp)q(onding)197 114 y(to)f(IP\(log\)?)430 96 y Fu(5)148 215 y Fm(\017)24 b Fs(Can)g(the)g(circuit)g(lo)o(w)o(er)f(b)q(ounds)i(of)f([HM-87])f(b)q (e)h(extended)f(to)h(circuits)g(of)g(greater)197 275 y(depth?)148 377 y Fm(\017)g Fs(Is)13 b(A)o(C)318 359 y Fu(0)351 377 y Fm(\022)f Fs(TC)472 359 y Fu(0)472 390 y(3)493 377 y Fs(,)h(or)g(is)h(the)f(sim)o(ulation)i(of)e(A)o(C)1060 359 y Fu(0)1092 377 y Fs(presen)o(ted)f(in)i([Al-89])f(optimal?)22 b(\(A)13 b(\014rst)197 437 y(step)19 b(in)h(this)g(direction)g(has)f(b) q(een)g(tak)o(en)g(b)o(y)f(Bruc)o(k)g(and)i(Smolensky)f([BS-92].)29 b(They)197 498 y(sho)o(w)17 b(that)f(A)o(C)494 479 y Fu(0)530 498 y Fs(requires)g(size)g(at)h(least)g(2)1003 479 y Fu(p)q(olylog)o Fl(n)1156 498 y Fs(on)f(depth)g(2)h(threshold)g (circuits.\))148 599 y Fm(\017)24 b Fs(And)16 b(last)h(but)g(not)f (least,)h(w)o(e)f(lea)o(v)o(e)g(the)g(big)h(question:)22 b(is)17 b(TC)1390 581 y Fu(0)1426 599 y Fs(=)f(NC)1552 581 y Fu(1)1572 599 y Fs(?)75 815 y Fa(References)75 946 y Fs([Aj-83])123 b(M.)16 b(Ajtai,)i(\006)592 928 y Fu(1)592 958 y(1)631 946 y Ft(formulae)g(on)h(\014nite)h(structur)n (es)p Fs(,)d(Annals)h(of)g(Pure)f(and)h(Applied)342 1006 y(Logic)g(24,)e(1-48.)75 1108 y([Al-89])125 b(E.)16 b(Allender,)g Ft(A)i(note)g(on)g(the)g(p)n(ower)f(of)h(thr)n(eshold)f(cir)n(cuits)p Fs(,)f(Pro)q(c.)h(30th)g(IEEE)342 1168 y(Symp)q(osium)g(on)g(F)l (oundations)i(of)d(Computer)h(Science,)f(pp.)g(580{584.)j(See)c(also) 342 1228 y([AH-92].)75 1330 y([Al-90])125 b(E.)16 b(Allender,)h Ft(Or)n(acles)i(vs)f(pr)n(o)n(of)e(te)n(chniques)k(that)e(do)g(not)h(r) n(elativize)p Fs(,)e(Pro)q(c.)g(In-)342 1390 y(ternational)i(Symp)q (osium)f(SIGAL)f('90,)g(Lecture)g(Notes)g(in)g(Computer)h(Science)342 1450 y(450,)f(pp.)f(39{52.)75 1552 y([AH-90])101 b(E.)31 b(Allender)h(and)g(U.)e(Hertrampf,)k Ft(On)e(the)g(p)n(ower)f(of)g (uniform)h(families)342 1612 y(of)f(c)n(onstant)h(depth)f(thr)n(eshold) g(cir)n(cuits)p Fs(,)j(Pro)q(c.)d(15th)h(In)o(ternational)g(Sym-)342 1672 y(p)q(osium)j(on)f(Mathematical)h(F)l(oundations)h(of)e(Computer)g (Science,)j(1990,)342 1732 y(Lecture)16 b(Notes)g(in)h(Computer)f (Science)p 342 1749 756 2 v 16 w(452,)h(pp.)f(158{164.)i(See)e(also)i ([AH-92].)75 1834 y([AH-92])101 b(E.)13 b(Allender)h(and)h(U.)d (Hertrampf,)h Ft(Depth)j(r)n(e)n(duction)f(for)f(cir)n(cuits)h(of)g (unb)n(ounde)n(d)342 1894 y(fan-in)p Fs(,)i(to)f(app)q(ear)i(in)e (Information)i(and)f(Computation.)75 1996 y([Ba-90])116 b(L.)11 b(Babai,)i Ft(E-mail)h(and)f(the)h(unexp)n(e)n(cte)n(d)g(p)n (ower)f(of)g(inter)n(action)p Fs(,)f(Pro)q(c.)g(5th)g(IEEE)342 2056 y(Structure)k(in)h(Complexit)o(y)f(Theory)g(Conference,)g(pp.)g (30{44.)p 75 2100 720 2 v 131 2130 a Fo(5)150 2146 y Fn(Just)11 b(b)q(efore)f(this)g(pap)q(er)h(w)o(as)f(ready)g(to)g(b)q(e) h(sen)o(t)f(o\013)g(to)g(EA)m(TCS)g(Bulletin,)g(w)o(e)g(learned)g(of)g (a)f(v)o(ery)i(imp)q(ortan)o(t)75 2195 y(result)g(of)e(Adi)h(Shamir,)f (building)f(on)i(earlier)g(w)o(ork)g(of)f(N.)h(Nisan,)g(and)g(of)g(C.)f (Lund,)h(L.)g(F)m(ortno)o(w,)g(and)g(H.)f(Karlo\013)75 2245 y([LFKN-90].)16 b(Shamir)8 b(has)j(sho)o(wn)f(that)h(IP=PSP)m(A)o (CE)g([Sh-90].)k(One)c(reason)g(this)g(is)f(an)g(esp)q(ecially)g(in)o (teresting)75 2295 y(result)16 b(is)f(the)g(fact)g(that)h(there)g(is)f (an)g(oracle)g(relativ)o(e)g(to)g(whic)o(h)f(IP)i(do)q(es)f(not)g(con)o (tain)g(coNP)h([FS-88].)k(Th)o(us)75 2345 y(this)13 b(is)f(the)i(most)d (imp)q(ortan)o(t)g(example)h(of)g(a)g(result)i(concerning)f(\\robust")g (complexit)o(y)e(classes)j(that)f(do)q(es)g(not)75 2395 y(relativize;)19 b(this)f(is)f(sure)i(to)e(ha)o(v)o(e)h(wide-ranging)f (implicatio)o(ns.)27 b(\(In)18 b(the)g(mean)o(time,)e(a)h(n)o(um)o(b)q (er)g(of)g(pap)q(ers)75 2444 y(ha)o(v)o(e)12 b(app)q(eared)h(in)f(whic) o(h)g(these)i(implications)c(are)i(discussed:)19 b([Br-90,)12 b(Br-90a,)g(HCR-90,)f(HCRR-90,)f(Al-90,)75 2494 y(Ba-90,)j(CGH-90].\))p eop %%Page: 11 11 11 10 bop 75 53 a Fs([BM-89])95 b(L.)12 b(Babai)h(and)f(S.)g(Moran,)g Ft(A)o(rthur-Merlin)i(games:)21 b(a)13 b(r)n(andomize)n(d)f(pr)n(o)n (of)g(system)342 114 y(and)19 b(a)h(hier)n(ar)n(chy)d(of)i(c)n (omplexity)h(classes)p Fs(,)g(J.)e(Comput.)g(and)h(System)e(Sciences) 342 174 y(36,)f(254{276.)75 275 y([BIS-90])95 b(D.)16 b(A.)g(Mix)h(Barrington,)g(N.)f(Immerman,)f(and)i(H.)f(Straubing,)i Ft(On)g(uniformity)342 336 y(within)g Fs(NC)562 318 y Fu(1)582 336 y Fs(,)d(Journal)j(of)f(Computer)f(and)h(System)f (Sciences)f(41,)i(274{306.)75 437 y([Be-92])118 b(R.)10 b(Beigel,)i Ft(Per)n(c)n(eptr)n(ons,)h(PP,)f(and)h(the)g(p)n(olynomial) g(hier)n(ar)n(chy)p Fs(,)c(Pro)q(c.)i(7th)h(IEEE)342 498 y(Structure)k(in)h(Complexit)o(y)f(Theory)g(Conference,)g(pp.)g (14{19.)75 599 y([BHW-91])53 b(R.)17 b(Beigel,)i(L.)f(Hemac)o(handra,)f (and)i(G.)f(W)l(ec)o(hsung,)g Ft(Pr)n(ob)n(abilistic)h(p)n(olynomial) 342 659 y(time)k(is)g(close)n(d)g(under)g(p)n(arity)e(r)n(e)n(ductions) p Fs(,)i(Information)g(Pro)q(cessing)h(Letters)342 720 y(37,)16 b(91{94.)75 821 y([BRS-91])77 b(R.)19 b(Beigel,)i(N.)d (Reingold,)k(and)f(D.)e(Spielman,)i Ft(PP)g(is)g(close)n(d)g(under)g (interse)n(c-)342 882 y(tion)p Fs(,)15 b(Pro)q(c.)f(23rd)i(A)o(CM)d (Symp)q(osium)j(on)f(Theory)f(of)h(Computing,)h(pp.)e(1{9.)h(T)l(o)342 942 y(app)q(ear)i(in)g(J.)f(Computer)g(and)h(System)f(Science.)75 1043 y([BHZ-87])73 b(R.)12 b(Boppana,)h(J.)f(H)-6 b(\027)-30 b(astad,)12 b(and)h(S.)f(Zac)o(hos,)h Ft(Do)n(es)h(c)n(o-NP)g(have)g (short)g(inter)n(active)342 1104 y(pr)n(o)n(ofs?)p Fs(,)g(Information)j (Pro)q(cessing)h(Letters)e(25,)h(127{132.)75 1205 y([Br-90])121 b(G.)14 b(Brassard,)g Ft(Hot)i(news)g(on)g(inter)n(active)g(pr)n(oto)n (c)n(ols)p Fs(,)d(SIGA)o(CT)h(News)f(21,)i(1,)f(pp.)342 1266 y(7{11.)75 1367 y([Br-90a])97 b(G.)16 b(Brassard,)g Ft(Hiding)i(information)f(fr)n(om)f(or)n(acles)p Fs(,)g(SIGA)o(CT)f (News)h(21,)g(2,)g(pp.)342 1427 y(5{11.)75 1529 y([Bru-90])94 b(J.)15 b(Bruc)o(k,)f Ft(Harmonic)j(analysis)g(of)f(p)n(olynomial)h (thr)n(eshold)f(functions)p Fs(,)h(SIAM)d(J.)342 1589 y(Disc.)i(Math.)g(3,)h(168{177.)75 1691 y([BS-92])113 b(J.)17 b(Bruc)o(k)g(and)i(C.)e(Smolensky)l(,)h Ft(Polynomial)i(thr)n (eshold)e(functions,)j Fj(AC)1729 1673 y Fu(0)1767 1691 y Ft(func-)342 1751 y(tions,)d(and)f(sp)n(e)n(ctr)n(al)g(norms)p Fs(,)e(SIAM)h(J.)f(Comput.)i(21,)f(33{42.)75 1853 y([CKS-81])75 b(A.)22 b(Chandra,)j(D.)e(Kozen,)g(and)h(L.)f(Sto)q(c)o(kmey)o(er,)f Ft(A)o(lternation)p Fs(,)j(J.)e(A)o(CM)f(28,)342 1913 y(114{133.)75 2015 y([CSV-84])76 b(A.)13 b(Chandra,)i(L.)e(Sto)q(c)o (kmey)o(er,)f(and)j(U.)e(Vishkin,)h Ft(Constant)i(depth)f(r)n(e)n (ducibility)p Fs(,)342 2075 y(SIAM)g(J.)h(Comput.)g(13,)h(423{439.)75 2177 y([CGH-90])65 b(B.)16 b(Chor,)j(O.)e(Goldreic)o(h,)h(and)g(J.)f(H) -6 b(\027)-30 b(astad,)17 b Ft(The)i(r)n(andom)f(or)n(acle)g(hyp)n (othesis)g(is)342 2237 y(false)p Fs(,)d(T)l(ec)o(hnical)h(Rep)q(ort)f (631,)h(Departmen)o(t)e(of)h(Computer)g(Science,)g(T)l(ec)o(hnion)342 2297 y({)i(Israel)f(Institute)h(of)f(T)l(ec)o(hnology)l(.)75 2399 y([FKPS-85])45 b(R.)19 b(F)l(agin,)h(M.)f(Kla)o(w)o(e,)h(N.)e (Pipp)q(enger,)j(and)f(L.)f(Sto)q(c)o(kmey)o(er,)f Ft(Bounde)n(d-depth) 342 2459 y(p)n(oly-size)d(cir)n(cuits)g(for)g(symmetric)g(functions)p Fs(,)g(Theoretical)g(Computer)f(Science)342 2519 y(36,)i(239{250.)p eop %%Page: 12 12 12 11 bop 75 53 a Fs([FS-88])116 b(L.)15 b(F)l(ortno)o(w)h(and)g(M.)e (Sipser,)i Ft(A)o(r)n(e)g(ther)n(e)h(inter)n(active)g(pr)n(oto)n(c)n (ols)f(for)g(c)n(o-NP)h(lan-)342 114 y(guages?)p Fs(,)g(Information)g (Pro)q(cessing)h(Letters)e(28,)h(249{251.)75 213 y([FSS-84])89 b(M.)18 b(F)l(urst,)i(J.)f(Saxe,)h(M.)e(Sipser,)j Ft(Parity,)f(cir)n (cuits,)h(and)f(the)h(p)n(olynomial-time)342 274 y(hier)n(ar)n(chy)p Fs(,)14 b(Mathematical)j(Systems)f(Theory)g(17,)h(13{27.)75 373 y([Gi-77])124 b(J.)10 b(Gill,)k Ft(Computational)f(c)n(omplexity)g (of)g(pr)n(ob)n(abilistic)f(T)l(uring)i(machines)p Fs(,)e(SIAM)342 433 y(J.)k(Comput.)g(6,)g(675{695.)75 533 y([GP-86])104 b(L.)22 b(Goldsc)o(hlager)i(and)e(I.)f(P)o(arb)q(erry)l(,)i Ft(On)g(the)h(c)n(onstruction)f(of)g(p)n(ar)n(al)r(lel)g(c)n(om-)342 593 y(puters)f(fr)n(om)f(various)g(b)n(ases)h(of)g(Bo)n(ole)n(an)g (functions)p Fs(,)i(Theoretical)e(Computer)342 654 y(Science)16 b(43,)g(43{58.)75 753 y([Go-89])113 b(C.)14 b(Gotsman,)h Ft(On)i(Bo)n(ole)n(an)f(functions,)h(p)n(olynomials,)f(and)g(algebr)n (aic)g(thr)n(eshold)342 813 y(functions)p Fs(,)h(T)l(ec)o(h.)e(Rep)q (ort)i(TR-89-18,)h(Hebrew)d(Univ)o(ersit)o(y)l(.)75 913 y([Gr-90])118 b(F.)16 b(Green,)h Ft(A)o(n)h(or)n(acle)h(sep)n(ar)n (ating)f Fm(\010)p Ft(P)g(fr)n(om)f Fj(P)7 b(P)1301 895 y Fl(P)e(H)1362 913 y Fs(,)17 b(Pro)q(c.)g(5th)h(IEEE)f(Struc-)342 973 y(ture)f(in)h(Complexit)o(y)f(Theory)h(Conference,)e(pp.)h (295{298.)75 1073 y([Gu-90])110 b(S.)23 b(Gupta,)k Ft(A)d(note)i(on)f (the)g(c)n(ounting)h(hier)n(ar)n(chy)p Fs(,)d(T)l(ec)o(hnical)i(Rep)q (ort)f(OSU-)342 1133 y(CISR)o(C-8/90-TR24,)15 b(Computer)e(and)g (Information)g(Science)f(Researc)o(h)g(Cen)o(ter,)342 1193 y(Ohio)17 b(State)f(Univ)o(ersit)o(y)l(.)75 1293 y([HM-87])93 b(A.)17 b(Ha)s(jnal,)h(W.)f(Maass,)h(P)l(.)f(Pudl\023)-24 b(ak,)19 b(M.)e(Szegedy)l(,)f(G.)i(T)l(ur\023)-24 b(an,)18 b Ft(Thr)n(eshold)g(cir-)342 1353 y(cuits)h(of)f(b)n(ounde)n(d)g(depth) p Fs(,)f(Pro)q(c.)h(28th)g(IEEE)f(Symp)q(osium)h(on)g(F)l(oundations)h (of)342 1414 y(Computer)d(Science,)f(pp.)h(99{110.)75 1513 y([HCR-90])67 b(J.)18 b(Hartmanis,)h(R.)f(Chang,)i(D.)e(Ranjan,)i (and)f(P)l(.)f(Rohatgi,)i Ft(On)g(IP=PSP)l(A)o(CE)342 1573 y(and)e(the)n(or)n(ems)e(with)i(narr)n(ow)f(pr)n(o)n(ofs)p Fs(,)d(EA)l(TCS)i(Bulletin)h(41,)g(pp.)f(166{174.)75 1673 y([HCRR-90])31 b(J.)21 b(Hartmanis,)i(R.)e(Chang,)j(D.)d(Ranjan,)j (and)e(P)l(.)f(Rohatgi,)j Ft(Structur)n(al)f(c)n(om-)342 1733 y(plexity)g(the)n(ory:)32 b(r)n(e)n(c)n(ent)22 b(surprises)p Fs(,)g(Pro)q(c.)f(2nd)i(Scandina)o(vian)g(W)l(orkshop)g(on)342 1794 y(Algorithm)17 b(Theory)l(,)f(Lecture)g(Notes)g(in)h(Computer)f (Science)g(447,)h(pp.)f(1{12.)75 1893 y([HZ-84])108 b(P)l(.)23 b(Hinman)g(and)h(S.)f(Zac)o(hos,)i Ft(Pr)n(ob)n(abilistic)f(machines,)i (or)n(acles,)g(and)e(quan-)342 1953 y(ti\014ers)p Fs(,)c(Pro)q(c.)g(Ob) q(erw)o(olfac)o(h)g(Recursion-Theoretic)h(W)l(eek,)f(Lecture)f(Notes)g (in)342 2014 y(Mathematics)d(1141,)i(pp.)e(159{192.)75 2113 y([H)-6 b(\027)-30 b(a-86])113 b(J.)19 b(H)-6 b(\027)-30 b(astad,)19 b Ft(A)o(lmost)h(optimal)h(lower)g(b)n(ounds)f(for)g(smal)r (l)h(depth)f(cir)n(cuits)p Fs(,)g(Pro)q(c.)342 2174 y(18th)d(A)o(CM)e (Symp)q(osium)i(on)g(Theory)g(of)f(Computing,)h(pp.)f(6{20.)75 2273 y([IL-89])127 b(N.)15 b(Immerman)h(and)h(S.)f(Landau,)h Ft(The)h(c)n(omplexity)h(of)e(iter)n(ate)n(d)g(multiplic)n(ation)p Fs(,)342 2333 y(Pro)q(c.)j(4th)g(IEEE)g(Structure)g(in)g(Complexit)o(y) g(Theory)g(Conference,)g(pp.)f(104{)342 2394 y(111.)75 2493 y([Ko-89])113 b(K.)20 b(Ko,)h Ft(R)n(elativize)n(d)g(p)n (olynomial-time)h(hier)n(ar)n(chies)e(having)i(exactly)h(K)e(levels)p Fs(,)342 2554 y(SIAM)15 b(J.)h(Comput.)g(18,)h(392{408.)p eop %%Page: 13 13 13 12 bop 75 53 a Fs([KSTT-89])40 b(J.)13 b(K\177)-24 b(obler,)14 b(U.)e(Sc)o(h\177)-24 b(oning,)15 b(S.)d(T)l(o)q(da,)j(and) f(J.)f(T)l(or\023)-24 b(an,)14 b Ft(T)l(uring)i(machines)f(with)g(few) 342 114 y(ac)n(c)n(epting)21 b(c)n(omputations)f(and)f(low)i(sets)f (for)f(PP)p Fs(,)g(Pro)q(c.)f(4th)i(IEEE)e(Structure)342 174 y(in)f(Complexit)o(y)f(Theory)h(Conference,)e(pp.)h(208{215.)75 274 y([La-83])121 b(C.)14 b(Lautemann,)i Ft(BPP)g(and)h(the)f(p)n (olynomial)g(hier)n(ar)n(chy)p Fs(,)d(Information)j(Pro)q(cess-)342 334 y(ing)h(Letters)f(17,)h(215-217.)75 433 y([LFKN-90])38 b(C.)20 b(Lund,)h(L.)f(F)l(ortno)o(w,)h(H.)e(Karlo\013,)j(and)f(N.)e (Nisan,)i Ft(A)o(lgebr)n(aic)h(metho)n(ds)f(for)342 494 y(inter)n(active)g(pr)n(o)n(of)d(systems)p Fs(,)h(Pro)q(c.)g(31st)h (IEEE)f(Symp)q(osium)h(on)f(F)l(oundations)342 554 y(of)d(Computer)h (Science,)e(pp.)h(2{10.)75 654 y([Mu-71])103 b(S.)24 b(Muroga,)j(Threshold)18 b(Logic)f(and)g(Its)f(Applications)p 611 670 796 2 v 2 w(,)27 b(1971,)g(J.)d(Wiley)h(and)342 714 y(Sons.)75 813 y([PZ-83])112 b(C.)14 b(P)o(apadimitriou)j(and)f(S.) e(Zac)o(hos,)h Ft(Two)h(r)n(emarks)f(on)h(the)h(p)n(ower)e(of)h(c)n (ounting)p Fs(,)342 874 y(Pro)q(c.)k(6th)g(GI)g(Conference,)g(Lecture)f (Notes)h(in)g(Computer)g(Science)g(145,)h(pp.)342 934 y(269{275.)75 1034 y([P)o(a-90])119 b(I.)20 b(P)o(arb)q(erry)l(,)j Ft(A)f(primer)g(on)g(the)h(c)n(omplexity)g(the)n(ory)e(of)h(neur)n(al)h (networks)p Fs(,)g(in)342 1094 y Ft(A)j(Sour)n(c)n(eb)n(o)n(ok)g(on)g (F)l(ormal)g(T)l(e)n(chniques)h(in)g(A)o(rti\014cial)f(Intel)r(ligen)q (c)n(e)p Fs(,)31 b(ed.)25 b(R.)342 1154 y(Banerji,)16 b(North-Holland.)75 1254 y([PS-88])115 b(I.)16 b(P)o(arb)q(erry)i(and)g (G.)f(Sc)o(hnitger,)g Ft(Par)n(al)r(lel)j(c)n(omputation)f(with)g(thr)n (eshold)f(func-)342 1314 y(tions)p Fs(,)e(J.)g(Computer)g(and)h(System) f(Science)f(36,)i(278{302.)75 1414 y([PS-89])115 b(I.)17 b(P)o(arb)q(erry)i(and)f(G.)h(Sc)o(hnitger,)f Ft(R)n(elating)i (Boltzmann)h(machines)f(to)f(c)n(onven-)342 1474 y(tional)f(mo)n(dels)f (of)h(c)n(omputation)p Fs(,)e(Neural)g(Net)o(w)o(orks)g(2,)g(59{67.)75 1573 y([Ra-87])115 b(A.)11 b(A.)f(Razb)q(oro)o(v,)j Ft(L)n(ower)g(b)n (ounds)g(on)g(the)h(size)f(of)h(b)n(ounde)n(d)f(depth)g(networks)i (over)342 1634 y(a)i(c)n(omplete)i(b)n(asis)e(with)i(lo)n(gic)n(al)f (addition)p Fs(,)e(Mathematic)o(heskie)g(Zametki)g(41\(4\),)342 1694 y(598{607.)k(English)g(translation)h(in)d(Mathematical)h(Notes)f (of)h(the)e(Academ)o(y)g(of)342 1754 y(Sciences)f(of)g(the)g(USSR)g (41:4,)h(333-338.)75 1854 y([Re-87])117 b(J.)23 b(Reif,)h Ft(On)h(thr)n(eshold)e(cir)n(cuits)h(and)g(p)n(olynomial)g(c)n (omputation)p Fs(,)h(Pro)q(c.)e(2nd)342 1914 y(IEEE)16 b(Structure)g(in)h(Complexit)o(y)f(Theory)h(Conference,)e(pp.)h (118{123.)75 2014 y([R)l(T-90])108 b(J.)18 b(Reif)h(and)g(S.)f(T)l (ate,)h Ft(On)i(thr)n(eshold)e(cir)n(cuits)h(and)g(p)n(olynomial)f(c)n (omputation)p Fs(,)342 2074 y(submitted)d(for)h(publication.)75 2174 y([Ru-81])112 b(W.)14 b(Ruzzo,)g Ft(On)j(Uniform)f(Cir)n(cuit)f (Complexity)p Fs(,)g(J.)f(Comput.)h(and)g(System)f(Sci.)342 2234 y(21,)i(365{383.)75 2333 y([Sc-87])126 b(U.)25 b(Sc)o(h\177)-24 b(oning,)29 b Ft(Pr)n(ob)n(abilistic)d(c)n(omplexity)h(classes)h(and)e (lowness)p Fs(,)j(Pro)q(c.)d(2nd)342 2394 y(IEEE)16 b(Structure)g(in)h (Complexit)o(y)f(Theory)h(Conference,)e(pp.)h(2{8.)75 2493 y([Sh-90])121 b(A.)13 b(Shamir,)i Ft(IP)h(=)g(PSP)l(A)o(CE)p Fs(,)e(Pro)q(c.)g(31st)i(IEEE)e(Symp)q(osium)h(on)g(F)l(oundations)342 2554 y(of)h(Computer)h(Science,)e(pp.)h(11{15.)p eop %%Page: 14 14 14 13 bop 75 53 a Fs([Si-77])135 b(J.)20 b(Simon,)h Ft(On)h(the)g (di\013er)n(enc)n(e)f(b)n(etwe)n(en)i(one)f(and)f(many)p Fs(,)f(Pro)q(c.)h(4th)f(ICALP)l(,)342 114 y(Lecture)c(Notes)g(in)h (Computer)f(Science)g(52,)g(pp.)g(480{491.)75 212 y([Si-83])135 b(M.)11 b(Sipser,)i Ft(Bor)n(el)g(sets)h(and)f(cir)n(cuit)h(c)n (omplexity)p Fs(,)f(Pro)q(c.)f(15th)g(A)o(CM)f(Symp)q(osium)342 272 y(on)17 b(Theory)f(of)h(Computing,)g(pp.)f(61{69.)75 371 y([Si-83a])111 b(M.)20 b(Sipser,)j Ft(A)f(c)n(omplexity)g(the)n(or) n(etic)g(appr)n(o)n(ach)e(to)i(r)n(andomness)p Fs(,)g(Pro)q(c.)f(15th) 342 431 y(Ann)o(ual)c(A)o(CM)e(Symp)q(osium)i(on)g(Theory)f(of)h (Computing,)g(pp.)f(330{335.)75 529 y([Sm-87])107 b(R.)28 b(Smolensky)l(,)j Ft(A)o(lgebr)n(aic)f(metho)n(ds)f(in)g(the)g(the)n (ory)f(of)h(lower)h(b)n(ounds)f(for)342 590 y(Bo)n(ole)n(an)21 b(cir)n(cuit)g(c)n(omplexity)p Fs(,)g(Pro)q(c.)f(19th)h(A)o(CM)e(Symp)q (osium)i(on)g(Theory)f(of)342 650 y(Computing,)d(pp.)f(77{82.)75 748 y([St-77])129 b(L.)23 b(Sto)q(c)o(kmey)o(er,)h Ft(The)g(p)n (olynomial-time)h(hier)n(ar)n(chy)p Fs(,)e(Theoretical)i(Computer)342 808 y(Science)16 b(3,)g(1{22.)75 907 y([T)l(o-89])120 b(S.)20 b(T)l(o)q(da,)j Ft(PP)f(is)f Fm(\024)730 883 y Fl(p)730 919 y(T)757 907 y Ft(-har)n(d)g(for)g(the)h(p)n (olynomial-time)h(hier)n(ar)n(chy)p Fs(,)c(Pro)q(c.)i(30th)342 967 y(IEEE)16 b(Symp)q(osium)h(on)g(F)l(oundations)h(of)f(Computer)f (Science,)g(pp.)g(514{519.)75 1066 y([T)l(or-88])101 b(J.)16 b(T)l(or\023)-24 b(an,)17 b Ft(Structur)n(al)h(pr)n(op)n (erties)e(of)h(the)h(c)n(ounting)h(hier)n(ar)n(chies)p Fs(,)c(Do)q(ctoral)j(dis-)342 1126 y(sertation,)f(Univ)o(ersitat)g(P)o (olit)o(\022)-23 b(ecnica)17 b(de)f(Catalun)o(y)o(a,)h(Barcelona.)75 1224 y([T)l(or-91])101 b(J.)14 b(T)l(or\023)-24 b(an,)15 b Ft(Complexity)i(classes)g(de\014ne)n(d)f(by)g(c)n(ounting)h (quanti\014ers)p Fs(,)f(J.)e(A)o(CM)g(38,)342 1284 y(753{774.)75 1383 y([VV-86])101 b(L.)17 b(V)l(alian)o(t)g(and)h(V.)e(V)l(azirani,)h Ft(NP)h(is)g(as)g(e)n(asy)f(as)h(dete)n(cting)h(unique)h(solutions)p Fs(,)342 1443 y(Theoretical)d(Computer)g(Science)e(47,)i(85{93.)75 1541 y([W)l(a-86])105 b(K.)17 b(W.)h(W)l(agner,)g Ft(The)h(c)n (omplexity)h(of)e(c)n(ombinatorial)i(pr)n(oblems)e(with)i(suc)n(cinct) 342 1602 y(input)e(r)n(epr)n(esentation)p Fs(,)e(Acta)g(Informatica)g (23,)h(325{356.)75 1700 y([W)l(a-86a])81 b(K.)19 b(W.)h(W)l(agner,)h Ft(Some)g(observations)h(on)f(the)g(c)n(onne)n(ction)h(b)n(etwe)n(en)h (c)n(ounting)342 1760 y(and)18 b(r)n(e)n(cursion)p Fs(,)d(Theoretical)i (Computer)f(Science)g(47,)h(131{147.)75 1859 y([W)l(r-77])110 b(C.)16 b(W)l(rathall,)i Ft(Complete)g(sets)g(and)g(the)g(p)n (olynomial-time)g(hier)n(ar)n(chy)p Fs(,)c(Theoret-)342 1919 y(ical)j(Computer)g(Science)e(3,)i(23{33.)75 2017 y([Y)l(a-85])118 b(A.)21 b(C.)h(Y)l(ao,)h Ft(Sep)n(ar)n(ating)g(the)g (p)n(olynomial-time)g(hier)n(ar)n(chy)e(by)i(or)n(acles)p Fs(,)g(Pro)q(c.)342 2078 y(26th)17 b(IEEE)f(Symp)q(osium)h(on)g(F)l (oundations)i(of)d(Computer)g(Science,)g(pp.)g(1{10.)75 2176 y([Y)l(a-89])118 b(A.)15 b(C.)h(Y)l(ao,)h Ft(Cir)n(cuits)f(and)i (lo)n(c)n(al)g(c)n(omputation)p Fs(,)e(Pro)q(c.)g(21st)i(A)o(CM)d(Symp) q(osium)342 2236 y(on)i(Theory)f(of)h(Computing,)g(pp.)f(186{196.)75 2335 y([Y)l(a-90])118 b(A.)14 b(C.)h(Y)l(ao,)g Ft(On)i(A)o(CC)f(and)h (thr)n(eshold)f(cir)n(cuits)p Fs(,)f(Pro)q(c.)g(31st)h(IEEE)f(Symp)q (osium)342 2395 y(on)i(F)l(oundations)h(of)e(Computer)h(Science.)75 2493 y([Za-88])121 b(S.)15 b(Zac)o(hos,)h Ft(Pr)n(ob)n(abilistic)h (Quanti\014ers)h(and)f(Games)p Fs(,)e(J.)g(Comput.)g(and)i(System)342 2554 y(Sci.)f(36,)h(433{451.)p eop %%Page: 15 15 15 14 bop 75 53 a Fs([ZF-87])113 b(S.)21 b(Zac)o(hos)g(and)h(M.)e(F)q (\177)-26 b(urer,)23 b Ft(Pr)n(ob)n(abilistic)f(quanti\014ers)h(vs.)f (distrustful)g(adver-)342 114 y(saries)p Fs(,)13 b(Pro)q(c.)i(7th)f (Conference)f(on)i(F)l(oundations)h(of)e(Soft)o(w)o(are)g(T)l(ec)o (hnology)g(and)342 174 y(Theoretical)k(Computer)e(Science,)g(Lecture)g (Notes)g(in)i(Computer)e(Science)g(287,)342 234 y(pp.)g(443{455.)75 336 y([ZH-86])108 b(S.)12 b(Zac)o(hos)h(and)h(H.)e(Heller,)h Ft(A)i(de)n(cisive)g(char)n(acterization)f(of)g(BPP)p Fs(,)f(Information)342 396 y(and)k(Con)o(trol)g(69,)g(125{135.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF