%!PS-Adobe-2.0 %%Creator: dvips 5.514 Copyright 1986, 1993 Radical Eye Software %%Title: relative.dvi %%CreationDate: Fri Jan 14 11:28:29 1994 %%Pages: 15 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips relative -o /homes/fortnow/ftp/relative.ps %DVIPSSource: TeX output 1994.01.14:1126 %%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 /@rigin{isls{[ 0 -1 1 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{Resolution hsize -72 div mul 0 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/homes/fortnow/papers/nonresearch/relative.dvi) @start /Fa 1 51 df<7FFFFF80FFFFFF80C0000180C0000180C0000180C0000180C000 0180C0000180C0000180C0000180C0000180C0000180C0000180C0000180C0000180C000 0180C0000180C0000180C0000180C0000180C0000180C0000180C0000180FFFFFF807FFF FF8019197C9B22>50 D E /Fb 2 108 df<001800003800003800005800009800008C00 010C00020C00060C0007FE00080600100600300600F81F80110E7E8D16>65 D<7800180018001800300030C03360344078007E0063006320C340C1800B0E7E8D10> 107 D E /Fc 2 9 df<040004000400C460E4E03F800E003F80E4E0C460040004000400 0B0D7E8D11>3 D<01F80006260008210010208020204020204040202040202080201080 2010FFFFF080201080201080201040202040202020204020204010208008210006260001 F80014167E911A>8 D E /Fd 5 85 df<00070700000707000007070000070700000E0E 00000E0E00000E0E00000E0E00001C1C00FFFFFFF8FFFFFFF87FFFFFF800707000007070 000070700000707000007070007FFFFFF8FFFFFFF8FFFFFFF801C1C00003838000038380 000383800003838000070700000707000007070000070700001D1D7E9622>35 D<00060000000F0000000F0000001F8000001F8000001F80000037C0000037C0000063E0 000063E00000E3F00000C1F00000C1F0000180F8000180F80003FFFC0003FFFC0007007E 0006003E000E003F000C001F00FF80FFF0FF80FFF01C177F961F>65 D80 D<07F0801FFD80380F80700380F00380F00180F00180F80000FF80007FF800 3FFE001FFF0007FF80007F80000FC00007C0C003C0C003C0C003C0E00380F80F00DFFE00 87F80012177E9617>83 D<7FFFFF007FFFFF00783E0F00603E0300E03E0380C03E0180C0 3E0180C03E0180003E0000003E0000003E0000003E0000003E0000003E0000003E000000 3E0000003E0000003E0000003E0000003E0000003E000007FFF00007FFF00019177F961C >I E /Fe 56 123 df<00003FE00000E010000180380003807800030078000700300007 00000007000000070000000E0000000E0000000E000000FFFFE0000E00E0001C01C0001C 01C0001C01C0001C01C0001C038000380380003803800038038000380700003807000070 07000070071000700E2000700E2000700E2000E00E2000E0064000E0038000E0000000C0 000001C0000001C000003180000079800000F3000000620000003C0000001D29829F1A> 12 D<1C3C3C3C3C040408081020204080060E7D840E>44 D<7FF0FFE07FE00C037D8A10> I<70F8F8F0E005057B840E>I<000F800030E000E07001C0700380300380380700380F00 780F00780E00781E00781E00703C00F03C00F03C00F03C00F07801E07801E07801E07801 C07003C0F003C0F00380F00780F00700700700700E00701C003038001870000FC000151F 7C9D17>48 D<000200020006000E003C00DC031C001C0038003800380038007000700070 007000E000E000E000E001C001C001C001C003800380038003800780FFF80F1E7B9D17> I<001F000061800080E00100E00200700220700420700410700820F00820F00820F00840 E00881E00703C0000380000700000C000018000060000080000300000400000800401000 401000802001807E030047FF0041FE0080FC00807800141F7C9D17>I<001F800060E000 80700100300200380420380420380410380420700460700380600000E00001C000030000 FE00001C00000600000700000780000780000780300780780780780780F00F00800F0040 1E00401C0040380020E0001F8000151F7C9D17>I<00C06000FFC001FF8001FE00010000 010000020000020000020000020000040000047800058C000606000C0700080700000780 000780000780000780000F00700F00F00F00F00E00E01E00801C00803800803000406000 61C0001F0000131F7B9D17>53 D<08E0100BF01017F8201FF8603E19C0380E8020008060 0100400300800300000600000E00000C00001C00001C0000380000380000700000700000 F00000F00001E00001E00001E00003C00003C00003C00007C00007800007800003000014 1F799D17>55 D<001F000061800080C00100600300600600600600600600600E00C00F00 800F818007C30007E40003F80001F80003FC00047E00183F00300F00200700600700C003 00C00300C00300800600800600C00C00C008004030003060001F8000131F7B9D17>I<00 1F0000718000C0C00180C00380E00700E00F00E00F01E01E01E01E01E01E01E01E01C01C 03C01C03C01C03C01C07C01C0F800C0F8006378003C700000F00000E00000E00001C0060 1C00F03800F07000E0600080C0004380003E0000131F7B9D17>I<070F1F1F0E00000000 00000000000070F8F8F0E008147B930E>I<00000200000006000000060000000E000000 1E0000001E0000003F0000002F0000004F0000004F0000008F0000010F0000010F000002 0F0000020F0000040F00000C0F0000080F0000100F0000100F0000200F80003FFF800040 078000C007800080078001000780010007800200078002000780060007801E000F80FF80 7FF81D207E9F22>65 D<01FFFFC0001E00F0001E0078001E0038001E003C003C003C003C 003C003C003C003C003C0078007800780078007800F0007801E000F0078000FFFE0000F0 0F8000F003C001E001C001E001E001E001E001E001E003C001E003C001E003C001E003C0 01C0078003C00780078007800F0007801E000F007800FFFFE0001E1F7D9E20>I<0000FE 0200078186001C004C0038003C0060003C00C0001C01C0001803800018070000180F0000 181E0000101E0000103C0000003C00000078000000780000007800000078000000F00000 00F0000000F0000000F0000000F000008070000080700000807000010038000100380002 00180004000C001800060020000381C00000FE00001F217A9F21>I<01FFFF80001E00E0 001E0070001E0038001E001C003C001C003C000E003C000E003C000E0078000E0078000E 0078000E0078000E00F0001E00F0001E00F0001E00F0001E01E0003C01E0003C01E0003C 01E0007803C0007003C0007003C000E003C001C0078001C00780038007800E0007801C00 0F007000FFFFC0001F1F7D9E22>I<01FFFFFE001E001C001E000C001E0004001E000400 3C0004003C0004003C0004003C00040078080800780800007808000078180000F0300000 FFF00000F0300000F0300001E0200001E0200001E0200001E0001003C0002003C0002003 C0004003C00040078000800780018007800100078007000F001F00FFFFFE001F1F7D9E1F >I<01FFFFFC001E0038001E0018001E0008001E0008003C0008003C0008003C0008003C 00080078001000780800007808000078080000F0100000F0300000FFF00000F0300001E0 200001E0200001E0200001E0200003C0000003C0000003C0000003C00000078000000780 000007800000078000000F800000FFF800001E1F7D9E1E>I<0000FC040007030C001C00 980030007800E0007801C000380380003003800030070000300E0000301E0000201E0000 203C0000003C00000078000000780000007800000078000000F0000000F000FFF0F00007 80F0000780F0000F0070000F0070000F0070000F0070001E0038001E0018003E001C002E 000E00CC000383040000FC00001E217A9F23>I<01FFF3FFE0001F003E00001E003C0000 1E003C00001E003C00003C007800003C007800003C007800003C007800007800F0000078 00F000007800F000007800F00000F001E00000FFFFE00000F001E00000F001E00001E003 C00001E003C00001E003C00001E003C00003C007800003C007800003C007800003C00780 0007800F000007800F000007800F000007800F00000F801F0000FFF1FFE000231F7D9E22 >I<01FFF0001F00001E00001E00001E00003C00003C00003C00003C0000780000780000 780000780000F00000F00000F00000F00001E00001E00001E00001E00003C00003C00003 C00003C0000780000780000780000780000F8000FFF800141F7D9E12>I<001FFF0000F8 0000F00000F00000F00001E00001E00001E00001E00003C00003C00003C00003C0000780 000780000780000780000F00000F00000F00000F00001E00001E00301E00781E00F83C00 F83C00F0780080700040E00021C0001F000018207D9E18>I<01FFF800001F0000001E00 00001E0000001E0000003C0000003C0000003C0000003C00000078000000780000007800 000078000000F0000000F0000000F0000000F0000001E0000001E0000001E0000001E000 8003C0010003C0010003C0030003C00200078006000780060007800C0007801C000F0078 00FFFFF800191F7D9E1D>76 D<01FE00007FC0001E0000FC00001E0000F8000017000178 0000170001780000270002F00000270004F00000270004F00000270008F00000470009E0 0000470011E00000470021E00000470021E00000870043C00000838043C00000838083C0 0000838083C0000103810780000103820780000103820780000103840780000203840F00 000203880F00000203900F00000203900F00000401E01E00000401E01E00000401C01E00 000C01801E00001C01803E0000FF8103FFC0002A1F7D9E29>I<01FF007FE0001F000F00 001F0004000017800400001780040000278008000023C008000023C008000023C0080000 41E010000041E010000041F010000040F010000080F02000008078200000807820000080 78200001003C400001003C400001003C400001001E400002001E800002001E800002000F 800002000F800004000F0000040007000004000700000C000700001C00020000FF800200 00231F7D9E22>I<01FFFF80001E00E0001E0070001E0038001E003C003C003C003C003C 003C003C003C003C0078007800780078007800F0007800E000F003C000F00F0000FFFC00 00F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C00000 078000000780000007800000078000000F800000FFF000001E1F7D9E1F>80 D<01FFFF00001E03C0001E00E0001E0070001E0078003C0078003C0078003C0078003C00 78007800F0007800F0007801E0007801C000F0070000F01E0000FFF00000F0380001E01C 0001E01E0001E00E0001E00F0003C01E0003C01E0003C01E0003C01E0007803C0007803C 0807803C0807803C100F801C10FFF00C20000007C01D207D9E21>82 D<0007E040001C18C0003005800060038000C0038001C001800180010003800100038001 00038001000380000003C0000003C0000003F8000001FF800001FFE000007FF000001FF0 000001F80000007800000078000000380000003800200038002000380020003000600070 00600060006000E0007000C000E8038000C606000081F800001A217D9F1A>I<0FFFFFF0 1E0780E0180780201007802020078020200F0020600F0020400F0020400F0020801E0040 001E0000001E0000001E0000003C0000003C0000003C0000003C00000078000000780000 007800000078000000F0000000F0000000F0000000F0000001E0000001E0000001E00000 01E0000003E00000FFFF00001C1F789E21>I87 D<00F1800389C00707800E03801C03803C0380380700780700780700780700F00E00 F00E00F00E00F00E20F01C40F01C40703C40705C40308C800F070013147C9317>97 D<07803F8007000700070007000E000E000E000E001C001C001CF01D0C3A0E3C0E380F38 0F700F700F700F700FE01EE01EE01EE01CE03CE038607060E031C01F0010207B9F15>I< 007E0001C1000300800E07801E07801C07003C0200780000780000780000F00000F00000 F00000F00000F0000070010070020030040018380007C00011147C9315>I<0000780003 F80000700000700000700000700000E00000E00000E00000E00001C00001C000F1C00389 C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E 20F01C40F01C40703C40705C40308C800F070015207C9F17>I<007C01C207010E011C01 3C013802780C7BF07C00F000F000F000F0007000700170023804183807C010147C9315> I<00007800019C00033C00033C000718000700000700000E00000E00000E00000E00000E 0001FFE0001C00001C00001C00001C000038000038000038000038000038000070000070 0000700000700000700000700000E00000E00000E00000E00000C00001C00001C0000180 003180007B0000F300006600003C00001629829F0E>I<003C6000E27001C1E00380E007 00E00F00E00E01C01E01C01E01C01E01C03C03803C03803C03803C03803C07003C07001C 0F001C17000C2E0003CE00000E00000E00001C00001C00301C00783800F0700060E0003F 8000141D7E9315>I<01E0000FE00001C00001C00001C00001C000038000038000038000 038000070000070000071E000763000E81800F01C00E01C00E01C01C03801C03801C0380 1C0380380700380700380700380E10700E20700C20701C20700C40E00CC060070014207D 9F17>I<00C001E001E001C000000000000000000000000000000E003300230043804300 470087000E000E000E001C001C001C003840388030807080310033001C000B1F7C9E0E> I<01E0000FE00001C00001C00001C00001C0000380000380000380000380000700000700 000703C00704200E08E00E11E00E21E00E40C01C80001D00001E00001FC00038E0003870 00387000383840707080707080707080703100E03100601E0013207D9F15>107 D<03C01FC0038003800380038007000700070007000E000E000E000E001C001C001C001C 0038003800380038007000700070007100E200E200E200E200640038000A207C9F0C>I< 1C0F80F0002630C318004740640C004780680E004700700E004700700E008E00E01C000E 00E01C000E00E01C000E00E01C001C01C038001C01C038001C01C038001C01C070803803 8071003803806100380380E10038038062007007006600300300380021147C9325>I<1C 0F802630C04740604780604700704700708E00E00E00E00E00E00E00E01C01C01C01C01C 01C01C03843803883803083807083803107003303001C016147C931A>I<007C0001C300 0301800E01C01E01C01C01E03C01E07801E07801E07801E0F003C0F003C0F003C0F00780 F00700700F00700E0030180018700007C00013147C9317>I<01C1E002621804741C0478 1C04701E04701E08E01E00E01E00E01E00E01E01C03C01C03C01C03C01C0380380780380 700380E003C1C0072380071E000700000700000E00000E00000E00000E00001C00001C00 00FFC000171D809317>I<00F0400388C00705800E03801C03803C038038070078070078 0700780700F00E00F00E00F00E00F00E00F01C00F01C00703C00705C0030B8000F380000 380000380000700000700000700000700000E00000E0000FFE00121D7C9315>I<1C1E00 2661004783804787804707804703008E00000E00000E00000E00001C00001C00001C0000 1C000038000038000038000038000070000030000011147C9313>I<00FC030206010C03 0C070C060C000F800FF007F803FC003E000E700EF00CF00CE008401020601F8010147D93 13>I<018001C0038003800380038007000700FFF007000E000E000E000E001C001C001C 001C003800380038003820704070407080708031001E000C1C7C9B0F>I<0E00C03300E0 2301C04381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C0710 1C0E20180E20180E201C1E200C264007C38014147C9318>I<0E03803307802307C04383 C04301C04700C08700800E00800E00800E00801C01001C01001C01001C02001C02001C04 001C04001C08000E300003C00012147C9315>I<0E00C1C03300E3C02301C3E04381C1E0 4301C0E04701C060870380400E0380400E0380400E0380401C0700801C0700801C070080 1C0701001C0701001C0602001C0F02000C0F04000E13080003E1F0001B147C931E>I<03 83800CC4401068E01071E02071E02070C040E00000E00000E00000E00001C00001C00001 C00001C040638080F38080F38100E5810084C60078780013147D9315>I<0E00C03300E0 2301C04381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C0700 1C0E00180E00180E001C1E000C3C0007DC00001C00001C00003800F03800F07000E06000 C0C0004380003E0000131D7C9316>I<01C04003E08007F1800C1F000802000004000008 000010000020000040000080000100000200000401000802001002003E0C0063FC0041F8 0080E00012147D9313>I E /Ff 45 123 df<0007F80FF000007FFE7FFC0001F80FF80E 0003E00FE01F0007C01FC03F000F801F803F000F801F803F000F800F801E000F800F800C 000F800F8000000F800F8000000F800F8000000F800F800000FFFFFFFFFF00FFFFFFFFFF 000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F 000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F 000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F 007FF07FF0FFE07FF07FF0FFE02B237FA22F>14 D45 D<387CFEFEFE7C3807077C8610>I<00180000780001F800FFF800FFF80001F80001F800 01F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F800 01F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8007FFFE0 7FFFE013207C9F1C>49 D<03FC000FFF003C1FC07007E07C07F0FE03F0FE03F8FE03F8FE 01F87C01F83803F80003F80003F00003F00007E00007C0000F80001F00003E0000380000 700000E01801C0180380180700180E00380FFFF01FFFF03FFFF07FFFF0FFFFF0FFFFF015 207D9F1C>I<00FE0007FFC00F07E01E03F03F03F03F81F83F81F83F81F81F03F81F03F0 0003F00003E00007C0001F8001FE0001FF000007C00001F00001F80000FC0000FC3C00FE 7E00FEFF00FEFF00FEFF00FEFF00FC7E01FC7801F81E07F00FFFC001FE0017207E9F1C> I<0000E00001E00003E00003E00007E0000FE0001FE0001FE00037E00077E000E7E001C7 E00187E00307E00707E00E07E00C07E01807E03807E07007E0E007E0FFFFFEFFFFFE0007 E00007E00007E00007E00007E00007E00007E000FFFE00FFFE17207E9F1C>I<1000201E 01E01FFFC01FFF801FFF001FFE001FF8001BC00018000018000018000018000019FC001F FF001E0FC01807E01803E00003F00003F00003F80003F83803F87C03F8FE03F8FE03F8FC 03F0FC03F07007E03007C01C1F800FFF0003F80015207D9F1C>I<000070000000007000 000000F800000000F800000000F800000001FC00000001FC00000003FE00000003FE0000 0003FE00000006FF000000067F0000000E7F8000000C3F8000000C3F800000183FC00000 181FC00000381FE00000300FE00000300FE00000600FF000006007F00000E007F80000FF FFF80000FFFFF800018001FC00018001FC00038001FE00030000FE00030000FE00060000 7F000600007F00FFE00FFFF8FFE00FFFF825227EA12A>65 DI<0003FE0080001FFF818000FF01E3 8001F8003F8003E0001F8007C0000F800F800007801F800007803F000003803F00000380 7F000001807E000001807E00000180FE00000000FE00000000FE00000000FE00000000FE 00000000FE00000000FE00000000FE000000007E000000007E000001807F000001803F00 0001803F000003801F800003000F8000030007C000060003F0000C0001F800380000FF00 F000001FFFC0000003FE000021227DA128>I70 D73 D76 D78 D<0007FC0000003FFF800000FC07E00003F0 01F80007E000FC000FC0007E001F80003F001F80003F003F00001F803F00001F807F0000 1FC07E00000FC07E00000FC0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000F E0FE00000FE0FE00000FE0FE00000FE0FE00000FE07E00000FC07F00001FC07F00001FC0 3F00001F803F80003F801F80003F000FC0007E0007E000FC0003F001F80000FC07E00000 3FFF80000007FC000023227DA12A>II<0007FC0000003FFF800000FC07E00003F001F80007 E000FC000FC0007E001F80003F001F80003F003F00001F803F00001F807F00001FC07E00 000FC07E00000FC0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE0000 0FE0FE00000FE0FE00000FE0FE00000FE07E00000FC07F00001FC07F00001FC03F00001F 803F81F03F801F83F83F000FC70C7E0007E606FC0003F607F80000FF07E000003FFF8000 0007FF80200000038020000003C020000003E0E0000003FFE0000001FFC0000001FFC000 0000FFC0000000FF800000007F000000001E00232C7DA12A>II<01FC0407FF8C1F03FC3C007C7C 003C78001C78001CF8000CF8000CFC000CFC0000FF0000FFE0007FFF007FFFC03FFFF01F FFF80FFFFC03FFFE003FFE0003FF00007F00003F00003FC0001FC0001FC0001FE0001EE0 001EF0003CFC003CFF00F8C7FFE080FF8018227DA11F>I<7FFFFFFF807FFFFFFF807E03 F80F807803F807807003F803806003F80180E003F801C0E003F801C0C003F800C0C003F8 00C0C003F800C0C003F800C00003F800000003F800000003F800000003F800000003F800 000003F800000003F800000003F800000003F800000003F800000003F800000003F80000 0003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F8000003FFFFF80003FFFFF80022227EA127>I<07FC001FFF803F07C03F03E03F01E0 3F01F01E01F00001F00001F0003FF003FDF01FC1F03F01F07E01F0FC01F0FC01F0FC01F0 FC01F07E02F07E0CF81FF87F07E03F18167E951B>97 DI<00FF8007FFE00F83F01F 03F03E03F07E03F07C01E07C0000FC0000FC0000FC0000FC0000FC0000FC00007C00007E 00007E00003E00301F00600FC0E007FF8000FE0014167E9519>I<0001FE000001FE0000 003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000 003E0000003E0001FC3E0007FFBE000F81FE001F007E003E003E007E003E007C003E00FC 003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E007C003E007C 003E003E007E001E00FE000F83BE0007FF3FC001FC3FC01A237EA21F>I<00FE0007FF80 0F87C01E01E03E01F07C00F07C00F8FC00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC0000 7C00007C00007E00003E00181F00300FC07003FFC000FF0015167E951A>I<003F8000FF C001E3E003C7E007C7E00F87E00F83C00F80000F80000F80000F80000F80000F8000FFFC 00FFFC000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80 000F80000F80000F80000F80000F80000F80000F80007FF8007FF80013237FA211>I<03 FC1E0FFF7F1F0F8F3E07CF3C03C07C03E07C03E07C03E07C03E07C03E03C03C03E07C01F 0F801FFF0013FC003000003000003800003FFF801FFFF00FFFF81FFFFC3800FC70003EF0 001EF0001EF0001EF0001E78003C7C007C3F01F80FFFE001FF0018217E951C>II< 1C003F007F007F007F003F001C000000000000000000000000000000FF00FF001F001F00 1F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE0 0B247EA310>I107 DIII<00 FE0007FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007EFC007EFC007EFC007EFC 007EFC007EFC007E7C007C7C007C3E00F81F01F00F83E007FFC000FE0017167E951C>I< FF0FE000FF3FF8001FF07C001F803E001F001F001F001F801F001F801F000FC01F000FC0 1F000FC01F000FC01F000FC01F000FC01F000FC01F000FC01F001F801F001F801F803F00 1FC03E001FE0FC001F3FF8001F0FC0001F0000001F0000001F0000001F0000001F000000 1F0000001F0000001F000000FFE00000FFE000001A207E951F>I<00FE030007FF87000F C1C7001F006F003F003F007E003F007E001F007C001F00FC001F00FC001F00FC001F00FC 001F00FC001F00FC001F00FC001F007E001F007E001F003E003F001F007F000FC1DF0007 FF9F0001FC1F0000001F0000001F0000001F0000001F0000001F0000001F0000001F0000 001F000000FFE00000FFE01B207E951E>II<0FF3003FFF00781F00600700E00300E003 00F00300FC00007FE0007FF8003FFE000FFF0001FF00000F80C00780C00380E00380E003 80F00700FC0E00EFFC00C7F00011167E9516>I<01800001800001800001800003800003 80000780000780000F80003F8000FFFF00FFFF000F80000F80000F80000F80000F80000F 80000F80000F80000F80000F80000F80000F81800F81800F81800F81800F81800F830007 C30003FE0000F80011207F9F16>IIII121 D<7FFFF07FFFF07C03E0 7007C0600FC0E01F80C01F00C03E00C07E0000FC0000F80001F00003F03007E03007C030 0F80701F80703F00603E00E07C03E0FFFFE0FFFFE014167E9519>I E /Fg 17 107 df0 D<70F8F8F87005057C8D0D>I<40 0004C0000C6000183000301800600C00C006018003030001860000CC0000780000300000 300000780000CC000186000303000601800C00C0180060300030600018C0000C40000416 187A9623>I<003FC00000C2300003020C00040202000802010010020080100200802002 004040020020400200204002002080020010800200108002001080020010FFFFFFF08002 001080020010800200108002001080020010400200204002002040020020200200401002 008010020080080201000402020003020C0000C23000003FC0001C207D9A23>8 D<03C00FF01FF83FFC7FFE7FFEFFFFFFFFFFFFFFFFFFFFFFFF7FFE7FFE3FFC1FF80FF003 C010127D9317>15 D<003FFFC000FFFFC003C00000070000000C00000018000000300000 00300000006000000060000000C0000000C0000000C0000000C0000000C0000000C00000 00C000000060000000600000003000000030000000180000000C0000000700000003C000 0000FFFFC0003FFFC0000000000000000000000000000000000000000000000000000000 007FFFFFC07FFFFFC01A247C9C23>18 D<003FF800FFF803C0000700000C000018000030 0000300000600000600000C00000C00000C00000FFFFF8FFFFF8C00000C00000C0000060 00006000003000003000001800000C000007000003C00000FFF8003FF8151C7C981E>50 D<00000C00000C0000180000180000300000300000600000600000C00000C00001800001 80000180000300000300000600000600000C00000C000018000018000030000030000060 0000600000C00000C0000180000180000300000300000600000600000600000C00000C00 00180000180000300000300000600000600000C00000400000162C7AA000>54 D<400001C0000360000660000660000630000C30000C30000C1800181800181800180FFF F00FFFF00C00300600600600600600600300C00300C001818001818001818000C30000C3 0000C300006600006600006600003C00003C00003C000018000018001821809F19>56 D<0000FC0007FE001C3E00201E00C01E01801C03801C07003C0600380E00381C00601C00 003C0000380000380000780000780000700000700000F00000F00000F00000F00000F000 00F00000F80018F800307800707C00C07E00803F83001FFC0007F0001721809F18>67 D<400002C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C000 06C00006C00006C00006C00006C00006C00006C00006C00006C0000660000C60000C3000 181C00700F01E003FF8000FE00171C7D9A1E>91 D95 D<000F0038006000E001C001C001C001C001C001C001C001C001C001C001C001 C001C001C001C0038007001E00F8001E000700038001C001C001C001C001C001C001C001 C001C001C001C001C001C001C001C000E000600038000F102D7DA117>102 DI<004000C0018001800180 0300030003000600060006000C000C00180018001800300030003000600060006000C000 C0006000600060003000300030001800180018000C000C00060006000600030003000300 01800180018000C000400A2E7CA112>III E /Fh 11 122 df<40E06020202040408003097D820A>59 D62 D<000100000300000700000780000B80001B80 0013800023800023800043800083800083C00101C003FFC00201C00401C00401C00801C0 1801E0FE07F815147F9319>65 D<07FFE000E03801C01801C01C01C01C01C01C03803803 80700380E003FFC00700E00700700700300700380E00700E00700E00E00E00E01C0380FF FE0016147F9319>I<07FFC000E07001C01801C01C01C01C01C01C0380380380700380C0 03FF000703C00701C00700E00700E00E01C00E01C00E01C00E01C21C01C4FF807817147F 9319>82 D<06070600000000384C4C8C98181830326262643808147F930C>105 D<0060007000600000000000000000038004C0046008C008C000C000C001800180018001 8003000300030003006600E600CC0078000C1A81930E>I<3E0006000C000C000C000C00 1800187018B819383230340038003E006300631063106310C320C1C00D147E9312>I<30 F8590C4E0C9C0C980C180C180C30183019303130316032601C100D7F8C15>110 D<0E3C13CE238E430C43000300030006000608C608E610CA2071C00F0D7F8C13>120 D<38184C184C188C3098301830183030603060306030E011C00EC000C00080E180E30046 003C000D137F8C11>I E /Fi 31 123 df<000040000040000080000080000080000080 000100000100000100000100000200000200001FC000E27003841806040C0C040E1C0406 380807300807700807700807E0100EE0100EE0100CE0101C6020387020303020601821C0 0E470003F80000400000400000800000800000800000800001000001000001000018297E 9F1B>30 D<00001000000010000000100000002000000020000000200000002000000040 00000040000000400000004000000080000F008180118083C0218083E021C101E041C100 E043810060838100400702004007020040070200400E0200800E0400800E0401000E0401 000E0402000E080400060808000708300001C8C000007F00000010000000100000001000 000020000000200000002000000020000000400000004000001B297E9F1E>32 D<70F8F8F87005057C840D>58 D<70F8FCFC74040404080810102040060E7C840D>I<00 0001C00000078000001E00000078000001E00000078000000E00000038000000F0000003 C000000F0000003C000000F0000000F00000003C0000000F00000003C0000000F0000000 380000000E0000000780000001E0000000780000001E0000000780000001C01A1A7C9723 >I<000100030003000600060006000C000C000C00180018001800300030003000600060 006000C000C000C00180018001800300030003000600060006000C000C000C0018001800 1800300030003000600060006000C000C000C000102D7DA117>II<000002000000 060000000E0000000E0000001E0000001F0000002F0000002F0000004F0000008F000000 8F0000010F0000010F0000020F0000040F0000040F0000080F8000080780001007800020 078000200780007FFF800040078000800780018007800100078002000780020007C00400 03C00C0003C01E0007C0FF807FFC1E207E9F22>65 D<00FFFFE0000F0078000F003C000F 001C000F001E001E001E001E001E001E001E001E001E003C003C003C003C003C0078003C 00F0007803C0007FFF80007803C0007801E000F000F000F000F000F000F000F0007001E0 00F001E000F001E000F001E000E003C001E003C003C003C0038003C00F0007801E00FFFF F0001F1F7E9E22>I<00FFFC00000F8000000F0000000F0000000F0000001E0000001E00 00001E0000001E0000003C0000003C0000003C0000003C00000078000000780000007800 000078000000F0000000F0000000F0000000F0004001E0008001E0008001E0018001E001 0003C0030003C0030003C0060003C00E0007803C00FFFFFC001A1F7E9E1F>76 D<00FF00001FF0000F00003F00000B80003E00000B80005E00000B80005E0000138000BC 00001380013C00001380013C00001380023C000023800278000023800478000023800878 000021C00878000041C010F0000041C020F0000041C020F0000041C040F0000081C041E0 000081C081E0000081C101E0000081C101E0000100E203C0000100E203C0000100E403C0 000100E803C0000200E80780000200F00780000200F00780000600E00780000F00C00F80 00FFE0C1FFF8002C1F7E9E2C>I<00FF803FF0000F800780000F800200000BC00200000B C002000013C004000011E004000011E004000011E004000020F008000020F008000020F8 08000020780800004078100000403C100000403C100000403C100000801E200000801E20 0000801E200000800F200001000F400001000F4000010007C000010007C0000200078000 0200038000020003800006000380000F00010000FFE0010000241F7E9E25>I<0001FC00 00070700001C01C0003000E000E0006001C000700380007007800038070000380E000038 1E0000381C0000383C0000383C00003878000078780000787800007878000078F00000F0 F00000F0F00000E0F00001E0F00001C0F00003C0700003807000070078000F0038001E00 38003C001C0070000E00E0000783800001FC00001D217E9F23>I<00FFFFC0000F007000 0F0038000F001C000F001E001E001E001E001E001E001E001E001E003C003C003C003C00 3C0078003C0070007800E000780380007FFE000078000000F0000000F0000000F0000000 F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C0000007 C00000FFFC00001F1F7E9E1D>I<00FFFF80000F01E0000F0070000F0038000F003C001E 003C001E003C001E003C001E003C003C0078003C0078003C00F0003C01E0007803800078 0F00007FF80000781C0000F00E0000F00F0000F0070000F0078001E00F0001E00F0001E0 0F0001E00F0003C01E0003C01E0203C01E0203C01E0407C00E04FFFC0718000003E01F20 7E9E23>82 D<0007E0800018118000300B000060070000C0070001C00300018002000380 02000380020003800200038000000380000003C0000003F8000003FF800001FFC00000FF E000003FF0000003F0000000F00000007000000070000000700020007000200070002000 60006000E0006000C0006001C00070018000E8030000C60E000081F8000019217D9F1C> I<007C01C207010E0F1E0F1C0E3C04780078007800F000F000F000F000F0007001700230 0418380FC010147E9314>99 D<00007C0000CE00019E00039E00030C0007000007000007 00000700000E00000E00000E0000FFF0000E00000E00001C00001C00001C00001C00001C 0000380000380000380000380000380000700000700000700000700000700000E00000E0 0000E00000E00000C00001C000318000798000F300006200003C000017297E9F16>102 D<00E001E001E000C000000000000000000000000000000E001300238043804380438087 00070007000E000E001C001C001C20384038403840388019000E000B1F7E9E10>105 D<01E0000FE00001C00001C00001C00001C0000380000380000380000380000700000700 000701E00706100E08700E10F00E20F00E40601C80001D00001E00001FC0003870003838 00383800381C20703840703840703840701880E01880600F0014207E9F18>107 D<03C01FC0038003800380038007000700070007000E000E000E000E001C001C001C001C 0038003800380038007000700070007100E200E200E200E200640038000A207E9F0E>I< 1E07802318C023A06043C0704380704380708700E00700E00700E00700E00E01C00E01C0 0E01C00E03821C03841C07041C07081C03083803101801E017147E931B>110 D<007C0001C3000301800E01C01E01C01C01E03C01E07801E07801E07801E0F003C0F003 C0F003C0F00780F00700700F00700E0030180018700007C00013147E9316>I<03C1E004 621804741C08781C08701E08701E10E01E00E01E00E01E00E01E01C03C01C03C01C03C01 C0380380780380700380E003C1C0072380071E000700000700000E00000E00000E00000E 00001C00001C0000FFC000171D819317>I<00F0400388C00705800E03801C03803C0380 380700780700780700780700F00E00F00E00F00E00F00E00F01C00F01C00703C00705C00 30B8000F380000380000380000700000700000700000700000E00000E0000FFE00121D7E 9314>I<1E1E0023210023C38043C7804387804383008700000700000700000700000E00 000E00000E00000E00001C00001C00001C00001C000038000018000011147E9315>I<00 7C018203010603060706060E00078007F803FC01FE001F00077007F006F006E004400820 301FC010147E9315>I<00C000E001C001C001C001C003800380FFF80380070007000700 07000E000E000E000E001C001C001C001C10382038203820384018800F000D1C7F9B10> I<03C1C00C62201034701038F02038F020386040700000700000700000700000E00000E0 0000E00000E02061C040F1C040F1C080E2C080446300383C0014147E931A>120 D<0F00601180702180E021C0E041C0E04380E08381C00701C00701C00701C00E03800E03 800E03800E03800E07000C07000C07000E0F00061E0003EE00000E00000E00001C007818 0078380070700060600021C0001F0000141D7E9316>I<01E02003F04007F8C00C1F8008 010000020000040000080000100000600000C0000100000200000400800801001003003F 060061FC0040F80080700013147E9315>I E /Fj 36 122 df 45 D<60F0F06004047D830B>I<0F80106020304038803CC01CE01C401C003C0038003800 70006000C001800100020004040804100430083FF87FF8FFF80E187E9713>50 D<0F8010E02070607870382038007800700070006000C00F8000E000700038003C003CE0 3CE03CC03C4038407030E00F800E187E9713>I<30183FF03FE03FC02000200020002000 200027C03860203000380018001C001C401CE01CE01C80184038403030E00F800E187E97 13>53 D<078018603030201860186018601870103C303E600F8007C019F030F86038401C C00CC00CC00CC00C6008201018600FC00E187E9713>56 D<07801860303070306018E018 E018E01CE01CE01C601C603C303C185C0F9C001C00180018003870307060604021801F00 0E187E9713>I<60F0F060000000000000000060F0F06004107D8F0B>I<007F00000180C0 00060030000800080010000400203E020020E1020041C081004380710083807080870070 808700708087007080870070808700708087007080838070804380708041C0F10020E131 00203E1E0010000000080000000600038001803E00007FE000191A7E991E>64 D<003F0201C0C603002E0E001E1C000E1C0006380006780002700002700002F00000F000 00F00000F00000F00000F000007000027000027800023800041C00041C00080E00080300 3001C0C0003F00171A7E991C>67 D69 DI78 D80 D82 D<0FC21836200E6006C006C002C002C002E0 0070007E003FE01FF807FC003E000E00070003800380038003C002C006E004D81887E010 1A7E9915>I<3F8070C070E020700070007007F01C7030707070E070E071E071E0F171FB 1E3C10107E8F13>97 DI<07F80C1C381C30087000E000E0 00E000E000E000E0007000300438080C1807E00E107F8F11>I<007E00000E00000E0000 0E00000E00000E00000E00000E00000E00000E0003CE000C3E00380E00300E00700E00E0 0E00E00E00E00E00E00E00E00E00E00E00600E00700E00381E001C2E0007CFC0121A7F99 15>I<07C01C3030187018600CE00CFFFCE000E000E000E0006000300438080C1807E00E 107F8F11>I<01F0031807380E100E000E000E000E000E000E00FFC00E000E000E000E00 0E000E000E000E000E000E000E000E000E000E007FE00D1A80990C>I<0FCE1873303070 38703870387038303018602FC02000600070003FF03FFC1FFE600FC003C003C003C00360 06381C07E010187F8F13>II<18003C003C001800000000 000000000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C 001C00FF80091A80990A>I108 DI< FCF8001D0C001E0E001E0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E00 1C0E001C0E001C0E00FF9FC012107F8F15>I<07E01C38300C700E6006E007E007E007E0 07E007E0076006700E381C1C3807E010107F8F13>II114 D<1F2060E04020C020C020F0007F003FC01FE000F080708030C030C020F0408F800C107F 8F0F>I<0400040004000C000C001C003C00FFC01C001C001C001C001C001C001C001C00 1C201C201C201C201C200E4003800B177F960F>II119 D121 D E /Fk 1 4 df<0C000C008C40EDC07F800C007F80EDC08C400C 000C000A0B7D8B10>3 D E /Fl 6 52 df5 D<00600000600000600000600000600000600000600000 6000006000006000FFFFF0FFFFF000600000600000600000600000600000600000600000 600000600000600014167E9119>43 D<0F0030C0606060604020C030C030C030C030C030 C030C030C030C03040206060606030C00F000C137E9211>48 D<0C001C00EC000C000C00 0C000C000C000C000C000C000C000C000C000C000C000C000C00FFC00A137D9211>I<1F 0060C06060F070F030603000700070006000C001C00180020004000810101020207FE0FF E00C137E9211>I<0FC030707038703870380038003000E00FC0007000380018001C601C F01CF018E03860701FC00E137F9211>I E /Fm 36 122 df<387CFEFEFE7C3807077C86 0F>46 D<00E00001E0000FE000FFE000F3E00003E00003E00003E00003E00003E00003E0 0003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E0 0003E00003E00003E00003E000FFFF80FFFF80111D7C9C1A>49 D<07F0001FFE00383F00 7C1F80FE0FC0FE0FC0FE0FE0FE07E07C07E03807E0000FE0000FC0000FC0001F80001F00 003E0000780000F00000E00001C0000380600700600E00601C00E01FFFC03FFFC07FFFC0 FFFFC0FFFFC0131D7D9C1A>I<01FC0007FF000E0F801E0FC03F07E03F07E03F07E03F07 E01E0FC0000FC0000F80001F0001FC0001FC00000F800007C00003E00003F00003F83803 F87C03F8FE03F8FE03F8FE03F0FC03F07807E03C0FC01FFF8003FC00151D7E9C1A>I<00 01C00003C00007C00007C0000FC0001FC0003BC00073C00063C000C3C00183C00383C007 03C00E03C00C03C01803C03803C07003C0E003C0FFFFFEFFFFFE0007C00007C00007C000 07C00007C00007C000FFFE00FFFE171D7F9C1A>I<3803803FFF803FFF003FFE003FFC00 3FF0003F800030000030000030000030000033F80037FE003C1F00380F801007C00007C0 0007E00007E07807E0FC07E0FC07E0FC07E0FC07C0780FC0600F80381F001FFC0007F000 131D7D9C1A>I<003F0001FFC007E0E00F81E01F03F01E03F03E03F07C03F07C01E07C00 00FC1000FCFF00FDFFC0FD03E0FE01F0FE01F0FC01F8FC01F8FC01F8FC01F87C01F87C01 F87C01F83C01F03E01F01E03E00F07C007FF8001FE00151D7E9C1A>I<6000007FFFF87F FFF87FFFF07FFFE07FFFC0E00180C00300C00300C00600000C0000180000380000380000 780000700000F00000F00001F00001F00001F00001F00003F00003F00003F00003F00003 F00003F00001E00000C000151E7D9D1A>I<387CFEFEFE7C38000000000000387CFEFEFE 7C3807147C930F>58 D<0000E000000000E000000001F000000001F000000001F0000000 03F800000003F800000006FC00000006FC0000000EFE0000000C7E0000000C7E00000018 3F000000183F000000303F800000301F800000701FC00000600FC00000600FC00000C007 E00000FFFFE00001FFFFF000018003F000018003F000030001F800030001F800060001FC 00060000FC000E0000FE00FFE00FFFE0FFE00FFFE0231F7E9E28>65 D<0007FC02003FFF0E00FE03DE03F000FE07E0003E0FC0001E1F80001E3F00000E3F0000 0E7F0000067E0000067E000006FE000000FE000000FE000000FE000000FE000000FE0000 00FE0000007E0000007E0000067F0000063F0000063F00000C1F80000C0FC0001807E000 3803F0007000FE01C0003FFF800007FC001F1F7D9E26>67 D69 DI< FFFF0FFFF0FFFF0FFFF007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007 E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007FF FFFE0007FFFFFE0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E000 7E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E0007E 00FFFF0FFFF0FFFF0FFFF0241F7E9E29>72 DI75 DI II80 D<03FC080FFF381E03F83800F8700078700038F00038F00018F00018F800 00FC00007FC0007FFE003FFF801FFFE00FFFF007FFF000FFF80007F80000FC00007C0000 3CC0003CC0003CC0003CE00038E00078F80070FE01E0E7FFC081FF00161F7D9E1D>83 D<7FFFFFFC7FFFFFFC7C07E07C7007E01C6007E00C6007E00CE007E00EC007E006C007E0 06C007E006C007E0060007E0000007E0000007E0000007E0000007E0000007E0000007E0 000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0 000007E00003FFFFC003FFFFC01F1E7E9D24>II88 D<07FC001FFF003F0F803F07C03F03E0 3F03E00C03E00003E0007FE007FBE01F03E03C03E07C03E0F803E0F803E0F803E0FC05E0 7E0DE03FF8FE0FE07E17147F9319>97 D<01FE0007FF801F0FC03E0FC03E0FC07C0FC07C 0300FC0000FC0000FC0000FC0000FC0000FC00007C00007E00003E00603F00C01F81C007 FF0001FC0013147E9317>99 D<01FE0007FF800F83C01E01E03E00F07C00F07C00F8FC00 F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00003E00181E00180F807007FFE000FF 8015147F9318>101 D<001F8000FFC001F3E003E7E003C7E007C7E007C3C007C00007C0 0007C00007C00007C000FFFC00FFFC0007C00007C00007C00007C00007C00007C00007C0 0007C00007C00007C00007C00007C00007C00007C00007C00007C0003FFC003FFC001320 7F9F10>I 104 D107 DI< FE0FE03F80FE1FF07FC01E70F9C3E01E407D01F01E807E01F01F807E01F01F007C01F01F 007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F00 7C01F01F007C01F01F007C01F01F007C01F0FFE3FF8FFEFFE3FF8FFE27147D932E>I<01 FF0007FFC01F83F03E00F83E00F87C007C7C007CFC007EFC007EFC007EFC007EFC007EFC 007E7C007C7C007C3E00F83E00F81F83F007FFC001FF0017147F931A>111 D114 D<01800180018003800380038007800F803F80FFFCFFFC0F800F800F800F800F800F800F 800F800F800F800F860F860F860F860F8607CC03F801F00F1D7F9C14>116 D121 D E /Fn 86 128 df5 D I<001F83E000F06E3001C078780380F8780300F030070070000700700007007000070070 00070070000700700007007000FFFFFF8007007000070070000700700007007000070070 000700700007007000070070000700700007007000070070000700700007007000070070 00070070000700700007007000070070007FE3FF001D20809F1B>11 D<003F0000E0C001C0C00381E00701E00701E00700000700000700000700000700000700 00FFFFE00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700 E00700E00700E00700E00700E00700E00700E00700E07FC3FE1720809F19>I<003FE000 E0E001C1E00381E00700E00700E00700E00700E00700E00700E00700E00700E0FFFFE007 00E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E07FE7FE1720809F19>I<001F81F80000F04F04 0001C07C06000380F80F000300F00F000700F00F00070070000007007000000700700000 070070000007007000000700700000FFFFFFFF0007007007000700700700070070070007 007007000700700700070070070007007007000700700700070070070007007007000700 700700070070070007007007000700700700070070070007007007000700700700070070 07007FE3FE3FF02420809F26>I<0E007E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E00FFC00A1480930C>16 D<07070F1C383060C00808 779F17>19 D<8010801080104020606030C03FC00F000C087B9F17>21 D<3E004100808080808080808041003E00090874A022>23 D<7038F87CFC7EFC7E743A04 02040204020804080410081008201040200F0E7E9F17>34 D<70F8FCFC74040404080810 102040060E7C9F0D>39 D<0020004000800100020006000C000C00180018003000300030 007000600060006000E000E000E000E000E000E000E000E000E000E000E000E000600060 0060007000300030003000180018000C000C000600020001000080004000200B2E7DA112 >I<800040002000100008000C00060006000300030001800180018001C000C000C000C0 00E000E000E000E000E000E000E000E000E000E000E000E000C000C000C001C001800180 018003000300060006000C00080010002000400080000B2E7DA112>I<00060000000600 000006000000060000000600000006000000060000000600000006000000060000000600 0000060000000600000006000000060000FFFFFFF0FFFFFFF00006000000060000000600 000006000000060000000600000006000000060000000600000006000000060000000600 000006000000060000000600001C207D9A23>43 D<70F8FCFC7404040408081010204006 0E7C840D>II<70F8F8F87005057C840D>I<03F0000E1C001C0E 00180600380700700380700380700380700380F003C0F003C0F003C0F003C0F003C0F003 C0F003C0F003C0F003C0F003C0F003C0F003C0F003C07003807003807003807807803807 001806001C0E000E1C0003F000121F7E9D17>48 D<018003800F80F38003800380038003 800380038003800380038003800380038003800380038003800380038003800380038003 800380038007C0FFFE0F1E7C9D17>I<03F0000C1C00100E00200700400780800780F007 C0F803C0F803C0F803C02007C00007C0000780000780000F00000E00001C000038000070 0000600000C0000180000300000600400C00401800401000803FFF807FFF80FFFF80121E 7E9D17>I<03F0000C1C00100E00200F00780F80780780780780380F80000F80000F0000 0F00000E00001C0000380003F000003C00000E00000F000007800007800007C02007C0F8 07C0F807C0F807C0F00780400780400F00200E001C3C0003F000121F7E9D17>I<000600 000600000E00000E00001E00002E00002E00004E00008E00008E00010E00020E00020E00 040E00080E00080E00100E00200E00200E00400E00C00E00FFFFF0000E00000E00000E00 000E00000E00000E00000E0000FFE0141E7F9D17>I<1803001FFE001FFC001FF8001FE0 0010000010000010000010000010000010000011F000161C00180E001007001007800003 800003800003C00003C00003C07003C0F003C0F003C0E00380400380400700200600100E 000C380003E000121F7E9D17>I<007C000182000701000E03800C07801C078038030038 0000780000700000700000F1F000F21C00F40600F80700F80380F80380F003C0F003C0F0 03C0F003C0F003C07003C07003C07003803803803807001807000C0E00061C0001F00012 1F7E9D17>I<4000007FFFC07FFF807FFF80400100800200800200800400000800000800 00100000200000200000400000400000C00000C00001C000018000038000038000038000 038000078000078000078000078000078000078000078000030000121F7D9D17>I<03F0 000C0C001006003003002001806001806001806001807001807803003E03003F06001FC8 000FF00003F80007FC000C7E00103F00300F806003804001C0C001C0C000C0C000C0C000 C0C000806001802001001002000C0C0003F000121F7E9D17>I<03F0000E18001C0C0038 0600380700700700700380F00380F00380F003C0F003C0F003C0F003C0F003C07007C070 07C03807C0180BC00E13C003E3C0000380000380000380000700300700780600780E0070 0C002018001070000FC000121F7E9D17>I<70F8F8F8700000000000000000000070F8F8 F87005147C930D>I<70F8F8F8700000000000000000000070F0F8F87808080810101020 2040051D7C930D>I<7FFFFFE0FFFFFFF000000000000000000000000000000000000000 00000000000000000000000000FFFFFFF07FFFFFE01C0C7D9023>61 D<0FC0307040384038E03CF03CF03C603C0038007000E000C00180018001000300020002 0002000200020002000000000000000000000007000F800F800F8007000E207D9F15>63 D<000100000003800000038000000380000007C0000007C0000007C0000009E0000009E0 000009E0000010F0000010F0000010F00000207800002078000020780000403C0000403C 0000403C0000801E0000801E0000FFFE0001000F0001000F0001000F0002000780020007 8002000780040003C00E0003C01F0007E0FFC03FFE1F207F9F22>65 DI<000FC040007030C001C009C0 038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000407C00004078000040 F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000 780000007C0000407C0000403C0000401C0000401E0000800E0000800700010003800200 01C0040000703800000FC0001A217D9F21>IIII<000FE0200078186000E004E0038002E0070001E0 0F0000E01E0000601E0000603C0000603C0000207C00002078000020F8000000F8000000 F8000000F8000000F8000000F8000000F8000000F8007FFCF80003E0780001E07C0001E0 3C0001E03C0001E01E0001E01E0001E00F0001E0070001E0038002E000E0046000781820 000FE0001E217D9F24>III<0FFFC0007C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00203C00F83C00F83C 00F83C00F0380040780040700030E0000F800012207E9E17>IIIII<001F800000F0F00001C0380007801E000F000F000E0007001E00 07803C0003C03C0003C07C0003E0780001E0780001E0F80001F0F80001F0F80001F0F800 01F0F80001F0F80001F0F80001F0F80001F0F80001F0780001E07C0003E07C0003E03C00 03C03C0003C01E0007800E0007000F000F0007801E0001C0380000F0F000001F80001C21 7D9F23>II82 D<07E0800C198010078030038060018060 0180E00180E00080E00080E00080F00000F000007800007F00003FF0001FFC000FFE0003 FF00001F800007800003C00003C00001C08001C08001C08001C08001C0C00180C00380E0 0300F00600CE0C0081F80012217D9F19>I<7FFFFFE0780F01E0600F0060400F0020400F 0020C00F0030800F0010800F0010800F0010800F0010000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000001F800007FFFE001C1F 7E9E21>IIII89 D91 D<080410082010201040204020804080408040 B85CFC7EFC7E7C3E381C0F0E7B9F17>II<1FE000 303000781800781C00300E00000E00000E00000E0000FE00078E001E0E00380E00780E00 F00E10F00E10F00E10F01E10781E103867200F83C014147E9317>97 D<0E0000FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00 000E3E000EC3800F01C00F00E00E00E00E00700E00700E00780E00780E00780E00780E00 780E00780E00700E00700E00E00F00E00D01C00CC300083E0015207F9F19>I<03F80E0C 1C1E381E380C70007000F000F000F000F000F000F00070007000380138011C020E0C03F0 10147E9314>I<000380003F800003800003800003800003800003800003800003800003 8000038000038003E380061B801C0780380380380380700380700380F00380F00380F003 80F00380F00380F003807003807003803803803807801C07800E1B8003E3F815207E9F19 >I<03F0000E1C001C0E00380700380700700700700380F00380F00380FFFF80F00000F0 0000F000007000007000003800801800800C010007060001F80011147F9314>I<007C00 C6018F038F07060700070007000700070007000700FFF007000700070007000700070007 00070007000700070007000700070007000700070007007FF01020809F0E>I<0000E003 E3300E3C301C1C30380E00780F00780F00780F00780F00780F00380E001C1C001E380033 E0002000002000003000003000003FFE001FFF800FFFC03001E0600070C00030C00030C0 0030C000306000603000C01C038003FC00141F7F9417>I<0E0000FE00000E00000E0000 0E00000E00000E00000E00000E00000E00000E00000E00000E3E000E43000E81800F01C0 0F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C0FFE7FC16207F9F19>I<1C001E003E001E001C0000000000000000 00000000000E007E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E00FFC00A1F809E0C>I<00E001F001F001F000E000000000000000000000 0000007007F000F000700070007000700070007000700070007000700070007000700070 00700070007000700070007000706070F060F0C061803F000C28829E0E>I<0E0000FE00 000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0FF00E03 C00E03000E02000E04000E08000E10000E30000E70000EF8000F38000E1C000E1E000E0E 000E07000E07800E03800E03C00E03E0FFCFF815207F9F18>I<0E00FE000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E00FFE00B20809F0C>I<0E1F01F000FE618618000E 81C81C000F00F00E000F00F00E000E00E00E000E00E00E000E00E00E000E00E00E000E00 E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E0 0E000E00E00E000E00E00E00FFE7FE7FE023147F9326>I<0E3E00FE43000E81800F01C0 0F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C0FFE7FC16147F9319>I<01F800070E001C03803801C03801C07000 E07000E0F000F0F000F0F000F0F000F0F000F0F000F07000E07000E03801C03801C01C03 80070E0001F80014147F9317>I<0E3E00FEC3800F01C00F00E00E00E00E00F00E00700E 00780E00780E00780E00780E00780E00780E00700E00F00E00E00F01E00F01C00EC3000E 3E000E00000E00000E00000E00000E00000E00000E00000E0000FFE000151D7F9319>I< 03E0800619801C05803C0780380380780380700380F00380F00380F00380F00380F00380 F003807003807803803803803807801C0B800E138003E380000380000380000380000380 000380000380000380000380003FF8151D7E9318>I<0E78FE8C0F1E0F1E0F0C0E000E00 0E000E000E000E000E000E000E000E000E000E000E000E00FFE00F147F9312>I<1F9030 704030C010C010C010E00078007F803FE00FF00070803880188018C018C018E030D0608F 800D147E9312>I<020002000200060006000E000E003E00FFF80E000E000E000E000E00 0E000E000E000E000E000E000E080E080E080E080E080610031001E00D1C7F9B12>I<0E 01C0FE1FC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E03C00603C0030DC001F1FC16147F9319>III<7FC3FC0F01E00701C007018003810001C20000E40000EC00007800003800003C 00007C00004E000087000107000303800201C00601E01E01E0FF07FE1714809318>II<3FFF380E200E201C40384078407000 E001E001C00380078007010E011E011C0338027006700EFFFE10147F9314>II<30307878F87C787830300E057C9E17>127 D E /Fo 41 123 df<0001FF0000001FFFC000007F81E00000FC01E00001F807F00003F807F00007 F007F00007F007F00007F007F00007F007F00007F001C00007F000000007F000000007F0 00000007F03FF800FFFFFFF800FFFFFFF800FFFFFFF80007F003F80007F003F80007F003 F80007F003F80007F003F80007F003F80007F003F80007F003F80007F003F80007F003F8 0007F003F80007F003F80007F003F80007F003F80007F003F80007F003F80007F003F800 07F003F80007F003F80007F003F80007F003F8007FFF3FFF807FFF3FFF807FFF3FFF8021 2A7FA925>12 D<000E00001E00007E0007FE00FFFE00FFFE00F8FE0000FE0000FE0000FE 0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 0000FE0000FE007FFFFE7FFFFE7FFFFE17277BA622>49 D<00FF800007FFF0000FFFFC00 1E03FE003800FF807C003F80FE003FC0FF001FC0FF001FE0FF000FE0FF000FE07E000FE0 3C001FE000001FE000001FC000001FC000003F8000003F0000007E000000FC000000F800 0001F0000003E00000078000000F0000001E0000003C00E0007000E000E000E001C001C0 038001C0060001C00FFFFFC01FFFFFC03FFFFFC07FFFFFC0FFFFFF80FFFFFF80FFFFFF80 1B277DA622>I<007F800003FFF00007FFFC000F80FE001F007F003F807F003F803F803F 803F803F803F801F803F801F003F8000007F0000007F0000007E000000FC000001F80000 07F00000FFC00000FFC0000001F80000007E0000003F0000003F8000001FC000001FC000 001FE000001FE03C001FE07E001FE0FF001FE0FF001FE0FF001FC0FF003FC0FE003F807C 007F003F00FE001FFFFC0007FFF00000FF80001B277DA622>I<00000E0000001E000000 3E0000007E000000FE000000FE000001FE000003FE0000077E00000E7E00000E7E00001C 7E0000387E0000707E0000E07E0000E07E0001C07E0003807E0007007E000E007E000E00 7E001C007E0038007E0070007E00E0007E00FFFFFFF8FFFFFFF8FFFFFFF80000FE000000 FE000000FE000000FE000000FE000000FE000000FE000000FE00007FFFF8007FFFF8007F FFF81D277EA622>I<180003001F801F001FFFFE001FFFFC001FFFF8001FFFF0001FFFC0 001FFF00001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C7FC0 001DFFF8001F80FC001E003F0008003F0000001F8000001FC000001FC000001FE000001F E018001FE07C001FE0FE001FE0FE001FE0FE001FE0FE001FC0FC001FC078003F8078003F 803C007F001F01FE000FFFFC0003FFF00000FF80001B277DA622>I<0007F800003FFE00 00FFFF0001FC078003F00FC007C01FC00F801FC01F801FC01F001FC03F000F803F000000 7E0000007E0000007E000000FE020000FE1FF000FE3FFC00FE603E00FE801F00FF801F80 FF000FC0FF000FC0FE000FE0FE000FE0FE000FE0FE000FE07E000FE07E000FE07E000FE0 7E000FE03E000FE03F000FC01F000FC01F001F800F801F0007E07E0003FFFC0001FFF800 003FC0001B277DA622>I<380000003E0000003FFFFFF03FFFFFF03FFFFFF07FFFFFE07F FFFFC07FFFFF807FFFFF0070000E0070000E0070001C00E0003800E0007000E000E00000 01E0000001C000000380000007800000070000000F0000001F0000001E0000003E000000 3E0000007E0000007C0000007C000000FC000000FC000000FC000000FC000001FC000001 FC000001FC000001FC000001FC000001FC000001FC000000F80000007000001C297CA822 >I<00000780000000000780000000000FC0000000000FC0000000000FC0000000001FE0 000000001FE0000000003FF0000000003FF0000000003FF00000000077F80000000077F8 00000000F7FC00000000E3FC00000000E3FC00000001C1FE00000001C1FE00000003C1FF 0000000380FF0000000380FF00000007007F80000007007F8000000F007FC000000E003F C000000E003FC000001C001FE000001C001FE000003FFFFFF000003FFFFFF000003FFFFF F00000700007F80000700007F80000F00007FC0000E00003FC0000E00003FC0001C00001 FE0001C00001FE0003C00001FF00FFFE003FFFFCFFFE003FFFFCFFFE003FFFFC2E297EA8 33>65 D<00007FE0030007FFFC07001FFFFF0F007FF00F9F00FF0001FF01FC0000FF03F8 00007F07F000003F0FE000001F1FC000001F1FC000000F3F8000000F3F800000077F8000 00077F800000077F00000000FF00000000FF00000000FF00000000FF00000000FF000000 00FF00000000FF00000000FF00000000FF000000007F000000007F800000007F80000007 3F800000073F800000071FC00000071FC000000E0FE000000E07F000001C03F800003C01 FC00007800FF0001F0007FF007C0001FFFFF800007FFFE0000007FF00028297CA831>67 DI70 D<00007FE003000007FFFC0700001FFFFF0F00007FF00F9F0000FF0001FF0001FC0000FF 0003F800007F0007F000003F000FE000001F001FC000001F001FC000000F003F8000000F 003F80000007007F80000007007F80000007007F0000000000FF0000000000FF00000000 00FF0000000000FF0000000000FF0000000000FF0000000000FF0000000000FF00000000 00FF0000FFFFF87F0000FFFFF87F8000FFFFF87F800000FF003F800000FF003F800000FF 001FC00000FF001FC00000FF000FE00000FF0007F00000FF0003F80000FF0001FC0000FF 0000FF0001FF00007FF007FF00001FFFFF9F000007FFFE0F0000007FF003002D297CA835 >I73 D78 D<0000FFC00000000FFF FC0000003F807F000000FE001FC00001F80007E00003F00003F00007E00001F8000FE000 01FC001FC00000FE001FC00000FE003F8000007F003F8000007F007F8000007F807F0000 003F807F0000003F807F0000003F80FF0000003FC0FF0000003FC0FF0000003FC0FF0000 003FC0FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0FF0000 003FC07F0000003F807F8000007F807F8000007F803F8000007F003F8000007F001FC000 00FE001FC00000FE000FE00001FC0007F00003F80003F80007F00001FC000FE00000FE00 1FC000003FC0FF0000000FFFFC00000000FFC000002A297CA833>II<0000FFC00000000FFFFC0000 003FC0FF000000FE001FC00001FC000FE00003F00003F00007F00003F8000FE00001FC00 1FC00000FE001FC00000FE003F8000007F003F8000007F007F8000007F807F8000007F80 7F0000003F807F0000003F80FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0 FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0 7F0000003F807F8000007F807F8000007F803F8000007F003F8000007F001FC00000FE00 1FC03E00FE000FE07F81FC0007E0C1C1F80003F180E3F00001F980E7E00000FF807FC000 003FC07F0000000FFFFC00000000FFF800C00000007C00C00000003E00C00000003E01C0 0000003F83C00000001FFFC00000001FFF800000001FFF800000000FFF0000000007FF00 00000003FE0000000001FC0000000000F8002A357CA833>II85 D87 D<03FF80000FFFF0001F01FC003F80FE003F80 7F003F803F003F803F801F003F8000003F8000003F8000003F8000003F80003FFF8001FC 3F800FE03F801F803F803F003F807E003F80FC003F80FC003F80FC003F80FC003F80FC00 5F807E00DF803F839FFC1FFE0FFC03F803FC1E1B7E9A21>97 D<003FF00001FFFC0003F0 3E000FC07F001F807F003F007F003F007F007F003E007E0000007E000000FE000000FE00 0000FE000000FE000000FE000000FE000000FE0000007E0000007E0000007F0000003F00 03803F8003801F8007000FE00E0003F83C0001FFF800003FC000191B7E9A1E>99 D<00007FF000007FF000007FF0000007F0000007F0000007F0000007F0000007F0000007 F0000007F0000007F0000007F0000007F0000007F0000007F0003F87F001FFF7F007F03F F00FC00FF01F8007F03F0007F03F0007F07E0007F07E0007F07E0007F0FE0007F0FE0007 F0FE0007F0FE0007F0FE0007F0FE0007F0FE0007F0FE0007F07E0007F07E0007F03F0007 F03F0007F01F800FF00FC01FF007E07FFF01FFE7FF007F87FF202A7EA925>I<003FC000 01FFF00003E07C000F803E001F801F001F001F003F000F807E000F807E000FC07E000FC0 FE0007C0FE0007C0FFFFFFC0FFFFFFC0FE000000FE000000FE0000007E0000007E000000 7F0000003F0001C01F0001C00F80038007C0070003F01E0000FFFC00003FE0001A1B7E9A 1F>I<0007F8003FFC007E3E01FC7F03F87F03F07F07F07F07F03E07F00007F00007F000 07F00007F00007F00007F000FFFFC0FFFFC0FFFFC007F00007F00007F00007F00007F000 07F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F000 07F00007F00007F00007F0007FFF807FFF807FFF80182A7EA915>I<007F80F001FFE3F8 07C0FE1C0F807C7C1F003E7C1F003E103F003F003F003F003F003F003F003F003F003F00 3F003F001F003E001F003E000F807C0007C0F80005FFE0000C7F8000180000001C000000 1C0000001E0000001FFFF8001FFFFF000FFFFFC007FFFFE003FFFFF00FFFFFF03E0007F0 7C0001F8F80000F8F80000F8F80000F8F80000F87C0001F07C0001F03F0007E00FC01F80 07FFFF00007FF0001E287E9A22>II<07000FC01FE03FE03FE03FE01FE00FC007000000000000000000 000000000000FFE0FFE0FFE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0 0FE00FE00FE00FE00FE00FE00FE00FE00FE0FFFEFFFEFFFE0F2B7EAA12>I107 DII< FFC07E00FFC1FF80FFC30FC00FC40FE00FC807E00FD807F00FD007F00FD007F00FE007F0 0FE007F00FE007F00FE007F00FE007F00FE007F00FE007F00FE007F00FE007F00FE007F0 0FE007F00FE007F00FE007F00FE007F00FE007F00FE007F0FFFE3FFFFFFE3FFFFFFE3FFF 201B7D9A25>I<003FE00001FFFC0003F07E000FC01F801F800FC03F0007E03F0007E07E 0003F07E0003F07E0003F0FE0003F8FE0003F8FE0003F8FE0003F8FE0003F8FE0003F8FE 0003F8FE0003F87E0003F07E0003F03F0007E03F0007E01F800FC00FC01F8007F07F0001 FFFC00003FE0001D1B7E9A22>I114 D<03FE300FFFF03E03F07800F07000F0F00070F00070F80070FE0000FFE0007FFF007FFF C03FFFE01FFFF007FFF800FFF80007FC0000FCE0007CE0003CF0003CF00038F80038FC00 70FF01E0E7FFC0C1FF00161B7E9A1B>I<00700000700000700000700000F00000F00000 F00001F00003F00003F00007F0001FFFE0FFFFE0FFFFE007F00007F00007F00007F00007 F00007F00007F00007F00007F00007F00007F00007F00007F00007F07007F07007F07007 F07007F07007F07007F07003F0E001F8C000FFC0003F0014267FA51A>I III<3FFFFF 3FFFFF3F00FE3C01FE3803FC7803F87807F0700FF0700FE0701FC0003FC0003F80007F00 00FF0000FE0001FC0703FC0703F80707F0070FF00F0FE00F1FC00E3FC01E7F803E7F00FE FFFFFEFFFFFE181B7E9A1E>122 D E /Fp 29 123 df<60F0F06004047C830C>46 D73 D<07E0801C1980300580700380600180E00180E00080E00080E00080F00000F800007C00 007FC0003FF8001FFE0007FF0000FF80000F800007C00003C00001C08001C08001C08001 C0C00180C00180E00300D00200CC0C0083F800121E7E9C17>83 D87 D<1FC000307000783800781C00301C00001C00001C0001FC000F1C00381C00701C00601C 00E01C40E01C40E01C40603C40304E801F870012127E9115>97 DI<07E00C301878307870306000E000E000E000E000E000E0 0060007004300418080C3007C00E127E9112>I<003F0000070000070000070000070000 070000070000070000070000070000070003E7000C1700180F00300700700700600700E0 0700E00700E00700E00700E00700E00700600700700700300700180F000C370007C7E013 1D7E9C17>I<03E00C301818300C700E6006E006FFFEE000E000E000E000600070023002 18040C1803E00F127F9112>I<00F8018C071E061E0E0C0E000E000E000E000E000E00FF E00E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E007FE00F 1D809C0D>I<00038003C4C00C38C01C3880181800381C00381C00381C00381C00181800 1C38000C300013C0001000003000001800001FF8001FFF001FFF803003806001C0C000C0 C000C0C000C06001803003001C0E0007F800121C7F9215>II<18003C003C0018000000000000000000000000000000FC001C 001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C00FF80091D7F 9C0C>I107 DIII<03F0000E1C00180600300300700380600180E001C0E001C0E001C0E0 01C0E001C0E001C06001807003803003001806000E1C0003F00012127F9115>II<03C1000C3300180B00300F00700700700700E00700E00700E007 00E00700E00700E00700600700700700300F00180F000C370007C7000007000007000007 00000700000700000700000700003FE0131A7E9116>II<1F9030704030 C010C010E010F8007F803FE00FF000F880388018C018C018E010D0608FC00D127F9110> I<04000400040004000C000C001C003C00FFE01C001C001C001C001C001C001C001C001C 001C101C101C101C101C100C100E2003C00C1A7F9910>IIII<7F8FF00F03800F030007020003840001C80001D80000F000007000 00780000F800009C00010E00020E000607000403801E07C0FF0FF81512809116>II<7FFC70386038407040F040E041C003C0038007000F040E041C 043C0C380870087038FFF80E127F9112>I E /Fq 7 117 df<00038000000380000007C0 000007C0000007C000000FE000000FE000001FF000001BF000001BF0000031F8000031F8 000061FC000060FC0000E0FE0000C07E0000C07E0001803F0001FFFF0003FFFF8003001F 8003001F8006000FC006000FC00E000FE00C0007E0FFC07FFEFFC07FFE1F1C7E9B24>65 D<0FF8001C1E003E0F803E07803E07C01C07C00007C0007FC007E7C01F07C03C07C07C07 C0F807C0F807C0F807C0780BC03E13F80FE1F815127F9117>97 DI<03FC000E0E001C1F003C1F00781F00780E00F80000F800 00F80000F80000F80000F800007800007801803C01801C03000E0E0003F80011127E9115 >I114 D<1FD830786018E018E018F000FF807FE07FF01FF807FC007CC01CC01CE01CE018F830CF C00E127E9113>I<0300030003000300070007000F000F003FFCFFFC1F001F001F001F00 1F001F001F001F001F001F0C1F0C1F0C1F0C0F08079803F00E1A7F9913>I E /Fr 1 4 df<020002000200C218F2783AE00F800F803AE0F278C2180200020002000D 0E7E8E12>3 D E /Fs 35 122 df<70F8FCFC7404040404080810102040060F7C840E> 44 D<01F000071C000C06001803003803803803807001C07001C07001C07001C0F001E0 F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0F001E0 F001E07001C07001C07001C07803C03803803803801C07000C0600071C0001F00013227E A018>48 D<008003800F80F3800380038003800380038003800380038003800380038003 8003800380038003800380038003800380038003800380038003800380038007C0FFFE0F 217CA018>I<03F8000C1E001007002007804007C07807C07803C07807C03807C0000780 000780000700000F00000E0000380003F000001C00000F000007800007800003C00003C0 0003E02003E07003E0F803E0F803E0F003C04003C0400780200780100F000C1C0003F000 13227EA018>51 D<1000801E07001FFF001FFE001FF80013E00010000010000010000010 000010000010000010F800130E001407001803801003800001C00001C00001E00001E000 01E00001E07001E0F001E0F001E0E001C08001C04003C04003802007001006000C1C0003 F00013227EA018>53 D<007E0001C1000300800601C00E03C01C03C01801803800003800 00780000700000700000F0F800F30C00F40600F40300F80380F801C0F001C0F001E0F001 E0F001E0F001E0F001E07001E07001E07001E03801C03801C01803801C03000C0600070C 0001F00013227EA018>I<4000006000007FFFE07FFFC07FFFC0400080C0010080010080 020080020000040000080000080000100000300000200000600000600000600000E00000 C00000C00001C00001C00001C00001C00003C00003C00003C00003C00003C00003C00003 C00003C00001800013237DA118>I<01F800060E000803001001802001802000C06000C0 6000C06000C07000C07801803E01003F02001FC4000FF80003F80003FC00067F00083F80 100F803007C06001C06000E0C000E0C00060C00060C00060C000606000406000C0300080 1803000E0E0003F00013227EA018>I<0007E0100038183000E0063001C00170038000F0 070000F00E0000701E0000701C0000303C0000303C0000307C0000107800001078000010 F8000000F8000000F8000000F8000000F8000000F8000000F8000000F800000078000000 780000107C0000103C0000103C0000101C0000201E0000200E0000400700004003800080 01C0010000E0020000381C000007E0001C247DA223>67 DIII73 D76 D<03F0200C0C601802603001 E07000E0600060E00060E00060E00020E00020E00020F00000F000007800007F00003FF0 001FFE000FFF0003FF80003FC00007E00001E00000F00000F00000708000708000708000 70800070C00060C00060E000C0F000C0C80180C6070081FC0014247DA21B>83 D85 D<0FE0001838003C0C003C0E0018070000070000070000070000FF0007C7001E 07003C0700780700700700F00708F00708F00708F00F087817083C23900FC1E015157E94 18>97 D<01FE000703000C07801C0780380300780000700000F00000F00000F00000F000 00F00000F00000F000007000007800403800401C00800C010007060001F80012157E9416 >99 D<01FC000707000C03801C01C03801C07801E07000E0F000E0FFFFE0F00000F00000 F00000F00000F000007000007800203800201C00400E008007030000FC0013157F9416> 101 D<003C00C6018F038F030F070007000700070007000700070007000700FFF8070007 00070007000700070007000700070007000700070007000700070007000700070007807F F8102380A20F>I<00007001F198071E180E0E181C07001C07003C07803C07803C07803C 07801C07001C07000E0E000F1C0019F0001000001000001800001800001FFE000FFFC00F FFE03800F0600030400018C00018C00018C000186000306000303800E00E038003FE0015 217F9518>I<0E0000FE00001E00000E00000E00000E00000E00000E00000E00000E0000 0E00000E00000E00000E00000E1F800E60C00E80E00F00700F00700E00700E00700E0070 0E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070 FFE7FF18237FA21B>I<1C001E003E001E001C0000000000000000000000000000000000 0E00FE001E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E00FFC00A227FA10E>I<0E00FE001E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E00FFE00B237FA20E>108 D<0E1FC07F00FE60E183801E807201C00F 003C00E00F003C00E00E003800E00E003800E00E003800E00E003800E00E003800E00E00 3800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E0038 00E00E003800E00E003800E0FFE3FF8FFE27157F942A>I<0E1F80FE60C01E80E00F0070 0F00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070 0E00700E00700E00700E0070FFE7FF18157F941B>I<01FC000707000C01801800C03800 E0700070700070F00078F00078F00078F00078F00078F00078F000787000707800F03800 E01C01C00E038007070001FC0015157F9418>I<0E1F00FE61C00E80600F00700E00380E 003C0E001C0E001E0E001E0E001E0E001E0E001E0E001E0E001E0E003C0E003C0E00380F 00700E80E00E41C00E3F000E00000E00000E00000E00000E00000E00000E00000E00000E 0000FFE000171F7F941B>I<0E3CFE461E8F0F0F0F060F000E000E000E000E000E000E00 0E000E000E000E000E000E000E000F00FFF010157F9413>114 D<0F8830786018C018C0 08C008E008F0007F803FE00FF001F8003C801C800C800CC00CC008E018D0308FC00E157E 9413>I<02000200020002000600060006000E001E003E00FFF80E000E000E000E000E00 0E000E000E000E000E000E000E040E040E040E040E040E040708030801F00E1F7F9E13> I<0E0070FE07F01E00F00E00700E00700E00700E00700E00700E00700E00700E00700E00 700E00700E00700E00700E00700E00F00E00F006017003827800FC7F18157F941B>III121 D E /Ft 19 123 df<00003FE0010001FFF8030007F01E03001F80 0307003E000087007800004F00F000002F01E000001F03C000000F078000000F0F800000 070F000000071F000000031E000000033E000000033C000000017C000000017C00000001 7C000000017800000000F800000000F800000000F800000000F800000000F800000000F8 00000000F800000000F800000000F800000000F800000000F80000000078000000007C00 0000007C000000017C000000013C000000013E000000011E000000011F000000020F0000 00020F80000006078000000403C000000801E000000800F00000100078000020003E0000 C0001F8003800007F00F000001FFFC0000003FE00028337CB130>67 D82 D<7FFFFFFFFFE07FFFFFFFFFE07E000F 8007E078000F8001E070000F8000E060000F80006040000F80002040000F800020C0000F 800030C0000F80003080000F80001080000F80001080000F80001080000F80001080000F 80001080000F80001000000F80000000000F80000000000F80000000000F80000000000F 80000000000F80000000000F80000000000F80000000000F80000000000F80000000000F 80000000000F80000000000F80000000000F80000000000F80000000000F80000000000F 80000000000F80000000000F80000000000F80000000000F80000000000F80000000000F 80000000000F80000000000F80000000000F80000000000F80000000000F80000000000F 80000000000F80000000001FC00000000FFFFF8000000FFFFF80002C317EB030>84 D<00FE00000303C0000C00E00010007000100038003C003C003E001C003E001E003E001E 0008001E0000001E0000001E0000001E00000FFE0000FC1E0003E01E000F801E001F001E 003E001E003C001E007C001E00F8001E04F8001E04F8001E04F8003E04F8003E0478003E 047C005E043E008F080F0307F003FC03E01E1F7D9E21>97 D<003F800000E0E000038038 0007003C000E001E001E001E001C000F003C000F007C000F0078000F8078000780F80007 80F8000780FFFFFF80F8000000F8000000F8000000F8000000F8000000F8000000780000 007C0000003C0000003C0000801E0000800E0001000F0002000780020001C00C0000F030 00001FC000191F7E9E1D>101 D<0007E0001C1000383800707C00E07C01E07C01C03803 C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C000FF FFC0FFFFC003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003 C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003 C00003C00003C00003C00007E0007FFF007FFF0016327FB114>I<0780000000FF800000 00FF800000000F8000000007800000000780000000078000000007800000000780000000 078000000007800000000780000000078000000007800000000780000000078000000007 80000000078000000007800000000780FE00000783078000078C03C000079001E00007A0 01E00007A000F00007C000F00007C000F000078000F000078000F000078000F000078000 F000078000F000078000F000078000F000078000F000078000F000078000F000078000F0 00078000F000078000F000078000F000078000F000078000F000078000F000078000F000 078000F000078000F0000FC001F800FFFC1FFF80FFFC1FFF8021327EB125>104 D<07000F801F801F800F8007000000000000000000000000000000000000000000000007 80FF80FF800F800780078007800780078007800780078007800780078007800780078007 800780078007800780078007800780078007800FC0FFF8FFF80D307EAF12>I<0780FF80 FF800F800780078007800780078007800780078007800780078007800780078007800780 078007800780078007800780078007800780078007800780078007800780078007800780 0780078007800780078007800780078007800FC0FFFCFFFC0E327EB112>108 D<0780FE001FC000FF83078060F000FF8C03C18078000F9001E2003C0007A001E4003C00 07A000F4001E0007C000F8001E0007C000F8001E00078000F0001E00078000F0001E0007 8000F0001E00078000F0001E00078000F0001E00078000F0001E00078000F0001E000780 00F0001E00078000F0001E00078000F0001E00078000F0001E00078000F0001E00078000 F0001E00078000F0001E00078000F0001E00078000F0001E00078000F0001E00078000F0 001E00078000F0001E00078000F0001E000FC001F8003F00FFFC1FFF83FFF0FFFC1FFF83 FFF0341F7E9E38>I<0780FE0000FF83078000FF8C03C0000F9001E00007A001E00007A0 00F00007C000F00007C000F000078000F000078000F000078000F000078000F000078000 F000078000F000078000F000078000F000078000F000078000F000078000F000078000F0 00078000F000078000F000078000F000078000F000078000F000078000F000078000F000 078000F0000FC001F800FFFC1FFF80FFFC1FFF80211F7E9E25>I<001FC00000F0780001 C01C00070007000F0007801E0003C01C0001C03C0001E03C0001E0780000F0780000F078 0000F0F80000F8F80000F8F80000F8F80000F8F80000F8F80000F8F80000F8F80000F878 0000F07C0001F03C0001E03C0001E01E0003C01E0003C00F00078007800F0001C01C0000 F07800001FC0001D1F7E9E21>I<0781FC00FF860700FF8803C00F9001E007A000F007C0 0078078000780780003C0780003C0780003E0780001E0780001F0780001F0780001F0780 001F0780001F0780001F0780001F0780001F0780001F0780003E0780003E0780003C0780 007C0780007807C000F007A000F007A001E00798038007860F000781F800078000000780 000007800000078000000780000007800000078000000780000007800000078000000780 00000FC00000FFFC0000FFFC0000202D7E9E25>I<0783E0FF8C18FF907C0F907C07A07C 07C03807C00007C00007C000078000078000078000078000078000078000078000078000 0780000780000780000780000780000780000780000780000780000780000780000FC000 FFFE00FFFE00161F7E9E19>114 D<00400000400000400000400000400000C00000C000 00C00001C00001C00003C00007C0000FC0001FFFE0FFFFE003C00003C00003C00003C000 03C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C000 03C01003C01003C01003C01003C01003C01003C01003C01001C02001E02000E0400078C0 001F00142C7FAB19>116 D118 D120 D I<3FFFFF3E001E38001E30003C2000782000786000F04001E04001E04003C04007800007 80000F00001E00001E00003C0000780000780000F00101E00101E00103C0010780010780 030F00021E00021E00063C000678000E78007EFFFFFE181F7E9E1D>I E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 267 381 a Ft(The)21 b(Role)g(of)h(Relativization)f(in)g (Complexit)n(y)g(Theory)816 508 y Fs(Lance)c(F)l(ortno)o(w)1133 490 y Fr(\003)745 566 y Fs(Univ)o(ersit)o(y)c(of)k(Chicago)619 624 y(Departmen)o(t)e(of)h(Computer)g(Science)743 682 y(1100)i(East)f(58th)g(Street)734 740 y(Chicago,)g(Illinois)e(60637)884 958 y Fq(Abstract)176 1034 y Fp(Sev)o(eral)k(recen)o(t)i (nonrelativizing)d(results)i(in)f(the)h(area)f(of)g(in)o(teractiv)o(e)h (pro)q(ofs)f(ha)o(v)o(e)g(caused)h(man)o(y)114 1084 y(p)q(eople)10 b(to)h(review)g(the)g(imp)q(ortance)e(of)h(relativization.)15 b(In)c(this)f(pap)q(er)h(w)o(e)g(tak)o(e)f(a)h(lo)q(ok)e(at)h(ho)o(w)g (complexit)o(y)114 1134 y(theorists)16 b(use)h(and)e(misuse)g(oracle)h (results.)25 b(W)m(e)15 b(pa)o(y)g(sp)q(ecial)h(atten)o(tion)g(to)f (the)i(new)f(in)o(teractiv)o(e)g(pro)q(of)114 1184 y(systems)g(and)g (program)f(c)o(hec)o(king)i(results)h(and)e(try)h(to)f(understand)h(wh) o(y)g(they)g(do)f(not)g(relativize.)26 b(W)m(e)114 1233 y(giv)o(e)13 b(some)g(new)h(results)h(that)f(ma)o(y)e(help)i(us)g(to)g (understand)h(these)h(questions)e(b)q(etter.)0 1377 y Fo(1)67 b(In)n(tro)r(duction)0 1478 y Fn(The)20 b(recen)o(t)g(result)g Fm(IP)g Fn(=)g Fm(PSP)l(A)o(CE)e Fn([LFKN92,)h(Sha92])g(surprised)i (the)e(theoretical)i(computer)e(science)0 1535 y(comm)o(unit)o(y)h(in)h (more)e(w)o(a)o(ys)g(than)h(one.)34 b(A)20 b(few)f(y)o(ears)h(earlier,) h(F)l(ortno)o(w)e(and)h(Sipser)h([FS88)o(])e(created)h(an)0 1591 y(oracle)e(relativ)o(e)h(to)e(whic)o(h)i(co-)p Fm(NP)e Fn(did)i(not)f(ha)o(v)o(e)f(in)o(teractiv)o(e)h(pro)q(ofs.)28 b(The)18 b Fm(IP)f Fn(=)g Fm(PSP)l(A)o(CE)f Fn(result)j(w)o(as)0 1648 y(honestly)d(a)f(nonrelativizing)i(theorem.)71 1704 y(Sev)o(eral)j(questions)h(immediately)h(p)q(opp)q(ed)f(up:)30 b(Wh)o(y)20 b(didn't)h(this)f(result)h(relativize?)37 b(What)19 b(sp)q(eci\014c)0 1760 y(tec)o(hniques)d(w)o(ere)f(used)h (that)e(a)o(v)o(oided)i(relativization?)22 b(Ho)o(w)14 b(can)h(w)o(e)g(use)h(these)f(tec)o(hniques)h(to)f(pro)o(v)o(e)f(other) 0 1817 y(nonrelativizing)j(facts?)71 1873 y(Also)f(m)o(uc)o(h)h(older)g (questions)g(resurfaced:)23 b(What)16 b(exactly)h(to)f(oracle)h (results)g(mean?)25 b(What)16 b(should)h(w)o(e)0 1930 y(infer,)f(if)f(an)o(ything,)g(from)g(a)g(relativization?)71 1986 y(Suc)o(h)j(questions)g(gained)h(ev)o(en)f(more)g(imp)q(ortance)g (when)h(w)o(e)e(disco)o(v)o(ered)i(the)f(amazing)g(p)q(o)o(w)o(er)f(of) g(m)o(ul-)0 2043 y(tiple)h(pro)o(v)o(er)e(in)o(teractiv)o(e)i(pro)q(of) e(systems)h([BFL91)o(],)g(transparen)o(t)f(pro)q(ofs)g([BFLS91])h(and)g (probabilistically)0 2099 y(c)o(hec)o(k)m(able)g(pro)q(ofs)e([AS92)o(,) g(ALM)587 2083 y Fl(+)614 2099 y Fn(92].)71 2156 y(W)l(e)i(ma)o(y)g (not)g(\014nd)i(satisfactory)d(answ)o(ers)h(to)g(these)h(questions)g (in)g(the)g(near)f(future.)27 b(Ho)o(w)o(ev)o(er,)17 b(in)i(this)0 2212 y(pap)q(er)g(w)o(e)f(will)h(giv)o(e)g(some)f(in)o (tuition)h(and)g(some)f(theorems)g(ab)q(out)g(oracles)g(that)f(ma)o(y)h (help)h(shed)g(ligh)o(t)g(on)0 2269 y(some)c(of)g(these)g(issues.)71 2325 y(In)g(Section)g(3,)f(w)o(e)g(will)i(see)f(that)e(relativization)j (is)f(an)g(extremely)f(p)q(o)o(w)o(erful)h(to)q(ol)g(in)g(helping)h (complexit)o(y)0 2381 y(theorists)f(direct)h(their)g(researc)o(h.)71 2438 y(In)c(Section)g(4,)f(w)o(e)g(will)i(lo)q(ok)f(at)f(early)h (results)f(of)g(pro)o(v)m(able)h(statemen)o(ts)f(with)g(negativ)o(e)h (relativization.)20 b(W)l(e)0 2494 y(will)c(lo)q(ok)f(at)f(these)h(v)m (arious)h(examples)f(and)g(argue)f(that)g(they)h(all)h(lac)o(k)f(a)f (prop)q(er)h(oracle)g(access)g(mec)o(hanism.)71 2551 y(In)f(section)g(5,)f(w)o(e)g(tak)o(e)g(a)g(close)h(lo)q(ok)g(at)f(the) g(new)h(unrelativizing)i(results)e(for)f(in)o(teractiv)o(e)h(pro)q(of)f (systems.)0 2607 y(W)l(e)f(pro)o(v)o(e)g(some)g(new)h(results)g(that)f (ma)o(y)f(help)j(us)e(understand)h(these)g(issues)g(b)q(etter.)19 b(W)l(e)13 b(also)f(argue)g(that)g(the)p 0 2647 780 2 v 51 2674 a Fk(\003)69 2690 y Fj(Email:)19 b(fortno)o(w@cs.uc)o (hicago.edu.)f(P)o(artially)e(supp)q(orted)e(b)o(y)g(NSF)f(gran)o(t)g (CCR)g(92-53582.)964 2828 y Fn(1)p eop %%Page: 2 2 2 1 bop 0 199 a Fn(new)18 b(in)o(teractiv)o(e)g(pro)q(of)f(system)g (tec)o(hniques)h(do)g(not)f(relativize)i(b)q(ecause)f(they)g(tak)o(e)f (adv)m(an)o(tage)f(of)i(certain)0 256 y(algebraic)e(prop)q(erties)g(of) f(complexit)o(y)h(classes.)71 312 y(In)i(section)h(5.1)e(w)o(e)h(lo)q (ok)g(at)f(what)h(happ)q(ens)h(when)f(w)o(e)g(add)g(an)g(oracle)h(to)e (probabilistically)k(c)o(hec)o(k)m(able)0 369 y(pro)q(ofs)c(\()p Fm(PCP)o Fn(\).)27 b(Arora,)17 b(Lund,)i(Mot)o(w)o(ani,)e(Sudan)i(and)e (Szegedy)i([ALM)1334 352 y Fl(+)1361 369 y Fn(92])e(sho)o(w)g(that)g (ev)o(ery)h(language)0 425 y(in)e Fm(NP)e Fn(has)h(a)g Fm(PCP)f Fn(using)i(only)f(a)g(logarithmic)g(n)o(um)o(b)q(er)h(of)e (random)h(coin)g(tosses)g(and)g(a)g(constan)o(t)f(n)o(um)o(b)q(er)0 482 y(of)20 b(queries)i(to)d(the)i(pro)q(of.)36 b(W)l(e)20 b(sho)o(w)g(that)g(in)h(a)g(relativized)h(w)o(orld,)f(for)f(all)i Fi(k)q Fn(,)f(suc)o(h)g(a)f(result)h(do)q(es)g(not)0 538 y(hold)16 b(ev)o(en)g(if)g(w)o(e)f(allo)o(w)g(the)g(v)o(eri\014er)h (to)f(use)h(a)f(p)q(olynomial)i(n)o(um)o(b)q(er)e(of)g(random)g(bits)h (and)f Fi(n)1657 521 y Fh(k)1693 538 y Fn(pro)q(of)g(queries)0 594 y(\(Theorem)g(5.2\).)71 651 y(Although)e(Heller)i([Hel81])d(has)h (created)g(an)g(oracle)h Fi(A)f Fn(relativ)o(e)g(to)g(whic)o(h)g Fm(NP)1441 630 y Fh(A)1481 651 y Fn(=)g Fm(EXP)1638 630 y Fh(A)1665 651 y Fn(,)g(w)o(e)g(sho)o(w)g(that)0 707 y Fm(PCP)109 686 y Fh(A)136 707 y Fn(\(log)8 b Fi(n;)g Fn(1\))13 b(=)h Fm(EXP)481 686 y Fh(A)524 707 y Fn(w)o(ould)i(imply)i (that)d Fm(P)f Fg(6)p Fn(=)g Fm(NP)i Fn(\(Theorem)f(5.4\).)21 b(Th)o(us)16 b(\014nding)h(suc)o(h)g(an)f(oracle)0 764 y(w)o(ould)g(b)q(e)f(as)g(hard)g(as)g(settling)h(the)f Fm(P)e Fn(=)g Fm(NP)i Fn(question.)71 820 y(Arora,)g(Impagliazzo)j(and) e(V)l(azirani)i([AIV92)o(])e(argue)h(that)e(the)i(\\lo)q(cal-c)o(hec)o (k)m(abilit)o(y")i(prop)q(ert)o(y)d(of)g(com-)0 877 y(plexit)o(y)j (classes)g(is)g(a)f(ma)s(jor)f(reason)h(that)g(the)g(results)h(on)f(in) o(teractiv)o(e)h(pro)q(ofs)f(do)g(not)g(relativize.)31 b(In)19 b(Sec-)0 933 y(tion)c(5.2,)e(w)o(e)h(giv)o(e)h(negativ)o(e)f (evidence)i(for)e(this)h(thesis)g(b)o(y)f(sho)o(wing)g(that)g(under)h (a)f(reasonable)h(access)g(mec)o(h-)0 990 y(anism,)g(lo)q(cal)i(c)o (hec)o(k)m(abilit)o(y)g(do)q(es)e(in)h(fact)f(relativize.)71 1046 y(W)l(e)i(giv)o(e)h(supp)q(ort)g(instead)g(to)f(the)h(thesis)g (that)f(it)g(is)h(the)g(algebraic)h(prop)q(erties)f(of)f(complexit)o(y) h(classes)0 1103 y(that)d(do)h(not)f(relativize.)24 b(In)16 b(Section)h(5.3,)e(w)o(e)g(giv)o(e)i(evidence)g(for)f(this)g(prop)q (osition)h(b)o(y)e(sho)o(wing)h(that)f Fm(IP)f Fn(=)0 1159 y Fm(PSP)l(A)o(CE)f Fn(holds)j(relativ)o(e)g(to)f(algebraic)h (extensions)g(of)e(arbitrarily)i(complicated)h(languages.)71 1215 y(Finally)l(,)g(in)g(Section)g(6,)f(w)o(e)g(giv)o(e)g(a)g(brief)g (arguemen)o(t)g(against)g(infering)h(an)o(y)f(information)g(from)f (random)0 1272 y(oracle)22 b(results.)39 b(W)l(e)22 b(argue)f(that)g(w) o(e)g(should)i(only)f(use)g(random)f(oracles)g(as)h(a)f(to)q(ol)g(to)g (com)o(bine)i(oracle)0 1328 y(constructions.)i(Ho)o(w)o(ev)o(er,)16 b(w)o(e)h(b)q(eliev)o(e)i(that)d(generic)i(oracles)f(are)g(a)f(m)o(uc)o (h)h(stronger)f(and)i(sharp)q(er)f(to)q(ol)g(for)0 1385 y(this)f(purp)q(ose.)0 1507 y Ff(Ca)n(v)n(eats)0 1592 y Fn(This)21 b(pap)q(er)h(con)o(tains)f(sev)o(eral)g(opinions)h(on)e (the)h(use)g(and)g(misuse)h(of)e(relativization)j(results.)37 b(W)l(e)21 b(m)o(ust)0 1649 y(caution)16 b(the)f(reader)g(that)g(other) f(complexit)o(y)i(theorists)f(ma)o(y)g(ha)o(v)o(e)g(di\013ering)h (opinions)g(on)f(these)h(matters.)71 1705 y(In)21 b(this)g(pap)q(er,)i (w)o(e)e(ha)o(v)o(e)f(tried)i(to)e(giv)o(e)h(sev)o(eral)g(examples)h (to)e(illustrate)i(v)m(arious)f(p)q(oin)o(ts.)38 b(Ho)o(w)o(ev)o(er)0 1762 y(this)18 b(pap)q(er)g(is)g Fe(not)g Fn(mean)o(t)f(to)g(b)q(e)h(a) f(surv)o(ey)h(pap)q(er.)27 b(Man)o(y)17 b(imp)q(ortan)o(t)h(w)o(orks)e (in)j(the)e(area)g(ha)o(v)o(e)h(not)f(b)q(een)0 1818 y(men)o(tioned)f(due)g(to)e(lac)o(k)i(of)f(space.)0 1961 y Fo(2)67 b(Notation)22 b(and)h(De\014nitions)0 2063 y Fn(Most)12 b(of)h(the)h(notation)f(and)h(de\014nitions)h(follo)o(w)f (from)e(the)i(standard)f(textb)q(o)q(oks)g(on)h(the)f(\014eld)i([HU79)o (,)e(GJ79].)71 2119 y(W)l(e)i(use)i Fg(\010)f Fn(to)f(represen)o(t)h (the)f(join)i(of)e(t)o(w)o(o)g(sets)g Fi(A)h Fn(and)g Fi(B)r Fn(,)g(i.e.,)g Fi(A)10 b Fg(\010)h Fi(B)16 b Fn(=)e(\()p Fg(f)p Fn(0)p Fg(g)c(\002)h Fi(A)p Fn(\))f Fg([)h Fn(\()p Fg(f)p Fn(1)p Fg(g)e(\002)i Fi(B)r Fn(\).)22 b(W)l(e)0 2176 y(use)16 b Fm(FP)e Fn(to)h(represen)o(t)g(the)g(p)q (olynomial-time)j(computable)e(functions.)71 2232 y(It)i(is)g(a)g (misnomer)g(to)f(relativize)j(a)d(complexit)o(y)i(class)f Fg(C)s Fn(.)28 b(Instead)18 b(supp)q(ose)h(w)o(e)f(tak)o(e)f(an)h(en)o (umeration)0 2289 y(of)i(mac)o(hines)h(for)e Fg(C)k Fn(and)d(giv)o(e)h (them)f(some)g(access)g(mec)o(hanism)h(to)e(an)h(oracle)h(set)f Fi(A)p Fn(.)35 b(W)l(e)20 b(then)g(sa)o(y)g(the)0 2345 y(relativized)c(class)f Fg(C)353 2329 y Fh(A)394 2345 y Fn(consists)g(of)e(the)i(languages)f(recognized)i(b)o(y)e(the)h (acceptance)g(criteria)g(for)e Fg(C)k Fn(applied)g(to)0 2402 y(the)e(mac)o(hines)h(using)g(the)f(oracle)h Fi(A)p Fn(.)71 2458 y(Of)g(course)g(this)g(de\014nition)i(ma)o(y)d(dep)q(end)i (greatly)f(on)g(the)g(sp)q(eci\014c)i(en)o(umeration)e(of)f(the)h(mac)o (hines)h(of)e Fg(C)0 2514 y Fn(as)h(w)o(ell)h(as)f(the)g(oracle)h (access)f(mec)o(hanism.)23 b(The)17 b(usual)g(access)f(mec)o(hanism)h (consists)f(of)g(a)g(separate)g(oracle)0 2571 y(tap)q(e)f(that)f(the)h (T)l(uring)h(mac)o(hine)g(can)f(write)g(do)o(wn)f(queries)i(and)f (learn)h(the)f(answ)o(ers.)k(Ho)o(w)o(ev)o(er,)14 b(as)g(w)o(e)h(shall) 0 2627 y(see)g(in)i(Sections)f(4)e(and)i(5.2,)e(suc)o(h)h(mo)q(dels)h (ma)o(y)f(unduly)h(handicap)h(the)e(mac)o(hines.)964 2828 y(2)p eop %%Page: 3 3 3 2 bop 0 199 a Ff(2.1)56 b(Relativizing)16 b(F)-5 b(orm)n(ulae)0 285 y Fn(It)15 b(will)i(b)q(e)f(useful)g(to)f(ha)o(v)o(e)g(relativized) i Fm(NP)o Fn(-complete)f(and)g Fm(PSP)l(A)o(CE)n Fn(-complete)g(sets.) 71 342 y(Let)f(a)g Fe(r)n(elativize)n(d)g(3CNF)h(formula)f Fn(b)q(e)h(a)f(CNF)g(form)o(ula)g(with)g(clauses)h(of)f(the)g(form:)669 439 y Fi(x)695 446 y Fh(i)p Fl(1)735 439 y Fg(_)10 b Fi(x)801 446 y Fh(i)p Fl(2)842 439 y Fg(_)g Fi(x)908 446 y Fh(i)p Fl(3)949 439 y Fg(_)g Fi(A)p Fn(\()p Fi(x)1067 446 y Fh(j)r Fl(1)1101 439 y Fi(;)e(:)g(:)g(:)d(;)j(x)1229 446 y Fh(j)r(k)1264 439 y Fn(\))0 537 y(where)16 b Fi(A)p Fn(\()p Fi(x)210 544 y Fh(j)r Fl(1)244 537 y Fi(;)8 b(:)g(:)g(:)t(;)g (x)371 544 y Fh(j)r(k)406 537 y Fn(\))16 b(is)g(true)f(if)h Fi(x)650 544 y Fh(j)r Fl(1)692 537 y Fi(:)8 b(:)g(:)d(x)778 544 y Fh(j)r(k)830 537 y Fn(is)16 b(in)g Fi(A)p Fn(.)21 b(An)o(y)15 b(of)h(the)f(v)m(ariables)i(or)e(the)h Fi(A)p Fn(\()p Fi(x)1627 544 y Fh(j)r Fl(1)1660 537 y Fi(;)8 b(:)g(:)g(:)d(;)j(x)1788 544 y Fh(j)r(k)1823 537 y Fn(\))15 b(term)0 593 y(ma)o(y)f(b)q(e)i(negated.)0 694 y Fm(Lemm)o(a)e(2.1)23 b Fe(L)n(et)13 b Fi(\036)378 701 y Fh(A)420 694 y Fe(b)n(e)h(a)g(r)n (elativize)n(d)f(3CNF)h(formula)h(over)f(an)h(or)n(acle)f Fi(A)p Fe(.)20 b(L)n(et)13 b Fi( )1490 701 y Fh(A)1531 694 y Fe(b)n(e)h(a)h(close)n(d)e(r)n(elativize)n(d)0 750 y(3CNF)i(formula)i(with)g(arbitr)n(ary)g(\014rst-or)n(der)f (existential)g(and)g(universal)g(quanti\014ers)f(over)i(the)f (variables.)54 840 y(1.)23 b(Determining)15 b(whether)i Fi(\036)573 847 y Fh(A)617 840 y Fe(is)f(satis\014able)e(is)i Fm(NP)999 820 y Fh(A)1026 840 y Fe(-c)n(omplete.)54 933 y(2.)23 b(Determining)15 b(the)i(truth)g(value)f(of)h Fi( )767 940 y Fh(A)810 933 y Fe(is)f Fm(PSP)l(A)o(CE)1065 912 y Fh(A)1092 933 y Fe(-c)n(omplete.)0 1023 y(F)m(urthermor)n(e)h (the)f(c)n(ompleteness)f(r)n(e)n(ductions)g(do)i(not)f(ne)n(e)n(d)f(ac) n(c)n(ess)g(to)i(the)f(or)n(acle.)0 1124 y Fn(Goldsmith)d(and)g(Joseph) g([GJ86)o(])f(pro)o(v)o(e)f(the)i(\014rst)f(part)g(of)g(the)g(lemma.)19 b(An)13 b(easy)f(mo)q(di\014cation)i(of)d(their)i(pro)q(of)0 1180 y(giv)o(es)i(us)h(the)f(second)h(part)e(as)h(w)o(ell.)0 1323 y Fo(3)67 b(Uses)21 b(of)g(Oracle)i(Results)0 1424 y Fn(In)g(this)h(section,)h(w)o(e)d(will)j(discuss)e(some)g(legitimate) h(uses)f(of)f(relativization)i(results.)43 b(As)23 b(w)o(e)g(will)h (see,)0 1481 y(complexit)o(y)16 b(theorists)f(ha)o(v)o(e)g(used)h (relativization)g(as)f(a)g(p)q(o)o(w)o(erful)g(to)q(ol)h(in)g(studying) f(complexit)o(y)i(theory)l(.)71 1537 y(In)g(Section)g(3.1)e(w)o(e)i (will)h(see)e(ho)o(w)g(theorists)h(use)f(oracles)h(to)f(disco)o(v)o(er) g(what)g(tec)o(hniques)i(will)g(not)e(lik)o(ely)0 1593 y(w)o(ork)d(to)g(solv)o(e)g(certain)h(problems.)20 b(In)14 b(Section)h(3.2,)d(w)o(e)i(will)h(see)f(ho)o(w)f(relativization)i(allo) o(ws)f(us)f(to)g(push)h(at)f(a)0 1650 y(problem)j(in)f(t)o(w)o(o)f (di\013eren)o(t)h(directions.)21 b(In)15 b(Section)h(3.3,)d(w)o(e)i (will)h(argue)f(that)f(that)g(lac)o(k)h(of)f(nonrelativizable)0 1706 y(tec)o(hniques)k(ha)o(v)o(e)f(caused)h(theorists)f(to)g(lo)q(ok)g (at)g(new)g(directions)h(of)f(researc)o(h.)26 b(Finally)l(,)19 b(in)f(Section)g(3.4)e(w)o(e)0 1763 y(will)j(see)e(ho)o(w)g(old)g (relativization)i(results)e(help)i(us)e(to)g(recognize)g(new)h(tec)o (hniques)g(that)f(can)g(b)q(e)h(applied)h(to)0 1819 y(other)c (problems.)71 1876 y(Of)i(course,)h(theorists)f(m)o(ust)f(execute)i (extreme)g(care)f(in)h(ho)o(w)f(one)g(should)i(in)o(terpret)e(oracle)h (results.)26 b(In)0 1932 y(Sections)19 b(4)f(and)h(5,)g(w)o(e)f(lo)q (ok)h(at)e(some)i(computational)f(mo)q(dels)i(where)e(oracle)h(results) g(ma)o(y)f(not)g(ha)o(v)o(e)g(the)0 1989 y(exp)q(ected)e(in)o (terpretation.)0 2110 y Ff(3.1)56 b(Limiting)15 b(tec)n(hniques)0 2195 y Fn(Supp)q(ose)e(w)o(e)f(can)g(sho)o(w)g(for)f(some)h(statemen)o (t)f Fi(S)j Fn(that)e(there)g(exists)g(an)g(oracle)h Fi(A)f Fn(suc)o(h)g(that)g Fi(S)i Fn(fails)f(relativ)o(e)g(to)0 2252 y Fi(A)g Fn(in)h(some)f(oracle)g(mo)q(del.)20 b(Then)13 b(an)o(y)g(pro)q(of)g(that)f Fi(S)k Fn(hold)d(m)o(ust)g(not)f (relativize)j(in)f(that)e(mo)q(del)i(or)f(otherwise)0 2308 y(that)f(statemen)o(t)g(w)o(ould)i(also)f(hold)h(relativ)o(e)g(to) e Fi(A)p Fn(.)19 b(If)14 b(w)o(e)f(can)g(also)g(\014nd)h(an)f(oracle)g (relativ)o(e)h(to)f(whic)o(h)h Fi(S)h Fn(holds)0 2365 y(then)h(no)f(relativizable)i(tec)o(hnique)g(can)e(decide)i(the)e (truth)g(of)g Fi(S)s Fn(.)71 2421 y(Bak)o(er,)k(Gill)i(and)f(Solo)o(v)m (a)o(y)g([BGS75)o(])f(noted)g(this)h(in)h(their)f(original)g(oracle)g (pap)q(er)g(where)g(they)g(giv)o(e)f(a)0 2478 y(relativized)e(w)o(orld) d(where)h Fm(P)d Fn(=)h Fm(NP)h Fn(and)h(another)f(where)h Fm(P)e Fg(6)p Fn(=)g Fm(NP)o Fn(.)20 b(They)15 b(also)f(noted)h(that)f (essen)o(tially)i(all)0 2534 y(the)g(kno)o(wn)g(complexit)o(y)g(tec)o (hniques)i(at)d(that)g(time)h(relativize.)24 b(They)16 b(concluded)i(that)d(curren)o(t)h(tec)o(hniques)0 2591 y(w)o(ould)g(not)e(solv)o(e)i(the)f Fm(P)d Fn(=)h Fm(NP)i Fn(question.)71 2647 y(In)d(the)h(nearly)g(t)o(w)o(o)e(decades)i(since) g(the)g(Bak)o(er-Gill-Solo)o(v)m(a)o(y)g(pap)q(er,)g(there)g(ha)o(v)o (e)e(b)q(een)j(literally)g(h)o(undreds)0 2704 y(of)e(results)h(in)h (complexit)o(y)f(theory)l(.)19 b(With)13 b(the)g(exception)g(of)g(some) f(results)h(in)h(in)o(teractiv)o(e)f(pro)q(of)f(systems)g(\(see)964 2828 y(3)p eop %%Page: 4 4 4 3 bop 0 199 a Fn(Sections)18 b(3.4)d(and)i(5\))f(all)i(of)e(the)h (results)g(in)g(complexit)o(y)h(theory)e(ha)o(v)o(e)g(relativized.)27 b(These)17 b(include)i(sev)o(eral)0 256 y(imp)q(ortan)o(t)c(results)g (suc)o(h)h(as)f Fm(PH)d Fg(\022)h Fm(P)691 235 y Fd(#P)770 256 y Fn([T)l(o)q(d91)o(])i(and)g Fm(PP)g Fn(is)g(closed)h(under)g(in)o (tersection)g([BRS91].)71 312 y(The)j(tec)o(hniques)h(for)e(in)o (teractiv)o(e)h(pro)q(ofs)f(ha)o(v)o(e)h(not)f(y)o(et)h(pro)o(v)o(en)f (fruitful)i(to)o(w)o(ards)d(pro)o(ving)i Fe(any)f Fn(other)0 369 y(theorems)f(ab)q(out)h(complexit)o(y)g(theory)l(.)27 b(Th)o(us)18 b(it)f(really)i(do)q(es)f(app)q(ear)g(that)e(w)o(e)i (still)h(need)f(to)f(dev)o(elop)i(new)0 425 y(tec)o(hniques)d(to)f (settle)g(the)h(h)o(undreds)g(of)f(complexit)o(y)h(statemen)o(ts)e (that)g(relativize)j(b)q(oth)e(w)o(a)o(ys.)71 482 y(Early)c(on)h(some)f (p)q(eople)j(sp)q(eculated)f(that)e(p)q(erhaps)h(the)g(Bak)o (er-Gill-Solo)o(v)m(a)o(y)h(result)f(indicated)i(that)d(these)0 538 y(questions)16 b(ab)q(out)g(complexit)o(y)g(theory)f(ma)o(y)g(fall) i(outside)f(the)g(axioms)f(of)g(set)h(theory)f(\(see)h([Har78)n(],)f(c) o(hapter)0 594 y(7\).)31 b(Ho)o(w)o(ev)o(er)19 b(most)f(researc)o(hers) h(no)g(longer)h(subscrib)q(e)h(to)d(this)i(viewp)q(oin)o(t)g(an)o (ymore)f(b)q(ecause)h(of)f(lac)o(k)g(of)0 651 y(evidence)e(and)e(some)g (of)g(the)g(examples)h(in)g(Sections)g(4)f(and)h(5.)0 773 y Ff(3.2)56 b(Tw)n(o)19 b(directions)0 858 y Fn(Often)f(in)g (complexit)o(y)g(theory)l(,)f(one)h(has)f(a)g(complexit)o(y)h(statemen) o(t)e Fi(S)k Fn(where)e(one)f(can)g(easily)i(sho)o(w)e(a)f(rela-)0 915 y(tivized)g(w)o(orld)f(where)g Fi(S)i Fn(holds)f(but)e(it)h(is)h (op)q(en)f(whether)g(there)g(exists)g(a)f(relativizable)j(pro)q(of)d (of)h Fi(S)s Fn(.)k(In)c(order)0 971 y(to)g(tac)o(kle)g(this)h (problem,)f(man)o(y)g(complexit)o(y)h(theorists)f(lo)q(ok)g(at)g (trying)g(to)g(pro)o(v)o(e)f(t)o(w)o(o)g(opp)q(osite)i(directions:)68 1065 y Fg(\017)23 b Fn(T)l(rying)15 b(to)g(pro)o(v)o(e)f Fi(S)s Fn(,)h(or)68 1159 y Fg(\017)23 b Fn(Creating)15 b(a)g(relativized)i(w)o(orld)e(where)g Fi(S)j Fn(fails.)0 1253 y(Often)g(b)o(y)g(w)o(orking)g(on)g(a)f(problem)i(in)f(t)o(w)o(o)f (directions,)j(one)e(can)g(often)f(push)i(a)e(failure)i(of)f(a)g(pro)q (of)f(in)i(one)0 1309 y(direction)e(in)o(to)e(a)g(pro)q(of)f(of)h(the)g (other)g(direction.)71 1366 y(Goldw)o(asser)f(and)i(Sipser)g([GS89)o(]) f(used)h(this)f(metho)q(d)h(in)g(their)g(pro)q(of)e(of)h(the)h(equiv)m (alence)i(of)c(public)k(and)0 1422 y(priv)m(ate)f(coins)f(in)h(in)o (teractiv)o(e)f(pro)q(of)f(systems.)22 b(Initially)l(,)c(Goldw)o(asser) d(and)h(Sipser)h(tried)f(to)g(pro)o(v)o(e)f(that)g(the)0 1479 y(priv)m(ate)20 b(coin)h(in)o(teractiv)o(e)f(pro)q(of)f(hierarc)o (h)o(y)h(w)o(as)e(in\014nite)k(relativ)o(e)e(to)f(some)g(oracle.)33 b(The)20 b(failure)h(of)e(that)0 1535 y(attempt)14 b(led)i(to)f(the)g (equiv)m(alence)j(result)e(that)e(implied)k(the)d(collapse)i(of)d(the)i (priv)m(ate)g(coin)g(hierarc)o(h)o(y)l(.)0 1657 y Ff(3.3)56 b(New)18 b(directions)0 1743 y Fn(Relativization)h(results)e(often)g (lead)h(researc)o(hers)f(in)g(new)h(directions)g(that)e(pro)o(v)o(e)h (extremely)g(fruitful.)26 b(This)0 1799 y(ma)o(y)14 b(happ)q(en)j(in)f (t)o(w)o(o)e(di\013eren)o(t)h(w)o(a)o(ys:)56 1893 y(1.)22 b(A)e(sp)q(eci\014c)h(problem)g(ma)o(y)e(ha)o(v)o(e)h(large)g(amoun)o (t)f(of)g(time)i(dev)o(oted)f(to)f(it)h(b)q(ecause)h(of)f(the)g(lac)o (k)g(of)f(a)114 1949 y(negativ)o(e)c(relativization)i(result.)56 2043 y(2.)22 b(Whole)16 b(new)f(directions)i(of)e(researc)o(h)g(ma)o(y) g(dev)o(elop)h(in)h(attempts)d(to)h(\014nd)h(new)g(tec)o(hniques)h(to)e (answ)o(er)114 2100 y(problems)g(with)h(negativ)o(e)f(relativizations.) 71 2193 y(Beigel,)j(Reingold)h(and)f(Spielman)h([BRS91])e(concen)o (trated)g(their)g(e\013orts)f(on)i(trying)f(to)f(sho)o(w)h(that)g Fm(PP)0 2250 y Fn(is)e(closed)h(under)g(in)o(tersection)g(mainly)g(b)q (ecause)g(of)e(the)h(imp)q(ortance)h(of)f(the)g(question)g(and)g(the)g (fact)g(that)f(no)0 2306 y(negativ)o(e)h(relativization)i(existed.)k (They)15 b(succeeded)i(in)f(\014nding)g(a)f(relativizable)j(pro)q(of.) 71 2363 y(The)h(whole)g(area)g(of)f(circuit)j(complexit)o(y)e(w)o(as)g (dev)o(elop)q(ed)h(as)f(a)f(p)q(oten)o(tial)i(metho)q(d)f(for)g(attac)o (king)f(the)0 2419 y(hard)d(problems)h(lik)o(e)g Fm(P)d Fg(6)p Fn(=)g Fm(NP)p Fn(.)20 b(Although)15 b(one)h(can)f(easily)h (relativize)h(circuits)g([Wil85],)d(man)o(y)h(researc)o(hers)0 2476 y(b)q(eliev)o(ed)k(the)d(structure)g(of)g(circuits)i(w)o(ould)f (allo)o(w)g(us)f(to)g(\014nd)h(nonrelativizable)i(tec)o(hniques)f(to)e (solv)o(e)g(some)0 2532 y(basic)g(complexit)o(y)g(questions.)71 2589 y(Circuit)g(complexit)o(y)g(still)g(has)f(a)g(long)g(w)o(a)o(y)g (to)f(go)h(b)q(efore)g(it)g(can)h(ful\014ll)h(this)f(promise.)k(Ho)o(w) o(ev)o(er,)14 b(circuit)0 2645 y(complexit)o(y)i(has)f(pro)o(vided)h (us)f(with)h(sev)o(eral)f(in)o(teresting)h(com)o(binatorial)g(problems) f(and)h(some)f(other)f(appli-)0 2701 y(cations)i(for)g(mac)o (hine-based)h(complexit)o(y)g(theory)l(.)23 b(In)17 b(fact,)e(circuit)i (complexit)o(y)g(has)f(giv)o(en)h(us)f(the)h(to)q(ols)f(to)964 2828 y(4)p eop %%Page: 5 5 5 4 bop 0 199 a Fn(pro)o(v)o(e)14 b(some)g(imp)q(ortan)o(t)g (relativization)h(results,)g(suc)o(h)f(as)g(a)g(relativized)j(w)o(orld) d(where)g(the)h(p)q(olynomial-time)0 256 y(hierarc)o(h)o(y)g(is)h (in\014nite)h(\(see)e([H)-6 b(\027)-28 b(as89)o(]\).)0 377 y Ff(3.4)56 b(Recognizing)17 b(new)i(tec)n(hniques)0 463 y Fn(Supp)q(ose)f(w)o(e)e(ha)o(v)o(e)h(a)f(pro)q(of)g(of)h(a)f (statemen)o(t)g Fi(S)j Fn(but)e(w)o(e)f(also)h(kno)o(w)f(that)g(there)h (exists)g(a)f(relativized)j(w)o(orld)0 520 y(where)g Fi(S)j Fn(do)q(es)d(not)f(hold.)32 b(W)l(e)19 b(can)h(then)f(analyze)g (the)h(pro)q(of)e(of)h Fi(S)i Fn(to)d(\014nd)i(the)f(tec)o(hnique)h (used)g(in)g(that)0 576 y(pro)q(of)e(that)g(do)q(es)h(not)g (relativize.)32 b(W)l(e)18 b(can)h(then,)h(hop)q(efully)l(,)h(apply)f (this)f(tec)o(hnique)h(to)e(other)g(negativ)o(ely)0 633 y(relativized)f(problems.)71 689 y(In)k(1989,)f(Noam)g(Nisan)h(found)g (a)g(m)o(ultiple-pro)o(v)o(er)g(in)o(teractiv)o(e)g(pro)q(of)g(for)p 1458 653 101 2 v 20 w Fm(SA)l(T)o Fn(,)h(a)e(problem)h(with)g(a)0 746 y(kno)o(wn)16 b(negativ)o(e)h(relativization)h([FRS88)o(].)24 b(Lund,)17 b(F)l(ortno)o(w)e(and)i(Karlo\013)f(analyzed)h(this)g(pro)q (of)g(and)f(using)0 802 y(Nisan's)h(tec)o(hniques)g(com)o(bined)h(with) e(some)g(new)h(ones)f(sho)o(w)o(ed)g(a)h(single-pro)o(v)o(er)g(in)o (teractiv)o(e)f(pro)q(of)g(system)0 858 y(for)p 75 822 V 20 w Fm(SA)l(T)21 b Fn([LFKN92].)37 b(Sev)o(eral)21 b(other)g(imp)q(ortan)o(t)f(pap)q(ers)i(on)f(in)o(teractiv)o(e)g(pro)q (of)g(theory)f(follo)o(w)o(ed)i(from)0 915 y(extensions)17 b(of)f(these)g(tec)o(hniques)i(\(e.g.)d([Sha92)o(,)h(BFL91)o(,)g (BFLS91,)g(ALM)1334 898 y Fl(+)1362 915 y Fn(92)o(]\).)22 b(Babai)17 b([Bab90)o(])f(go)q(es)g(in)o(to)0 971 y(more)f(detail)h(ab) q(out)f(the)g(history)h(of)e(these)i(dev)o(elopmen)o(ts.)0 1115 y Fo(4)67 b(When)23 b(Oracles)f(F)-6 b(ail)0 1216 y Fn(Almost)12 b(since)h(the)f(\014rst)f(relativization)j(results)e(of) f(Bak)o(er,)h(Gill)i(and)e(Solo)o(v)m(a)o(y)f([BGS75],)g(complexit)o(y) i(theorists)0 1272 y(ha)o(v)o(e)g(lo)q(ok)g(for)g(true)g(mathematical)g (statemen)o(ts)f(that)g(fail)i(in)g(some)f(relativized)i(w)o(orld.)k (Though)13 b(researc)o(hers)0 1329 y(ha)o(v)o(e)20 b(published)j(sev)o (eral)d(pap)q(ers)h(along)f(these)h(lines)h(\(e.g.)d([Mor81)n(,)h (Kur83,)g(Har85)o(,)g(HCKM88,)f(Cha90]\))0 1385 y(most)14 b(of)h(these)h(results)f(hold)h(b)q(ecause)g(the)g(mac)o(hine)g(mo)q (del)g(do)q(es)f(not)g(ha)o(v)o(e)g(prop)q(er)g(access)h(to)e(the)h (oracle.)71 1442 y(By)d(understanding)i(the)e(v)m(arious)h(t)o(yp)q(es) g(of)f(failures,)i(it)e(will)j(enhance)e(our)f(abilit)o(y)i(to)e(in)o (terpret)h(relativiza-)0 1498 y(tion)i(results.)21 b(One)16 b(should)g(not)f(simply)h(ignore)g(relativization)h(results)e(that)g (fall)h(in)o(to)f(the)g(categories)g(b)q(elo)o(w)0 1555 y(but)g(one)h(should)g(cautiously)g(dra)o(w)f(inferences)h(from)f(suc)o (h)g(results.)71 1611 y(In)e(the)h(section)g(w)o(e)f(discuss)h(sev)o (eral)g(di\013eren)o(t)f(categories)g(of)g(examples)h(where)g(oracles)f (fail.)20 b(In)14 b(Section)g(5)0 1668 y(w)o(e)h(will)i(lo)q(ok)e(at)g (the)g(sp)q(ecial)i(case)e(of)g(in)o(teractiv)o(e)h(pro)q(ofs.)0 1789 y Ff(Space-Bounded)i(Computation)0 1875 y Fn(Should)f(the)f (oracle)h(tap)q(e)f(coun)o(t)g(to)o(w)o(ards)e(the)i(space)g(b)q(ound?) 24 b(Either)17 b(w)o(a)o(y)e(can)h(cause)g(problems.)23 b(If)16 b(w)o(e)g(do)0 1932 y(coun)o(t)e(the)h(tap)q(e)f(that)g(w)o (ould)h(prev)o(en)o(t)f(a)h(result)g(lik)o(e)g Fm(ASP)l(A)o(CE)n Fn(\()p Fi(pol)q(y)r Fn(\))d(=)h Fm(EXP)h Fn(from)f(relativizing)k(b)q (ecause)0 1988 y(the)22 b(space-b)q(ounded)i(mac)o(hine)f(could)g(not)f (ask)g(exp)q(onen)o(tially)i(long)e(queries.)42 b(If)22 b(w)o(e)g(do)g(not)g(coun)o(t)g(the)0 2045 y(tap)q(e)17 b(then)g(a)f(result)h(lik)o(e)g Fm(A)l(TIME)p Fn(\()p Fi(pol)q(y)r Fn(\))c(=)j Fm(PSP)l(A)o(CE)e Fn(will)19 b(not)d(relativize)i(b)q(ecause)f(the)g(space-b)q(ounded)0 2101 y(mac)o(hine)g(could)g(ask)f(exp)q(onen)o(tially)i(long)e (queries.)24 b(Hartmanis,)15 b(Chang,)h(Kadin)h(and)g(Mitc)o(hell)g ([HCKM88)o(])0 2157 y(ha)o(v)o(e)e(further)g(discussion)i(on)e(these)g (oracle)h(mo)q(dels.)71 2214 y(Ladner)21 b(and)g(Lync)o(h)h([LL76])f (suggest)f(a)h(reasonable)g(alternativ)o(e:)32 b(Do)20 b(not)h(coun)o(t)g(the)g(space)g(on)g(the)0 2270 y(oracle)g(tap)q(e)g (but)f(mak)o(e)g(the)h(oracle)g(tap)q(e)g(a)f(write-only)i(tap)q(e)e (that)g(is)h(automatically)g(erased)g(after)f(eac)o(h)0 2327 y(query)l(.)j(While)18 b(this)e(suggestion)g(w)o(orks)f(w)o(ell)i (b)q(elo)o(w)g Fm(P)p Fn(,)f(it)g(do)q(es)h(not)e(solv)o(e)i(the)f (quandary)g(describ)q(ed)i(in)f(the)0 2383 y(previous)f(paragraph.)71 2440 y(Buss)i([Bus88)o(])g(creates)f(an)h(oracle)g(mo)q(del)h(that)e (seems)h(to)f(get)g(around)h(this)g(problem)h(but)f(is)g(to)q(o)g(cum-) 0 2496 y(b)q(ersome)k(for)f(use)h(in)h(practice.)40 b(If)22 b(one)g(m)o(ust)f(relativize)j(a)d(space)h(class)g(w)o(e)g(suggest)f (to)g(either)i(use)f(the)0 2553 y(corresp)q(onding)e(relativized)i (alternating)d(time)h(class)g(or)f(to)g(use)g(the)h(Landner)g(and)g (Lync)o(h)g(mo)q(del)g(with)g(a)0 2609 y(careful)c(ey)o(e.)964 2828 y(5)p eop %%Page: 6 6 6 5 bop 0 199 a Ff(P)n(artial)19 b(Relativizations)0 285 y Fn(In)d(these)g(results)g(some,)f(but)h(not)f(all,)h(of)f(the)h (ob)s(jects)f(in)o(v)o(olv)o(ed)h(are)g(allo)o(w)o(ed)g(to)f(ha)o(v)o (e)g(access)g(to)g(the)h(oracle.)0 342 y(Kurtz)e([Kur83])f(sho)o(w)o (ed)h(that)f Fm(NP)f Fg(\022)h Fm(P)719 321 y Fd(SA)m(T)813 342 y Fn(but)h(for)f(a)h(random)f Fi(R)p Fn(,)h Fm(NP)1304 321 y Fh(R)1343 342 y Fg(6\022)f Fm(P)1427 321 y Fd(SA)m(T)o Fc(\010)p Fh(R)1572 342 y Fn(giving)i(a)f(coun)o(terex-)0 398 y(ample)19 b(to)e(the)h(Random)g(Oracle)h(Hyp)q(othesis)f(\(See)h (Section)f(6\).)28 b(Ho)o(w)o(ev)o(er,)17 b(it)h(uses)g(hea)o(vily)h (the)f(fact)g(that)0 461 y(queries)f(to)e(the)g Fm(SA)l(T)g Fn(oracle)h(do)g(not)f(ha)o(v)o(e)g(access)h(to)f Fi(R)p Fn(.)21 b(In)16 b(fact,)f(for)g(all)i Fi(A)p Fn(,)e Fm(NP)1479 440 y Fh(A)1519 461 y Fg(\022)f Fm(P)1603 440 y Fd(SA)m(T)1682 428 y Fb(A)1707 461 y Fn(.)21 b(Hartmanis)0 518 y([Har85)o(])14 b(has)i(a)e(similar)j(example.)71 574 y(Chang)e([Cha90)o(])h(has)g(a)f (di\013eren)o(t)i(example)f(where)h(a)e(function)i Fi(s)p Fn(\()p Fi(n)p Fn(\))f(is)h(not)e(space-constructible)j(in)f(the)0 630 y(unrelativized)h(w)o(orld)d(but)g Fi(s)p Fn(\()p Fi(n)p Fn(\))g(is)h(space-constructible)h(in)f(a)f(relativized)i(w)o (orld.)i(Ho)o(w)o(ev)o(er,)14 b(if)i(the)f(function)0 687 y Fi(s)p Fn(\()p Fi(n)p Fn(\))f(w)o(as)f(computed)h(using)h(a)e (relativized)j(T)l(uring)f(mac)o(hine,)f(the)g(theorem)g(Chang)f (states)g(w)o(ould)i(relativize.)0 807 y Ff(Insu\016cien)n(t)j(Oracle)g (Access)0 893 y Fn(One)13 b(of)g(the)g(basic)g(theorems)f(in)i (complexit)o(y)f(theory)g(is)g(linear)h(sp)q(eedup:)20 b(if)13 b(a)f(program)g(tak)o(es)g Fi(t)p Fn(\()p Fi(n)p Fn(\))h(time)g(with)0 949 y Fi(t)p Fn(\()p Fi(n)p Fn(\))g(sup)q (erlinear)i(then)f(for)f(ev)o(ery)g Fi(c)p Fn(,)g(for)f(all)i(but)g(a)f (\014nite)h Fi(n)p Fn(,)f(there)h(is)f(a)g(another)g(T)l(uring)h(mac)o (hine)g(that)f(tak)o(es)0 1006 y(only)i Fi(t)p Fn(\()p Fi(n)p Fn(\))p Fi(=c)f Fn(time.)20 b(Moran)13 b([Mor81)n(])h(noted)h (that)e(this)i(result)g(do)q(es)g(not)f(relativize:)21 b(w)o(e)14 b(need)h(only)g(mak)o(e)f(the)0 1062 y(language)h(dep)q (enden)o(t)i(on)e(strings)g(in)h(the)g(oracle)f(of)g(length)h(sa)o(y)e Fi(t)p Fn(\()p Fi(n)p Fn(\))c(+)h(1.)71 1119 y(This)j(oracle)h(failure) g(o)q(ccurs)g(b)q(ecause)g(of)f(insu\016cien)o(t)h(oracle)g(access.)20 b(The)14 b(pro)q(of)g(of)g(the)g(linear)h(sp)q(eed-up)0 1175 y(theorem)20 b(w)o(orks)e(b)o(y)i(enco)q(ding)i(sev)o(eral)e(tap)q (e)g(square)f(in)o(to)h(single)h(square)f(b)o(y)g(using)h(a)e(larger)h (set)f(of)h(tap)q(e)0 1232 y(sym)o(b)q(ols.)g(Ho)o(w)o(ev)o(er,)13 b(the)i(relativized)i(mo)q(del)e(do)q(es)g(not)g(allo)o(w)g(this)g (compression)g(on)g(the)g(oracle)f(tap)q(e.)20 b(If)15 b(w)o(e)0 1288 y(c)o(hange)h(the)f(mo)q(del)i(to)e(allo)o(w)g (compressed)h(queries)h(to)e(the)g(oracle)h(then)g(w)o(e)f(will)i (indeed)h(ha)o(v)o(e)d(a)g(relativized)0 1345 y(linear)h(sp)q(eedup)h (theorem.)j(W)l(e)15 b(will)i(sho)o(w)d(another)h(example)h(of)f(this)h (t)o(yp)q(e)f(of)g(failure)h(in)g(Section)g(5.2.)71 1444 y(When)f(in)o(terpreting)i(a)e(relativization)i(result,)e(one)h(m)o (ust)e(b)q(e)j(extremely)f(careful)g(in)g(lo)q(oking)g(at)f(ho)o(w)g (the)0 1501 y(computational)20 b(mo)q(del)g(ma)o(y)e(access)i(the)f (oracle.)32 b(If)20 b(w)o(e)f(can)g(pro)o(v)o(e)g(a)g(statemen)o(t)f Fi(S)k Fn(false)e(relativ)o(e)f(to)g(an)0 1557 y(oracle)e(in)g(a)f (certain)h(mo)q(del)g(then)g(tec)o(hniques)h(that)d(relativize)k Fe(only)d(in)h(the)h(mo)n(del)e Fn(will)i(not)e(w)o(ork)g(to)g(pro)o(v) o(e)0 1614 y Fi(S)s Fn(.)71 1670 y(Recen)o(t)j(nonrelativizing)j (results)e(on)f(in)o(teractiv)o(e)g(pro)q(ofs)g(do)g(not)g(app)q(ear)h (to)e(\014t)h(in)h(an)o(y)f(of)g(the)g(ab)q(o)o(v)o(e)0 1727 y(categories.)h(In)15 b(Section)i(5,)d(w)o(e)h(will)i(explore)f (as)f(b)q(est)g(w)o(e)g(can)g(wh)o(y)g(these)h(tec)o(hniques)g(do)f (not)g(relativize.)0 1868 y Fo(5)67 b(Relativizations)24 b(of)e(In)n(teractiv)n(e)i(Pro)r(ofs)0 1970 y Fn(In)o(teractiv)o(e)15 b(pro)q(ofs)g(w)o(ere)g(in)o(v)o(en)o(ted)h(in)g(1985)e(sim)o (ultaneously)i(b)o(y)f(Babai)h([Bab85)o(,)f(BM88)o(])g(and)g(Goldw)o (asser,)0 2026 y(Micali)22 b(and)g(Rac)o(k)o(o\013)e([GMR89)o(].)36 b(W)l(e)21 b(refer)g(the)g(reader)g(to)g(these)g(pap)q(ers)g(for)g (descriptions)h(and)f(formal)0 2083 y(de\014nitions)c(of)e(in)o (teractiv)o(e)g(pro)q(ofs.)71 2139 y(In)g(1986,)f(F)l(ortno)o(w)f(and)i (Sipser)h([FS88)o(])f(created)f(a)h(relativized)i(w)o(orld)e(where)g (some)f(language)i(in)f(co-)p Fm(NP)0 2195 y Fn(do)q(es)f(not)f(ha)o(v) o(e)g(an)g(in)o(teractiv)o(e)h(pro)q(of.)19 b(F)l(ortno)o(w)11 b(and)j(Sipser)g(then)g(conjectured)g(that)f(there)g(exist)h(languages) 0 2252 y(in)i(co-)p Fm(NP)f Fn(that)f(do)i(not)e(ha)o(v)o(e)h(in)o (teractiv)o(e)h(pro)q(ofs.)71 2308 y(In)h(1989,)e(Lund,)i(F)l(ortno)o (w,)e(Karlo\013)i(and)f(Nisan)h([LFKN92])f(sho)o(w)o(ed)g(that)g(ev)o (ery)g(co-)p Fm(NP)g Fn(language)h(has)0 2365 y(an)e(in)o(teractiv)o(e) g(pro)q(of)g(system.)k(By)c(the)g(F)l(ortno)o(w)f(and)h(Sipser)h (oracle,)e(their)i(pro)q(of)e(could)i(not)f(relativize.)21 b(In)0 2421 y(this)16 b(section,)f(w)o(e)g(will)i(try)d(to)h(examine)h (wh)o(y)f(that)f(pro)q(of)h(do)q(es)h(not)f(relativize.)71 2478 y(In)g(Section)h(5.1,)d(w)o(e)i(discuss)h(a)f(recen)o(t)f(imp)q (ortan)o(t)h(result)g(ab)q(out)g(probabilistically)j(c)o(hec)o(k)m (able)f(pro)q(ofs)d(b)o(y)0 2534 y(Arora,)e(Lund,)i(Mot)o(w)o(ani,)e (Sudan)h(and)g(Szegedy)h([ALM)980 2518 y Fl(+)1007 2534 y Fn(92])e(and)h(sho)o(w)f(that)g(that)h(result)g(do)q(es)g(not)f (relativize)0 2591 y(in)19 b(a)g(strong)e(w)o(a)o(y)l(.)29 b(W)l(e)19 b(also)g(discuss)g(the)g(p)q(ossibilit)o(y)i(that)d(one)g (can)h(use)g(the)g(probabilistically)i(c)o(hec)o(k)m(able)0 2647 y(pro)q(of)16 b(result)h(to)f(sho)o(w)g(that)f Fm(NP)g Fg(6)p Fn(=)g Fm(EXP)p Fn(.)23 b(In)17 b(Section)h(5.2,)d(w)o(e)h (discuss)i(lo)q(cal)f(c)o(hec)o(k)m(abilit)o(y)i(dev)o(elop)q(ed)f(b)o (y)0 2704 y(Arora,)f(Impagliazzo)i(and)e(V)l(azirani)i([AIV92])e(and)h (argue)f(that)g(this)h(notion)g(do)q(es)g(not)f(giv)o(e)h(a)f (satisfactory)964 2828 y(6)p eop %%Page: 7 7 7 6 bop 0 199 a Fn(answ)o(er)11 b(to)f(the)i(question)g(of)e(wh)o(y)i (the)f(in)o(teractiv)o(e)h(pro)q(of)e(results)i(do)f(not)g(relativize.) 20 b(In)12 b(Section)h(5.3,)d(w)o(e)h(argue)0 256 y(that)16 b(a)f(more)h(algebraic)h(prop)q(ert)o(y)f(of)g(complexit)o(y)h(classes) g(is)g(the)f(ro)q(ot)f(of)h(this)h(nonrelativization.)25 b(Finally)l(,)0 312 y(in)16 b(Section)g(5.4)e(w)o(e)h(discuss)i(some)d (further)h(questions)h(ab)q(out)f(in)o(teractiv)o(e)h(pro)q(ofs)f(and)g (relativization.)0 434 y Ff(5.1)56 b(Probabilistically)16 b(Chec)n(k)m(able)i(Pro)r(ofs)0 520 y Fn(In)f(this)f(section,)g(w)o(e)g (will)i(sho)o(w)d(t)o(w)o(o)g(results)h(ab)q(out)g(probabilisticall)q (y)j(c)o(hec)o(k)m(able)e(pro)q(of)f(systems.)22 b(First)15 b(w)o(e)0 576 y(sho)o(w)e(that)f(the)h(result)h(of)f(Arora,)f(Lund,)j (Mot)o(w)o(ani,)d(Sudan)i(and)f(Szegedy)h([ALM)1440 560 y Fl(+)1468 576 y Fn(92)o(])f(do)q(es)g(not)g(relativize)i(in)0 633 y(a)f(strong)e(w)o(a)o(y)l(.)19 b(W)l(e)14 b(then)g(lo)q(ok)g(at)f (what)h(happ)q(ens)h(if)f(w)o(e)f(lo)q(ok)i(at)e(oracles)h(trying)g(to) f(relate)h Fm(PCP)f Fn(and)h Fm(EXP)o Fn(.)71 689 y(Arora)k(and)i (Safra)e([AS92])h(de\014ne)h(a)f(hierarc)o(h)o(y)h(of)f(complexit)o(y)h (classes)g Fm(PCP)o Fn(,)g(corresp)q(onding)g(to)f(the)0 746 y(n)o(um)o(b)q(er)g(of)g(random)g(and)g(query)h(bits)f(required)i (to)d(v)o(erify)h(a)g(pro)q(of)g(of)g(mem)o(b)q(ership)h(in)g(the)f (language,)h(as)0 802 y(follo)o(ws:)71 858 y(A)14 b Fe(veri\014er)g Fi(M)20 b Fn(is)15 b(a)f(probabilistic)i(p)q(olynomial-time)h(T)l (uring)e(mac)o(hine)h(with)e(random)g(access)h(to)f(a)g(string)0 915 y(\005)j(represen)o(ting)g(a)g(mem)o(b)q(ership)h(pro)q(of;)f Fi(M)22 b Fn(can)17 b Fe(query)g Fn(an)o(y)f(bit)i(of)e(\005.)25 b(Call)17 b Fi(M)22 b Fn(an)17 b(\()p Fi(r)q Fn(\()p Fi(n)p Fn(\))p Fi(;)8 b(q)r Fn(\()p Fi(n)p Fn(\)\)-)p Fe(r)n(estricte)n(d)0 971 y Fn(v)o(eri\014er)k(if,)g(on)g(an)f(input)i (of)e(size)h Fi(n)p Fn(,)h(it)e(is)h(allo)o(w)o(ed)g(to)f(use)h(at)f (most)g Fi(O)q Fn(\()p Fi(r)q Fn(\()p Fi(n)p Fn(\)\))f(random)h(bits)h (for)f(its)g(computation,)0 1028 y(and)k(query)h(at)e(most)h Fi(O)q Fn(\()p Fi(q)r Fn(\()p Fi(n)p Fn(\)\))f(bits)h(of)g(the)g(pro)q (of.)71 1084 y(A)k(language)h Fi(L)f Fn(is)h(in)g Fm(PCP)o Fn(\()p Fi(r)q Fn(\()p Fi(n)p Fn(\))p Fi(;)8 b(q)r Fn(\()p Fi(n)p Fn(\)\))17 b(if)j(there)g(exists)f(an)h(\()p Fi(r)q Fn(\()p Fi(n)p Fn(\))p Fi(;)8 b(q)r Fn(\()p Fi(n)p Fn(\)\)-restricted) 17 b(v)o(eri\014er)j Fi(M)25 b Fn(suc)o(h)0 1141 y(that)14 b(for)h(ev)o(ery)g(input)h Fi(x)p Fn(:)56 1235 y(1.)22 b(If)c Fi(x)g Fg(2)g Fi(L)p Fn(,)h(there)f(is)h(a)f(pro)q(of)g(\005)682 1242 y Fh(x)722 1235 y Fn(whic)o(h)h(causes)f Fi(M)24 b Fn(to)17 b(accept)i(for)f(ev)o(ery)g(random)g(string,)h Fe(i.e.)g Fn(with)114 1291 y(probabilit)o(y)d(1.)56 1385 y(2.)22 b(If)16 b Fi(x)e Fg(62)g Fi(L)p Fn(,)i(then)g(for)g(all)g(pro)q (ofs)g(\005,)g(the)g(probabilit)o(y)h(that)f Fi(M)21 b Fn(using)16 b(pro)q(of)g(\005)g(accepts)g(is)h(b)q(ounded)g(b)o(y)114 1441 y(1)p Fi(=)p Fn(2.)71 1535 y(In)12 b(1988,)f(Ben-Or,)i(Goldw)o (asser,)f(Kilian)i(and)e(Wigderson)g([BGKW88])f(de\014ned)i Fe(multiple)h(pr)n(over)f(inter)n(ac-)0 1592 y(tive)k(pr)n(o)n(of)g (systems)d Fn(where)i(the)g(v)o(eri\014er)g(comm)o(unicates)g(with)g (sev)o(eral)g(pro)o(v)o(ers)f(that)g(cannot)h(comm)o(unicate)0 1648 y(among)j(themselv)o(es.)35 b(F)l(ortno)o(w,)20 b(Romp)q(el)h(and)g(Sipser)g([FRS88)o(])f(sho)o(w)f(that)h(the)g (languages)g(accepted)h(b)o(y)0 1704 y(m)o(ultiple)c(pro)o(v)o(ers)d (\()p Fm(MIP)o Fn(\))h(and)h Fg([)611 1711 y Fh(k)q(>)p Fl(0)674 1704 y Fm(PCP)o Fn(\()p Fi(n)828 1688 y Fh(k)848 1704 y Fi(;)8 b(n)896 1688 y Fh(k)916 1704 y Fn(\))15 b(are)g(equiv)m(alen)o(t.)22 b(Babai,)15 b(F)l(ortno)o(w)f(and)i(Lund)g ([BFL91)o(])0 1761 y(building)i(on)d(the)g(w)o(ork)f(of)h([LFKN92])g (sho)o(w)f(that)h Fm(NEXP)d Fn(=)h Fm(MIP)f Fn(=)h Fg([)1313 1768 y Fh(k)q(>)p Fl(0)1376 1761 y Fm(PCP)o Fn(\()p Fi(n)1530 1744 y Fh(k)1550 1761 y Fi(;)8 b(n)1598 1744 y Fh(k)1618 1761 y Fn(\).)71 1817 y(Arora,)20 b(Lund,)j(Mot)o(w)o(ani,)d(Sudan)i (and)e(Szegedy)i([ALM)1100 1801 y Fl(+)1127 1817 y Fn(92)o(])f (building)i(on)d(tec)o(hniques)i(of)e(Arora)g(and)0 1874 y(Safra)15 b([AS92)o(])g(sho)o(w)f(the)i(follo)o(wing)g(surprising)g (and)f(p)q(o)o(w)o(erful)h(theorem:)0 1968 y Fm(Theorem)f(5.1)22 b(NP)13 b Fn(=)g Fm(PCP)o Fn(\(log\()p Fi(n)p Fn(\))p Fi(;)8 b Fn(1\))0 2061 y(One)15 b(can)g(easily)h(create)f(an)f(oracle)h (relativ)o(e)g(to)f(whic)o(h)i(this)f(result)g(do)q(es)g(not)g (relativize)h(b)q(ecause)g(the)e(v)o(eri\014er)0 2118 y(has)19 b(only)g(a)f(p)q(olynomial)i(n)o(um)o(b)q(er)f(of)f (computation)h(paths.)30 b(W)l(e)19 b(use)g(tec)o(hniques)h(of)e(F)l (ortno)o(w)f(and)i(Sipser)0 2174 y([FS88)o(])c(and)g(F)l(ortno)o(w,)f (Romp)q(el)i(and)g(Sipser)g([FRS88)o(])f(to)g(sho)o(w)f(a)h(m)o(uc)o(h) g(stronger)g(negativ)o(e)g(oracle)g(result:)0 2268 y Fm(Theorem)g(5.2)22 b Fe(F)m(or)16 b(some)g(or)n(acle)h Fi(A)p Fe(,)f Fm(NP)786 2247 y Fh(A)830 2268 y Fe(is)g(not)g(c)n (ontaine)n(d)f(in)h Fg([)1248 2275 y Fh(j)r(>)p Fl(0)1308 2268 y Fm(PCP)1417 2247 y Fh(A)1444 2268 y Fn(\()p Fi(n)1489 2252 y Fh(j)1507 2268 y Fi(;)8 b(n)1555 2252 y Fh(k)1575 2268 y Fn(\))16 b Fe(for)g(any)g(\014xe)n(d)g Fi(k)q Fe(.)71 2362 y Fm(Pro)q(of:)27 b Fn(Let)14 b Fi(L)351 2369 y Fh(k)371 2362 y Fn(\()p Fi(A)p Fn(\))e(=)h Fg(f)p Fn(1)547 2345 y Fh(n)569 2362 y Fg(j)p Fn(There)i(exists)h(a)f(string)g Fi(x)g Fn(of)g(length)h Fi(n)1265 2345 y Fl(2)p Fh(k)1317 2362 y Fn(in)g Fi(A)p Fg(g)p Fn(.)j(Clearly)c Fi(L)1647 2369 y Fh(k)1667 2362 y Fn(\()p Fi(A)p Fn(\))e(is)i(in)f Fm(NP)1923 2341 y Fh(A)0 2418 y Fn(for)h(ev)o(ery)g Fi(A)p Fn(.)71 2475 y(Let)g Fi(M)196 2482 y Fl(1)215 2475 y Fi(;)8 b(M)280 2482 y Fl(2)298 2475 y Fi(;)g(:)g(:)g(:)k Fn(b)q(e)k(an)f(en)o(umerate)g(of)g(probabilistic)i(v)o(eri\014ers)f (where)g Fi(M)1390 2482 y Fh(i)1419 2475 y Fn(runs)f(in)h(time)g Fi(n)1704 2458 y Fh(i)1718 2475 y Fn(.)71 2531 y(T)l(erminology:)j Fi(M)394 2538 y Fh(i)420 2531 y Fn(mak)o(es)13 b(t)o(w)o(o)e(kinds)j (of)e(queries:)20 b(A)12 b(pro)q(of)h(query)g(is)g(a)f(query)h(to)g (the)f(mem)o(b)q(ership)i(pro)q(of)0 2588 y(\005;)h(An)g(oracle)h (query)f(is)h(a)f(query)g(to)g Fi(A)p Fn(.)71 2644 y(Requiremen)o(t)k Fi(R)377 2651 y Fh(i;k)419 2644 y Fn(:)26 b Fi(L)489 2651 y Fh(k)510 2644 y Fn(\()p Fi(A)p Fn(\))18 b(is)h(not)f(accepted)h (b)o(y)g(v)o(eri\014er)g Fi(M)1192 2628 y Fh(A)1187 2655 y(i)1237 2644 y Fn(where)g Fi(M)1421 2628 y Fh(A)1416 2655 y(i)1467 2644 y Fn(mak)o(es)f(at)f(most)h Fi(n)1807 2628 y Fh(k)1846 2644 y Fn(pro)q(of)0 2701 y(queries.)964 2828 y(7)p eop %%Page: 8 8 8 7 bop 71 199 a Fn(W)l(e)20 b(will)h(handle)h(these)e(coun)o(tably)g (man)o(y)g(requiremen)o(ts)g(one)g(at)g(a)f(time.)35 b(Initially)23 b Fi(A)d Fn(is)g(the)g(empt)o(y)0 256 y(oracle.)25 b(W)l(e)17 b(will)i(add)e(a)f(\014nite)i(n)o(um)o(b)q(er)f (of)g(strings)g(to)f Fi(A)h Fn(in)g(eac)o(h)g(stage.)25 b(The)17 b(\014nal)g Fi(A)g Fn(is)h(the)f(union)h(of)e(all)0 312 y(the)f(strings)g(added)h(in)g(eac)o(h)g(stage.)71 369 y(Stage)e(\()p Fi(i;)8 b(k)q Fn(\):)56 453 y(1.)22 b(Pic)o(k)14 b Fi(n)h Fn(large)f(enough)h(so)f(that)g(it)g(do)q(es)h (not)f(con\015ict)h(with)g(earlier)g(stages)e(and)i(suc)o(h)f(that)g(2) 1743 437 y Fh(n)1778 453 y Fi(>>)f(n)1888 437 y Fl(2)p Fh(ik)1937 453 y Fn(.)56 543 y(2.)22 b(Lo)q(ok)e(at)g Fi(M)343 527 y Fh(A)338 554 y(i)370 543 y Fn(\(1)411 527 y Fh(n)433 543 y Fn(\).)35 b(If)20 b(there)h(exists)g(a)f(mem)o(b)q (ership)h(pro)q(of)f(that)g(causes)g Fi(M)1526 527 y Fh(A)1521 554 y(i)1553 543 y Fn(\(1)1594 527 y Fh(n)1616 543 y Fn(\))g(to)g(accept)h(with)114 600 y(probabilit)o(y)16 b(greater)e(than)h(1)p Fi(=)p Fn(4)g(then)g(w)o(e)g(ha)o(v)o(e)g (ful\014lled)j Fi(R)1163 607 y Fh(i;k)1204 600 y Fn(.)i(Go)15 b(on)g(to)g(the)g(next)g(stage.)56 690 y(3.)22 b(If)c(some)g(\014nite)i (extension)f(to)f Fi(A)g Fn(w)o(ould)h(cause)f Fi(M)1023 673 y Fh(A)1018 701 y(i)1050 690 y Fn(\(1)1091 673 y Fh(n)1113 690 y Fn(\))g(to)g(ask)g(more)g(than)g Fi(n)1544 673 y Fh(k)1583 690 y Fn(pro)q(of)g(queries)i(then)114 746 y(mak)o(e)14 b(that)h(extension)h(and)f Fi(R)655 753 y Fh(i;k)712 746 y Fn(is)h(ful\014lled.)22 b(Go)15 b(on)g(to)f(the)i(next)f(stage.)56 836 y(4.)22 b(Put)15 b Fi(x)g Fn(from)g(Lemma)g(5.3)g(in)o(to)g Fi(A)p Fn(.)21 b(Supp)q(ose)c(there)e(existed)h(some)g(mem)o(b)q(ership)g(pro)q(of)f (suc)o(h)h(that)f(the)114 893 y(probabilit)o(y)i(of)e Fi(M)448 876 y Fh(A)443 904 y(i)475 893 y Fn(\(1)516 876 y Fh(n)538 893 y Fn(\))h(accepts)g(is)g(one.)22 b(Then)16 b(this)g(same)g(mem)o(b)q(ership)h(pro)q(of)e(will)j(cause)e Fi(A)11 b Fg(\000)g(f)p Fi(x)p Fg(g)114 949 y Fn(to)j(accept)h(with)g (probabilit)o(y)h(at)f(least)g(3)p Fi(=)p Fn(4)f(b)q(ecause)h(of)g (Lemma)g(5.3.)k(This)c(con)o(tradicts)g(step)g(2.)k(Th)o(us)114 1006 y(w)o(e)c(ha)o(v)o(e)f(ful\014lled)k Fi(R)483 1013 y Fh(i;k)525 1006 y Fn(.)i(Go)14 b(on)h(to)g(the)g(next)g(stage.)0 1099 y Fm(Lemm)o(a)f(5.3)23 b Fe(Ther)n(e)16 b(exists)f(a)i(string)e Fi(x)h Fe(of)h(length)e Fi(n)955 1082 y Fl(2)p Fh(k)1009 1099 y Fe(such)h(that)122 1190 y Fn(Pr)o(\()p Fe(Ther)n(e)g(exists)f(a) i(memb)n(ership)f(pr)n(o)n(of)g Fn(\005)h Fe(wher)n(e)f Fi(M)1074 1173 y Fh(A)1069 1201 y(i)1101 1190 y Fn(\(1)1142 1173 y Fh(n)1164 1190 y Fn(\))g Fe(has)g(an)g(or)n(acle)h(query)f(to)h Fi(x)p Fn(\))12 b Fi(<)h Fn(1)p Fi(=)p Fn(4)0 1281 y Fe(The)j(pr)n(ob)n(ability)g(is)g(taken)g(over)g(the)h(r)n(andom)f (strings)f(of)i Fi(M)1075 1264 y Fh(A)1070 1292 y(i)1102 1281 y Fn(\(1)1143 1264 y Fh(n)1165 1281 y Fn(\))p Fe(.)71 1374 y Fm(Pro)q(of:)34 b Fn(Fix)18 b(a)f(random)g(coin)h(toss)f Fi(r)q Fn(.)26 b(The)18 b(n)o(um)o(b)q(er)g(of)f(oracle)h(queries)g (that)f Fi(M)1550 1357 y Fh(A)1545 1385 y(i)1577 1374 y Fn(\(1)1618 1357 y Fh(n)1640 1374 y Fn(\))g(could)h(mak)o(e)f(is)0 1430 y(at)g(most)f Fi(n)198 1414 y Fh(i)212 1430 y Fn(2)235 1414 y Fh(n)256 1401 y Fb(k)293 1430 y Fn(for)h(all)h(p)q(ossible)i (mem)o(b)q(ership)e(pro)q(ofs)f(b)q(ecause)i(there)e(are)g(at)g(most)f Fi(n)1565 1414 y Fh(k)1604 1430 y Fn(pro)q(of)h(queries.)27 b(So)0 1487 y(a)16 b(randomly)h(c)o(hosen)g(string)g(of)f(length)i Fi(n)743 1470 y Fl(2)p Fh(k)797 1487 y Fn(will)g(ha)o(v)o(e)e (extremely)h(lo)o(w)g(probabilit)o(y)h(of)e(b)q(eing)i(in)g(this)f(set) f(of)0 1543 y(oracle)f(queries.)21 b(The)16 b(lemma)f(follo)o(ws)g (from)g(the)g(usual)h(a)o(v)o(eraging)e(argumen)o(t.)20 b Fa(2)71 1610 y Fn(The)c(oracle)h(constructed)g(b)o(y)f(this)h (algorithm)g(will)h(ful\014ll)g(all)g(the)e(requiremen)o(ts)i(and)e(th) o(us)g Fi(L)p Fn(\()p Fi(A)p Fn(\))g(is)h(not)0 1667 y(con)o(tained)f(in)g Fg([)289 1674 y Fh(j)r(>)p Fl(0)349 1667 y Fm(PCP)458 1646 y Fh(A)485 1667 y Fn(\()p Fi(n)530 1650 y Fh(j)548 1667 y Fi(;)8 b(n)596 1650 y Fh(k)616 1667 y Fn(\))15 b(for)f(an)o(y)h(\014xed)h Fi(k)q Fn(.)k Fa(2)71 1744 y Fn(Since)k(clearly)g Fm(PCP)459 1723 y Fh(A)486 1744 y Fn(\(log)8 b Fi(n;)g Fn(1\))24 b Fg(\022)i Fm(NP)820 1723 y Fh(A)870 1744 y Fn(for)c(all)i Fi(A)p Fn(,)g(W)l(e)f(can)g(in)o(terpret)g(Theorem)g(5.1)f(as)g(a)h(w)o(eak)0 1801 y(c)o(haracterization)d(of)g Fm(NP)p Fn(.)34 b(P)o(erhaps)20 b(w)o(e)g(can)g(use)h(this)g(c)o(haracterization)f(to)f(separate)h Fm(NP)g Fn(from)f(higher)0 1857 y(complexit)o(y)d(classes)g(lik)o(e)g Fm(PSP)l(A)o(CE)e Fn(and)h Fm(EXP)g Fn(b)o(y)g(separating)g Fm(PCP)o Fn(\(log)8 b Fi(n;)g Fn(1\))14 b(from)h(these)g(classes.)71 1914 y(Ho)o(w)o(ev)o(er)10 b Fm(P)286 1893 y Fh(A)325 1914 y Fg(\022)j Fm(PCP)483 1893 y Fh(A)510 1914 y Fn(\(log)8 b Fi(n;)g Fn(1\))i(for)h(all)h Fi(A)f Fn(and)h(for)f(some)g Fi(B)j Fn(w)o(e)d(ha)o(v)o(e)g Fm(P)1372 1893 y Fh(B)1413 1914 y Fn(=)i Fm(PSP)l(A)o(CE)1667 1893 y Fh(B)1707 1914 y Fn([BGS75)o(],)f(for)0 1970 y(this)k Fi(B)i Fn(w)o(e)d(will)i(ha)o(v) o(e)e Fm(P)435 1949 y Fh(B)476 1970 y Fn(=)e Fm(PCP)633 1949 y Fh(B)662 1970 y Fn(\(log)8 b Fi(n;)g Fn(1\))k(=)h Fm(NP)972 1949 y Fh(B)1013 1970 y Fn(=)g Fm(PSP)l(A)o(CE)1267 1949 y Fh(B)1296 1970 y Fn(.)20 b(Th)o(us)c(w)o(e)f(w)o(ould)g(need)i (additional)0 2027 y(nonrelativizable)h(tec)o(hniques)e(to)f(separate)f Fm(PCP)p Fn(\(log)8 b Fi(n;)g Fn(1\))14 b(from)g Fm(PSP)l(A)o(CE)n Fn(.)71 2083 y(The)k(class)h Fm(EXP)f Fn(do)q(es)g(not)g(fall)h(in)o (to)g(the)f(same)g(trap.)29 b(F)l(or)17 b(ev)o(ery)h(oracle)h Fi(A)p Fn(,)g(w)o(e)f(ha)o(v)o(e)g Fm(P)1715 2062 y Fh(A)1760 2083 y Fg(6)p Fn(=)g Fm(EXP)1923 2062 y Fh(A)0 2139 y Fn(since)d(the)g(deterministic)h(time)f(hierarc)o(h)o(y)f(theorem)g (relativizes)i([HS65].)j(Heller)c([Hel81])f(sho)o(w)o(ed)g(that)g (there)0 2196 y(exists)i(an)g(oracle)g Fi(A)g Fn(where)h Fm(NP)581 2175 y Fh(A)622 2196 y Fn(=)e Fm(EXP)781 2175 y Fh(A)808 2196 y Fn(.)22 b(Since)c(Theorem)e(5.1)f(do)q(es)h(not)g (relativize,)h(Heller's)g(theorem)0 2252 y(do)q(es)f(not)g(necessarily) h(imply)h(that)d Fm(PCP)749 2231 y Fh(A)776 2252 y Fn(\(log)8 b Fi(n;)g Fn(1\))13 b(=)h Fm(EXP)1121 2231 y Fh(A)1148 2252 y Fn(.)22 b(In)17 b(fact)e(an)o(y)h(suc)o(h)g(oracle)g(will)i(b)q (e)f(hard)f(to)0 2309 y(\014nd:)0 2393 y Fm(Theorem)f(5.4)22 b Fe(If)15 b(ther)n(e)f(exists)g(an)h(or)n(acle)f Fi(A)h Fe(such)g(that)g Fm(PCP)1138 2372 y Fh(A)1166 2393 y Fn(\(log)7 b Fi(n;)h Fn(1\))k(=)h Fm(EXP)1508 2372 y Fh(A)1549 2393 y Fe(then)i Fm(P)d Fg(6)p Fn(=)h Fm(NP)i Fe(in)f(the)0 2450 y(unr)n(elativize)n(d)h(world.)71 2534 y Fm(Pro)q(of:)27 b Fn(Since)15 b(a)e Fm(PCP)503 2513 y Fh(A)530 2534 y Fn(\(log)8 b Fi(n;)g Fn(1\))k(v)o(eri\014er)j (has)e(only)i(a)e(p)q(olynomial)j(n)o(um)o(b)q(er)e(of)f(computation)h (paths,)f(a)0 2591 y(p)q(olynomial)h(time)e(mac)o(hine)h(could)g(query) f(all)h(of)f(the)g(oracle)g(queries)i(on)e(these)g(paths.)18 b(Then)13 b(the)f(p)q(olynomial-)0 2647 y(time)f(mac)o(hine)h(could)g (determine)g(whether)f(a)g(pro)q(of)g(\005)g(exists)g(b)o(y)g(a)g (single)h(unrelativized)h Fm(NP)e Fn(question.)19 b(Th)o(us)0 2704 y(w)o(e)c(ha)o(v)o(e)g(for)f(ev)o(ery)h Fi(A)h Fn(that)e Fm(PCP)618 2683 y Fh(A)645 2704 y Fn(\(log)8 b Fi(n;)g Fn(1\))k Fg(\022)h Fm(P)914 2683 y Fh(A)p Fc(\010)p Fd(SA)m(T)1045 2704 y Fn(.)964 2828 y(8)p eop %%Page: 9 9 9 8 bop 71 199 a Fn(Assume)23 b(that)f Fm(P)i Fn(=)i Fm(NP)c Fn(and)h(for)f(some)h(oracle)g Fi(A)p Fn(,)h Fm(PCP)1187 178 y Fh(A)1214 199 y Fn(\(log)8 b Fi(n;)g Fn(1\))24 b(=)i Fm(EXP)1581 178 y Fh(A)1608 199 y Fn(.)43 b(W)l(e)22 b(then)h(ha)o(v)o(e)0 256 y Fm(EXP)110 235 y Fh(A)150 256 y Fn(=)14 b Fm(PCP)308 235 y Fh(A)335 256 y Fn(\(log)8 b Fi(n;)g Fn(1\))k Fg(\022)i Fm(P)605 235 y Fh(A)p Fc(\010)p Fd(SA)m(T)749 256 y Fn(=)g Fm(P)834 235 y Fh(A)877 256 y Fn(whic)o(h)i(con)o(tradicts)f(the)h(fact)f(that)g (the)h(deterministic)i(time)0 312 y(hierarc)o(h)o(y)d(relativizes.)22 b Fa(2)0 434 y Ff(5.2)56 b(Lo)r(cal)17 b(Chec)n(k)m(abilit)n(y)0 520 y Fn(Arora,)d(Impagliazzo)i(and)g(V)l(azirani)g([AIV92])e(de\014ne) j(the)e(notion)g(of)g(pro)q(of)g(c)o(hec)o(k)o(er)g(as)g(follo)o(ws:)71 576 y(A)d Fe(pr)n(o)n(of-che)n(cker)g Fn(is)h(a)f(T)l(uring)h(mac)o (hine)g Fi(M)k Fn(that)11 b(uses)i(univ)o(ersal)g(quan)o(ti\014cation)g (and)g(whic)o(h)g(is)g(pro)o(vided,)0 633 y(in)h(addition)g(to)e(the)i (input,)g(a)e Fe(pr)n(o)n(of)j(string)p Fn(.)j(It)13 b(is)h(allo)o(w)o(ed)f(random)g(access)g(to)g(b)q(oth)g(the)g(input)h (and)f(the)g(pro)q(of)0 689 y(string.)27 b(It)17 b(is)h(said)g(to)f Fe(ac)n(c)n(ept)g Fn(an)h(input)g Fi(x)g Fn(using)g(pro)q(of-string)f (\005)h(\(denoted)f Fi(M)1440 673 y Fl(\005)1467 689 y Fn(\()p Fi(x)p Fn(\))f(=)h(1\))g(i\013)g(all)i(branc)o(hes)0 746 y(created)c(b)o(y)g(its)h(univ)o(ersal)g(branc)o(hing)g(accept.)71 802 y(A)f(language)g Fi(L)h Fn(is)g(in)g(the)f(class)h Fm(PF)o(CHK)o Fn(\()p Fi(t)p Fn(\()p Fi(n)p Fn(\)\))e(i\013)i(there)f (is)h(a)f(pro)q(of-c)o(hec)o(k)o(er)g(M)g(that)g(runs)g(in)i Fi(O)q Fn(\()p Fi(t)p Fn(\()p Fi(n)p Fn(\)\))0 858 y(time)f(and)f(has)g (the)g(prop)q(ert)o(y)68 952 y Fg(\017)23 b(8)p Fi(x)12 b Fg(2)h Fi(L)p Fn(,)i(there)g(exists)h(a)f(\005)g(suc)o(h)h(that)e Fi(M)858 936 y Fl(\005)885 952 y Fn(\()p Fi(x)p Fn(\))e(=)h(1.)68 1046 y Fg(\017)23 b(8)p Fi(x)12 b Fg(62)h Fi(L)p Fn(,)i Fi(M)328 1030 y Fl(\005)355 1046 y Fn(\()p Fi(x)p Fn(\))d(=)h(0)i(for)f (ev)o(ery)h(\005.)71 1140 y(Using)21 b(the)h(Co)q(ok-Levin)g(theorem)f ([Co)q(o71)o(,)g(Lev73],)h(Arora,)g(Impagliazzo)g(and)f(V)l(azirani)i (sho)o(w)e(that)0 1196 y Fm(NP)f Fn(=)h Fm(PF)o(CHK)n Fn(\(log)8 b Fi(n)p Fn(\).)34 b(Arora,)20 b(Impagliazzo)g(and)g(V)l (azirani)h(call)g(this)g(fact)e(the)h(\\Lo)q(cal)g(Chec)o(k)m(abilit)o (y)0 1253 y(Theorem".)71 1309 y(No)o(w)14 b(supp)q(ose)j(w)o(e)e (relativize)i Fm(PF)o(CHK)d Fn(to)h(an)h(oracle)f Fi(A)h Fn(b)o(y)f(giving)i(the)e(pro)q(of-c)o(hec)o(k)o(er)h(an)f(oracle)h (tap)q(e)0 1366 y(b)o(y)g(writing)g(a)f(full)i(oracle)f(query)f Fi(z)j Fn(on)e(the)f(tap)q(e)h(and)g(magically)g(en)o(tering)g(a)g (state)e Fi(q)1519 1373 y Fh(y)1555 1366 y Fn(if)i Fi(z)g Fg(2)d Fi(A)j Fn(and)g(a)f(state)0 1422 y Fi(q)20 1429 y Fh(n)62 1422 y Fn(if)k Fi(z)i Fg(62)e Fi(A)p Fn(.)30 b(Ho)o(w)o(ev)o(er)18 b(since)i(only)g(queries)f(of)g(length)g Fi(O)q Fn(\(log)8 b Fi(n)p Fn(\))19 b(can)g(b)q(e)g(ask)o(ed)g(b)o(y)g (a)f Fm(PF)o(CHK)1794 1401 y Fh(A)1821 1422 y Fn(\(log)8 b Fi(n)p Fn(\))0 1479 y(pro)q(of)16 b(c)o(hec)o(k)o(er,)h(it)g(is)h (easy)e(to)g(construct)h(oracles)g Fi(A)g Fn(suc)o(h)g(that)f Fi(A)f Fg(62)h Fm(PF)o(CHK)1436 1458 y Fh(A)1464 1479 y Fn(\(log)7 b Fi(n)p Fn(\))17 b(and)g(th)o(us)g Fm(NP)1877 1458 y Fh(A)1920 1479 y Fg(62)0 1535 y Fm(PF)o(CHK)187 1514 y Fh(A)214 1535 y Fn(\(log)8 b Fi(n)p Fn(\).)71 1592 y(Arora,)14 b(Impagliazzo)i(and)f(V)l(azirani)i(conclude)g(that)d (lo)q(cal)j(c)o(hec)o(k)m(abilit)o(y)g(do)q(es)f(not)f(relativize.)21 b(Ho)o(w)o(ev)o(er,)0 1648 y(w)o(e)12 b(feel)i(that)d(an)o(y)i(oracle)f (access)h(mec)o(hanism)g(that)f(prev)o(en)o(ts)g(a)g(mac)o(hine)i(from) d(querying)j(its)e(o)o(wn)g(input)i(is)f(an)0 1704 y(extremely)j(w)o (eak)f(access)h(mo)q(del.)22 b(W)l(e)16 b(will)h(presen)o(t)f(a)g(more) f(robust)g(access)h(mo)q(del)g(and)g(sho)o(w)f(that)g(relativ)o(e)0 1761 y(to)g(this)g(mo)q(del,)h(lo)q(cal)g(c)o(hec)o(k)m(abilit)o(y)h (do)q(es)f(relativize.)71 1817 y(W)l(e)h(will)i(allo)o(w)e Fi(M)23 b Fn(to)16 b(query)i(the)f(oracle)h(as)f(follo)o(ws:)24 b(When)17 b Fi(M)23 b Fn(w)o(an)o(ts)16 b(to)h(mak)o(e)f(an)i(oracle)f (query)l(,)h Fi(M)0 1874 y Fn(writes)h(t)o(w)o(o)e(p)q(oin)o(ters)i(on) f(the)h(oracle)g(tap)q(e.)30 b Fi(M)23 b Fn(will)e(no)o(w)d(go)g(to)g (state)f Fi(q)1330 1881 y Fh(y)1369 1874 y Fn(if)i(the)g(string)f(lo)q (cated)i(b)q(et)o(w)o(een)0 1930 y(those)15 b(t)o(w)o(o)f(p)q(oin)o (ters)h(on)h(the)f(pro)q(of)g(tap)q(e)g(is)h(in)g(the)f(oracle)g(and)h (will)h(go)d(to)h(state)f Fi(q)1472 1937 y Fh(n)1510 1930 y Fn(otherwise.)0 2037 y Fm(Theorem)h(5.5)22 b Fe(F)m(or)16 b(al)r(l)g(or)n(acles)g Fi(A)p Fe(,)g Fm(NP)754 2016 y Fh(A)794 2037 y Fn(=)d Fm(PF)o(CHK)1028 2016 y Fh(A)1055 2037 y Fn(\(log)8 b Fi(n)p Fn(\))p Fe(.)71 2143 y Fm(Pro)q(of:)67 b Fn(Let)18 b Fi(\036)391 2150 y Fh(A)436 2143 y Fn(b)q(e)h(a)f (relativized)i(3CNF)d(form)o(ula)h(as)g(describ)q(ed)i(in)f(Section)g (2.1.)27 b(A)18 b(pro)q(of)g(\005)g(will)0 2199 y(consist)13 b(of)g(a)f(satisfying)h(assignmen)o(t)g(as)g(w)o(ell)h(as)e(a)h(list)h (of)e Fi(x)1046 2206 y Fh(i)p Fl(1)1076 2199 y Fi(;)c(:)g(:)g(:)d(;)j (x)1204 2206 y Fh(ik)1248 2199 y Fn(for)13 b(eac)o(h)g Fi(A)p Fn(\()p Fi(x)1494 2206 y Fh(i)p Fl(1)1524 2199 y Fi(;)8 b(:)g(:)g(:)d(;)j(x)1652 2206 y Fh(ik)1683 2199 y Fn(\))k(o)q(ccurring)i(in)0 2256 y(a)d(clause.)20 b(Suc)o(h)12 b(a)f(pro)q(of)g(can)g(b)q(e)i(univ)o(ersally)g(v)o(eri\014ed)f(in)g Fi(O)q Fn(\(log)c Fi(n)p Fn(\))k(time)f(using)i(the)e(oracle)h(access)f (mec)o(hanism)0 2312 y(describ)q(ed)17 b(ab)q(o)o(v)o(e.)71 2369 y(Let)i Fi(L)f Fg(2)h Fm(NP)331 2348 y Fh(A)358 2369 y Fn(.)31 b(By)19 b(Lemma)g(2.1)f(there)h(is)g(an)g(unrelativized) i(reduction)f Fi(f)k Fn(mapping)19 b(an)g(input)h Fi(x)f Fn(to)0 2425 y(some)c(relativized)i(3CNF)e(form)o(ula)f Fi(\036)663 2432 y Fh(A)690 2425 y Fn(.)20 b(P)o(art)14 b(of)h(\005)g(will)i(con)o(tain)f(the)f(form)o(ula)g Fi(\036)1446 2432 y Fh(A)1488 2425 y Fn(as)g(w)o(ell)h(as)f(as)g(pro)q (of)g(that)0 2482 y Fi(\036)27 2489 y Fh(A)67 2482 y Fn(=)e Fi(f)5 b Fn(\()p Fi(x)p Fn(\).)19 b Fa(2)964 2828 y Fn(9)p eop %%Page: 10 10 10 9 bop 0 199 a Ff(5.3)56 b(Algebraic)18 b(Oracles)0 285 y Fn(Babai)11 b(and)g(F)l(ortno)o(w)f([BF91)o(])g(giv)o(e)h(an)g (algebraic)h(c)o(haracterization)f(of)f(v)m(arious)h(complexit)o(y)h (classes)f(and)g(argue)0 342 y(that)16 b(the)g(in)o(teractiv)o(e)h(pro) q(of)f(tak)o(e)f(adv)m(an)o(tage)h(of)g(this)h(c)o(haracterization.)23 b(This)17 b(algebraic)g(c)o(haracterization)0 398 y(also)e(do)q(es)h (not)e(seem)i(to)e(relativize.)71 454 y(In)g(this)h(section,)f(w)o(e)g (will)i(giv)o(e)e(additional)i(evidence)g(that)d(it)i(is)f(the)h (algebraic)g(prop)q(erties)f(of)g(complexit)o(y)0 511 y(classes)i(that)e(prev)o(en)o(t)h(the)g(relativization)i(of)e(in)o (teractiv)o(e)g(pro)q(of)g(results.)71 567 y(Let)g Fi(A)g Fn(b)q(e)g(an)o(y)g(function)g(mapping)h Fg(f)p Fn(0)p Fi(;)8 b Fn(1)p Fg(g)825 551 y Fc(\003)857 567 y Fn(to)14 b Fg(f)p Fn(0)p Fi(;)8 b Fn(1)p Fg(g)p Fn(.)18 b(Let)d Fi(A)1171 574 y Fh(n)1209 567 y Fn(b)q(e)g(that)f(function)i (restricted)f(to)g Fg(f)p Fn(0)p Fi(;)8 b Fn(1)p Fg(g)1917 551 y Fh(n)1937 567 y Fn(.)0 624 y(Let)15 b Fi(f)103 631 y Fh(n)141 624 y Fn(to)g(b)q(e)h(the)f(unique)i(m)o(ultilinear)g (extension)f(to)f Fi(A)1007 631 y Fh(n)1029 624 y Fn(.)71 680 y(Let)10 b Fg(h)p Fi(y)187 687 y Fl(1)206 680 y Fi(;)e(:)g(:)g(:)d (;)j(y)330 687 y Fh(k)350 680 y Fg(i)i Fn(b)q(e)h(a)f(standard)g (pairing)h(function)g(suc)o(h)g(that)f Fg(jh)p Fi(y)1220 687 y Fl(1)1238 680 y Fi(;)e(:)g(:)g(:)d(;)j(y)1362 687 y Fh(k)1382 680 y Fg(ij)k Fi(>)g Fg(j)p Fi(y)1507 687 y Fl(1)1526 680 y Fg(j)p Fn(+)p Fg(j)p Fi(y)1609 687 y Fl(2)1629 680 y Fg(j)p Fn(+)p Fg(j)p Fi(y)1712 687 y Fl(3)1731 680 y Fg(j)p Fn(+)p Fg(\001)c(\001)g(\001)p Fn(+)p Fg(j)p Fi(y)1904 687 y Fh(k)1925 680 y Fg(j)p Fn(.)71 737 y(F)l(or)14 b(an)o(y)h(set)g Fi(L)e Fg(\022)f Fn(\006)433 720 y Fc(\003)468 737 y Fn(w)o(e)i(de\014ne)j(the)e Fe(algebr)n(aic)g Fn(extension)h Fi(A)f Fn(of)g Fi(L)g Fn(inductiv)o(ely)i(in)f Fi(n)g Fn(as)f(follo)o(ws:)56 827 y(1.)22 b(Let)15 b Fi(f)5 b Fn(\()p Fi(x)266 834 y Fl(1)285 827 y Fi(;)j(:)g(:)g(:)t(;)g(x)412 834 y Fh(n)434 827 y Fn(\))15 b(b)q(e)h(the)f(unique)i(m)o(ultilinear)g(extension)f (of)f Fi(A)p Fn(\()p Fi(x)1317 834 y Fl(1)1343 827 y Fi(:)8 b(:)g(:)d(x)1429 834 y Fh(n)1452 827 y Fn(\).)56 920 y(2.)22 b(Let)15 b Fg(h)p Fn(0)p Fi(;)8 b(y)279 927 y Fl(1)297 920 y Fi(;)g(:)g(:)g(:)t(;)g(y)420 927 y Fh(n)442 920 y Fg(i)15 b Fn(b)q(e)h(in)g Fi(A)f Fn(i\013)h Fi(y)716 927 y Fl(1)742 920 y Fi(:)8 b(:)g(:)e(y)825 927 y Fh(n)863 920 y Fn(is)16 b(in)g Fi(L)p Fn(.)56 1012 y(3.)22 b(Let)15 b Fg(h)p Fn(1)p Fi(;)8 b(x)283 1019 y Fl(1)300 1012 y Fi(;)g(:)g(:)g(:)d(;)j(x)428 1019 y Fh(n)450 1012 y Fg(i)15 b Fn(b)q(e)h(in)g Fi(A)f Fn(if)h Fi(f)5 b Fn(\()p Fi(x)760 1019 y Fl(1)778 1012 y Fi(;)j(:)g(:)g(:)d(;)j(x)906 1019 y Fh(n)928 1012 y Fn(\))k Fi(>)h Fn(0.)56 1105 y(4.)22 b(Let)15 b Fg(h)p Fi(i)10 b Fn(+)g(2)p Fi(;)e(x)354 1112 y Fl(1)371 1105 y Fi(;)g(:)g(:)g(:)d(;)j(x)499 1112 y Fh(n)521 1105 y Fg(i)15 b Fn(b)q(e)h(in)g Fi(A)f Fn(if)h(the)f Fi(i)p Fn(th)g(bit)g(of)g Fi(f)5 b Fn(\()p Fi(x)1105 1112 y Fl(1)1124 1105 y Fi(;)j(:)g(:)g(:)t(;)g(x)1251 1112 y Fh(n)1273 1105 y Fn(\))15 b(is)h(one.)71 1195 y(Note)e(that)h Fi(L)g Fn(is)h(man)o(y-one)f(reducible)i(to)e Fi(A)p Fn(.)71 1252 y(Lund,)i(F)l(ortno)o(w,)d(Karlo\013)i(and)g(Nisan) g([LFKN92])g(and)g(Shamir)g([Sha92])f(sho)o(w)h(that)f(ev)o(ery)h (language)g(in)0 1308 y Fm(PSP)l(A)o(CE)i Fn(has)i(an)g(in)o(teractiv)o (e)h(pro)q(of.)34 b(This)21 b(result)f(do)q(es)h(not)f(relativize,)i(F) l(ortno)o(w)d(and)h(Sipser)h([FS88)o(])0 1365 y(sho)o(w)c(that)f (relativ)o(e)i(to)f(some)g(oracle)g Fi(A)p Fn(,)g(ev)o(en)h(co-)p Fm(NP)f Fn(do)q(es)h(not)e(ha)o(v)o(e)h(in)o(teractiv)o(e)h(pro)q(ofs.) 25 b(Ho)o(w)o(ev)o(er,)17 b(the)0 1421 y Fm(IP)12 b Fn(=)h Fm(PSP)l(A)o(CE)h Fn(result)h(do)q(es)h(hold)g(for)e(algebraic)i (extensions:)0 1512 y Fm(Theorem)f(5.6)22 b Fe(F)m(or)16 b Fi(A)h Fe(an)f(algebr)n(aic)g(extension)f(for)h(any)g(set)g Fi(L)d Fg(\022)g Fn(\006)1257 1495 y Fc(\003)1276 1512 y Fe(,)j Fm(IP)1361 1491 y Fh(A)1401 1512 y Fn(=)d Fm(PSP)l(A)o(CE)1655 1491 y Fh(A)1682 1512 y Fe(.)71 1602 y Fm(Pro)q(of)k(Sk)o(etc)o(h:)71 1659 y Fn(Instead)e(of)g(rep)q(eating)h(the)f(en)o(tire)h(pro)q(of)f (in)h([Sha92)o(],)e(w)o(e)h(will)i(just)e(describ)q(e)i(ho)o(w)e(to)f (mo)q(dify)i(it.)71 1715 y(W)l(e)f(use)i(the)e(relativized)j(form)o (ulae)e(describ)q(ed)h(in)g(Section)g(2.1.)j(W)l(e)c(arithmetized)h (the)f(form)o(ulas)f(in)i(the)0 1771 y(same)12 b(w)o(a)o(y)f(as)h(in)h ([Sha92])f(replacing)h Fi(A)p Fn(\()p Fi(x)729 1778 y Fh(j)r Fl(1)763 1771 y Fi(;)8 b(:)g(:)g(:)d(;)j(x)891 1778 y Fh(j)r(k)926 1771 y Fn(\))k(with)g Fi(f)5 b Fn(\()p Fi(x)1127 1778 y Fh(j)r Fl(1)1161 1771 y Fi(;)j(:)g(:)g(:)d(;)j(x)1289 1778 y Fh(j)r(k)1324 1771 y Fn(\).)19 b(Th)o(us)12 b(the)g (arithmetized)i(degree)0 1828 y(remains)i(lo)o(w)g(as)g(required.)24 b(A)o(t)15 b(the)h(end)h(of)f(the)g(proto)q(col)g(the)g(v)o(eri\014er)h (can)f(read)g(o\013)f(the)h(v)m(alues)h(of)f Fi(f)21 b Fn(using)0 1884 y(the)15 b(enco)q(ding)i(in)f(the)f(oracle)h Fi(A)p Fn(.)k Fa(2)71 1941 y Fn(F)l(rom)14 b(Theorem)h(5.6)f(w)o(e)h (immediately)i(ha)o(v)o(e)e(the)g(ha)o(v)o(e)g(the)g(follo)o(wing)h (corollary:)0 2031 y Fm(Corollary)i(5.7)k Fe(F)m(or)16 b(any)g(set)g Fi(L)g Fe(ther)n(e)g(is)g(an)g(or)n(acle)g Fi(A)h Fe(such)f(that)54 2122 y(1.)23 b Fi(L)16 b Fe(is)g(many-one)g(r) n(e)n(ducible)f(to)i Fi(A)f Fe(and)54 2214 y(2.)23 b Fm(IP)169 2193 y Fh(A)209 2214 y Fn(=)13 b Fm(PSP)l(A)o(CE)463 2193 y Fh(A)490 2214 y Fe(.)0 2336 y Ff(5.4)56 b(F)-5 b(urther)18 b(Questions)g(ab)r(out)h(In)n(teractiv)n(e)f(Pro)r(ofs)0 2421 y Fn(W)l(e)c(w)o(ould)g(lik)o(e)h(to)f(see)g(the)g(ideas)h(of)e (Section)i(5.3)e(applied)j(to)d(other)g(classes)i(based)f(on)g(the)g (in)o(teractiv)o(e)g(pro)q(of)0 2478 y(system)c(suc)o(h)h(as)f(m)o (ultiple)i(pro)o(v)o(er)e(in)o(teractiv)o(e)h(pro)q(of)f(systems)g(and) h(probabilistically)i(c)o(hec)o(k)m(able)g(pro)q(ofs.)k(This)0 2534 y(ma)o(y)10 b(lead)i(to)e(ev)o(en)h(more)f(evidence)j(of)d(an)h (algebraic)h(prop)q(ert)o(y)e(that)g(is)h(the)g(main)g(cause)g(of)g (the)g(nonrelativizing)0 2591 y(nature)k(of)g(these)g(results.)71 2647 y(Ho)o(w)o(ev)o(er,)21 b(giv)o(en)g(what)f(w)o(e)h(ha)o(v)o(e)g (seen)g(in)h(Section)g(5.2,)f(w)o(e)f(ma)o(y)g(question)i(the)f(usual)h (oracle)f(access)0 2704 y(mec)o(hanisms)d(used)h(in)g(these)f(mo)q (dels.)28 b(W)l(e)18 b(think)h(the)f(oracle)g(access)g(mec)o(hanism)h (used)f(in)h Fm(PCP)o Fn(\(log)8 b Fi(n;)g Fn(1\))952 2828 y(10)p eop %%Page: 11 11 11 10 bop 0 199 a Fn(w)o(orks)15 b(\014ne)i(b)q(ecause)g(the)f(v)o (eri\014er)h(is)g(allo)o(w)o(ed)f(to)g(run)g(in)h(p)q(olynomial)h (time.)23 b(Ho)o(w)o(ev)o(er,)15 b(time)i(ma)o(y)e(pro)o(v)o(e)h(us)0 256 y(wrong.)71 312 y(The)d(access)g(mec)o(hanism)g(used)h(b)o(y)f(F)l (ortno)o(w,)f(Romp)q(el)i(and)f(Sipser)h([FRS88)o(])f(is)g(almost)g (surely)h(the)f(wrong)0 369 y(one.)27 b(If)18 b(one)g(thinks)h(ab)q (out)e(m)o(ultiple-pro)o(v)o(ers)i(as)e Fg([)942 376 y Fh(j)r(>)p Fl(0)1002 369 y Fm(PCP)p Fn(\()p Fi(n)1157 352 y Fh(j)1174 369 y Fi(;)8 b(n)1222 352 y Fh(j)1239 369 y Fn(\))17 b(then)h(w)o(e)g(see)g(the)g(pro)q(of)f(migh)o(t)g(ha)o (v)o(e)0 425 y(exp)q(onen)o(tial)h(size)f(and)f(th)o(us)g(describ)q(e)i (exp)q(onen)o(tial)g(strings)e(in)h(the)f(oracle.)23 b(It)16 b(is)h(not)f(clear)g(ho)o(w)g(to)f(extend)0 482 y(the)d(access)g(mec)o(hanism.)20 b(One)12 b(simple)i(but)e(w)o(ork)m (able)g(suggestion)g(is)h(to)e(ha)o(v)o(e)h(the)g(v)o(eri\014er)g(run)h (in)f(exp)q(onen)o(tial)0 538 y(time.)71 594 y(It)i(should)h(b)q(e)g (noted)f(ho)o(w)o(ev)o(er)g(that)f(ev)o(en)i(if)g(the)f(v)o(eri\014er)h (is)f(giv)o(en)h(access)g(to)e(exp)q(onen)o(tially)k(long)d(strings)0 651 y(in)h(the)g(oracle,)f(there)h(will)h(still)f(b)q(e)h(an)e(oracle)g Fi(A)h Fn(suc)o(h)g(that)e(co-)p Fm(NP)1198 630 y Fh(A)1238 651 y Fg(6\022)g Fm(MIP)1391 630 y Fh(A)1418 651 y Fn(.)19 b(W)l(e)c(can)f(easily)i(mo)q(dify)f(the)0 707 y(pro)q(of)j(of)g(F)l (ortno)o(w,)f(Romp)q(el)j(and)e(Sipser)h([FRS88])f(so)g(all)h(the)f (diagonalizations)i(o)q(ccur)f(on)f(exp)q(onen)o(tially)0 764 y(distan)o(t)d(lengths)h(with)f(the)h(oracle)f(empt)o(y)g(in)h(b)q (et)o(w)o(een.)71 820 y(Because)e(of)g(the)g(di\016cult)o(y)h(in)g (creating)f(an)g(oracle)g Fi(A)g Fn(suc)o(h)h(that)e Fm(PCP)o Fn(\(log)8 b Fi(n;)g Fn(1\))1505 804 y Fh(A)1544 820 y Fn(=)13 b Fm(EXP)1701 799 y Fh(A)1728 820 y Fn(,)h(w)o(e)g (should)0 877 y(con)o(tin)o(ue)j(to)e(try)h(to)g(sho)o(w)f(that)h Fm(PCP)o Fn(\(log)8 b Fi(n;)g Fn(1\))13 b Fg(6)p Fn(=)i Fm(EXP)h Fn(and)g(th)o(us)g Fm(NP)e Fg(6)p Fn(=)h Fm(EXP)o Fn(.)23 b(W)l(e)17 b(should)g(also)f(see)g(if)0 933 y(some)d (di\013eren)o(t)g(assumption,)h(lik)o(e)g(a)f(suitably)h(strong)e (one-w)o(a)o(y)g(function,)i(w)o(ould)g(allo)o(w)f(us)g(to)g(\014nd)h (an)f(oracle)0 990 y(relativ)o(e)j(to)e(whic)o(h)i Fm(PCP)p Fn(\(log)8 b Fi(n;)g Fn(1\))630 973 y Fh(A)668 990 y Fn(=)13 b Fm(EXP)826 969 y Fh(A)853 990 y Fn(.)0 1133 y Fo(6)67 b(Random)21 b(and)h(Generic)h(Oracles)0 1234 y Fn(In)18 b(1981,)f(Bennet)i(and)f(Gill)h([BG81)o(])e(lo)q(ok)o(ed)i (at)e(what)g(happ)q(ens)i(when)f(w)o(e)g(c)o(ho)q(ose)f(the)h(oracles)g (randomly:)0 1291 y(decide)k(for)d(eac)o(h)h(string)g(whether)g(or)f (not)g(it)i(should)f(b)q(e)h(in)g(the)f(oracle)g(indep)q(enden)o(tly)j (with)d(probabilit)o(y)0 1347 y(one-half.)k(W)l(e)16 b(sa)o(y)f(a)h(statemen)o(t)f Fi(S)k Fe(holds)e(with)h(pr)n(ob)n (ability)e(one)g Fn(if)h(the)f(set)g(of)g(oracles)g(relativ)o(e)h(to)e (whic)o(h)j Fi(S)0 1404 y Fn(holds)e(has)g(measure)g(one.)21 b(F)l(rom)15 b(measure)h(theory)f(w)o(e)h(ha)o(v)o(e)f(a)g(w)o (onderful)i(zero-one)e(la)o(w:)21 b(for)15 b(virtually)i(an)o(y)0 1460 y(complexit)o(y)h(theory)e(statemen)o(t)g Fi(S)s Fn(,)g(w)o(e)h(kno)o(w)f(that)h Fi(S)i Fn(holds)f(with)f(either)g (probabilit)o(y)i(zero)d(or)h(probabilit)o(y)0 1517 y(one.)71 1573 y(Bennet)h(and)g(Gill)i(conjectured)e(the)g Fe(r)n(andom)h(or)n (acle)g(hyp)n(othesis)e Fn(roughly)i(stated)e(as)g(\\if)i(a)e (complexit)o(y)0 1629 y(statemen)o(t)10 b(holds)j(with)f(a)f(random)g (oracle)h(with)f(probabilit)o(y)i(one)f(then)g(it)g(holds)g(in)g(the)g (unrelativized)i(w)o(orld".)0 1686 y(The)h(random)f(oracle)h(h)o(yp)q (othesis)g(has)g(great)e(app)q(eal.)21 b(In)o(tuitiv)o(ely)16 b(it)f(seems)g(righ)o(t:)k(W)l(e)c(ough)o(t)f(to)g(b)q(e)h(able)h(to)0 1742 y(sim)o(ulate)g(a)f(random)f(oracle)i(with)f(a)g(suitably)i (strong)d(pseudorandom)h(n)o(um)o(b)q(er)h(generator.)71 1799 y(Kurtz)11 b([Kur83)o(])g(sho)o(w)o(ed)g(that)f(the)h(form)o (ulation)g(of)g(the)g(random)f(oracle)i(h)o(yp)q(othesis)f(giv)o(en)h (b)o(y)f(Bennet)h(and)0 1855 y(Gill)i(w)o(as)f(false.)19 b(Other)13 b(coun)o(terexamples)h(come)f(from)f(the)h(area)g(of)f(in)o (teractiv)o(e)i(pro)q(ofs)e([CGH90)o(,)g(HCRR90)q(].)0 1912 y(Despite)18 b(these)g(examples,)h(man)o(y)e(complexit)o(y)i (theorists)f(still)h(b)q(eliev)o(e)h(that)d(some)g(v)o(ersion)h(of)g (the)f(random)0 1968 y(oracle)k(h)o(yp)q(othesis.)38 b(W)l(e)22 b(ho)o(w)o(ev)o(er)e(w)o(ould)h(lik)o(e)h(to)f(argue)f(that) h(w)o(e)f(should)i(not)f(ha)o(v)o(e)g(ev)o(er)g(b)q(eliev)o(ed)i(the)0 2025 y(random)15 b(oracle)g(h)o(yp)q(othesis)h(in)g(the)g(\014rst)e (place.)71 2081 y(Kolmogoro)o(v)i(complexit)o(y)j(tells)f(us)g(that)f (a)g(\\random")g(set)g Fi(R)h Fn(will)h(con)o(tain)f(lots)f(of)h (information.)27 b(It)17 b(is)0 2138 y(true)i(that)g(for)g(a)g(\014xed) h(set)f Fi(L)p Fn(,)h(lo)q(oking)g(at)f(a)g(random)f Fi(R)i Fn(ma)o(y)e(not)h(greatly)g(a\013ect)g(the)g(complexit)o(y)i(of) d Fi(L)p Fn(.)0 2194 y(Ho)o(w)o(ev)o(er)12 b(the)h(theory)f(of)h (random)f(oracles)h(w)o(orks)f(in)i(the)f(other)g(direction.)20 b(First)13 b(w)o(e)f(\014x)h(the)g(set)g Fi(R)p Fn(.)19 b(Then)13 b(w)o(e)0 2250 y(can)h(lo)q(ok)g(at)f(a)g(language)h Fi(L)g Fn(designed)h(to)e(tak)o(e)g(adv)m(an)o(tage)g(of)g(the)h (information)g(in)g Fi(R)p Fn(.)20 b(F)l(or)13 b(example,)h(Bennet)0 2307 y(and)j(Gill)i([BG81)o(])d(create)h(a)g(language)g Fi(L)f Fg(2)f Fm(NP)872 2286 y Fh(R)911 2307 y Fg(\000)c Fm(P)993 2286 y Fh(R)1037 2307 y Fn(that)17 b(tak)o(es)f(adv)m(an)o (tage)g(of)h(the)g(fact)f(that)h(some)f(of)0 2363 y(the)f(information)h (in)g Fi(R)f Fn(can)g(b)q(e)h(accessed)g(nondeterministically)i(but)d (not)g(deterministically)l(.)71 2420 y(Since)d(an)g(empt)o(y)f(oracle)g (do)q(es)h(not)f(con)o(tain)g(an)o(y)g(information,)h(there)f(is)h(no)f (reason)g(to)g(b)q(eliev)o(e)i(that)e(results)0 2476 y(ab)q(out)j(random)g(oracles)h(should)g(carry)f(o)o(v)o(er)f(to)h(the) h(unrelativized)h(w)o(orld.)k(If)15 b(w)o(e)f(kno)o(w)g(that)f(a)h (statemen)o(t)g Fi(S)0 2533 y Fn(holds)k(with)f(probabilit)o(y)h(one,)f (w)o(e)f(should)i(not)e(infer)i(an)o(ything)f(ab)q(out)g(the)f (statemen)o(t)g Fi(S)j Fn(other)e(than)g(what)0 2589 y(w)o(e)e(can)g(infer)h(from)f(the)g(fact)g(that)f(there)h(exists)h(an) f(oracle)g(where)h Fi(S)h Fn(holds)f(\(see)g(Section)g(3\).)71 2646 y(W)l(e)11 b(kno)o(w)g(that)f(all)j(the)e(de\014nable)i(statemen)o (ts)d(that)h(hold)h(with)f(probabilit)o(y)i(one)e(all)h(hold)h(sim)o (ultaneously)0 2702 y(with)g(probabilit)o(y)g(one.)19 b(Th)o(us)13 b(random)f(oracles)g(giv)o(e)h(us)g(a)f(nice)h (relativized)i(w)o(orld)d(where)h(sev)o(eral)f(in)o(teresting)952 2828 y(11)p eop %%Page: 12 12 12 11 bop 0 199 a Fn(complexit)o(y)17 b(theory)f(statemen)o(ts)e(all)j (hold)g(at)f(the)g(same)f(time.)23 b(Ho)o(w)o(ev)o(er,)15 b(a)h(m)o(uc)o(h)g(more)f(p)q(o)o(w)o(erful)i(to)q(ol)f(for)0 256 y(suc)o(h)g(purp)q(oses)f(is)h(the)f(theory)g(of)g(generic)h (oracles.)71 312 y(Generic)f(oracles)f(allo)o(w)h(us)f(to)g(com)o(bine) h(di\013eren)o(t)f(oracle)h(requiremen)o(ts)f(in)h(a)f(clean)i(manner.) j(They)c(giv)o(e)0 369 y(us)c(v)o(ery)g(p)q(o)o(w)o(erful)g(to)q(ols)g (in)g(dev)o(eloping)i(oracles.)19 b(F)l(enner,)12 b(F)l(ortno)o(w)d (and)i(Kurtz)g([FFK92)o(])g(use)g(generic)h(oracles)0 425 y(to)j(dev)o(elop)h(a)f(relativized)j(w)o(orld)d(where)h(the)g (isomorphism)g(conjecture)f(holds,)h(answ)o(ering)g(a)f(long-standing)0 482 y(op)q(en)k(question.)30 b(Space)19 b(limitations)g(prev)o(en)o(t)f (us)h(from)e(giving)j(more)d(details)j(ab)q(out)e(generic)h(oracles)g (here)0 538 y(but)c(for)g(the)g(in)o(terested)h(reader)f(w)o(e)g (recommend)h([BI87)o(,)f(FFKL93,)f(FR93].)0 681 y Fo(7)67 b(Conclusions)22 b(and)h(Other)g(Questions)0 783 y Fn(Hop)q(efully)l(,) 17 b(this)e(pap)q(er)h(will)h(con)o(vince)f(the)f(reader)g(of)g(the)g (man)o(y)g(and)g(v)m(aried)h(uses)f(of)g(relativization)i(results)0 839 y(if)d(done)g(prop)q(erly)l(.)20 b(The)14 b(area)f(of)g (relativization)i(remains)f(a)f(v)o(ery)g(imp)q(ortan)o(t)g(and)h (activ)o(e)f(area)g(of)g(complexit)o(y)0 896 y(theory)l(.)28 b(W)l(e)17 b(caution)i(researc)o(hers)e(in)i(the)f(area)f(though)h(to)f (k)o(eep)h(in)h(mind)f(the)g(limitations)i(men)o(tioned)e(in)0 952 y(Sections)e(4)f(and)g(5.)20 b(Also,)15 b(theorists)g(m)o(ust)f (remem)o(b)q(er)i(that)e(oracles)h(results)h(are)f(a)g(to)q(ol.)20 b(Theorems)14 b(strictly)0 1008 y(ab)q(out)h(the)g(structure)g(of)g (oracles)g(should)i(b)q(e)e(discouraged.)71 1065 y(Although)20 b(w)o(e)f(do)h(not)f(kno)o(w)h(ho)o(w)f(to)g(settle)h(man)o(y)f(imp)q (ortan)o(t)h(complexit)o(y)g(theory)g(statemen)o(ts,)f(the)0 1121 y(opp)q(osite)i(is)f(true)g(in)g(relativized)i(w)o(orlds.)34 b(F)l(or)19 b(most)h(imp)q(ortan)o(t)f(complexit)o(y)i(theory)e (statemen)o(ts)g Fi(S)s Fn(,)h(w)o(e)0 1178 y(either)14 b(kno)o(w)e(ho)o(w)h(to)f(pro)o(v)o(e)h Fi(S)i Fn(or)e(sho)o(w)f(that)h Fi(S)i Fn(do)q(es)e(not)g(hold)h(in)g(some)f(relativized)i(w)o(orld.)k (W)l(e)13 b(th)o(us)g(w)o(ould)0 1234 y(lik)o(e)j(to)f(end)h(this)f (pap)q(er)h(with)g(t)o(w)o(o)d(in)o(teresting)j(exceptions:)56 1328 y(1.)22 b(Do)q(es)15 b Fm(P)d Fn(=)h Fm(UP)i Fn(and)g Fm(NP)e Fn(=)g(co-)p Fm(NP)i Fn(imply)h(that)f Fm(P)d Fn(=)h Fm(NP)p Fn(?)20 b(\(See)c([HS92)o(]\))56 1422 y(2.)22 b(Do)q(es)15 b(the)g(isomorphism)h(conjecture)f(imply)i(that)d (there)i(are)e(no)i(one-w)o(a)o(y)e(functions?)22 b(\(See)15 b([FFK92)o(]\))0 1565 y Fo(Ac)n(kno)n(wledgmen)n(ts)0 1667 y Fn(This)h(pap)q(er)h(grew)e(out)h(of)f(an)h(informal)g(debate)g (with)h(Russell)g(Impagliazzo)g(on)f(relativization)h(results)g(held)0 1723 y(at)d(the)g(Eigh)o(th)h(Ann)o(ual)h(Structures)e(in)h(Complexit)o (y)g(Theory)g(Conference)g(that)f(w)o(as)f(part)h(of)g(the)h(F)l (ederated)0 1780 y(Computing)h(Researc)o(h)h(Conference)f(in)h(San)g (Diego)f(in)h(Ma)o(y)l(,)e(1993.)21 b(I)c(thank)f(the)g(Structures)g (program)f(and)0 1836 y(conference)20 b(committees,)f(particularly)h (Stev)o(e)e(Homer,)h(in)h(organizing)f(the)g(debate.)30 b(I)19 b(w)o(ould)g(also)g(lik)o(e)h(to)0 1892 y(thank)15 b(Russell)i(Impagliazzo)f(for)f(in)o(teresting)h(discussion)h(b)q (efore)e(and)h(during)g(the)f(debate.)71 1949 y(I)d(ha)o(v)o(e)f(also)h (had)g(sev)o(eral)g(in)o(teresting)h(discussion)g(ab)q(out)f(oracles)g (and)g(pro)q(of)f(c)o(hec)o(king)i(with)f(man)o(y)f(p)q(eople)0 2005 y(including)20 b(Sanjeev)e(Arora,)f(L\023)-23 b(aszl\023)g(o)18 b(Babai,)g(Ric)o(hard)g(Beigel,)h(Joan)f(F)l(eigen)o(baum,)g(Stuart)f (Kurtz,)h(Carsten)0 2062 y(Lund,)13 b(Muli)g(Safra)f(and)g(Mik)o(e)g (Sipser.)20 b(Stuart)11 b(Kurtz)h(w)o(as)f(particularly)i(helpful)h(in) f(Section)g(5.2.)k(The)c(author)0 2118 y(based)j(Section)g(3.2)e(on)h (discussions)i(with)e(Mik)o(e)h(Sipser.)0 2261 y Fo(References)0 2363 y Fn([AIV92])87 b(S.)19 b(Arora,)f(R.)h(Impagliazzo,)h(and)f(U.)f (V)l(azirani.)31 b(Relativizing)21 b(v)o(ersus)e(nonrelativizing)i(tec) o(h-)243 2419 y(niques:)k(The)17 b(role)g(of)f(lo)q(cal)i(c)o(hec)o(k)m (abilit)o(y)l(.)27 b(Man)o(uscript,)17 b(Univ)o(ersit)o(y)g(of)g (California,)g(Berk)o(eley)l(,)243 2476 y(1992.)0 2570 y([ALM)117 2553 y Fl(+)144 2570 y Fn(92])40 b(S.)19 b(Arora,)f(C.)h (Lund,)h(R.)f(Mot)o(w)o(ani,)f(M.)g(Sudan,)i(and)f(M.)f(Szegedy)l(.)32 b(Pro)q(of)18 b(v)o(eri\014cation)i(and)243 2626 y(hardness)c(of)g (appro)o(ximation)f(problems.)22 b(In)16 b Fe(Pr)n(o)n(c)n(e)n(e)n (dings)f(of)i(the)g(33r)n(d)g(IEEE)e(Symp)n(osium)i(on)243 2683 y(F)m(oundations)f(of)g(Computer)h(Scienc)n(e)p Fn(,)c(pages)i(14{23.)f(IEEE,)h(New)g(Y)l(ork,)g(1992.)952 2828 y(12)p eop %%Page: 13 13 13 12 bop 0 199 a Fn([AS92])112 b(S.)14 b(Arora)g(and)g(S.)g(Safra.)k (Probabilistic)e(c)o(hec)o(king)f(of)f(pro)q(ofs:)19 b(A)14 b(new)g(c)o(haracterization)h(of)e(NP.)243 256 y(In)22 b Fe(Pr)n(o)n(c)n(e)n(e)n(dings)e(of)i(the)g(33r)n(d)g(IEEE)f (Symp)n(osium)h(on)f(F)m(oundations)g(of)h(Computer)h(Scienc)n(e)p Fn(,)243 312 y(pages)15 b(2{13.)f(IEEE,)h(New)g(Y)l(ork,)g(1992.)0 402 y([Bab85])91 b(L.)21 b(Babai.)38 b(T)l(rading)21 b(group)f(theory)h(for)f(randomness.)37 b(In)21 b Fe(Pr)n(o)n(c)n(e)n (e)n(dings)e(of)j(the)g(17th)g(A)o(CM)243 459 y(Symp)n(osium)17 b(on)f(the)g(The)n(ory)g(of)h(Computing)p Fn(,)e(pages)g(421{429.)d(A)o (CM,)j(New)g(Y)l(ork,)f(1985.)0 549 y([Bab90])91 b(L.)17 b(Babai.)25 b(E-mail)18 b(and)f(the)g(unexp)q(ected)i(p)q(o)o(w)o(er)d (of)g(in)o(teraction.)26 b(In)17 b Fe(Pr)n(o)n(c)n(e)n(e)n(dings)e(of)j (the)g(5th)243 605 y(IEEE)12 b(Structur)n(e)g(in)g(Complexity)g(The)n (ory)h(Confer)n(enc)n(e)p Fn(,)c(pages)i(30{44.)e(IEEE,)h(New)h(Y)l (ork,)g(1990.)0 696 y([BF91])109 b(L.)19 b(Babai)f(and)h(L.)f(F)l (ortno)o(w.)27 b(Arithmetization:)g(A)18 b(new)h(metho)q(d)f(in)h (structural)f(complexit)o(y)243 752 y(theory)l(.)i Fe(Computational)d (Complexity)p Fn(,)d(1\(1\):41{66,)e(1991.)0 842 y([BFL91])81 b(L.)12 b(Babai,)h(L.)f(F)l(ortno)o(w,)f(and)h(C.)f(Lund.)16 b(Non-deterministic)e(exp)q(onen)o(tial)g(time)e(has)g(t)o(w)o(o-pro)o (v)o(er)243 899 y(in)o(teractiv)o(e)k(proto)q(cols.)k Fe(Computational)d(Complexity)p Fn(,)d(1\(1\):3{40,)e(1991.)0 989 y([BFLS91])56 b(L.)16 b(Babai,)g(L.)f(F)l(ortno)o(w,)f(L.)i(Levin,) g(and)g(M.)f(Szegedy)l(.)22 b(Chec)o(king)16 b(computations)g(in)g(p)q (olyloga-)243 1045 y(rithmic)d(time.)i(In)d Fe(Pr)n(o)n(c)n(e)n(e)n (dings)f(of)i(the)g(23r)n(d)h(A)o(CM)e(Symp)n(osium)h(on)g(the)g(The)n (ory)g(of)g(Computing)p Fn(,)243 1102 y(pages)i(21{31.)f(A)o(CM,)g(New) h(Y)l(ork,)g(1991.)0 1192 y([BG81])103 b(C.)18 b(Bennet)i(and)e(J.)h (Gill.)31 b(Relativ)o(e)19 b(to)f(a)g(random)h(oracle,)g Fi(P)1363 1175 y Fh(A)1408 1192 y Fg(6)p Fn(=)g Fi(N)5 b(P)1539 1175 y Fh(A)1584 1192 y Fg(6)p Fn(=)19 b Fi(co)12 b Fg(\000)g Fi(N)5 b(P)1816 1175 y Fh(A)1862 1192 y Fn(with)243 1248 y(probabilit)o(y)17 b(one.)j Fe(SIAM)15 b(Journal)h(on)g (Computing)p Fn(,)f(10:96{113,)d(1981.)0 1339 y([BGKW88])21 b(M.)h(Ben-Or,)i(S.)f(Goldw)o(asser,)g(J.)f(Kilian,)k(and)c(A.)g (Wigderson.)41 b(Multi-pro)o(v)o(er)23 b(in)o(teractiv)o(e)243 1395 y(pro)q(ofs:)k(Ho)o(w)19 b(to)f(remo)o(v)o(e)g(in)o(tractabilit)o (y)i(assumptions.)32 b(In)19 b Fe(Pr)n(o)n(c)n(e)n(e)n(dings)f(of)i (the)g(20th)g(A)o(CM)243 1451 y(Symp)n(osium)d(on)f(the)g(The)n(ory)g (of)h(Computing)p Fn(,)e(pages)g(113{131.)d(A)o(CM,)j(New)g(Y)l(ork,)f (1988.)0 1542 y([BGS75])78 b(T.)20 b(Bak)o(er,)g(J.)g(Gill,)j(and)d(R.) g(Solo)o(v)m(a)o(y)l(.)34 b(Relativizations)22 b(of)e(the)g(P)g(=)g(NP) h(question.)34 b Fe(SIAM)243 1598 y(Journal)17 b(on)f(Computing)p Fn(,)f(4\(4\):431{44)o(2,)d(1975.)0 1688 y([BI87])123 b(M.)14 b(Blum)h(and)f(R.)g(Impagliazzo.)19 b(Generic)c(oracles)g(and)f (oracle)g(classes.)19 b(In)c Fe(Pr)n(o)n(c)n(e)n(e)n(dings)d(of)k(the) 243 1745 y(28th)22 b(IEEE)d(Symp)n(osium)i(on)f(F)m(oundations)g(of)g (Computer)h(Scienc)n(e)p Fn(,)e(pages)h(118{126.)d(IEEE,)243 1801 y(New)f(Y)l(ork,)e(1987.)0 1891 y([BM88])97 b(L.)21 b(Babai)h(and)f(S.)g(Moran.)36 b(Arth)o(ur-Merlin)22 b(games:)30 b(a)21 b(randomized)h(pro)q(of)f(system,)g(and)g(a)243 1948 y(hierarc)o(h)o(y)15 b(of)e(complexit)o(y)i(classes.)j Fe(Journal)d(of)g(Computer)h(and)f(System)f(Scienc)n(es)p Fn(,)e(36\(2\):254{)243 2004 y(276,)i(1988.)0 2094 y([BRS91])81 b(R.)11 b(Beigel,)i(N.)d(Reingold,)j(and)e(D.)f(Spielman.)k(PP)c(is)h (closed)h(under)f(in)o(tersection.)i(In)e Fe(Pr)n(o)n(c)n(e)n(e)n (dings)243 2151 y(of)j(the)f(23r)n(d)h(A)o(CM)e(Symp)n(osium)h(on)g (the)g(The)n(ory)g(of)h(Computing)p Fn(,)e(pages)f(1{9.)g(A)o(CM,)g (New)h(Y)l(ork,)243 2207 y(1991.)0 2297 y([Bus88])96 b(J.)18 b(Buss.)28 b(Relativized)21 b(alternation)d(and)g(space-b)q (ounded)i(computations.)27 b Fe(Journal)19 b(of)g(Com-)243 2354 y(puter)e(and)g(System)e(Scienc)n(es)p Fn(,)e(36\(3\):351{378)o(,) f(1988.)0 2444 y([CGH90])68 b(B.)27 b(Chor,)h(O.)f(Goldreic)o(h,)j(and) c(J.)h(H)-6 b(\027)-28 b(astad.)53 b(The)27 b(random)f(oracle)h(h)o(yp) q(othesis)g(is)g(false.)243 2501 y(Man)o(uscript,)15 b(T)l(ec)o(hnion,)h(Haifa,)f(Israel,)h(1990.)0 2591 y([Cha90])90 b(R.)23 b(Chang.)40 b(An)23 b(example)g(of)f(a)g(theorem)g(that)f(has)i (con)o(tradictory)e(relativizations)j(and)e(a)243 2647 y(diagonalization)c(pro)q(of.)j Fe(Bul)r(letin)16 b(of)h(the)g(Eur)n (op)n(e)n(an)f(Asso)n(ciation)g(for)h(The)n(or)n(etic)n(al)e(Computer) 243 2704 y(Scienc)n(e)p Fn(,)f(42:172{173,)d(Octob)q(er)16 b(1990.)952 2828 y(13)p eop %%Page: 14 14 14 13 bop 0 199 a Fn([Co)q(o71])91 b(S.)20 b(Co)q(ok.)31 b(The)20 b(complexit)o(y)g(of)f(theorem-pro)o(ving)g(pro)q(cedures.)33 b(In)20 b Fe(Pr)n(o)n(c)n(e)n(e)n(dings)e(of)i(the)h(3r)n(d)243 256 y(A)o(CM)14 b(Symp)n(osium)g(on)g(the)h(The)n(ory)f(of)h(Computing) p Fn(,)e(pages)g(151{158.)e(A)o(CM,)h(New)h(Y)l(ork,)g(1971.)0 350 y([FFK92])76 b(S.)19 b(F)l(enner,)h(L.)f(F)l(ortno)o(w,)f(and)h(S.) g(Kurtz.)31 b(The)20 b(isomorphism)f(conjecture)g(holds)h(relativ)o(e)g (to)243 406 y(an)d(oracle.)26 b(In)18 b Fe(Pr)n(o)n(c)n(e)n(e)n(dings)d (of)j(the)h(33r)n(d)f(IEEE)f(Symp)n(osium)h(on)g(F)m(oundations)f(of)h (Computer)243 462 y(Scienc)n(e)p Fn(,)c(pages)h(30{39.)e(IEEE,)i(New)g (Y)l(ork,)g(1992.)0 556 y([FFKL93])48 b(S.)15 b(F)l(enner,)g(L.)f(F)l (ortno)o(w,)f(S.)h(Kurtz,)h(and)f(L.)h(Li.)20 b(An)15 b(oracle)f(builder's)i(to)q(olkit.)j(In)c Fe(Pr)n(o)n(c)n(e)n(e)n (dings)243 613 y(of)21 b(the)g(8th)g(IEEE)e(Structur)n(e)i(in)f (Complexity)g(The)n(ory)g(Confer)n(enc)n(e)p Fn(,)e(pages)i(120{131.)d (IEEE,)243 669 y(New)f(Y)l(ork,)e(1993.)0 763 y([FR93])108 b(L.)17 b(F)l(ortno)o(w)e(and)i(J.)f(Rogers.)24 b(Separabilit)o(y)18 b(and)f(one-w)o(a)o(y)f(functions.)25 b(T)l(ec)o(hnical)18 b(Rep)q(ort)f(CS)243 819 y(93-14,)d(Univ)o(ersit)o(y)i(of)f(Chicago)g (Departmen)o(t)f(of)h(Computer)g(Science,)i(1993.)0 913 y([FRS88])83 b(L.)23 b(F)l(ortno)o(w,)g(J.)g(Romp)q(el,)i(and)e(M.)f (Sipser.)44 b(On)23 b(the)g(p)q(o)o(w)o(er)f(of)h(m)o(ulti-pro)o(v)o (er)g(in)o(teractiv)o(e)243 970 y(proto)q(cols.)17 b(In)d Fe(Pr)n(o)n(c)n(e)n(e)n(dings)e(of)j(the)g(3r)n(d)g(IEEE)e(Structur)n (e)i(in)g(Complexity)f(The)n(ory)g(Confer)n(enc)n(e)p Fn(,)243 1026 y(pages)h(156{161.)e(IEEE,)i(New)g(Y)l(ork,)g(1988.)0 1120 y([FS88])116 b(L.)17 b(F)l(ortno)o(w)f(and)h(M.)f(Sipser.)27 b(Are)17 b(there)g(in)o(teractiv)o(e)g(proto)q(cols)g(for)g(co-NP)g (languages?)35 b Fe(In-)243 1176 y(formation)17 b(Pr)n(o)n(c)n(essing)d (L)n(etters)p Fn(,)g(28:249{251,)e(1988.)0 1270 y([GJ79])112 b(M.)15 b(R.)h(Garey)f(and)g(D.)g(S.)h(Johnson.)21 b Fe(Computers)c(and)f(intr)n(actability.)g(A)h(Guide)g(to)g(the)g(the)n (ory)243 1327 y(of)g(NP-c)n(ompleteness)p Fn(.)h(W.)c(H.)h(F)l(reeman)g (and)h(Compan)o(y)l(,)e(New)h(Y)l(ork,)g(1979.)0 1421 y([GJ86])112 b(J.)13 b(Goldsmith)g(and)g(D.)f(Joseph.)k(Three)d (results)g(on)g(the)f(p)q(olynomial)j(isomorphism)e(of)f(complete)243 1477 y(sets.)i(In)e Fe(Pr)n(o)n(c)n(e)n(e)n(dings)f(of)i(the)g(27th)h (IEEE)d(Symp)n(osium)i(on)g(F)m(oundations)f(of)h(Computer)h(Scienc)n (e)p Fn(,)243 1533 y(pages)h(390{397.)e(IEEE,)i(New)g(Y)l(ork,)g(1986.) 0 1627 y([GMR89])60 b(S.)20 b(Goldw)o(asser,)g(S.)g(Micali,)j(and)d(C.) f(Rac)o(k)o(o\013.)33 b(The)21 b(kno)o(wledge)f(complexit)o(y)h(of)f (in)o(teractiv)o(e)243 1684 y(pro)q(of-systems.)f Fe(SIAM)c(Journal)i (on)f(Computing)p Fn(,)f(18\(1\):186{2)o(08,)d(1989.)0 1778 y([GS89])110 b(S.)20 b(Goldw)o(asser)f(and)h(M.)f(Sipser.)35 b(Priv)m(ate)20 b(coins)g(v)o(ersus)g(public)i(coins)e(in)h(in)o (teractiv)o(e)f(pro)q(of)243 1834 y(systems.)f(In)d(S.)e(Micali,)i (editor,)f Fe(R)n(andomness)g(and)h(Computation)p Fn(,)f(v)o(olume)g(5) g(of)f Fe(A)n(dvanc)n(es)h(in)243 1890 y(Computing)i(R)n(ese)n(ar)n(ch) p Fn(,)d(pages)h(73{90.)e(JAI)j(Press,)f(Green)o(wic)o(h,)g(1989.)0 1984 y([Har78])96 b(J.)17 b(Hartmanis.)22 b Fe(F)m(e)n(asible)16 b(Computations)h(and)g(Pr)n(ovable)g(Complexity)g(Pr)n(op)n(erties)p Fn(,)f(v)o(olume)h(30)243 2041 y(of)e Fe(CBMS-NSF)f(R)n(e)n(gional)h (Confer)n(enc)n(e)f(Series)h(in)h(Mathematics)p Fn(.)j(So)q(ciet)o(y)d (for)e(Industrial)j(and)243 2097 y(Applied)h(Mathematics,)c (Philadelphi)q(a,)j(1978.)0 2191 y([Har85])96 b(J.)15 b(Hartmanis.)j(Solv)m(able)e(problems)f(with)g(con\015icting)h (relativizations.)k Fe(Bul)r(letin)15 b(of)h(the)f(Eur)n(o-)243 2247 y(p)n(e)n(an)h(Asso)n(ciation)f(for)i(The)n(or)n(etic)n(al)e (Computer)i(Scienc)n(e)p Fn(,)c(27:40{49,)f(Octob)q(er)k(1985.)0 2341 y([H)-6 b(\027)-28 b(as89])96 b(J.)15 b(H)-6 b(\027)-28 b(astad.)19 b(Almost)c(optimal)h(lo)o(w)o(er)e(b)q(ounds)i(for)e(small) i(depth)g(circuits.)21 b(In)15 b(S.)g(Micali,)h(editor,)243 2398 y Fe(R)n(andomness)i(and)h(Computation)p Fn(,)g(v)o(olume)f(5)g (of)f Fe(A)n(dvanc)n(es)h(in)g(Computing)h(R)n(ese)n(ar)n(ch)p Fn(,)e(pages)243 2454 y(143{170.)c(JAI)j(Press,)f(Green)o(wic)o(h,)g (1989.)0 2548 y([HCKM88])27 b(J.)20 b(Hartmanis,)g(R.)g(Chang,)g(J.)g (Kadin,)h(and)f(S.)g(Mitc)o(hell.)34 b(Some)20 b(observ)m(ations)g(ab)q (out)f(rela-)243 2604 y(tivizations)g(of)d(space)i(b)q(ounded)g (computations.)26 b Fe(Bul)r(letin)18 b(of)g(the)g(Eur)n(op)n(e)n(an)g (Asso)n(ciation)f(for)243 2661 y(The)n(or)n(etic)n(al)e(Computer)i (Scienc)n(e)p Fn(,)d(35:82{92,)e(June)k(1988.)952 2828 y(14)p eop %%Page: 15 15 15 14 bop 0 199 a Fn([HCRR90])38 b(J.)19 b(Hartmanis,)f(R.)h(Chang,)g (D.)f(Ranjan,)h(and)f(P)l(.)h(Rohatgi.)30 b(Structural)18 b(complexit)o(y)i(theory:)243 256 y(Recen)o(t)h(surprises.)34 b(In)20 b Fe(SW)m(A)m(T)f(90:)29 b(2nd)21 b(Sc)n(andinavian)e(Workshop) i(on)f(A)o(lgorithm)h(The)n(ory)p Fn(,)243 312 y(v)o(olume)16 b(447)e(of)g Fe(L)n(e)n(ctur)n(e)h(Notes)h(in)f(Computer)i(Scienc)n(e)p Fn(,)c(pages)h(1{12.)g(Springer,)h(Berlin,)h(1990.)0 406 y([Hel81])105 b(H.)10 b(Heller.)k Fe(R)n(elativize)n(d)d(p)n (olynomial)g(hier)n(ar)n(chy)h(extending)f(two)h(levels)p Fn(.)f(PhD)f(thesis,)i(Univ)o(ersit\177)-23 b(at)243 462 y(M)q(\177)f(unc)o(hen,)16 b(1981.)0 556 y([HS65])112 b(J.)15 b(Hartmanis)f(and)h(R.)g(Stearns.)j(On)d(the)g(computational)g (complexit)o(y)h(of)e(algorithms.)k Fe(T)m(r)n(ans-)243 613 y(actions)e(of)h(the)f(A)o(meric)n(an)g(Mathematic)n(al)g(So)n (ciety)p Fn(,)e(117:285{306,)e(1965.)0 707 y([HS92])112 b(S.)14 b(Homer)f(and)h(A.)g(Selman.)k(Oracles)d(for)e(structural)h (prop)q(erties:)20 b(The)14 b(isomorphism)g(problem)243 763 y(and)19 b(public-k)o(ey)h(cryptograph)o(y)l(.)27 b Fe(Journal)19 b(of)g(Computer)h(and)e(System)h(Scienc)n(es)p Fn(,)d(44\(2\):287{)243 819 y(301,)e(1992.)0 913 y([HU79])103 b(J.)18 b(E.)g(Hop)q(croft)g(and)g(J.)g(D.)g(Ullman.)30 b Fe(Intr)n(o)n(duction)18 b(to)i(A)o(utomata)g(The)n(ory,)f(L)n (anguages)f(and)243 970 y(Computation)p Fn(.)j(Addison-W)l(esley)l(,)c (Reading,)f(Mass.,)e(1979.)0 1064 y([Kur83])93 b(S.)19 b(Kurtz.)31 b(On)19 b(the)g(random)f(oracle)h(h)o(yp)q(othesis.)31 b Fe(Information)20 b(and)f(Contr)n(ol)p Fn(,)g(57\(1\):40{47)o(,)243 1120 y(April)e(1983.)0 1214 y([Lev73])99 b(L.)15 b(Levin.)20 b(Univ)o(ersal'n)o(y)-5 b(\025)-18 b(\020e)16 b(p)q(ereb)q(orn)o(y)-5 b(\025)-18 b(\020e)16 b(zadac)o(hi)f(\(Univ)o(ersal)h(searc)o(h)e (problems:)20 b(in)c(Russian\).)243 1270 y Fe(Pr)n(oblemy)h(Per)n(e)n (dachi)f(Informatsii)p Fn(,)f(9\(3\):265{266)o(,)e(1973.)20 b(Corrected)15 b(English)i(translation)f(in)243 1327 y([T)l(ra84)o(].)0 1421 y([LFKN92])44 b(C.)12 b(Lund,)h(L.)f(F)l(ortno) o(w,)f(H.)h(Karlo\013,)g(and)h(N.)e(Nisan.)16 b(Algebraic)d(metho)q(ds) f(for)g(in)o(teractiv)o(e)g(pro)q(of)243 1477 y(systems.)20 b Fe(Journal)c(of)g(the)h(A)o(CM)p Fn(,)d(39\(4\):859{8)o(68,)e(1992.)0 1571 y([LL76])115 b(R.)23 b(Ladner)g(and)f(N.)g(Lync)o(h.)41 b(Relativization)25 b(of)d(questions)g(ab)q(out)h(log-space)f (reducibili)q(t)o(y)l(.)243 1627 y Fe(Mathematic)n(al)17 b(Systems)e(The)n(ory)p Fn(,)g(10:19{32,)d(1976.)0 1721 y([Mor81])88 b(S.)15 b(Moran.)k(Some)c(results)g(on)g(relativized)i (deterministic)g(and)e(nondeterministic)i(time)e(hierar-)243 1778 y(c)o(hies.)21 b Fe(Journal)16 b(of)h(Computer)g(and)f(System)g (Scienc)n(es)p Fn(,)d(22:1{8,)g(1981.)0 1871 y([Sha92])98 b(A.)15 b(Shamir.)21 b(IP)15 b(=)h(PSP)l(A)o(CE.)j Fe(Journal)e(of)f (the)h(A)o(CM)p Fn(,)c(39\(4\):869{877)o(,)f(1992.)0 1965 y([T)l(o)q(d91])93 b(S.)12 b(T)l(o)q(da.)j(PP)d(is)g(as)g(hard)g (as)f(the)i(p)q(olynomial-time)h(hierarc)o(h)o(y)l(.)h Fe(SIAM)d(Journal)h(on)g(Computing)p Fn(,)243 2022 y(20\(5\):865{877,)e (1991.)0 2115 y([T)l(ra84])101 b(R.)23 b(T)l(rakh)o(ten)o(brot.)41 b(A)23 b(surv)o(ey)g(of)f(Russian)i(approac)o(hes)f(to)f Fe(Per)n(eb)n(or)g Fn(\(brute-force)g(searc)o(h\))243 2172 y(algorithms.)e Fe(A)o(nnals)15 b(of)h(the)g(History)h(of)f (Computing)p Fn(,)f(6\(4\):384{400)o(,)d(1984.)0 2266 y([Wil85])100 b(C.)15 b(Wilson.)20 b(Relativized)e(circuit)e(complexit) o(y)l(.)21 b Fe(Journal)16 b(of)g(Computer)h(and)f(System)f(Scienc)n (es)p Fn(,)243 2322 y(31:169{181,)d(1985.)952 2828 y(15)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF