%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: jun01.dvi %%CreationDate: Tue May 15 14:10:28 2001 %%Pages: 17 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%DocumentFonts: Times-Bold Times-Roman Helvetica Courier Times-Italic %%DocumentPaperSizes: a4 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -ta4 jun01 %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2001.05.15:1406 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet %%BeginProcSet: 8r.enc % @@psencodingfile@{ % author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry", % version = "0.6", % date = "1 July 1998", % filename = "8r.enc", % email = "tex-fonts@@tug.org", % docstring = "Encoding for TrueType or Type 1 fonts % to be used with TeX." % @} % % Idea is to have all the characters normally included in Type 1 fonts % available for typesetting. This is effectively the characters in Adobe % Standard Encoding + ISO Latin 1 + extra characters from Lucida. % % Character code assignments were made as follows: % % (1) the Windows ANSI characters are almost all in their Windows ANSI % positions, because some Windows users cannot easily reencode the % fonts, and it makes no difference on other systems. The only Windows % ANSI characters not available are those that make no sense for % typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen % (173). quotesingle and grave are moved just because it's such an % irritation not having them in TeX positions. % % (2) Remaining characters are assigned arbitrarily to the lower part % of the range, avoiding 0, 10 and 13 in case we meet dumb software. % % (3) Y&Y Lucida Bright includes some extra text characters; in the % hopes that other PostScript fonts, perhaps created for public % consumption, will include them, they are included starting at 0x12. % % (4) Remaining positions left undefined are for use in (hopefully) % upward-compatible revisions, if someday more characters are generally % available. % % (5) hyphen appears twice for compatibility with both % ASCII and Windows. % /TeXBase1Encoding [ % 0x00 (encoded characters from Adobe Standard not in Windows 3.1) /.notdef /dotaccent /fi /fl /fraction /hungarumlaut /Lslash /lslash /ogonek /ring /.notdef /breve /minus /.notdef % These are the only two remaining unencoded characters, so may as % well include them. /Zcaron /zcaron % 0x10 /caron /dotlessi % (unusual TeX characters available in, e.g., Lucida Bright) /dotlessj /ff /ffi /ffl /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef % very contentious; it's so painful not having quoteleft and quoteright % at 96 and 145 that we move the things normally found there to here. /grave /quotesingle % 0x20 (ASCII begins) /space /exclam /quotedbl /numbersign /dollar /percent /ampersand /quoteright /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash % 0x30 /zero /one /two /three /four /five /six /seven /eight /nine /colon /semicolon /less /equal /greater /question % 0x40 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O % 0x50 /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore % 0x60 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o % 0x70 /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar /braceright /asciitilde /.notdef % rubout; ASCII ends % 0x80 /.notdef /.notdef /quotesinglbase /florin /quotedblbase /ellipsis /dagger /daggerdbl /circumflex /perthousand /Scaron /guilsinglleft /OE /.notdef /.notdef /.notdef % 0x90 /.notdef /.notdef /.notdef /quotedblleft /quotedblright /bullet /endash /emdash /tilde /trademark /scaron /guilsinglright /oe /.notdef /.notdef /Ydieresis % 0xA0 /.notdef % nobreakspace /exclamdown /cent /sterling /currency /yen /brokenbar /section /dieresis /copyright /ordfeminine /guillemotleft /logicalnot /hyphen % Y&Y (also at 45); Windows' softhyphen /registered /macron % 0xD0 /degree /plusminus /twosuperior /threesuperior /acute /mu /paragraph /periodcentered /cedilla /onesuperior /ordmasculine /guillemotright /onequarter /onehalf /threequarters /questiondown % 0xC0 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla /Egrave /Eacute /Ecircumflex /Edieresis /Igrave /Iacute /Icircumflex /Idieresis % 0xD0 /Eth /Ntilde /Ograve /Oacute /Ocircumflex /Otilde /Odieresis /multiply /Oslash /Ugrave /Uacute /Ucircumflex /Udieresis /Yacute /Thorn /germandbls % 0xE0 /agrave /aacute /acircumflex /atilde /adieresis /aring /ae /ccedilla /egrave /eacute /ecircumflex /edieresis /igrave /iacute /icircumflex /idieresis % 0xF0 /eth /ntilde /ograve /oacute /ocircumflex /otilde /odieresis /divide /oslash /ugrave /uacute /ucircumflex /udieresis /yacute /thorn /ydieresis ] def %%EndProcSet %%BeginProcSet: texps.pro %! TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type/integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics/Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{ dup sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1 roll mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def dup[exch{dup CharStrings exch known not{pop/.notdef/Encoding true def} if}forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def} def end %%EndProcSet TeXDict begin 39158280 55380996 1000 600 600 (jun01.dvi) @start %DVIPSBitmapFont: Fa cmsy10 10 1 /Fa 1 25 df24 D E %EndDVIPSBitmapFont /Fb 133[50 2[50 1[50 50 50 50 1[50 5[50 1[50 50 1[50 50 50 50 50 38[50 6[50 2[50 50 50 46[{TeXBase1Encoding ReEncodeFont}20 83.022 /Courier rf /Fc 200[42 42 42 42 42 42 42 42 48[{ TeXBase1Encoding ReEncodeFont}8 83.022 /Times-Bold rf %DVIPSBitmapFont: Fd cmmi10 10 3 /Fd 3 79 df<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206 120E5A5A5A12600A19798817>59 D<9339FF8001C0030F13E0037F9038F80380913A01FF 807E07913A07F8000F0FDA1FE0EB079FDA3F80903803BF0002FFC76CB4FCD901FC80495A 4948157E495A495A4948153E017F163C49C9FC5B1201484816385B1207485A1830121F49 93C7FCA2485AA3127F5BA312FF90CCFCA41703A25F1706A26C160E170C171C5F6C7E5F00 1F5E6D4A5A6C6C4A5A16076C6C020EC8FC6C6C143C6C6C5C6CB4495A90393FE00FC0010F B5C9FC010313FC9038007FC03A3D7CBA3B>67 D<902603FFF891381FFFF8496D5CA2D900 07030113006FEC007C02061678DA0EFF157081020C6D1460A2DA1C3F15E0705CEC181F82 023815016F6C5C1430150702706D1303030392C7FC02607FA2DAE0015C701306ECC00082 01016E130EEF800C5C163F0103EDC01C041F131891C713E0160F49EDF038183001061407 17F8010E02031370EFFC60130CEE01FE011C16E004005B011815FF177F1338600130153F A20170151F95C8FC01F081EA07FCB512E01706A245397DB843>78 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmr7 7 2 /Fe 2 50 df48 D<13381378EA01F8121F12FE12E01200B3AB487EB512F8A2 15267BA521>I E %EndDVIPSBitmapFont /Ff 134[37 37 55 37 42 23 32 32 42 42 42 42 60 23 2[23 42 42 23 37 42 37 42 42 12[46 42 2[51 60 55 69 46 1[37 28 2[51 51 60 55 1[51 6[28 42 42 2[42 42 1[42 42 42 1[21 28 21 2[28 28 28 39[{TeXBase1Encoding ReEncodeFont}51 83.022 /Times-Italic rf /Fg 75[28 29[42 13[28 13[37 42 42 60 42 42 23 32 28 42 42 42 42 65 23 42 23 23 42 42 28 37 42 37 42 37 3[28 1[28 3[78 60 60 51 46 55 1[46 60 60 74 51 60 32 28 60 60 46 51 60 55 55 60 6[23 42 42 42 42 42 42 42 42 42 42 1[21 28 21 2[28 28 28 36[46 2[{TeXBase1Encoding ReEncodeFont}71 83.022 /Times-Roman rf /Fh 138[55 33 39 44 1[55 50 55 83 28 2[28 55 1[33 44 55 44 1[50 12[66 55 2[61 6[39 1[78 1[66 1[72 1[72 10[50 1[50 50 50 50 2[25 33 45[{TeXBase1Encoding ReEncodeFont}31 99.6264 /Times-Bold rf %DVIPSBitmapFont: Fi cmr10 10 1 /Fi 1 49 df48 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmsy6 6 1 /Fj 1 49 df48 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmex8 8 1 /Fk 1 81 df80 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmmi6 6 3 /Fl 3 107 df<127812FCA212FEA2127E1206A3120CA2121C121812301260124007107A 8513>59 D<1338137CA2137813701300A7EA0780EA1FC0EA38E01230EA60F0EAC1E0A3EA 03C0A3EA0780A2EA0F0013041306EA1E0CA21318121CEA1E70EA0FE0EA07800F237DA116 >105 D<1418143C147CA214381400A7EB0780EB1FE01338EB60F013C0A2EA0180A23800 01E0A4EB03C0A4EB0780A4EB0F00A4131EA21238EA783CEAF8381378EA70F0EA7FC0001F C7FC162D81A119>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmsy8 8 4 /Fm 4 100 df0 D<137813FE1201A3120313FCA3EA07F8A313F0 A2EA0FE0A313C0121F1380A3EA3F00A3123E127E127CA35AA35A0F227EA413>48 D<126012E0B3B3B3A9B51280A27E114374B11F>98 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmex10 10.95 3 /Fn 3 89 df 80 DI88 D E %EndDVIPSBitmapFont /Fo 166[53 2[53 53 44 40 49 1[40 53 53 1[44 1[28 24 3[44 53 49 1[53 65[{TeXBase1Encoding ReEncodeFont}16 72.7272 /Times-Roman rf %DVIPSBitmapFont: Fp msbm10 10.95 1 /Fp 1 79 df78 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fq cmr10 10.95 14 /Fq 14 112 df<913801FFC0021F13FC9139FF007F80D903F8EB0FE0D90FF0EB07F8D91F C0EB01FCD97F806DB4FC49C86C7E48486F7E00038348486F7E000F8349150F001F834915 07003F83A348486F7EAA6C6C4B5AA3001F5FA26C6C4B5AA200075F6D151F00035FA26C6C 4B5A00005FA2017F4BC7FC6D157EA26D6C5C010F5DA26D6C495A00E0EF0380010315E0D8 70019238C007006E130301001580A36C0160EC000E003C017049131E263FFFF0ECFFFEA3 6C5FA339407CBF42>10 D<1430147014E0EB01C0EB03801307EB0F00131E133E133C5B13 F85B12015B1203A2485AA2120F5BA2121F90C7FCA25AA3123E127EA6127C12FCB2127C12 7EA6123E123FA37EA27F120FA27F1207A26C7EA212017F12007F13787F133E131E7FEB07 801303EB01C0EB00E014701430145A77C323>40 D<12C07E12707E7E121E7E6C7E7F1203 6C7E7F12007F1378137CA27FA2133F7FA21480130FA214C0A3130714E0A6130314F0B214 E01307A614C0130FA31480A2131F1400A25B133EA25BA2137813F85B12015B485A12075B 48C7FC121E121C5A5A5A5A145A7BC323>I<1506150FB3A9007FB912E0BA12F0A26C18E0 C8000FC9FCB3A915063C3C7BB447>43 D48 DII<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00C7FCB3121EEA7F80A2EAFFC0A4 EA7F80A2EA1E000A2779A619>58 D<007FB912E0BA12F0A26C18E0CDFCAE007FB912E0BA 12F0A26C18E03C167BA147>61 D100 D<167C903903F801FF903A1FFF 078F8090397E0FDE1F9038F803F83803F001A23B07E000FC0600000F6EC7FC49137E001F 147FA8000F147E6D13FE00075C6C6C485AA23901F803E03903FE0FC026071FFFC8FCEB03 F80006CAFC120EA3120FA27F7F6CB512E015FE6C6E7E6C15E06C810003813A0FC0001FFC 48C7EA01FE003E140048157E825A82A46C5D007C153E007E157E6C5D6C6C495A6C6C495A D803F0EB0FC0D800FE017FC7FC90383FFFFC010313C0293D7EA82D>103 D108 D<2701F801FE14FF00FF902707FFC00313E0913B1E07E00F03F0913B7803F03C01F80007 903BE001F87000FC2603F9C06D487F000101805C01FBD900FF147F91C75B13FF4992C7FC A2495CB3A6486C496CECFF80B5D8F87FD9FC3F13FEA347287DA74C>I<14FF010713E090 381F81F890387E007E01F8131F4848EB0F804848EB07C04848EB03E0000F15F04848EB01 F8A2003F15FCA248C812FEA44815FFA96C15FEA36C6CEB01FCA3001F15F86C6CEB03F0A2 6C6CEB07E06C6CEB0FC06C6CEB1F80D8007EEB7E0090383F81FC90380FFFF0010090C7FC 282A7EA82D>111 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fr cmr6 6 3 /Fr 3 51 df<13FF000313C0380781E0380F00F0001E137848133CA248131EA400F8131F AD0078131EA2007C133E003C133CA26C13786C13F0380781E03803FFC0C6130018227DA0 1E>48 D<13E01201120712FF12F91201B3A7487EB512C0A212217AA01E>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fs cmr8 8 14 /Fs 14 112 df<13031307130E131C1338137013F0EA01E013C01203EA0780A2EA0F00A2 121EA35AA45AA512F8A25AAB7EA21278A57EA47EA37EA2EA0780A2EA03C0120113E0EA00 F013701338131C130E1307130310437AB11B>40 D<12C07E12707E7E7E120FEA07801203 13C0EA01E0A2EA00F0A21378A3133CA4131EA5131FA2130FAB131FA2131EA5133CA41378 A313F0A2EA01E0A2EA03C013801207EA0F00120E5A5A5A5A5A10437CB11B>I43 D48 D<130C133C137CEA03FC12FFEAFC7C1200B3B113FE387FFFFEA2172C7AAB23>II61 D<4A7E4A7EA34A7EA24A7EA3EC1BF814 19A2EC30FCA2EC70FEEC607EA24A7EA349486C7EA2010380EC000FA201066D7EA3496D7E A2011FB57EA29038180001496D7EA349147EA201E0147F4980A20001ED1F801203000716 C0D80FF0EC3FE0D8FFFC0103B5FCA2302F7EAE35>65 D67 D78 D<007FB712F8A29039000FC003007C150000701638A200601618A200E0161CA248160CA5 C71500B3A94A7E011FB512E0A22E2D7EAC33>84 D<013F13F89038FFC3FE3903E1FF1E38 07807C000F140C391F003E00A2003E7FA76C133EA26C6C5A00071378380FE1F0380CFFC0 D81C3FC7FC90C8FCA3121E121F380FFFF814FF6C14C04814F0391E0007F848130048147C 12F848143CA46C147C007C14F86CEB01F06CEB03E03907E01F803901FFFE0038003FF01F 2D7E9D23>103 D108 D111 D E %EndDVIPSBitmapFont /Ft 134[45 1[66 1[51 30 35 40 2[45 51 76 25 51 1[25 51 45 30 40 51 1[51 45 12[61 3[56 1[66 1[61 8[66 61 7[30 2[45 1[45 45 45 45 45 2[23 4[30 30 40[{TeXBase1Encoding ReEncodeFont}35 90.9091 /Times-Bold rf /Fu 138[45 45 45 45 3[45 1[45 4[45 1[45 45 45 1[45 32[45 17[45 46[{TeXBase1Encoding ReEncodeFont}13 74.7198 /Courier rf /Fv 134[37 1[54 37 37 21 29 25 1[37 37 37 58 21 37 1[21 37 37 25 33 37 33 37 33 11[54 46 42 50 3[54 6[54 42 1[54 50 9[37 37 37 2[37 37 1[37 2[19 25 19 44[{TeXBase1Encoding ReEncodeFont}40 74.7198 /Times-Roman rf /Fw 206[25 49[{TeXBase1Encoding ReEncodeFont}1 49.8132 /Times-Roman rf /Fx 134[40 40 61 40 45 25 35 35 45 45 45 45 66 25 40 1[25 45 45 25 40 45 40 45 45 3[35 1[35 6[51 1[56 1[56 1[61 1[51 2[30 1[66 56 56 66 61 3[45 4[30 1[45 6[45 2[23 30 23 2[30 30 30 36[45 2[{TeXBase1Encoding ReEncodeFont} 48 90.9091 /Times-Italic rf /Fy 206[33 49[{ TeXBase1Encoding ReEncodeFont}1 66.4176 /Times-Roman rf /Fz 141[33 3[50 1[28 2[28 3[44 50 44 29[61 3[72 65[{ TeXBase1Encoding ReEncodeFont}9 99.6264 /Times-Roman rf /FA 137[72 72 40 56 48 2[72 72 2[72 1[40 72 72 1[64 3[64 12[88 15[104 1[96 66[{TeXBase1Encoding ReEncodeFont}16 143.462 /Times-Roman rf %DVIPSBitmapFont: FB cmmi8 8 19 /FB 19 121 df<123C127EB4FCA21380A2127F123D1201A312031300A25A1206120E5A5A 5A126009157A8714>59 D<15C0140114031580A214071500A25C140EA2141E141CA2143C 143814781470A214F05CA213015CA213035C130791C7FCA25B130EA2131E131CA2133C13 38A21378137013F05BA212015BA212035BA2120790C8FC5A120EA2121E121CA2123C1238 A212781270A212F05AA21A437CB123>61 D<013FB512FEEEFFC0903A00FE0007F0EE01F8 4AEB007E8301018118804A140F18C00103150718E05CA21307A25CA2130FA24A140FA213 1F18C04A141FA2013F1680173F91C81300A249157EA2017E5D5F01FE14014C5A494A5A4C 5A00014BC7FC163E4914FCED03F00003EC1FC0B7C8FC15F8332D7CAC3A>68 D77 D79 D<013FB6FC17E0903A00FE0007F0EE01FC4AEB007EA2010181A25C1880010316005F5CA2 010715FEA24A5C4C5A010F4A5A4C5A4AEB1F8004FFC7FC91B512F84914C00280C9FCA313 3F91CAFCA35B137EA313FE5BA312015BA21203B512E0A2312D7DAC2D>I<000FB8FCA23B 1FC003F8003F0100151F001C4A130E123C003801071406123000704A130EA20060010F14 0C12E0485CA2141FC715005DA2143FA292C8FCA25CA2147EA214FEA25CA21301A25CA213 03A25CA21307A25C130F131F001FB512F0A2302D7FAC29>84 D96 DI<13F8121F A21201A25BA21203A25BA21207A25BA2120FEBC7E0EB9FF8EBB83C381FF01EEBE01F13C0 9038800F80EA3F00A2123EA2007E131FA2127CA2143F00FC14005AA2147EA2147C14FC5C 387801F01303495A383C0F806C48C7FCEA0FFCEA03F0192F7DAD1E>I<151FEC03FFA2EC 003FA2153EA2157EA2157CA215FCA215F8A21401EB07E190381FF9F0EB7C1DEBF80FEA01 F03903E007E0EA07C0120FEA1F8015C0EA3F00140F5A007E1480A2141F12FE481400A2EC 3F021506143E5AEC7E0E007CEBFE0C14FC0101131C393E07BE18391F0E1E38390FFC0FF0 3903F003C0202F7DAD24>100 D<1307EB0F80EB1FC0A2EB0F80EB070090C7FCA9EA01E0 EA07F8EA0E3CEA1C3E123812301270EA607EEAE07C12C013FC485A120012015B12035BA2 1207EBC04014C0120F13801381381F01801303EB0700EA0F06131EEA07F8EA01F0122E7E AC18>105 D<15E0EC01F01403A3EC01C091C7FCA9147CEB03FE9038078F80EB0E07131C 013813C01330EB700F0160138013E013C0EB801F13001500A25CA2143EA2147EA2147CA2 14FCA25CA21301A25CA21303A25CA2130700385BEAFC0F5C49C7FCEAF83EEAF0F8EA7FF0 EA1F801C3B81AC1D>I<131FEA03FFA2EA003FA2133EA2137EA2137CA213FCA25BA21201 15F89038F003FCEC0F0E0003EB1C1EEC387EEBE07014E03807E1C09038E3803849C7FC13 CEEA0FDC13F8A2EBFF80381F9FE0EB83F0EB01F81300481404150C123EA2007E141C1518 007CEBF038ECF83000FC1470EC78E048EB3FC00070EB0F801F2F7DAD25>I<27078007F0 137E3C1FE01FFC03FF803C18F0781F0783E03B3878E00F1E01263079C001B87F26707F80 13B00060010013F001FE14E000E015C0485A4914800081021F130300015F491400A20003 4A13076049133E170F0007027EEC8080188149017C131F1801000F02FCEB3F03053E1300 49495C180E001F0101EC1E0C183C010049EB0FF0000E6D48EB03E0391F7E9D3E>109 D<3907C007E0391FE03FF83918F8783E393879E01E39307B801F38707F00126013FEEAE0 FC12C05B00815C0001143E5BA20003147E157C5B15FC0007ECF8081618EBC00115F0000F 1538913803E0300180147016E0001F010113C015E390C7EAFF00000E143E251F7E9D2B> I<90387C01F89038FE07FE3901CF8E0F3A03879C0780D907B813C0000713F000069038E0 03E0EB0FC0000E1380120CA2D8081F130712001400A249130F16C0133EA2017EEB1F80A2 017C14005D01FC133E5D15FC6D485A3901FF03E09038FB87C0D9F1FFC7FCEBF0FC000390 C8FCA25BA21207A25BA2120FA2EAFFFCA2232B829D24>112 D117 D<013F137C9038FFC1FF3A01C1E383803A0380F703C0390700F60F000E13FE4813FC1218 0038EC0700003049C7FCA2EA200100005BA313035CA301075B5D14C000385CD87C0F1306 00FC140E011F130C011B131C39F03BE038D8707113F0393FE0FFC0260F803FC7FC221F7E 9D28>120 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: FC cmsy10 10.95 12 /FC 12 104 df<007FB812FEBAFCA26C17FE3804799847>0 D15 D<007FB912E0BA12F0A26C18E0CDFCAE00 7FB912E0BA12F0A26C18E0CDFCAE007FB912E0BA12F0A26C18E03C287BAA47>17 D<180E183F18FFEF03FEEF0FF8EF3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF80DB03FE C7FCED0FF8ED7FE0913801FF80DA07FEC8FCEC1FF8EC7FC04948C9FCEB07FCEB1FF0EB7F C04848CAFCEA07FCEA1FF0EA7FC048CBFCA2EA7FC0EA1FF0EA07FCEA01FF38007FC0EB1F F0EB07FCEB01FF9038007FC0EC1FF0EC07FE913801FF809138007FE0ED1FF8ED03FE9238 00FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FEEF00FF183F180E1800AE 007FB812FEBAFCA26C17FE384879B947>20 D<19301978A2197C193CA2193E191EA2191F 737EA2737E737EA2737E737E1A7C1A7EF21F80F20FC0F207F0007FBB12FCBDFCA26C1AFC CDEA07F0F20FC0F21F80F27E001A7C624F5A4F5AA24F5A4F5AA24FC7FC191EA2193E193C A2197C1978A2193050307BAE5B>33 D<0203B512F8023F14FC91B6FC010315F8D90FFEC8 FCEB1FE0EB7F8001FEC9FCEA01F8485A485A485A5B48CAFCA2123EA25AA21278A212F8A2 5AA2B812F817FCA217F800F0CAFCA27EA21278A2127CA27EA27EA26C7E7F6C7E6C7E6C7E EA00FEEB7F80EB1FE0EB0FFE0103B612F8010015FC143F020314F82E3679B13D>50 D<1718173C177CA217F8A2EE01F0A2EE03E0A2EE07C0160F1780EE1F00A2163EA25EA25E A24B5AA24B5AA24B5AA24B5AA24BC7FCA2153E157E157C5DA24A5AA24A5AA24A5AA24A5A A24AC8FCA2143EA25CA25C13015C495AA2495AA2495AA249C9FCA2133EA25BA25BA2485A A2485AA2485A120F5B48CAFCA2123EA25AA25AA25A12602E5474C000>54 D<126012F0AE12FCA412F0AE126006227BA700>I<126012F0B3B3B3B3ADB512FCA37E16 5A71C328>98 D<1418143CB3B3B3B3ADB512FCA314F8165A7EC328>I<153FEC03FFEC0F E0EC3F80EC7E00495A5C495AA2495AB3AA130F5C131F495A91C7FC13FEEA03F8EA7FE048 C8FCEA7FE0EA03F8EA00FE133F806D7E130F801307B3AA6D7EA26D7E80EB007EEC3F80EC 0FE0EC03FFEC003F205B7AC32D>102 D<12FCEAFFC0EA07F0EA01FCEA007E6D7E131F6D 7EA26D7EB3AA801303806D7E1300147FEC1FC0EC07FEEC00FFEC07FEEC1FC0EC7F0014FC 1301495A5C13075CB3AA495AA2495A133F017EC7FC485AEA07F0EAFFC000FCC8FC205B7A C32D>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: FD cmmi10 10.95 41 /FD 41 122 df<121EEA7F80A2EAFFC0A4EA7F80A2EA1E000A0A798919>58 D<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A312011380120313005A 120E5A1218123812300B1C798919>I<180E183F18FFEF03FEEF0FF8EF3FE0EFFF809338 03FE00EE0FF8EE3FE0EEFF80DB03FEC7FCED1FF8ED7FE0913801FF80DA07FEC8FCEC1FF0 EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFCA2EA7FC0 EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF9038007FC0EC1FF0EC07FE913801 FF809138007FE0ED1FF8ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF 0FF8EF03FEEF00FF183F180E383679B147>II<127012FCB4FCEA7FC0EA1FF0EA07 FCEA01FF38007FC0EB1FF0EB07FCEB01FF9038007FC0EC1FF8EC07FE913801FF80913800 7FE0ED0FF8ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FE EF00FFA2EF03FEEF0FF8EF3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF80DB03FEC7FCED 0FF8ED7FE0913801FF80DA07FEC8FCEC1FF8EC7FC04948C9FCEB07FCEB1FF0EB7FC04848 CAFCEA07FCEA1FF0EA7FC048CBFC12FC1270383679B147>I<17075F84171FA2173F177F A217FFA25E5EA24C6C7EA2EE0E3F161E161C1638A21670A216E0ED01C084ED0380171FED 07005D150E5DA25D157815705D844A5A170F4A5A4AC7FC92B6FC5CA2021CC7120F143C14 384A81A24A140713015C495AA249C8FC5B130E131E4982137C13FED807FFED1FFEB500F0 0107B512FCA219F83E417DC044>65 D<49B712F818FF19E090260001FEC7EA3FF0F007F8 4B6E7E727E850203815D1A80A20207167F4B15FFA3020F17004B5C611803021F5E4B4A5A 180FF01FE0023F4B5A4B4A5ADD01FEC7FCEF07F8027FEC7FE092B6C8FC18E092C7EA07F8 4AEC01FE4A6E7E727E727E13014A82181FA213034A82A301075F4A153FA261010F167F4A 5E18FF4D90C7FC011F5E4A14034D5A013FED1FF04D5A4AECFFC0017F020790C8FCB812FC 17F094C9FC413E7DBD45>II<49 B712F818FF19C0D9000190C7EA3FF0F00FF84BEC03FCF000FE197F0203EE3F805DF11FC0 A20207EE0FE05D1AF0A2020F16075DA21AF8141F5DA2190F143F5DA21AF0147F4B151FA3 02FF17E092C9123FA21AC049177F5C1A8019FF010318005C4E5A61010716034A5E4E5A18 0F010F4C5A4A5E4E5A4EC7FC011F16FE4A4A5AEF07F8013FED0FE0EF3FC04A49B4C8FC01 7FEC0FFCB812F017C004FCC9FC453E7DBD4B>I71 D<49B612C05BA2D90001EB800093C7FC5DA31403 5DA314075DA3140F5DA3141F5DA3143F5DA3147F5DA314FF92C8FCA35B5CA313035CA313 075CA3130F5CA3131F5CA2133FA25CEBFFE0B612E0A32A3E7DBD28>73 D<49B56C93383FFFF05113E098B5FCD90001F1E000704B5B03DF933803BF80A2F2077F14 03039F040E90C7FC1A1CDB8FE05E02075F030F4C5AA21AE1020FEE01C1020E606F6CEC03 811A83021EEE0703021C040E5BA2F11C07023C16380238606F6C1470F1E00F14780270DB 01C05BA2953803801F02F0ED07004A6C6C5E180E4E133F130102C04B5C601A7F01036D6C 5B4A95C8FC4D5A4D485B130791C749C75A170E047F1401495D010E4B5CA24D1303131E01 1C4B5C5F013C023F1407017C5D01FE92C75BD803FF4D7EB500FC013E011FB512F8163C04 1C5E5C3E7DBD58>77 D<49B56C49B512F81BF0A290C76D9039000FFE004AEE03F0705D73 5A03DF150302037F038F5E82190791380787FC030793C7FC1503705C140F91260E01FF14 0EA26F151E021E80021C017F141C83193C023C6D7E02381638161F711378147802706D6C 1370A2040714F002F0804A01035C8318010101EC01FF4A5E82188313034A91387FC380A2 EF3FC7010716E791C8001F90C8FC18F718FF4981010E5E1707A2131E011C6F5AA2013C15 01137C01FE6F5AEA03FFB512FC187818704D3E7DBD49>II<49B712F018FF19C0D9000190C76C7EF00FF84BEC03FC180102 0382727E5DA214071A805DA2140F4E13005DA2021F5E18034B5D1807023F5E4E5A4B4A5A 4E5A027F4B5A06FEC7FC4BEB03FCEF3FF091B712C005FCC8FC92CBFCA25BA25CA21303A2 5CA21307A25CA2130FA25CA2131FA25CA2133FA25C497EB612E0A3413E7DBD3A>II<49B77E18F818FFD90001D900017F9438003FE04BEC 0FF0727E727E14034B6E7EA30207825DA3020F4B5A5DA24E5A141F4B4A5A614E5A023F4B 5A4B4A5A06FEC7FCEF03FC027FEC0FF04BEBFF8092B500FCC8FC5F9139FF8001FE92C7EA 7F80EF1FC084496F7E4A1407A28413035CA2170F13075C60171F130F5CA3011F033F5B4A EE038018E0013F17071A004A021F5B496C160EB600E090380FF01E05075B716C5ACBEAFF E0F03F8041407DBD45>II<48B912FCA25A913A 0003FE000F01F84A1301D807E0EE00F8491307491778000F5D90C7FC001E140FA2001C4B 1470123C0038141FA200785D1270033F15F000F018E0485DC81600157FA25EA215FFA293 C9FCA25CA25DA21403A25DA21407A25DA2140FA25DA2141FA25DA2143FA25DA2147FA214 FF497F001FB612FCA25E3E3D7FBC35>I<027FB5D88007B512C091B6FCA2020101F8C7EB F8009126007FE0EC7F804C92C7FC033F157C701478616F6C495A4E5A6F6C495A4EC8FC18 0E6F6C5B606F6C5B6017016F6C485A4D5A6F018FC9FC179E17BCEE7FF85F705AA3707EA2 83163F167FEEF7FCED01E7EEC3FEED0383ED070392380E01FF151E4B6C7F5D5D4A486D7E 4A5A4A486D7E92C7FC140E4A6E7E5C4A6E7E14F0495A49486E7E1307D91F806E7ED97FC0 14072603FFE0EC1FFF007F01FC49B512FEB55CA24A3E7EBD4B>88 DI<151EED7F 80913801F1C0EC03C1EC07C0ED80E0EC0F005C141E91383E01C0147CA214F81503D901F0 1380A21303ECE007010714005D90380FC00EA2151E90381F801C153C5D133F4A5A5D1401 49485A017E5B14074AC7FCEBFE1E13FC5C5C5C3801F9E0EBFBC0A2EBFF8091C8FC5B5B5B 5BA212031207120F121F123D127800F0140300E0EC0780C66CEB0F000178131E157C6D13 F04A5A90381E0F80D90FFEC7FCEB03F823417FBF26>96 DII100 D<163EEEFFC0923803E1E0923807C0F0ED0F811687ED1F8F160F15 3FA217E092387E038093C7FCA45DA514015DA30103B512FCA390260003F0C7FCA314075D A4140F5DA5141F5DA4143F92C8FCA45C147EA414FE5CA413015CA4495AA35CEA1E07127F 5C12FF495AA200FE90C9FCEAF81EEA703EEA7878EA1FF0EA07C02C537CBF2D>102 DII< 143C14FEA21301A314FCEB00701400AD137E3801FF803803C7C0EA0703000F13E0120E12 1C13071238A2EA780F007013C0A2EAF01F14801200133F14005B137EA213FE5BA212015B 0003130E13F0A20007131EEBE01CA2143CEBC0381478147014E013C13803E3C03801FF00 EA007C173E7EBC1F>III109 DIII114 DI<137C48B4EC03802603C7C0EB0FC0EA0703000F7F000E151F121C010715801238 163FEA780F0070491400A2D8F01F5C5C0000157E133F91C712FEA2495C137E150113FE49 5CA215030001161C4914F0A21507173CEEE038150F031F1378000016706D133F017C0173 13F0017E01E313E0903A3F03C1F1C0903A0FFF007F80D901FCEB1F002E297EA734>117 D<017E147848B4EB01FC2603C7C013FED807031303000F13E0120E121C01071301003814 00167ED8780F143E00705B161EEAF01F4A131C1200133F91C7123C16385B137E167801FE 14705B16F016E0120149EB01C0A2ED0380A2ED0700A20000140E5D6D133C017C5B6D5B90 381F03C0903807FF80D901FCC7FC27297EA72C>I120 D<137C48B4EC03802603C7C0EB0FC0EA0703000F7F000E151F001C168013071238163FD8 780F150000705BA2D8F01F5C4A137E1200133F91C712FE5E5B137E150113FE495CA21503 00015D5BA215075EA2150F151F00005D6D133F017C137F017E13FF90393F03DF8090380F FF1FEB01FC90C7123F93C7FCA25DD80380137ED80FE013FE001F5C4A5AA24848485A4A5A 6CC6485A001C495A001E49C8FC000E137C380781F03803FFC0C648C9FC2A3B7EA72D>I E %EndDVIPSBitmapFont /FE 136[55 2[55 55 55 2[55 55 55 2[55 1[55 1[55 55 1[55 1[55 32[55 17[55 46[{TeXBase1Encoding ReEncodeFont}15 90.9091 /Courier rf /FF 145[51 8[51 1[45 1[51 9[86 2[56 1[66 2[71 66 1[51 5[56 70[{TeXBase1Encoding ReEncodeFont}11 90.9091 /Helvetica rf /FG 75[30 29[45 1[40 40 24[40 45 45 66 45 45 25 35 30 45 45 45 45 71 25 45 25 25 45 45 30 40 45 40 45 40 3[30 1[30 1[66 1[86 66 66 56 51 61 1[51 66 66 81 56 1[35 30 66 66 51 56 66 61 61 66 1[40 3[25 25 45 45 45 45 45 45 45 45 45 45 25 23 30 23 2[30 30 30 3[45 1[30 29[51 51 2[{TeXBase1Encoding ReEncodeFont}78 90.9091 /Times-Roman rf /FH 134[60 60 1[60 66 40 47 53 1[66 60 66 100 33 66 1[33 66 60 40 53 66 53 1[60 11[86 80 66 86 5[80 2[47 4[86 86 80 86 9[60 60 60 60 60 60 60 49[{TeXBase1Encoding ReEncodeFont}38 119.552 /Times-Bold rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%BeginPaperSize: a4 a4 %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop 912 573 a FH(The)30 b(Computational)g(Complexity)g(Column)1897 799 y FG(by)1574 1024 y FF(Lance)24 b(FOR)m(TNO)m(W)1513 1250 y FG(NEC)e(Research)j(Institute)1057 1363 y(4)e(Independence)28 b(W)-7 b(ay)h(,)22 b(Princeton,)j(NJ)e(08540,)i(USA)1206 1476 y FE(fortnow@research)o(.n)o(j.)o(ne)o(c.)o(com)942 1589 y FG(http://www)-6 b(.neci.nj.nec.com/homepag)q(es/)q(for)q(tno)o (w/bea)q(tcs)589 1898 y(Sometimes)23 b(the)f(simplest)i(problems)f (lead)g(to)f(the)h(most)f(interesting)j(theory)-6 b(.)30 b(Consider)448 2011 y(the)24 b(di)n(vision)i(problem,)f(gi)n(v)o(en)f FD(a)f FG(and)h FD(b)f FG(in)g(binary)-6 b(,)25 b(output)h FC(b)2424 1975 y FB(a)p 2424 1990 38 4 v 2428 2042 a(b)2472 2011 y FC(c)p FG(.)i(W)-7 b(e)23 b(ha)n(v)o(e)i(as)e(kids)i(learned)448 2124 y(ef)n(\002cient)33 b(algorithms)g(for)f(di)n(vision,)j(b)n(ut)d (to)g(do)g(di)n(vision)h(ef)n(\002ciently)g(in)f(parallel)h(or)e(with) 448 2237 y(small)21 b(space)g(appeared)h(to)e(require)i(a)d (considerable)24 b(amount)d(of)f(precomputation.)31 b(A)19 b(series)448 2350 y(of)h(recent)h(results)g(ha)n(v)o(e)g(remo)o(v)o(ed) f(the)g(need)h(for)f(precomputation)j(and)d(ha)n(v)o(e)h(e)o(xactly)g (nailed)448 2463 y(the)f(comple)o(xity)h(of)d(the)i(di)n(vision)h (problem.)28 b(F)o(ormer)19 b(column)h(editor)g(Eric)e(Allender)j (guides)448 2575 y(us)j(through)h(these)g(e)o(xciting)g(de)n(v)o (elopments.)1128 2996 y FA(The)35 b(Di)l(vision)f(Breakthroughs)1642 3109 y Fz(Eric)25 b(Allender)2206 3072 y Fy(1)448 3401 y FH(1)120 b(Intr)n(oduction)448 3608 y FG(All)28 b(of)h(us)g(learn)g (to)g(do)g(arithmetic)h(in)f(grade)g(school.)46 b(The)28 b(algorithms)j(for)e(addition)i(and)448 3721 y(subtraction)23 b(tak)o(e)e(some)e(time)h(to)f(master)l(,)i(and)g(the)f(multiplication) j(algorithm)e(is)e(e)n(v)o(en)h(more)448 3834 y(complicated.)43 b(Ev)o(entually)29 b(students)g(learn)f(the)g(di)n(vision)h(algorithm;) i(most)c(students)j(\002nd)448 3947 y(it)24 b(to)f(be)h(complicated,)h (time-consuming,)i(and)d(tedious.)30 b(Is)24 b(there)g(a)f(better)i(w)o (ay)e(to)h(di)n(vide?)589 4059 y(F)o(or)g(most)h(practical)i(purposes,) g(the)f(correct)g(w)o(ay)e(to)h(answer)h(this)f(question)i(is)e(to)g (con-)448 4172 y(sider)h(the)g(time-comple)o(xity)i(of)d(di)n(vision;)k (what)c(is)g(the)g(f)o(astest)i(di)n(vision)g(algorithm?)36 b(That)448 4285 y(is)d Fx(not)h FG(the)f(subject)i(of)e(this)h (article.)59 b(I)33 b(am)f(not)i(a)o(w)o(are)f(of)g(an)o(y)h(recent)g (breakthrough)j(on)448 4398 y(this)24 b(question;)h(an)o(y)e(good)g(te) o(xtbook)i(on)e(design)h(and)f(analysis)i(of)e(algorithms)h(will)f (tell)g(you)448 4511 y(about)i(the)f(current)h(state)f(of)g(the)g(art)f (on)h(that)g(front.)589 4624 y(Comple)o(xity)29 b(theory)g(gi)n(v)o(es) f(us)f(an)g(equally-v)n(alid)k(w)o(ay)c(to)h(ask)f(about)i(the)e (comple)o(xity)448 4737 y(of)d(di)n(vision:)p 448 4798 1196 4 v 554 4853 a Fw(1)583 4885 y Fv(Department)d(of)f(Computer)h (Science,)f(Rutgers)h(Uni)n(v)o(ersity)-5 b(,)20 b Fu (allender@cs.rutgers.edu)p Fv(.)j(This)448 4976 y(w)o(ork)d(w)o(as)f (supported)h(in)f(part)g(by)g(National)g(Science)g(F)o(oundation)h (Grant)f(CCR-9734918.)p eop %%Page: 2 2 2 1 bop 1166 573 a Fx(In)23 b(what)h(comple)n(xity)i(class)e(does)h (division)g(lie?)589 760 y FG(One)k(of)h(the)f(most)h(important)h (subclasses)h(of)e(P)e(\(and)i(one)g(of)f(the)h(\002rst)f(to)g(be)g (de\002ned)448 873 y(and)e(studied\))h(is)e(the)g(class)h(L)e (\(deterministic)k(logarithmic)f(space\).)37 b(It)26 b(is)g(easy)h(to)f(see)g(ho)n(w)448 986 y(to)g(add)g(and)g(subtract)h (in)f(L)o(.)35 b(It)25 b(is)g(a)g(simple)i(e)o(x)o(ercise)f(to)g(sho)n (w)f(that)h(multiplication)j(can)d(be)448 1099 y(computed)d(in)e (logspace,)i(too.)28 b(Ho)n(we)n(v)o(er)l(,)21 b(it)g(had)g(been)h(an)f (open)h(question)h(since)f(the)f(1960')-5 b(s)448 1212 y(if)24 b(logspace)h(machines)g(can)f(di)n(vide.)589 1325 y(This)g(w)o(as)f(f)o(airly)i(anno)o(ying.)589 1438 y(Let)e(me)g(gi)n(v)o(e)h(an)f(e)o(xample,)h(to)g(illustrate)i(ho)n(w)d (anno)o(ying)j(this)e(w)o(as.)589 1551 y(W)-7 b(e)36 b(lik)o(e)g(to)g(think)i(of)e(comple)o(xity)i(classes)f(as)f(capturing) j(fundamental)g(aspects)e(of)448 1664 y(computation.)55 b(The)31 b(question)j(of)d(whether)h(a)f(particular)j(problem)e(lies)g (in)g(a)e(comple)o(xity)448 1777 y(class)23 b(or)f(not)g(should)h(not)g (depend)g(on)f(tri)n(vial)h(matters,)g(such)f(as)g(minor)g(issues)h(of) f(encoding.)448 1890 y(As)30 b(long)h(as)f(a)g(\223reasonable\224)k (encoding)e(is)e(used,)j(it)d(should)i(not)e(mak)o(e)h(much)f(dif)n (ference)448 2002 y(e)o(xactly)j(ho)n(w)d(the)h(problem)i(is)d (encoded.)54 b(F)o(or)30 b(e)o(xample,)j(a)e(computational)j(problem)e (in-)448 2115 y(v)n(olving)c(numbers)f(should)g(ha)n(v)o(e)f(roughly)i (the)e(same)f(comple)o(xity)-6 b(,)28 b(re)o(gardless)g(of)d(whether) 448 2228 y(the)i(numbers)h(are)e(encoded)j(in)d(base)h(ten,)g(or)f (base)h(tw)o(o,)g(or)f(some)h(other)g(reasonable)i(nota-)448 2341 y(tion.)50 b(Unfortunately)-6 b(,)36 b(it)30 b(w)o(as)g(not)h(kno) n(wn)f(ho)n(w)g(con)l(v)o(ert)j(from)d(base)h(ten)g(to)f(base)h(tw)o(o) f(in)448 2454 y(logspace,)j(and)d(thus)g(one)g(could)h(not)f(safely)h (ignore)f(such)h(matters)f(when)g(discussing)i(the)448 2567 y(class)25 b(L)o(.)589 2680 y Ft(Br)n(eakthr)n(ough)f(number)e(1:) 29 b FG([13)q(])23 b Fx(Division)i(is)f(in)f(Lo)o(gspace)o(.)589 2793 y FG(As)i(a)g(consequence,)k(related)e(problems)g(\(such)g(as)e (con)l(v)o(erting)j(from)d(base)i(ten)e(to)h(base)448 2906 y(tw)o(o\))e(also)g(lie)g(in)f(logspace.)589 3019 y(Comple)o(xity)h(theorists)g(are)e(not)h(happ)o(y)g(until)g(the)o(y)f (ha)n(v)o(e)h(pinpointed)i(the)e(\223right\224)g(com-)448 3132 y(ple)o(xity)d(class)f(for)g(a)e(problem.)29 b(That)18 b(is,)h(the)o(y)f(w)o(ant)g(to)h(\002nd)f(the)g(comple)o(xity)i(class)f (for)g(which)448 3245 y(a)26 b(problem)i(is)f(complete;)i(this)e (corresponds)j(to)d(a)f(tight)h(lo)n(wer)g(bound)h(on)f(the)f(comple)o (xity)448 3357 y(of)f(a)f(problem.)34 b(In)24 b(the)h(case)g(of)g(di)n (vision,)i(de\002ning)e(the)g(\223right\224)i(comple)o(xity)f(class)g (tak)o(es)g(a)448 3470 y(bit)h(of)g(e)o(xplanation,)j(as)c(does)h (de\002ning)h(the)f(notion)h(of)f(\223completeness\224.)41 b(I')o(ll)27 b(pro)o(vide)h(the)448 3583 y(necessary)e(de\002nitions)g (later)-5 b(.)29 b(F)o(or)23 b(no)n(w)-6 b(,)23 b(let')-5 b(s)24 b(state)h(the)e(result:)589 3696 y Ft(Br)n(eakthr)n(ough)f (number)d(2:)28 b FG([18)q(])21 b Fx(Division)h(is)f(complete)i(for)e FG(DLOGTIME)n Fx(-uniform)448 3809 y FG(TC)564 3773 y Fs(0)604 3809 y Fx(.)589 3922 y FG(This)36 b(latest)g(breakthrough)j (will)c(be)g(presented)j(at)d(ICALP)e(2001)j(by)g(Bill)f(Hesse,)j(a)448 4035 y(student)d(at)d(the)h(Uni)n(v)o(ersity)h(of)f(Massachusetts.)60 b(He)32 b(will)g(be)h(recei)n(ving)i(the)e Fx(best)g(paper)448 4148 y(awar)m(d)24 b FG(for)g(T)m(rack)f(A)g(at)g(ICALP)e(2001)k (\(combined)g(with)f(the)g(best)g(student)h(paper)g(a)o(w)o(ard\).)589 4261 y(All)19 b(of)h(these)h(results)g(b)n(uild)g(on)f(the)g(earlier)h (w)o(ork)e(of)h(Beame,)g(Cook,)g(and)g(Hoo)o(v)o(er)g(\([9)q(]\).)589 4374 y(In)32 b(the)g(follo)n(wing)g(sections,)k(I)31 b(will)g(pro)o(vide)i(the)f(necessary)i(background)g(about)f(the)448 4487 y(comple)o(xity)40 b(classes)f(I')o(ll)f(be)f(discussing,)44 b(and)38 b(then)h(I')o(ll)e(present)j(the)e(history)h(of)e(these)448 4599 y(breakthroughs,)28 b(and)c(the)f(main)h(ideas)g(in)l(v)n(olv)o (ed.)32 b(In)23 b(a)g(closing)i(section,)g(I')o(ll)f(discuss)h(some)448 4712 y(of)f(the)g(applications)j(that)d(these)g(adv)n(ances)i(ha)n(v)o (e)e(already)h(found.)p eop %%Page: 3 3 3 2 bop 498 561 a FG(Comple)o(xity)25 b(Class)p 1194 594 4 113 v 100 w(Complete)g(Problem)p 448 598 2385 4 v 448 614 V 498 693 a(GapL)p 1194 727 4 113 v 540 w(Determinant)h(of)d (Inte)o(ger)i(Matrices)p 448 731 2385 4 v 498 810 a(#L)p 1194 844 4 113 v 646 w(Counting)h(paths)e(in)g(a)f(D)l(A)l(G)p 448 847 2385 4 v 498 926 a(Mod)669 940 y FB(p)710 926 y FG(L)p 1194 960 4 113 v 479 w(Determinant)j(of)d(Inte)o(ger)i (Matrices)g(mod)e FD(p)p 448 963 2385 4 v 498 1042 a FG(NL)p 1194 1076 4 113 v 625 w(Shortest)i(paths,)g(T)m(ransiti)n(v)o (e)f(Closure)p 448 1079 2385 4 v 498 1158 a(L)p 1194 1192 4 113 v 691 w(Graph)g(Ac)o(yclicity)-6 b(,)25 b(T)m(ree)e (Isomorphism)p 448 1196 2385 4 v 498 1275 a(NC)625 1242 y Fs(1)p 1194 1308 4 113 v 1245 1275 a FG(Re)o(gular)i(sets,)e(Boolean) i(F)o(ormula)f(Ev)n(aluation)p 448 1312 2385 4 v 498 1391 a(TC)615 1358 y Fs(0)p 1194 1425 4 113 v 448 1428 2385 4 v 448 1598 a FG(Figure)34 b(1:)48 b(Some)32 b(comple)o(xity)j (classes,)i(and)c(some)g(sample)h(sets)f(complete)i(under)f(A)l(C)3398 1562 y Fs(0)448 1711 y FG(reductions.)448 1959 y FH(2)120 b(Backgr)n(ound)30 b(on)h(Complexity)f(Classes)448 2166 y FG(In)22 b(order)h(to)e(understand)k(the)d(recent)h(progress)h(on)e (di)n(vision,)h(it)f(is)f(necessary)k(to)c(understand)448 2279 y(the)36 b(signi\002cance)h(of)e(the)g(comple)o(xity)i(classes)g (in)l(v)n(olv)o(ed.)66 b(In)35 b(this)g(article,)k(we)34 b(shall)i(be)448 2392 y(concerned)k(almost)e(e)o(xclusi)n(v)o(ely)h (with)e(subclasses)j(of)c(P.)68 b(Figure)38 b(2)e(lists)i(some)f(of)g (the)448 2505 y(classes)25 b(that)f(we)f(will)g(focus)i(on,)e(along)i (with)e(a)g(list)h(of)g(some)f(problems)i(that)f(are)g(complete)448 2618 y(for)g(each)h(class)f(under)h FC(\024)1267 2585 y Fs(A)n(C)1369 2561 y Fr(0)1267 2640 y FB(m)1431 2618 y FG(reductions.)32 b(\(F)o(or)23 b(small)h(comple)o(xity)i(classes,)f FC(\024)3059 2585 y Fs(A)n(C)3161 2561 y Fr(0)3059 2640 y FB(m)3222 2618 y FG(is)f(one)448 2731 y(of)31 b(the)g(most)g(natural) i(notions)g(of)e(reducibility)j(to)d(consider)-5 b(.)53 b(F)o(or)30 b(more)h(background)j(on)448 2844 y FC(\024)519 2811 y Fs(A)n(C)621 2787 y Fr(0)519 2866 y FB(m)682 2844 y FG(you)24 b(can)g(consult)i(an)d(earlier)i(edition)g(of)f(this)g (column)g([2)q(].\))589 2957 y(Deterministic)i(and)e(nondeterministic)j (logspace)f(\(L)c(and)i(NL)o(\))f(are)h(probably)h(f)o(amiliar)448 3069 y(to)e(the)f(reader)-5 b(.)30 b(#L)21 b(is)h(the)h (logspace-analog)k(of)22 b(the)h(class)g(#P;)f(#L)g(is)g(the)g(class)i (of)e(functions)448 3182 y FD(f)33 b FG(for)24 b(which)h(there)g(e)o (xists)g(a)e(nondeterministic)29 b(logspace)d(machine)f FD(M)34 b FG(such)25 b(that)f FD(f)10 b Fq(\()p FD(x)p Fq(\))23 b FG(is)448 3295 y(the)30 b(number)f(of)g(accepting)j (computations)g(of)c FD(M)39 b FG(on)29 b(input)h FD(x)p FG(.)44 b(GapL)28 b(is)g(the)i(class)f(of)g(all)448 3408 y(functions)h(that)e(can)f(be)h(e)o(xpressed)h(as)e(the)h(dif)n (ference)h(of)f(tw)o(o)e(#L)h(functions.)42 b(Additional)448 3521 y(background)e(about)e(these)f(comple)o(xity)i(classes)f(can)f(be) f(found)i(in)e(an)h(earlier)h(surv)o(e)o(y)f(I)448 3634 y(wrote)24 b([3)q(],)e(and)i(in)g(the)g(e)o(xcellent)h(te)o(xtbook)h (by)d(V)-12 b(ollmer)24 b([33)r(].)589 3747 y(The)18 b(remaining)i(tw)o(o)e(comple)o(xity)i(classes)f(in)f(Figure)h(2)f(are) g(circuit)i(comple)o(xity)g(classes.)448 3860 y(NC)575 3824 y Fs(1)633 3860 y FG(is)h(the)f(class)h(of)f(languages)j FD(A)d FG(for)g(which)h(there)g(e)o(xist)g(circuit)h(f)o(amilies)f FC(f)p FD(C)3037 3874 y FB(n)3110 3860 y Fq(:)k FD(n)g FC(2)g Fp(N)7 b FC(g)448 3973 y FG(where)24 b(each)g(circuit)h FD(C)1202 3987 y FB(n)585 4148 y FC(\017)46 b FG(computes)25 b(the)f(characteristic)j(function)f(of)d FD(A)g FG(on)h(inputs)h(of)e (length)i FD(n)p FG(,)585 4330 y FC(\017)46 b FG(consists)25 b(of)h(A)t Fo(N)t(D)f FG(and)h(O)t Fo(R)e FG(gates)h(of)e(f)o(an-in)i (tw)o(o,)585 4513 y FC(\017)46 b FG(has)23 b(depth)i FD(O)s Fq(\(log)17 b FD(n)p Fq(\))23 b FG(\(and)h(consequently)j(has)d (size)g FD(n)2446 4480 y FB(O)r Fs(\(1\))2596 4513 y FG(\).)448 4688 y(TC)564 4653 y Fs(0)624 4688 y FG(is)d(the)g(class)h (of)f(languages)j FD(A)c FG(for)i(which)f(there)h(e)o(xist)f(circuit)i (f)o(amilies)f FC(f)p FD(C)3037 4702 y FB(n)3110 4688 y Fq(:)j FD(n)g FC(2)g Fp(N)7 b FC(g)448 4801 y FG(where)24 b(each)g(circuit)h FD(C)1202 4815 y FB(n)585 4976 y FC(\017)46 b FG(computes)25 b(the)f(characteristic)j(function)f(of)d FD(A)g FG(on)h(inputs)h(of)e(length)i FD(n)p FG(,)p eop %%Page: 4 4 4 3 bop 585 573 a FC(\017)46 b FG(consists)25 b(of)h(M)t Fo(A)t(J)t(O)t(R)t(I)t(T)t(Y)h FG(gates)d(\(with)g(no)g(bound)h(on)e (the)h(f)o(an-in\),)585 758 y FC(\017)46 b FG(has)23 b(depth)i FD(O)s Fq(\(1\))585 943 y FC(\017)46 b FG(has)23 b(size)i FD(n)1039 910 y FB(O)r Fs(\(1\))1188 943 y FG(.)448 1124 y(It)30 b(will)g(cause)i(no)e(confusion)j(to)d(use)h(the)f(terms)h (NC)2193 1088 y Fs(1)2262 1124 y FG(and)f(TC)2539 1088 y Fs(0)2607 1124 y FG(also)h(to)g(refer)g(to)f(classes)448 1237 y(of)f Fx(functions)i FG(computed)f(by)f(these)h(classes)g(of)f (circuits,)i(instead)f(of)f(merely)g(focusing)i(on)448 1350 y Fx(langua)o(g)o(es)p FG(.)41 b(F)o(or)26 b(instance,)k(the)c FC(\024)1586 1317 y Fs(A)n(C)1688 1293 y Fr(0)1586 1372 y FB(m)1753 1350 y FG(reducibility)k(mentioned)e(earlier)g(comes)f (from)g(the)448 1463 y(class)k(A)l(C)777 1427 y Fs(0)816 1463 y FG(,)f(which)h(is)e(de\002ned)i(the)f(class)h(of)f(functions)i FD(f)38 b FG(for)30 b(which)h(there)f(e)o(xist)h(circuit)448 1575 y(f)o(amilies)25 b FC(f)p FD(C)873 1589 y FB(n)946 1575 y Fq(:)g FD(n)g FC(2)g Fp(N)7 b FC(g)29 b FG(where)24 b(each)g(circuit)h FD(C)2050 1589 y FB(n)585 1756 y FC(\017)46 b FG(computes)25 b FD(f)32 b FG(on)23 b(inputs)i(of)f(length)h FD(n)p FG(,)585 1941 y FC(\017)46 b FG(consists)25 b(of)h(A)t Fo(N)t(D)f FG(and)h(O)t Fo(R)e FG(gates)h(\(with)e(no)h(bound)h(on)e (the)h(f)o(an-in\),)585 2126 y FC(\017)46 b FG(has)23 b(depth)i FD(O)s Fq(\(1\))585 2311 y FC(\017)46 b FG(has)23 b(size)i FD(n)1039 2278 y FB(O)r Fs(\(1\))1188 2311 y FG(.)589 2492 y(The)30 b(circuit)i(classes)g(NC)1430 2457 y Fs(1)1469 2492 y FG(,)f(TC)1639 2457 y Fs(0)1679 2492 y FG(,)f(and)h(A)l(C)2016 2457 y Fs(0)2085 2492 y FG(each)f(come)h(in)f(dif)n(ferent)i(\003a)n(v)n(ors)f(corre-)448 2605 y(sponding)k(to)d(dif)n(ferent)i Fx(uniformity)g(conditions)p FG(.)58 b(As)31 b(de\002ned)i(abo)o(v)o(e,)h(these)f(classes)h(are)448 2718 y Fx(nonuniform)p FG(.)54 b(That)31 b(is,)i(there)f(is)e Fx(no)i(r)m(estriction)h FG(on)f(ho)n(w)e(dif)n(\002cult)i(it)f(is)g (to)g(compute)h(the)448 2831 y(function)f FD(n)i FC(7!)h FD(C)1057 2845 y FB(n)1131 2831 y FG(\(i.e.,)29 b(on)f(ho)n(w)f(hard)i (it)f(is)g(to)g Fx(b)n(uild)i FG(the)e(circuits\).)45 b(In)28 b(order)h(to)f(obtain)448 2944 y(subclasses)i(of)c(P)o(,)g(it)h (is)f(necessary)j(to)d(impose)h(a)f(\223P-uniformity\224)j(condition.) 40 b(That)26 b(is,)h(the)448 3057 y(function)g FD(n)h FC(7!)g FD(C)1042 3071 y FB(n)1113 3057 y FG(must)d(be)g(computable)i (in)e(polynomial)j(time.)k(Ev)o(en)25 b(the)g(P-uniformity)448 3170 y(condition)31 b(does)d(not)g(seem)g(to)f(be)h(strong)h(enough)h (to)d(de\002ne)h(subclasses)j(of)c(L;)i(this)f(leads)448 3283 y(us)f(to)g(consider)i(L-uniformity)-6 b(.)42 b(In)26 b(the)i(same)f(w)o(ay)-6 b(,)27 b(L-uniformity)i(is)e(a)o(wkw)o(ard)g (when)g(we)448 3396 y(w)o(ant)21 b(to)f(consider)i(subclasses)h(of)d (NC)1681 3360 y Fs(1)1720 3396 y FG(.)27 b(W)-7 b(e)19 b(seem)h(to)g(ha)n(v)o(e)h(started)h(do)n(wn)e(a)g(slippery)i(slope)448 3509 y(of)f(increasingly)j(more)d(restricti)n(v)o(e)h(uniformity)h (conditions,)h(and)d(it)g(is)f(natural)i(to)f(w)o(onder)h(if)448 3621 y(there)h(is)f(an)o(y)h(uniformity)h(condition)h(that)d(is)g (particularly)k(natural)d(or)f(preferable)j(to)d(others.)589 3734 y(There)f(is)g(a)f(consensus)k(in)c(the)h(community)h(of)f (researchers)i(in)e(circuit)h(comple)o(xity)h(that)448 3847 y(the)f(\223right\224)h(uniformity)g(condition)h(is)d(DLOGTIME)m (-uniformity)-6 b(.)31 b(F)o(or)20 b(the)i(rest)f(of)g(this)h(pa-)448 3960 y(per)l(,)38 b(an)o(y)d(reference)h(to)f(\223uniform\224)h (circuits)h(means)e(\223DLOGTIME)m(-uniform\224)i(circuits,)448 4073 y(unless)f(some)f(other)g(uniformity)i(condition)g(is)d(e)o (xplicitly)j(mentioned.)64 b(F)o(or)33 b(this)i(paper)l(,)448 4186 y(you)29 b(w)o(on')n(t)g(need)g(to)g(be)f(concerned)j(with)d(the)h (details)h(of)e(this)h(uniformity)h(condition;)k(for)448 4299 y(details)24 b(you)g(can)e(consult)j([29)q(,)d(8,)f(33)q(].)28 b(\(The)23 b(\223straightforw)o(ard\224)k(notion)d(of)e(DLOGTIME)n(-) 448 4412 y(uniformity)k(needs)f(to)e(modi\002ed)h(a)g(bit)f(in)h(order) h(to)e(gi)n(v)o(e)h(a)f(satisf)o(actory)k(uniformity)f(condi-)448 4525 y(tion)e(for)g(NC)867 4489 y Fs(1)930 4525 y FG([29)q(].\))k(What) c(gi)n(v)o(es)g(rise)g(to)f(this)h(consensus?)589 4638 y(The)19 b(answer)h(to)e(this)i(question)h(lies)f(in)f(the)g(f)o(act)g (that)h(most)f(members)g(of)g(the)g(comple)o(xity)448 4751 y(theory)i(community)g(are)f(more)g(comfortable)i(programming)f (than)f(b)n(uilding)i(circuits.)30 b(The)o(y)448 4863 y(prefer)c(to)e(ha)n(v)o(e)g(a)g(machine)h(model)g(that)g(the)o(y)f (can)h(program)g(in.)30 b(Thus)25 b(it)e(is)h(v)o(ery)h(desirable)448 4976 y(that)d(uniform)g(NC)1044 4941 y Fs(1)1104 4976 y FG(correspond)i(to)d(logarithmic)i(time)e(on)g(an)g(alternating)j(T)l (uring)d(machine)p eop %%Page: 5 5 5 4 bop 448 573 a FG([29)r(])35 b(and)h(uniform)i(A)l(C)1252 537 y Fs(0)1327 573 y FG(correspond)h(to)d(logarithmic)i(time)e(on)g (an)g(alternating)j(T)l(uring)448 686 y(machine)34 b(making)f FD(O)s Fq(\(1\))f FG(alternations)k([10)q(].)54 b(Similarly)-6 b(,)35 b(uniform)f(TC)2825 650 y Fs(0)2896 686 y FG(corresponds)h(to) 448 799 y(logarithmic)26 b(time)d(and)h FD(O)s Fq(\(1\))g FG(\223alternations\224)k(on)23 b(a)g(threshold)j(machine)f([26)q(,)e (1].)589 912 y(Further)32 b(support)g(for)f(this)g(uniformity)i (condition)g(comes)e(from)g(a)f(series)i(of)e(striking)448 1024 y(connections)40 b(to)c(\002nite)h(model)f(theory)-6 b(.)69 b(A)35 b(language)k(is)d(in)g(uniform)h(A)l(C)2943 989 y Fs(0)3018 1024 y FG(if)f(and)g(only)448 1137 y(if)g(it)h(can)f (be)h(vie)n(wed)g(as)f(the)h(class)g(of)f(\002nite)h(models)g(of)f(a)g (\002rst-order)i(formula.)68 b(That)448 1250 y(is,)37 b(a)d(single)h(formula)g(\(with)g(e)o(xistential)i(and)d(uni)n(v)o (ersal)i(quanti\002ers\))h(de\002nes)e(an)f(entire)448 1363 y(language,)24 b(as)d(opposed)i(to)d(ha)n(ving)j(a)d(dif)n(ferent) j(circuit)f(\(i.e.,)f(a)f(Boolean)i(formula\))h(for)e(each)448 1476 y(input)h(length.)29 b(The)20 b(reader)i(can)f(\002nd)f(out)h (more)g(about)h(this)f(connection)j(between)d(logic)h(and)448 1589 y(comple)o(xity)33 b(in)f(an)f(earlier)i(edition)g(of)e(this)g (column)i([19)q(])e(or)g(in)g(the)g(te)o(xt)h(by)f(Immerman)448 1702 y([20)r(].)c(Lindell)22 b(gi)n(v)o(es)g(yet)g(another)h (characterization)k(of)21 b(uniform)i(A)l(C)2701 1666 y Fs(0)2762 1702 y FG([24)q(],)e(lending)i(more)448 1815 y(support)31 b(to)e(this)h(choice)g(of)f(uniformity)i(condition.)48 b(When)29 b(we)f(augment)i(the)g(e)o(xistential)448 1928 y(and)21 b(uni)n(v)o(ersal)h(quanti\002ers)g(with)e(\223majority\224)i (quanti\002ers)g(\(i.e.,)e(instead)i(of)e(asserting)i(that)f(a)448 2041 y(predicate)26 b(holds)e(for)g(all)f(or)h(some)f(elements,)h(we)f (assert)h(that)g(it)f(holds)i(for)e(\223most\224)h(domain)448 2154 y(elements\),)h(then)f(we)f(obtain)i(an)f(equi)n(v)n(alent)i (characterization)i(of)23 b(uniform)i(TC)3044 2118 y Fs(0)3084 2154 y FG(.)589 2267 y(F)o(or)e(this)g(reason,)h(uniform)h(A) l(C)1610 2231 y Fs(0)1672 2267 y FG(is)e(frequently)i(referred)g(to)e (as)g(FO)e(\(for)j(\223\002rst)f(order\224\),)448 2379 y(and)28 b(uniform)h(TC)1042 2344 y Fs(0)1109 2379 y FG(is)e(frequently)j(referred)g(to)d(as)h(FOM)e(\(for)i (\223\002rst-order)i(with)f(M)t Fo(A)t(J)t(O)t(R)t FG(-)450 2492 y Fo(I)t(T)t(Y)r FG(\224\).)589 2605 y(The)g(logical)i(frame)n(w)o (ork)f(gi)n(v)o(es)f(rise)h(to)f(a)g(natural)h(notion)h(of)e (reducibility)-6 b(.)49 b(Suppose)448 2718 y(that)22 b(language)h FD(A)d FG(can)i(be)e(e)o(xpressed)k(by)d(a)f (\002rst-order)j(formula)f(\(or)f(a)f(FOM)f(formula\))j(with)448 2831 y(a)h(ne)n(w)g(predicate)j(symbol)f FD(Q)p FG(.)i(Then)d(we)f(say) h(that)g FD(A)f FG(is)g(in)g(FO)d Fq(+)g FD(Q)i FG(\(or)i(FOM)19 b Fq(+)h FD(Q)p FG(\).)589 2944 y(There)28 b(are)f(yet)g(more)g(types)h (of)f(reducibility)j(that)e(we')o(ll)f(need.)39 b(The)27 b(alert)g(reader)i(will)448 3057 y(ha)n(v)o(e)38 b(noticed)g(that)g (Figure)f(2)g(does)g(not)g(list)h Fx(any)f FG(complete)h(problems)g (for)f(TC)3155 3021 y Fs(0)3230 3057 y FG(under)448 3170 y FC(\024)519 3137 y Fs(A)n(C)621 3113 y Fr(0)519 3192 y FB(m)687 3170 y FG(reducibility)-6 b(.)46 b(This)28 b(is)g(because)i(it)e(is)g(widely)h(belie)n(v)o(ed)h(that)f(no)f(such)h (language)h(or)448 3283 y(function)i(e)o(xists!)50 b(On)29 b(the)h(other)h(hand,)i(TC)1907 3247 y Fs(0)1975 3283 y FG(does)e(ha)n(v)o(e)g(se)n(v)o(eral)g(natural)g(problems)h(that)448 3396 y(are)20 b(complete)i(under)f FC(\024)1228 3363 y Fs(A)n(C)1330 3339 y Fr(0)1228 3423 y FB(T)1388 3396 y FG(reductions,)i(including)i(M)t Fo(A)t(J)t(O)t(R)t(I)t(T)t(Y)r FG(,)d(inte)o(ger)f(multiplication,)448 3519 y(and)35 b(sorting.)64 b(Function)36 b FD(g)h FG(is)e FC(\024)1553 3486 y Fs(A)n(C)1655 3463 y Fr(0)1553 3546 y FB(T)1727 3519 y FG(reducible)i(to)d FD(f)43 b FG(if)35 b(there)g(is)f(a)h (uniform)g(f)o(amily)g(of)448 3632 y(polynomial-size,)g FD(O)s Fq(\(1\))p FG(-depth)d(circuits)f(of)h(A)t Fo(N)t(D)r FG(,)g(O)t Fo(R)r FG(,)e(and)i(N)t Fo(O)q(T)g FG(gates)e(and)g(\223)p FD(f)38 b FG(gates\224)448 3745 y(\(i.e.,)30 b(gates)g(with)f FD(m)f FG(input)i(wires)g(and)f FD(r)i FG(output)g(wires,)f(where)g (for)f(each)h FD(m)p FG(-bit)f(input)i FD(y)s FG(,)448 3858 y(the)24 b FD(r)g FG(output)h(wires)e(tak)o(e)h(on)f(the)h FD(r)s FG(-bit)f(v)n(alue)h FD(f)10 b Fq(\()p FD(y)s Fq(\))p FG(\),)22 b(where)h(the)g(circuit)i(f)o(amily)f(computes)448 3971 y FD(g)s FG(.)589 4084 y(In)g(the)g(same)f(w)o(ay)-6 b(,)23 b(we)g(can)h(de\002ne)g FC(\024)1815 4051 y Fs(TC)1917 4027 y Fr(0)1815 4111 y FB(T)1978 4084 y FG(reductions.)589 4208 y(W)-7 b(e)28 b(no)n(w)f(kno)n(w)h(that)g(di)n(vision)i(is)e(also) h(complete)g(for)f(TC)2496 4172 y Fs(0)2563 4208 y FG(under)h FC(\024)2868 4175 y Fs(A)n(C)2970 4151 y Fr(0)2868 4235 y FB(T)3036 4208 y FG(reductions.)448 4321 y(\(It)k(had)g(been)g(kno)n (wn)g(for)g(a)f(while)h(that)g(multiplication)j(reduces)f(to)d(di)n (vision,)37 b(and)c(thus)448 4434 y(di)n(vision)28 b(w)o(as)d(kno)n(wn) i(to)e(be)h(hard)h(for)f(TC)1840 4398 y Fs(0)1879 4434 y FG(.)35 b(In)26 b(f)o(act,)g(di)n(vision)i(had)e(been)h(kno)n(wn)f (to)g(be)f(in)448 4546 y(P-uniform)h(TC)962 4511 y Fs(0)1025 4546 y FG(e)n(v)o(er)f(since)h(it)e(w)o(as)g(observ)o(ed)j(in)d([27)r (,)f(28)q(])h(that)h(the)g(algorithm)i(of)d([9)q(])g(can)448 4659 y(be)i(implemented)i(in)d(P-uniform)i(TC)1669 4624 y Fs(0)1708 4659 y FG(.)35 b(The)25 b(breakthrough)30 b(of)25 b([18)q(])h(is)f(that)h(di)n(vision)i(is)d(in)448 4772 y(DLOGTIME)n(-uniform)g(TC)1385 4737 y Fs(0)1424 4772 y FG(.)p eop %%Page: 6 6 6 5 bop 448 573 a FH(3)120 b(Backgr)n(ound)30 b(on)h(Di)o(vision)448 780 y FG(All)22 b(of)f(the)h(recent)h(w)o(ork)f(on)g(di)n(vision)i(b)n (uilds)g(on)d(the)i(w)o(ork)f(of)f(Beame,)h(Cook,)g(and)g(Hoo)o(v)o(er) 448 893 y([9)q(].)63 b(Beame,)38 b(Cook,)g(and)e(Hoo)o(v)o(er)f(mak)o (e)h(use)f(of)g(the)h(f)o(act)g(that,)i(for)e(small)f(enough)i FD(u)p FG(,)448 1006 y Fq(1)p FD(=)p Fq(\(1)26 b FC(\000)d FD(u)p Fq(\))34 b(=)963 937 y Fn(P)1059 1033 y FB(i)p Fs(=0)1193 1006 y FD(u)1245 973 y FB(i)1273 1006 y FG(.)42 b(Thus)28 b(to)g(di)n(vide)h FD(x)e FG(by)h FD(y)s FG(,)g(we)g(\002rst) g(let)g FD(j)33 b FG(be)28 b(roughly)i(the)e(num-)448 1119 y(ber)38 b(of)f(bits)g(in)g FD(y)s FG(,)i(so)e Fq(2)1259 1086 y FB(j)t Fm(\000)p Fs(1)1437 1119 y FC(\024)50 b FD(y)j(<)d Fq(2)1822 1086 y FB(j)1859 1119 y FG(,)39 b(and)f(let)f FD(u)50 b Fq(=)g(1)31 b FC(\000)e Fq(\()p FD(y)s(=)p Fq(2)2788 1086 y FB(j)2826 1119 y Fq(\))p FG(.)69 b(Thus)37 b FD(x=y)53 b Fq(=)448 1231 y FD(x)p Fq(2)545 1199 y Fm(\000)p FB(j)637 1231 y Fq(\()672 1163 y Fn(P)768 1258 y FB(i)p Fs(=0)902 1231 y FD(u)954 1199 y FB(i)982 1231 y Fq(\))p FG(,)32 b(which)f(can)g(be)f(approximated)k (to)c FD(n)g FG(bits)h(of)f(accurac)o(y)j(by)d(computing)448 1344 y FD(x=y)f Fq(=)c FD(x)p Fq(2)812 1311 y Fm(\000)p FB(j)904 1344 y Fq(\()939 1276 y Fn(P)1035 1303 y FB(n)1035 1371 y(i)p Fs(=0)1168 1344 y FD(u)1220 1311 y FB(i)1249 1344 y Fq(\))p FG(.)i(Since)21 b(addition)j(of)d(polynomially-man)o(y)k (numbers)d(can)f(be)h(per)n(-)448 1468 y(formed)29 b(in)e(uniform)i(TC) 1271 1432 y Fs(0)1310 1468 y FG(,)f(this)g(entire)h(algorithm)g(can)f (be)g(vie)n(wed)g(as)f(a)h FC(\024)2927 1435 y Fs(TC)3029 1412 y Fr(0)2927 1495 y FB(T)3094 1468 y FG(reduction)448 1581 y(from)i(di)n(vision)i(to)e(the)g(problem)i(of)d(computing)k(the)d (po)n(wers)g FD(u)2551 1548 y FB(i)2580 1581 y FG(.)47 b(F)o(or)29 b(our)h(purposes,)k(we)448 1694 y(will)25 b(focus)h(on)f(the)g(more)g(general)h(problem)g(of)h(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)32 b FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)5 b(C)t(A)l(T)t(I)g(O)t(N)32 b FG(\(gi)n(v)o(en)26 b FD(n)448 1807 y FG(inte)o(gers,)f(each)f(of)g FD(n)e FG(bits,)i(compute)h(their) f(product\).)589 1920 y(That)31 b(is,)i(the)e(ar)n(gument)i(of)d (Beame,)i(Cook,)h(and)f(Hoo)o(v)o(er)f(sho)n(ws)g(that)g(if)i(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)450 2033 y FG(M)t Fo(U)t(L)m(T)t(I)t(P)t (L)t(I)t(C)t(A)l(T)5 b(I)g(O)t(N)31 b FG(is)24 b(in)f(FOM)o(,)g(so)h (is)g(di)n(vision.)32 b(Accordingly)-6 b(,)26 b(most)e(of)g(the)g(w)o (ork)g(in)g([9)q(])448 2146 y(focuses)i(on)d(presenting)k(ef)n (\002cient)d(circuits)h(for)h(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)31 b FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)g(O)t(N)r FG(.)589 2258 y(The)25 b(central)i(idea)e(of)g(all)g(the)g(TC)1669 2223 y Fs(0)1732 2258 y FG(algorithms)i(for)g(D)t Fo(I)t(V)t(I)t(S)t(I) t(O)t(N)j FG(and)25 b(related)i(problems)448 2371 y(is)j(that)h(of)f Fx(Chinese)h(r)m(emainder)g(r)m(epr)m(esentation)j(\(CRR\))p FG(.)28 b(An)h FD(n)p FG(-bit)h(number)h(is)f(uniquely)448 2484 y(determined)j(by)e(its)f(residues)j(modulo)f(polynomially)h(man)o (y)e(primes,)i(each)e(of)f FD(O)s Fq(\(log)17 b FD(n)p Fq(\))448 2597 y FG(bits.)29 b(\(The)24 b(Prime)e(Number)h(Theorem)h (guarantees)i(that)e(there)g(will)f(be)g(more)h(than)f(enough)448 2710 y(primes)31 b(of)e(that)i(length.\))49 b(More)30 b(precisely)-6 b(,)33 b(let)d FD(m)2123 2724 y Fs(1)2162 2710 y FD(;)15 b(:)g(:)g(:)i(;)e(m)2444 2725 y FB(k)2516 2710 y FG(be)30 b(a)f(sequence)j(of)e(primes,)448 2823 y(each)h(of)f FD(O)s Fq(\(log)17 b FD(n)p Fq(\))29 b FG(bits.)49 b(Let)30 b FD(M)47 b Fq(=)1704 2755 y Fn(Q)1790 2781 y FB(k)1790 2850 y(i)p Fs(=1)1924 2823 y FD(m)2004 2837 y FB(i)2032 2823 y FG(.)g(An)o(y)30 b(number)h FD(X)45 b(<)37 b(M)i FG(can)31 b(be)f(repre-)448 2936 y(sented)f(uniquely)g(by) e(the)g(sequence)j Fq(\()p FD(x)1752 2950 y Fs(1)1791 2936 y FD(;)15 b(:)g(:)g(:)i(;)e(x)2045 2951 y FB(k)2088 2936 y Fq(\))26 b FG(with)h FD(X)39 b FC(\021)31 b FD(x)2605 2950 y FB(i)2725 2936 y Fq(\(mo)s(d)e FD(m)3044 2950 y FB(i)3072 2936 y Fq(\))e FG(for)g(all)g FD(i)p FG(.)448 3049 y(The)f(sequence)i Fq(\()p FD(x)1060 3063 y Fs(1)1100 3049 y FD(;)15 b(:)g(:)g(:)i(;)e(x)1354 3064 y FB(k)1397 3049 y Fq(\))25 b FG(is)h(called)h(the)g(CRR)2105 3063 y FB(M)2208 3049 y FG(of)f FD(X)7 b FG(.)35 b(If)26 b FD(M)36 b FG(is)25 b(clear)i(from)f(conte)o(xt,)448 3162 y(we)d(will)g(simply)h(call)g(this)h(the)e(CRR)f(of)h FD(X)7 b FG(.)589 3275 y(F)o(or)20 b(each)h(number)h FD(i)p FG(,)e(let)h FD(C)1468 3289 y FB(i)1516 3275 y FG(be)f(the)h(product)h(of)f(all)f(the)h FD(m)2466 3289 y FB(j)2502 3275 y FG(')-5 b(s)21 b(e)o(xcept)g FD(m)2918 3289 y FB(i)2946 3275 y FG(,)f(and)h(let)g FD(h)3303 3289 y FB(i)3351 3275 y FG(be)448 3388 y(the)j(in)l(v)o(erse)h(of)e FD(C)1025 3402 y FB(i)1076 3388 y FG(modulo)h FD(m)1456 3402 y FB(i)1484 3388 y FG(.)k(It)23 b(is)h(easy)g(to)f(v)o(erify)h (that)g FD(X)30 b FG(is)23 b(congruent)j(modulo)f FD(M)32 b FG(to)448 3432 y Fn(P)544 3459 y FB(k)544 3527 y(i)p Fs(=1)678 3500 y FD(x)730 3514 y FB(i)758 3500 y FD(h)810 3514 y FB(i)838 3500 y FD(C)903 3514 y FB(i)932 3500 y FG(.)f(In)25 b(f)o(act)g FD(X)31 b FG(is)25 b Fx(equal)p FG(,)h(as)e(an)h(inte)o(ger)l(,)h(to)f Fq(\()2318 3432 y Fn(P)2414 3459 y FB(k)2414 3527 y(i)p Fs(=1)2548 3500 y FD(x)2600 3514 y FB(i)2628 3500 y FD(h)2680 3514 y FB(i)2708 3500 y FD(C)2773 3514 y FB(i)2802 3500 y Fq(\))c FC(\000)g FD(r)s(M)33 b FG(for)25 b(some)448 3613 y(particular)h (number)e FD(r)s FG(,)e(called)j(the)e Fx(r)o(ank)h FG(of)f FD(X)30 b FG(with)23 b(respect)i(to)e FD(M)33 b FG(\(denoted)25 b(rank)3152 3627 y FB(M)3231 3613 y Fq(\()p FD(X)7 b Fq(\))p FG(\).)589 3726 y(Here)32 b(I)e(am)h(follo)n(wing)i(the)e(con)l (v)o(ention)k(introduced)f(in)d([6)q(])f(of)i(using)g(capital)h (letters)448 3839 y(\(such)26 b(as)f FD(X)r(;)15 b(M)10 b FG(,)25 b(etc.\))33 b(to)24 b(refer)i(to)f(numbers)h(with)e(bit)h (length)h(polynomially-related)31 b(to)25 b FD(n)448 3952 y FG(\(call)k(these)f(\223long)h(numbers\224\),)h(and)e(lo)n(wer)n (-case)h(letters)g(\(such)g(as)e FD(r)m(;)15 b(x)2792 3966 y FB(i)2821 3952 y FG(,)28 b(etc.\))41 b(to)27 b(refer)h(to)448 4065 y(numbers)f(with)f(bit)g(length)h FD(O)s Fq(\(log)17 b FD(n)p Fq(\))25 b FG(\(call)h(these)h(\223short)g(numbers\224\).)37 b(In)26 b(particular)l(,)j(note)448 4178 y(that)24 b FD(r)i FG(is)d(a)g(short)i(number)-5 b(.)589 4291 y(The)19 b(algorithm)i(of)d(Beame,)i(Cook,)f(and)h(Hoo)o(v)o(er)f(can)g(be)g (summed)g(up)g(in)g(the)g(follo)n(wing)448 4404 y(three)25 b(lines:)562 4591 y(1.)46 b(Con)l(v)o(erting)25 b(from)f(binary)h(to)e (CRR)f(is)h(in)h(L-uniform)g(TC)2549 4556 y Fs(0)2589 4591 y FG(.)562 4779 y(2.)48 b(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)37 b FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)t(O)t(N)37 b FG(is)29 b(in)g(L-uniform)i(TC)2513 4743 y Fs(0)2552 4779 y FG(,)f(if)f(the)h(input)h(and)f(output)676 4892 y(are)23 b(in)h(CRR.)p eop %%Page: 7 7 7 6 bop 562 573 a FG(3.)46 b(Con)l(v)o(erting)25 b(from)f(CRR)d(to)j (binary)h(is)e(in)h(P-uniform)g(TC)2544 537 y Fs(0)2584 573 y FG(.)589 760 y(Let)f(us)h(consider)i(the)d(\002rst)h(tw)o(o)f(of) g(these)i(points.)589 873 y(T)-7 b(o)33 b(con)l(v)o(ert)i(an)e FD(n)p FG(-bit)h(number)g FD(X)40 b FG(from)33 b(binary)i(to)e(CRR)f (we)g(merely)i(need)g(to)g(\002nd)448 986 y FD(x)500 1000 y FB(i;j)623 986 y Fq(=)42 b(2)781 953 y FB(j)909 986 y Fq(\(mo)s(d)30 b FD(m)1229 1000 y FB(i)1257 986 y Fq(\))i FG(for)h(each)g(modulus)i FD(m)2086 1000 y FB(i)2146 986 y FG(and)e(each)g FD(j)48 b(<)42 b(n)32 b FG(such)h(that)h(bit)f FD(j)k FG(of)448 1099 y FD(X)e FG(is)28 b(1.)42 b(T)-7 b(aking)29 b(the)g(sum)1351 1031 y Fn(P)1447 1126 y FB(j)1499 1099 y FD(x)1551 1113 y FB(i;j)1656 1099 y Fq(mo)s(d)c FD(m)1936 1113 y FB(i)1991 1099 y FG(gi)n(v)o(es)k(us)f(the)h(v)n(alue)g FD(x)2728 1113 y FB(i)2783 1099 y FG(in)f(the)h(CRR)d(of)i FD(X)7 b FG(.)448 1224 y(Since)26 b(the)f(v)n(alues)h Fq(2)1109 1191 y FB(j)1171 1224 y Fq(mo)s(d)f FD(m)1451 1238 y FB(i)1503 1224 y FG(are)g(easy)h(to)f(compute)h(in)f(L,)f(this)i(part)f (of)g(the)h(ar)n(gument)g(is)448 1337 y(established.)589 1450 y(Computing)37 b(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)k FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)g(O)t(N)40 b FG(in)33 b(CRR)e(is)j(easy)-6 b(,)36 b(when)d(we)g(observ)o(e)448 1563 y(that)d(we)f(can)g(add)h(the)g(discrete)h(logs.)47 b(More)29 b(precisely)-6 b(,)33 b(each)d(prime)g(modulus)h FD(m)3191 1577 y FB(i)3247 1563 y FG(has)f(a)448 1676 y(generator)j FD(g)864 1690 y FB(i)922 1676 y FG(generating)g(the)e (\(c)o(yclic\))g(multiplicati)n(v)o(e)i(group)f(of)e(the)g(inte)o(gers) i(mod)e FD(m)3386 1690 y FB(i)3414 1676 y FG(.)448 1802 y(That)c(is,)g(for)g(each)g FD(x)k(<)f(m)1333 1816 y FB(i)1386 1802 y FG(there)d(is)g(a)f(number)i FD(`)p Fq(\()p FD(x)p Fq(\))f FG(such)g(that)h FD(x)i FC(\021)g FD(g)2812 1754 y FB(`)p Fs(\()p FB(x)p Fs(\))2809 1829 y FB(i)3031 1802 y Fq(\(mo)s(d)h FD(m)3351 1816 y FB(i)3379 1802 y Fq(\))p FG(.)448 1914 y(W)-7 b(e)30 b(are)g(gi)n(v)o(en)h(a)f (sequence)j(of)d(numbers)i FD(X)1921 1928 y Fs(1)1960 1914 y FD(;)15 b(:)g(:)g(:)i(;)e(X)2237 1928 y FB(n)2314 1914 y FG(in)30 b(CRR,)e(and)j(we)f(w)o(ant)g(to)g(com-)448 2027 y(pute)638 1959 y Fn(Q)724 2054 y FB(j)776 2027 y FD(X)851 2041 y FB(j)888 2027 y FG(.)60 b(Thus,)36 b(for)f(each)g(modulus)g FD(i)f FG(we)f(w)o(ant)i(to)f(compute)2761 1959 y Fn(Q)2847 2054 y FB(j)2899 2027 y FD(X)2974 2041 y FB(j)3056 2027 y FC(\021)3171 1959 y Fn(Q)3257 2054 y FB(j)3309 2027 y FD(x)3361 2041 y FB(j;i)448 2187 y Fq(\(mo)s(d)c FD(m)768 2201 y FB(i)796 2187 y Fq(\))c FC(\021)953 2119 y Fn(Q)1039 2214 y FB(j)1090 2187 y FD(g)1136 2136 y FB(`)p Fs(\()p FB(x)1232 2146 y Fl(j;i)1303 2136 y Fs(\))1133 2214 y FB(i)1426 2187 y Fq(\(mo)s(d)k FD(m)1746 2201 y FB(i)1774 2187 y Fq(\))25 b FC(\021)g FD(g)1976 2075 y Fk(P)2051 2146 y Fl(j)2096 2125 y FB(`)p Fs(\()p FB(x)2192 2135 y Fl(j;i)2262 2125 y Fs(\))1973 2214 y FB(i)2385 2187 y Fq(\(mo)s(d)k FD(m)2704 2201 y FB(i)2732 2187 y Fq(\))p FG(.)589 2300 y(In)d(logspace,)i(it)d(is)g (easy)h(to)g(b)n(uild)g(a)f(table)i(of)e(discrete)j(logs)e(for)f(each)i (small)e(modulus,)448 2413 y(and)33 b(hardwire)h(this)f(into)h(an)e (L-uniform)i(TC)1947 2377 y Fs(0)2018 2413 y FG(circuit.)58 b(Thus)32 b(we)g(can)h(\002nd)f(the)h(discrete)448 2526 y(logs)26 b(of)g(each)g FD(x)968 2540 y FB(j;i)1068 2526 y FG(and)g(we)f(add)g(them)h(mod)f FD(m)1983 2540 y FB(i)2011 2526 y FG(,)f(and)i(then)g(\(again)h(using)f(our)g(discrete)h(log)448 2639 y(table\))k(\002nd)d(the)i(result)g(of)f(raising)i FD(g)1646 2653 y FB(i)1703 2639 y FG(to)e(that)g(po)n(wer)-5 b(.)46 b(This)29 b(gi)n(v)o(es)g(us)h(one)f(component)i(of)448 2752 y(our)24 b(answer)g(in)g(CRR.)589 2865 y(The)d(remaining)i(part)f (of)f(the)g(algorithm)i(in)e(Beame,)g(Cook,)h(and)f(Hoo)o(v)o(er)g(is)g (con)l(v)o(erting)448 2977 y(from)j(CRR)d(to)j(binary)-6 b(.)30 b(As)22 b(presented)k(in)e([9])f(\(see)h(also)g([21)q(]\),)f (the)h(basic)h(approach)g(w)o(as)e(to)448 3090 y(note)e(that)f FD(X)26 b FG(is)19 b(equal)i(to)e Fq(\()1299 3022 y Fn(P)1396 3048 y FB(k)1396 3117 y(i)p Fs(=1)1529 3090 y FD(x)1581 3104 y FB(i)1609 3090 y FD(h)1661 3104 y FB(i)1690 3090 y FD(C)1755 3104 y FB(i)1783 3090 y Fq(\))5 b FC(\000)g FD(r)s(M)10 b FG(.)27 b(If)20 b(the)g(binary)h(representation)i(of)d FD(M)29 b FG(w)o(as)448 3214 y(gi)n(v)o(en,)24 b(then)g(the)f(v)n(alue) h Fq(\()1256 3145 y Fn(P)1352 3172 y FB(k)1352 3240 y(i)p Fs(=1)1486 3214 y FD(x)1538 3228 y FB(i)1566 3214 y FD(h)1618 3228 y FB(i)1647 3214 y FD(C)1712 3228 y FB(i)1740 3214 y Fq(\))f FG(could)h(be)f(computed)i(in)e(binary)-6 b(.)30 b(It)23 b(w)o(as)g(not)g(clear)448 3326 y(ho)n(w)h(to)g(compute)i(the)e (number)h FD(r)h FG(\(the)f(rank)g(of)f FD(X)7 b FG(\),)24 b(b)n(ut)h(since)g FD(r)h FG(is)e(a)g(short)h(number)l(,)g(there)448 3439 y(are)30 b(not)f(man)o(y)g(possible)j(v)n(alues)e(for)f FD(r)s FG(.)45 b(Thus)29 b(the)g(circuit)i(could)f(try)g(all)f (possible)i(v)n(alues)448 3552 y(of)d Fq(\()586 3484 y Fn(P)682 3510 y FB(k)682 3579 y(i)p Fs(=1)815 3552 y FD(x)867 3566 y FB(i)896 3552 y FD(h)948 3566 y FB(i)976 3552 y FD(C)1041 3566 y FB(i)1069 3552 y Fq(\))c FC(\000)f FD(r)s(M)36 b FG(and)28 b(pick)g(the)g(right)g(one.)41 b(The)27 b(bottleneck)j(w)o(as)d(that)h(nobody)448 3665 y(kne)n(w)c(ho)n(w)f(to)g(compute)i(the)f(binary)h(representation)j(of) 23 b FD(M)33 b FG(in)23 b(logspace)j(\(although)g(it)e(w)o(as)448 3778 y(easy)h(to)e(compute)i(this)f(in)f(polynomial)j(time\).)589 3891 y(A)d(ne)n(w)g(approach)j(w)o(as)d(needed.)448 4184 y FH(4)120 b(Br)n(eaking)30 b(the)g(Logspace)f(Barrier)448 4391 y FG(Andre)n(w)c(Y)-12 b(.)23 b(Chiu)i(recei)n(v)o(ed)h(his)f(MS)f (de)o(gree)h(from)g(the)g(Uni)n(v)o(ersity)h(of)f(W)l(isconsin)i(at)d (Mil-)448 4504 y(w)o(auk)o(ee)k(in)f(August,)h(1995.)39 b(A)25 b(mathematical)k(prodigy)-6 b(,)29 b(he)e(subsequently)k(left)c (computer)448 4616 y(science)f(to)d(enter)h(la)o(w)f(school.)589 4729 y(His)30 b(MS)e(thesis)j([12)r(])e(remained)i(unkno)n(wn)g(to)f (most)g(of)g(the)g(community)h(for)f(se)n(v)o(eral)448 4842 y(years.)j(No)23 b(paper)j(summarizing)g(its)f(contrib)n(utions)k (w)o(as)24 b(presented)j(at)d(an)o(y)g(of)h(the)f(confer)n(-)448 4955 y(ences)30 b(where)e(researchers)k(usually)e(announce)h(their)e (latest)g(theorems.)45 b(No)28 b(technical)i(re-)p eop %%Page: 8 8 8 7 bop 448 573 a FG(port)26 b(w)o(as)e(published)j(on)e(ECCC)d(or)i (on)h(an)o(y)g(of)f(the)h(other)g(repositories)j(for)d(such)g (material.)448 686 y(W)-7 b(e)26 b(all)g(o)n(we)g(a)g(great)h(debt)g (to)g(Chiu')-5 b(s)27 b(advisor)l(,)i(Geor)n(ge)e(Da)n(vida,)h(and)f (to)f(his)h(collaborator)448 799 y(Bruce)33 b(Lito)n(w)-6 b(,)34 b(for)f(preparing)j(a)c(paper)i(b)n(uilding)h(on)e(his)g(w)o (ork)g(for)g(journal)i(submission)448 912 y([13)r(].)589 1024 y(Chiu')-5 b(s)32 b(MS)d(thesis)j([12)q(])e(sho)n(ws)h(that)h(di)n (vision)g(and)h(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)39 b FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)t(O)t(N)448 1137 y FG(lie)24 b(in)f(uniform)i(NC)1097 1102 y Fs(1)1137 1137 y FG(.)589 1250 y(In)33 b(this)g(surv)o(e)o(y)-6 b(,)35 b(I')o(ll)d(sk)o(etch)i(for)f(no)n(w)e(only)i(a)f(proof)i(that)f (these)g(problems)h(lie)e(in)g(L-)448 1363 y(uniform)26 b(TC)881 1328 y Fs(0)921 1363 y FG(.)31 b(As)24 b(observ)o(ed)i(in)f (the)g(pre)n(vious)h(section,)h(it)d(is)h(suf)n(\002cient)h(to)e(sho)n (w)h(that)g(one)448 1476 y(can)f(con)l(v)o(ert)i(from)d(CRR)f(to)h (binary)i(in)f(L-uniform)g(TC)2251 1440 y Fs(0)2291 1476 y FG(.)589 1589 y(F)o(ollo)n(wing)19 b(the)f(de)n(v)o(elopment)j(in)d ([6],)h(I')o(ll)f(actually)i(state)f(and)g(sk)o(etch)g(a)f(slightly)i (stronger)448 1702 y(result.)48 b(Let)29 b(PO)m(W)o Fq(\()p FD(a;)15 b(i;)g(b;)g(p)p Fq(\))31 b FG(be)e(de\002ned)i(to)e(be)h(true) g(if)f(and)h(only)g(if)g FD(a)2815 1669 y FB(i)2879 1702 y FC(\021)36 b FD(b)91 b Fq(\(mo)s(d)30 b FD(p)p Fq(\))448 1815 y FG(where)d FD(a)p FG(,)f FD(b)p FG(,)g FD(i)g FG(and)h FD(p)e FG(each)i(ha)n(v)o(e)g FD(O)s Fq(\(log)17 b FD(n)p Fq(\))26 b FG(bits,)h(and)g FD(p)e FG(is)h(prime.)38 b(W)-7 b(e')o(ll)26 b(sho)n(w)h(that)g(con-)448 1928 y(v)o(erting)36 b(from)f(CRR)d(to)j(binary)h(is)e(in)h(FOM)27 b Fq(+)h FG(PO)m(W)o(.)61 b(It)34 b(is)g(easy)i(to)e(see)h(that)g(PO)m (W)d(is)448 2041 y(computable)26 b(in)e(logspace,)h(as)f(desired.)589 2154 y(The)k(reader)h(can)f(check)h(that)f(the)h(L-uniform)f(TC)2227 2118 y Fs(0)2294 2154 y FG(circuits)i(for)e(con)l(v)o(erting)i(from)e (bi-)448 2267 y(nary)j(to)f(CRR)d(and)k(for)f(computing)k(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)j FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C) t(A)l(T)5 b(I)g(O)t(N)36 b FG(in)30 b(CRR)e(represen-)448 2379 y(tation)k(can)f(actually)i(be)d(implemented)j(in)d(FOM)25 b Fq(+)g FG(PO)m(W)n(.)49 b(Thus,)32 b(if)f(we)e(can)i(sho)n(w)g(that) 448 2492 y(con)l(v)o(erting)c(from)d(CRR)e(to)i(binary)i(is)d(in)h(FOM) c Fq(+)g FG(PO)m(W)o(,)j(it)h(will)f(follo)n(w)h(that)h(di)n(vision)h (lies)448 2605 y(in)e(this)g(class.)30 b(\(In)24 b(f)o(act,)g(it)f(is)h (sho)n(wn)g(in)f([6)q(])g(that)h(di)n(vision)i(is)d Fx(complete)i FG(for)f(FOM)c Fq(+)g FG(PO)m(W)n(,)448 2718 y(and)28 b(that)f(it)g(follo)n(ws)g(from)g(a)f(well-kno)n(wn)i(number)n (-theoretic)k(conjecture)e(that)d(PO)m(W)e(lies)448 2831 y(in)f(FOM)o(.)k(Both)23 b(of)h(these)g(latter)h(results)g(are)f (superseded)i(by)e([18)q(].\))589 2944 y(In)33 b(this)g(o)o(v)o(ervie)n (w)-6 b(,)35 b(I)d(will)g(state)h(and)g(gi)n(v)o(e)g(a)f(hint)h(of)f (the)h(main)f(lemmas.)56 b(F)o(or)31 b(more)448 3057 y(details,)25 b(the)f(reader)h(can)f(consult)h([6)q(].)448 3269 y Ft(Lemma)e(4.1)46 b Fx(Let)24 b FD(p)g Fx(be)g(a)h(short)g (prime)o(.)32 b(Then)25 b(the)g(binary)h(r)m(epr)m(esentation)i(of)d Fq(1)p FD(=p)f Fx(can)h(be)448 3382 y(computed)g(to)f FD(n)973 3349 y FB(O)r Fs(\(1\))1145 3382 y Fx(bits)g(of)g(accur)o(acy) h(in)f FG(FO)19 b Fq(+)h FG(PO)m(W)o Fx(.)448 3595 y Ft(Pr)n(oof)o(.)28 b FG(The)18 b(reader)i(may)f(wish)g(to)g(pro)o(v)o (e)g(that)h(if)e FD(p)g FG(is)h(an)g(odd)g(prime,)h(then)g(the)f(the)g FD(k)s FG(th)g(bit)g(of)448 3708 y(the)26 b(binary)h(e)o(xpansion)g(of) f(the)f(rational)i(number)g Fq(1)p FD(=p)e FG(is)g(the)g(lo)n(w-order)i (bit)f(of)f Fq(2)3101 3675 y FB(k)3169 3708 y Fq(mo)s(d)g FD(p)p FG(.)p 448 3821 48 48 v 589 3934 a(It)f(is)h(not)f(at)g(all)h (ob)o(vious)h(ho)n(w)d(to)h(tell,)h(gi)n(v)o(en)g(tw)o(o)f(numbers)h (in)f(CRR,)e(which)j(is)f(lar)n(ger)-5 b(.)448 4046 y(Logspace)40 b(algorithms)g(for)e(this)h(were)f(presented)i(in)e([14)q(,)f(15)q(].) 72 b(Using)38 b(the)h(preceding)448 4159 y(lemma,)23 b(we)g(obtain)i(yet)f(another)h(algorithm.)448 4372 y Ft(Lemma)e(4.2)46 b Fx(Let)37 b FD(X)45 b Fx(and)39 b FD(Y)57 b Fx(be)38 b(number)o(s)h(less)g(than)g FD(M)47 b Fx(given)39 b(in)f(CRR)2980 4386 y FB(M)3095 4372 y Fx(form.)72 b(In)448 4485 y FG(FOM)20 b Fq(+)f FG(PO)m(W)j Fx(we)h(can)h(determine)h(whether)g FD(X)32 b(<)25 b(Y)20 b Fx(.)448 4697 y Ft(Pr)n(oof)o(.)33 b FG(Clearly)-6 b(,)26 b FD(X)35 b(<)28 b(Y)44 b FG(if)24 b(and)i(only)f(if)g FD(X=)-5 b(M)38 b(<)27 b(Y)10 b(=)-5 b(M)10 b FG(.)32 b(Thus)25 b(it)g(is)g(suf)n(\002cient)h(to)e(sho)n(w)448 4810 y(that)g(we)f(can)h(compute)h FD(X=)-5 b(M)33 b FG(to)23 b(polynomially-man)o(y)28 b(bits)c(of)f(accurac)o(y)-6 b(.)p eop %%Page: 9 9 9 8 bop 589 573 a FG(Recall)24 b(that)h FD(X)32 b Fq(=)25 b(\()1242 505 y Fn(P)1339 531 y FB(k)1339 600 y(i)p Fs(=1)1472 573 y FD(x)1524 587 y FB(i)1552 573 y FD(h)1604 587 y FB(i)1633 573 y FD(C)1698 587 y FB(i)1726 573 y Fq(\))20 b FC(\000)g FG(rank)2034 587 y FB(M)2113 573 y Fq(\()p FD(x)p Fq(\))p FD(M)10 b FG(.)29 b(Thus)23 b FD(X=)-5 b(M)33 b FG(is)24 b(equal)g(to)1369 868 y Fq(\()1451 755 y FB(k)1404 782 y Fn(X)1413 977 y FB(i)p Fs(=1)1551 868 y FD(x)1603 882 y FB(i)1631 868 y FD(h)1683 882 y FB(i)1712 868 y Fq(\(1)p FD(=m)1917 882 y FB(i)1946 868 y Fq(\)\))d FC(\000)f FG(rank)2289 882 y FB(M)2368 868 y Fq(\()p FD(x)p Fq(\))p FD(:)448 1149 y FG(The)i(reader)g(can)g(v)o (erify)h(that)f(the)g(numbers)h FD(x)1917 1163 y FB(i)1945 1149 y FG(,)e FD(C)2054 1163 y FB(i)2108 1149 y Fq(mo)s(d)j FD(m)2387 1163 y FB(i)2415 1149 y FG(,)d(and)h FD(h)2663 1163 y FB(i)2712 1149 y FG(are)g(easy)h(to)e(obtain)i(in)448 1262 y(FOM)e Fq(+)h FG(PO)m(W)o(.)35 b(By)26 b(Lemma)f(4.1,)h(each)h (summand)f(can)h(be)f(computed)i(in)d(FOM)d Fq(+)f FG(PO)m(W)448 1375 y(to)28 b FD(n)601 1342 y FB(O)r Fs(\(1\))777 1375 y FG(bits)g(of)g(accurac)o(y)-6 b(.)43 b(Hence)28 b(we)f(obtain)i (polynomially-man)o(y)j(bits)c(of)g(the)g(binary)448 1488 y(representation)e(of)21 b Fq(\()1115 1420 y Fn(P)1211 1446 y FB(k)1211 1515 y(i)p Fs(=1)1344 1488 y FD(x)1396 1502 y FB(i)1425 1488 y FD(h)1477 1502 y FB(i)1505 1488 y Fq(\(1)p FD(=m)1710 1502 y FB(i)1739 1488 y Fq(\)\))p FG(,)h(which)f(is)g(equal)h(to)f FD(X=)-5 b(M)22 b Fq(+)11 b FG(rank)2953 1502 y FB(M)3032 1488 y Fq(\()p FD(X)c Fq(\))p FG(.)28 b(Since)448 1601 y(the)c(rank)g(is)g(an)f(inte)o(ger)l (,)i FD(X=)-5 b(M)33 b FG(is)24 b(simply)g(the)g(fractional)i(part)e (of)f(this)h(v)n(alue.)p 3390 1601 48 48 v 589 1714 a(A)k(crucial)i (insight)g(of)f([13)q(])f(is)g(that)h(it)g(is)f(easy)h(to)g(change)h (from)e(CRR)f(representation)448 1827 y(with)d(one)f(set)h(of)f (moduli,)h(to)g(CRR)d(representation)28 b(using)d(another)g(set)e(of)h (moduli.)29 b(This)23 b(is)448 1939 y(called)i Fx(c)o(hanging)h(the)e (CRR)d(basis)p FG(.)448 2152 y Ft(Lemma)i(4.3)46 b Fx(Given)22 b FD(X)29 b Fx(in)22 b(CRR)1535 2166 y FB(M)1634 2152 y Fx(and)g(a)g(short)h(prime)f FD(p)p Fx(,)f(we)g(can)h(compute)h FD(X)33 b Fq(mo)s(d)25 b FD(p)20 b Fx(in)448 2265 y FG(FOM)g Fq(+)f FG(PO)m(W)o Fx(.)448 2477 y Ft(Pr)n(oof)o(.)54 b FG(Assume)32 b(wlog)g(that)g FD(p)f FG(does)h(not)g(di)n(vide)h FD(M)10 b FG(.)53 b(In)32 b(this)g(case,)i(consider)g(the)e(CRR)448 2590 y(base)24 b FD(M)730 2557 y Fm(0)779 2590 y Fq(=)h FD(M)10 b(p)p FG(.)27 b(W)-7 b(e)22 b(w)o(ould)i(lik)o(e)f(to)g (compute)h FD(X)30 b FG(in)23 b(CRR)2425 2606 y FB(M)2500 2587 y Fj(0)2525 2590 y FG(,)f(since)i(this)g(w)o(ould)f(gi)n(v)o(e)g (us)448 2703 y FD(X)33 b Fq(mo)s(d)25 b FD(p)p FG(.)589 2816 y(T)m(rying)32 b(each)g(of)f(the)g FD(p)39 b Fq(=)g FD(n)1558 2783 y FB(O)r Fs(\(1\))1738 2816 y FG(possible)33 b(v)n(alues)f FD(i)f FG(for)g FD(X)i Fq(mo)s(d)25 b FD(p)p FG(,)31 b(we)f(obtain)j(the)448 2929 y FD(C)7 b(R)q(R)659 2944 y FB(M)734 2925 y Fj(0)789 2929 y FG(of)29 b FD(n)948 2896 y FB(O)r Fs(\(1\))1126 2929 y FG(dif)n(ferent)i(numbers)g FD(X)1882 2943 y Fs(0)1922 2929 y FD(;)15 b(X)2037 2943 y Fs(1)2077 2929 y FD(;)g(:)g(:)g(:)i(;)e(X)2354 2943 y FB(p)p Fm(\000)p Fs(1)2484 2929 y FG(,)30 b(one)g(of)f(which)h(is)f FD(X)7 b FG(.)46 b(It)29 b(is)448 3042 y(easy)e(to)f(see)g(that)h FD(X)32 b FG(is)26 b(the)g(only)h(one)f(of)g(these)h(numbers)g(that)g (is)f(less)g(than)h FD(M)10 b FG(.)35 b(Since)26 b(we)448 3155 y(can)e(compute)h(the)f FD(C)7 b(R)q(R)1278 3170 y FB(M)1353 3151 y Fj(0)1401 3155 y FG(of)24 b FD(M)10 b FG(,)22 b(the)i(lemma)f(no)n(w)g(follo)n(ws)h(from)g(Lemma)e(4.2.)p 3390 3155 V 589 3268 a(Another)36 b(important)h(insight)g(of)d([13)q(]) h(is)f(that)i(it)e(is)h(easy)h(to)e(di)n(vide)i(by)f(products)i(of)448 3381 y(distinct)26 b(short)e(primes.)448 3593 y Ft(Lemma)f(4.4)46 b Fx(Let)29 b FD(b)1112 3607 y Fs(1)1151 3593 y FD(;)15 b(:)g(:)g(:)i(;)e(b)1392 3608 y FB(`)1454 3593 y Fx(be)30 b(distinct)h(short)g(primes,)h FD(B)h Fx(be)c(the)h(pr)l(oduct)i(of)d (the)h FD(b)3324 3607 y FB(i)3352 3593 y Fx(')l(s,)448 3706 y(and)c(let)f FD(X)31 b Fx(be)25 b(given)h(in)e FG(CRR)1437 3720 y FB(M)1540 3706 y Fx(form.)32 b(Then)25 b(we)f(can)h(compute)h FC(b)p FD(X=B)5 b FC(c)p Fx(,)25 b(also)h(in)e FG(CRR)3358 3720 y FB(M)448 3819 y Fx(form,)f(in)h FG(FOM)19 b Fq(+)h FG(PO)m(W)o Fx(.)448 4032 y Ft(Pr)n(oof)o(.)45 b FG(Assume)29 b(without)h(loss)g(of)e(generality)k(that)d FD(B)k FG(di)n(vides)d FD(M)10 b FG(.)44 b(\(Otherwise,)31 b(e)o(xtend)448 4145 y(the)24 b(basis,)g(using)h(Lemma)e(4.3.\))28 b(Thus)c(let)g FD(M)35 b Fq(=)25 b FD(B)5 b(P)35 b FG(where)24 b FD(P)38 b Fq(=)2666 4076 y Fn(Q)2752 4103 y FB(k)2752 4171 y(i)p Fs(=1)2886 4145 y FD(p)2932 4159 y FB(i)2959 4145 y FG(.)589 4257 y(In)24 b(FOM)19 b Fq(+)h FG(PO)m(W)i(we)g(can)i (compute)h(the)f(follo)n(wing)h(quantities:)585 4445 y FC(\017)46 b FD(B)27 b FG(in)c(CRR)1048 4459 y FB(M)1149 4445 y FG(\(by)h(adding)h(the)f(discrete)h(logs)g(modulo)f(each)g FD(m)2746 4459 y FB(i)2774 4445 y FG(\),)585 4633 y FC(\017)46 b FG(The)29 b(CRR)1029 4647 y FB(M)1136 4633 y FG(of)g FD(S)42 b Fq(=)36 b(\()1480 4565 y Fn(P)1576 4591 y FB(`)1576 4660 y(i)p Fs(=1)1710 4633 y FD(x)1762 4647 y FB(i)1790 4633 y FD(h)1842 4647 y FB(i)1871 4633 y Fq(\()p FD(B)5 b(=b)2064 4647 y FB(i)2092 4633 y Fq(\)\))p FG(,)31 b(where)f FD(h)2519 4647 y FB(i)2576 4633 y FG(is)g(the)g(multiplicati)n(v)o(e)i (in-)676 4746 y(v)o(erse)24 b(of)f FD(B)5 b(=b)1145 4760 y FB(i)1199 4746 y Fq(mo)s(d)24 b FD(b)1437 4760 y FB(i)1465 4746 y FG(,)585 4933 y FC(\017)46 b FD(Y)f Fq(=)25 b FD(X)i FC(\000)20 b FD(S)28 b FG(in)c(CRR)1424 4947 y FB(M)1501 4933 y FG(,)p eop %%Page: 10 10 10 9 bop 585 573 a FC(\017)46 b FD(B)750 540 y Fm(\000)p Fs(1)869 573 y Fq(mo)s(d)24 b FD(P)34 b FG(\(i.e.,)22 b(the)g(unique)h(number)g FD(T)38 b(<)25 b(P)34 b FG(such)22 b(that)h FD(B)5 b(T)37 b FC(\021)25 b Fq(1)92 b(\(mo)s(d)29 b FD(P)13 b Fq(\))p FG(;)676 686 y(this)21 b(can)g(be)f(computed)j(in)d (CRR)1730 700 y FB(P)1808 686 y FG(by)h(merely)g(in)l(v)o(erting)i (each)e(nonzero)i(component)676 799 y(of)g(the)h(CRR)1091 813 y FB(M)1191 799 y FG(of)g FD(B)5 b FG(\).)448 980 y(The)21 b(important)i(things)f(to)f(note)h(are)f(that)h FD(S)30 b FC(\021)25 b FD(X)33 b Fq(mo)s(d)24 b FD(B)5 b FG(,)20 b(and)h(also)h FD(S)j FG(is)c(only)h(lar)n(ger)h(than)448 1093 y FD(B)29 b FG(by)c(a)f(polynomial)k(f)o(actor)-5 b(.)34 b(Since)25 b FD(Y)44 b FG(is)24 b(a)h(multiple)h(of)f FD(B)5 b FG(,)23 b FD(Y)10 b(=B)29 b FG(is)c(an)g(inte)o(ger)h(less)g (than)448 1206 y FD(P)13 b FG(.)31 b(Thus)25 b(if)f(we)g(compute)i FD(Y)20 b(T)37 b FG(in)24 b(CRR)1765 1220 y FB(P)1847 1206 y FG(we)f(ha)n(v)o(e)j(the)e(CRR)2486 1220 y FB(P)2568 1206 y FG(of)g(the)h(inte)o(ger)h FD(Y)10 b(=B)5 b FG(,)24 b(and)448 1319 y(from)g(this)g(we)f(can)g(compute)i FD(Y)10 b(=B)28 b FG(in)23 b FD(C)7 b(R)q(R)1924 1333 y FB(M)2003 1319 y FG(.)589 1432 y(Therefore)24 b FC(b)p FD(X=B)5 b FC(c)21 b FG(dif)n(fers)i(from)e FD(Y)10 b(=B)26 b FG(by)21 b(at)h(most)f(an)h(additi)n(v)o(e)h(term)e(of)h FD(n)3071 1399 y FB(O)r Fs(\(1\))3220 1432 y FG(.)27 b(That)448 1545 y(is,)36 b(we)c(can)i(compute)h(a)d(list)i(of)f FD(n)1589 1512 y FB(O)r Fs(\(1\))1771 1545 y FG(consecuti)n(v)o(e)j(v)n (alues,)h(one)d(of)f(which)h(is)f(equal)h(to)448 1658 y FC(b)p FD(X=B)5 b FC(c)p FG(.)28 b(W)-7 b(e)22 b(can)g(\002nd)g(the)g (correct)i(v)n(alue)f(by)f(determining)j(the)e(v)n(alue)g FD(j)k FG(such)c(that)f Fq(\()p FD(Y)f(T)27 b Fq(+)448 1771 y FD(j)5 b Fq(\))p FD(B)31 b FC(\024)25 b FD(X)33 b(<)25 b Fq(\()p FD(Y)20 b(T)33 b Fq(+)20 b FD(j)26 b Fq(+)20 b(1\))p FD(B)5 b FG(.)p 3390 1771 48 48 v 448 1976 a Ft(Theor)n(em)24 b(4.5)46 b Fx(Let)30 b FD(X)37 b Fx(be)31 b(given)h(in)e FG(CRR)1865 1990 y FB(M)1974 1976 y Fx(form.)50 b(Then)30 b(we)g(can)h(compute)h(the)f(binary)448 2089 y(r)m(epr)m(esentation)d(of)23 b FD(X)30 b Fx(in)24 b FG(FOM)19 b Fq(+)h FG(PO)m(W)o Fx(.)448 2294 y Ft(Pr)n(oof)o(.)29 b FG(As)20 b(observ)o(ed)k(in)d([13)r(],)g(it)g(is)g(suf)n(\002cient)i (to)f(sho)n(w)f(that)h(we)f(can)h(compute)g(the)g(CRR)3359 2308 y FB(M)448 2407 y FG(of)31 b FC(b)p FD(X=)p Fq(2)759 2374 y FB(k)803 2407 y FC(c)g FG(for)g(an)o(y)h FD(k)s FG(.)51 b(This)31 b(is)g(because,)j(to)d(get)h(the)f FD(k)s FG(-th)h(bit)f(of)g(a)g(number)h FD(X)38 b FG(that)31 b(is)448 2520 y(gi)n(v)o(en)e(to)e(us)h(in)g(CRR,)d(we)i(compute)i FD(u)k Fq(=)g FC(b)p FD(X=)p Fq(2)2075 2487 y FB(k)2119 2520 y FC(c)27 b FG(and)i FD(v)36 b Fq(=)d FC(b)p FD(X=)p Fq(2)2734 2487 y FB(k)r Fs(+1)2868 2520 y FC(c)p FG(,)28 b(and)g(note)h(that)448 2633 y(the)24 b(desired)h(bit)f(is)f FD(u)e FC(\000)f Fq(2)p FD(v)s FG(.)589 2746 y(First,)36 b(we)d(create)i(numbers)g FD(A)1617 2760 y Fs(1)1656 2746 y FD(;)15 b(:)g(:)g(:)i(;)e(A)1926 2761 y FB(k)1969 2746 y FG(,)35 b(each)g(a)e(product)i(of)f(polynomially)i(man)o(y)448 2859 y(short)26 b(odd)f(primes)g(that)h(do)e(not)h(di)n(vide)h FD(M)10 b FG(,)24 b(with)h(each)g FD(A)2338 2873 y FB(i)2394 2859 y FD(>)i(M)10 b FG(.)31 b(Let)24 b FD(P)40 b Fq(=)27 b FD(M)3099 2791 y Fn(Q)3185 2817 y FB(k)3185 2886 y(i)p Fs(=1)3318 2859 y FD(A)3386 2873 y FB(i)3414 2859 y FG(,)448 2972 y(and)22 b(compute)h FD(X)28 b FG(in)21 b(CRR)1311 2986 y FB(P)1368 2972 y FG(.)28 b(By)20 b(Lemma)g(4.4)h(\(or)h (directly\))h(we)e(can)h(compute)g Fq(\(1)12 b(+)g FD(A)3282 2986 y FB(i)3311 2972 y Fq(\))p FD(=)p Fq(2)448 3085 y FG(in)24 b(CRR)725 3099 y FB(P)782 3085 y FG(.)k(It)c(is)f(easy)h(to) g(sho)n(w)f(that)h Fq(\()1679 3016 y Fn(Q)1765 3043 y FB(k)1765 3111 y(i)p Fs(=1)1884 3085 y Fq(\()p FD(A)1987 3099 y FB(i)2036 3085 y Fq(+)19 b(1\)\))p FD(=)2301 3016 y Fn(Q)2389 3043 y FB(k)2389 3111 y(i)p Fs(=1)2523 3085 y FD(A)2591 3099 y FB(i)2644 3085 y FD(<)25 b Fq(1)c(+)f(\()p FD(k)s(=)-5 b(M)10 b Fq(\))p FG(.)589 3197 y(Note)27 b(that)h(in)f(FOM)22 b Fq(+)h FG(PO)m(W)i(we)h(can)i(compute)g(the)f (CRR)2535 3211 y FB(P)2619 3197 y FG(representation)32 b(of)27 b FD(Q)k Fq(=)448 3310 y FC(b)p FD(X)586 3242 y Fn(Q)672 3269 y FB(k)672 3337 y(i)p Fs(=1)791 3310 y Fq(\(\(1)17 b(+)f FD(A)1078 3324 y FB(i)1106 3310 y Fq(\))p FD(=)p Fq(2\))p FD(=)1326 3242 y Fn(Q)1414 3269 y FB(k)1414 3337 y(i)p Fs(=1)1548 3310 y FD(A)1616 3324 y FB(i)1644 3310 y FC(c)p FG(.)28 b(But)22 b FD(X)1986 3242 y Fn(Q)2072 3269 y FB(k)2072 3337 y(i)p Fs(=1)2190 3310 y Fq(\(\(1)c(+)e FD(A)2478 3324 y FB(i)2506 3310 y Fq(\))p FD(=)p Fq(2\))p FD(=)2726 3242 y Fn(Q)2814 3269 y FB(k)2814 3337 y(i)p Fs(=1)2947 3310 y FD(A)3015 3324 y FB(i)3066 3310 y FG(is)22 b(equal)h(to)448 3434 y Fq(\()p FD(X=)p Fq(2)648 3401 y FB(k)692 3434 y Fq(\)\()762 3365 y Fn(Q)849 3392 y FB(k)849 3460 y(i)p Fs(=1)967 3434 y Fq(\()p FD(A)1070 3448 y FB(i)1122 3434 y Fq(+)g(1\)\))p FD(=)1391 3365 y Fn(Q)1478 3392 y FB(k)1478 3460 y(i)p Fs(=1)1612 3434 y FD(A)1680 3448 y FB(i)1741 3434 y FD(<)32 b Fq(\()p FD(X=)p Fq(2)2044 3401 y FB(k)2088 3434 y Fq(\)\(1)24 b(+)f(\()p FD(k)s(=)-5 b(M)10 b Fq(\)\))p FG(.)42 b(W)-7 b(e)27 b(determine)i(which)448 3547 y(of)24 b FC(f)p FD(Q;)15 b(Q)21 b FC(\000)e Fq(1)p FC(g)24 b FG(is)f(the)h(correct)h (answer)g(by)e(checking)j(if)d FD(Q)p Fq(2)2433 3514 y FB(k)2502 3547 y FD(>)i(X)7 b FG(.)p 3390 3547 V 448 3838 a FH(5)120 b(Di)o(vision)30 b(in)g(Unif)m(orm)h(TC)1836 3795 y Fi(0)448 4045 y FG(In)e(order)g(to)g(present)h(Hesse')-5 b(s)30 b(FOM)d(di)n(vision)j(algorithm,)h(it)e(is)f(useful)i(to)f (de\002ne)g(param-)448 4158 y(eterized)i(v)o(ersions)f(of)f(the)g (three)h(problems)g(we)e(ha)n(v)o(e)h(been)h(studying)h(thus)e(f)o(ar) -5 b(.)45 b(Let)28 b FD(b)p Fq(\()p FD(n)p Fq(\))448 4271 y FG(be)i(a)e(function)k(on)d Fp(N)7 b FG(.)51 b(\(W)-7 b(e)29 b(will)g(need)h(to)f(consider)i(only)g FD(b)p Fq(\()p FD(n)p Fq(\))36 b FC(2)28 b(f)p FD(k)19 b Fq(log)d(log)h FD(n)p FG(,)29 b FD(k)18 b Fq(log)f FD(n)p FG(,)448 4384 y FD(k)i Fq(log)631 4347 y Fs(2)686 4384 y FD(n)p FG(,)j FD(n)p FC(g)g FG(for)i(v)n(arious)h(constants)h FD(k)s FG(.\))j(De\002ne)585 4565 y FC(\017)48 b FG(D)t Fo(I)t(V)t(I)t(S)t(I)t (O)t(N)1045 4584 y FB(b)p Fs(\()p FB(n)p Fs(\))1207 4565 y FG(to)27 b(be)h(the)g(problem)h(of)f(computing)i FC(b)p FD(X=)5 b(Y)20 b FC(c)28 b FG(where)g FD(X)34 b FG(and)28 b FD(Y)47 b FG(are)676 4678 y(inte)o(gers)25 b(with)e FD(b)p Fq(\()p FD(n)p Fq(\))g FG(bits.)585 4863 y FC(\017)48 b FG(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)31 b FG(M)t Fo(U)t(L)m(T)t(I)t(P) t(L)t(I)t(C)t(A)l(T)5 b(I)g(O)t(N)1761 4882 y FB(b)p Fs(\()p FB(n)p Fs(\))1922 4863 y FG(to)24 b(be)h(the)f(problem)h(of)g (taking)g FD(b)p Fq(\()p FD(n)p Fq(\))f FG(numbers)676 4976 y FD(X)751 4990 y Fs(1)790 4976 y FD(;)15 b(:)g(:)g(:)i(;)e(X)1067 4995 y FB(b)p Fs(\()p FB(n)p Fs(\))1222 4976 y FG(\(each)25 b(with)e FD(b)p Fq(\()p FD(n)p Fq(\))g FG(bits\))i(as)e(input,)i(and)f (computing)2894 4908 y Fn(Q)2980 5003 y FB(i)3023 4976 y FD(X)3098 4990 y FB(i)3127 4976 y FG(.)p eop %%Page: 11 11 11 10 bop 585 573 a FC(\017)46 b FG(PO)m(W)874 591 y FB(b)p Fs(\()p FB(n)p Fs(\))1032 573 y FG(to)26 b(be)h(the)g(problem)g (of)g(computing)h(PO)m(W)o Fq(\()p FD(a;)15 b(i;)g(b;)g(p)p Fq(\))p FG(,)28 b(where)f(each)g(of)f FD(a)p FG(,)676 686 y FD(i)p FG(,)c FD(b)p FG(,)h FD(p)f FG(has)i FD(b)p Fq(\()p FD(n)p Fq(\))f FG(bits.)589 873 y(Thus)k(the)g(preceding)i (section)g(sho)n(wed)e(that,)h(for)f(some)f FD(k)s FG(,)h(FOM)22 b Fq(+)g FG(PO)m(W)3050 888 y FB(k)13 b Fs(log)g FB(n)3276 873 y FG(con-)448 986 y(tains)25 b(both)h(I)t Fo(T)t(E)t(R)t(A)l(T)t(E) t(D)31 b FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)g(O)t(N)1912 1000 y FB(n)1987 986 y FG(and)26 b(D)t Fo(I)t(V)t(I)t(S)t(I)t(O)t(N)2510 1000 y FB(n)2560 986 y FG(.)589 1099 y(The)j(same)f(analysis)j(sho)n(ws)e(that)g(for)g(an)o (y)f(reasonable)k FD(b)p Fq(\()p FD(n)p Fq(\))p FG(,)f(D)t Fo(I)t(V)t(I)t(S)t(I)t(O)t(N)3004 1118 y FB(b)p Fs(\()p FB(n)p Fs(\))3167 1099 y FG(and)g(I)t Fo(T)m FG(-)450 1212 y Fo(E)t(R)t(A)l(T)t(E)t(D)d FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t (C)t(A)l(T)t(I)5 b(O)t(N)1447 1231 y FB(b)p Fs(\()q FB(n)p Fs(\))1606 1212 y FG(lie)21 b(inside)i(FOM)11 b Fq(+)h FG(PO)m(W)2446 1231 y FB(k)h Fs(log)g FB(b)p Fs(\()p FB(n)p Fs(\))2731 1212 y FG(.)28 b(A)20 b(direct)i(ar)n(gument)448 1325 y(sho)n(ws)f(that)g(for)g(small)f(enough)j FD(b)p Fq(\()p FD(n)p Fq(\))d FG(\(for)h(instance,)h(for)f FD(b)p Fq(\()p FD(n)p Fq(\))26 b(=)f FD(O)s Fq(\(log)16 b(log)h FD(n)p Fq(\))p FG(\),)j(PO)m(W)3305 1344 y FB(b)p Fs(\()p FB(n)p Fs(\))448 1438 y FG(is)k(in)f(FO)o(.)28 b(W)-7 b(e)23 b(thus)h(ha)n(v)o(e)g(the)g(follo)n(wing)h(corollary:)448 1650 y Ft(Cor)n(ollary)h(5.1)46 b Fx(F)-10 b(or)24 b(any)g(constant)i FD(k)s Fx(,)c(uniform)j FG(TC)2164 1615 y Fs(0)2226 1650 y Fx(contains)450 1763 y FG(D)t Fo(I)t(V)t(I)t(S)t(I)t(O)t(N)817 1790 y FB(k)17 b Fs(log)962 1764 y Fr(2)1008 1790 y FB(n)1078 1763 y Fx(and)26 b FG(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)31 b FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)g(O)t(N)2322 1790 y FB(k)19 b Fs(log)2469 1764 y Fr(2)2515 1790 y FB(n)2562 1763 y Fx(.)589 1989 y FG(Hesse')-5 b(s)23 b(theorem)g(sho)n(wing)f(that)g(di)n(vision)i(is)d(in)h(uniform)h(TC) 2605 1953 y Fs(0)2665 1989 y FG(thus)f(follo)n(ws)h(from)e(the)448 2102 y(preceding)26 b(corollary)g(and)e(the)g(follo)n(wing)h(theorem.) 448 2315 y Ft(Theor)n(em)f(5.2)46 b Fx([18)q(])23 b(F)-10 b(or)24 b(some)f(constant)j FD(k)s Fx(,)d FG(PO)m(W)e Fx(is)j(in)448 2427 y FG(FOM)o Fq(+)h FG(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t (D)31 b FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)t(O)t(N)1823 2442 y FB(k)19 b Fs(log)13 b FB(n)2029 2427 y Fq(+)25 b FG(D)t Fo(I)t(V)t(I)t(S)t(I)t(O)t(N)2492 2454 y FB(k)16 b Fs(log)2636 2428 y Fr(2)2683 2454 y FB(n)2730 2427 y Fx(.)448 2652 y Ft(Pr)n(oof)o(.)41 b FG(W)-7 b(e)26 b(are)i(gi)n(v)o(en)g FD(a;)15 b(b;)g(i)28 b FG(and)g FD(p)e FG(and)i(we)f(w)o(ant)g(to)g(determine)i(if)f FD(a)2800 2619 y FB(i)2860 2652 y FC(\021)k FD(b)91 b Fq(\(mo)s(d)30 b FD(p)p Fq(\))p FG(.)448 2765 y(Again,)23 b(we)g(will)g(resort)i(to)f(the)f(Chinese)i(Remainder)g(Theorem.)589 2877 y(In)g(FO)f(we)g(can)h(\002nd)g(a)f(list)h(of)g FD(k)31 b Fq(=)d FD(o)p Fq(\(log)17 b FD(n)p Fq(\))24 b FG(primes)h FD(d)2396 2891 y Fs(1)2436 2877 y FD(;)15 b(:)g(:)g(:)i(;)e(d)2685 2892 y FB(k)2728 2877 y FG(,)24 b(such)i(that)g(for)f(all)g FD(j)5 b FG(,)448 2990 y FD(d)495 3004 y FB(j)559 2990 y FD(<)27 b Fq(2)15 b(log)i FD(p)23 b FG(and)i FD(d)1121 3004 y FB(j)1181 2990 y FG(does)h(not)e(di)n(vide)i FD(p)21 b FC(\000)f Fq(1)p FG(.)31 b(\(In)25 b(this)g(o)o(v)o(ervie)n(w)-6 b(,)24 b(I')o(ll)h(ignore)h(the)f(details)448 3103 y(of)30 b(ho)n(w)e(to)i (\002nd)f(this)h(list.\))46 b(Furthermore,)33 b(we)28 b(can)i(\002nd)f(such)h(a)f(list)h(where)f FD(D)39 b Fq(=)3216 3035 y Fn(Q)3302 3130 y FB(j)3353 3103 y FD(d)3400 3117 y FB(j)448 3216 y FG(itself)25 b(has)f(only)g FD(O)s Fq(\(log)17 b FD(n)p Fq(\))23 b FG(bits.)589 3329 y(Our)39 b(ne)o(xt)h(step)g(is)f(to)g(compute,)44 b(for)c(each)g FD(j)5 b FG(,)42 b(the)e(v)n(alue)g FD(a)2622 3343 y FB(j)2713 3329 y Fq(=)54 b FD(a)2886 3296 y Fm(b)p Fs(\()p FB(p)p Fm(\000)p Fs(1\))p FB(=d)3168 3306 y Fl(j)3202 3296 y Fm(c)3263 3329 y Fq(mo)s(d)448 3442 y FD(p)p FG(.)60 b(T)-7 b(o)33 b(do)i(this,)i(compute)f FD(p)1412 3456 y FB(j)1493 3442 y Fq(=)45 b FD(p)25 b Fq(mo)s(d)g FD(d)1927 3456 y FB(j)1963 3442 y FG(.)61 b(\(Since)34 b(these)i(numbers)f(are)g (v)o(ery)f(small,)448 3555 y(this)k(can)g(be)f(done)i(in)e(FO)o(.\))70 b(In)37 b(FO)f(\002nd)h(the)h(multiplicati)n(v)o(e)i(in)l(v)o(erse)f (of)e FD(a)g FG(in)g(the)h(in-)448 3668 y(te)o(gers)f(mod)e FD(p)g FG(\(call)h(this)g FD(a)1386 3635 y Fm(\000)p Fs(1)1480 3668 y FG(,)i(and)e(\(using)j(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t (D)k FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)t(O)t(N)3065 3683 y FB(k)19 b Fs(log)13 b FB(n)3306 3668 y FG(and)450 3781 y(D)t Fo(I)t(V)t(I)t(S)t(I)t(O)t(N)817 3807 y FB(k)k Fs(log)962 3782 y Fr(2)1008 3807 y FB(n)1055 3781 y FG(\))35 b(compute)i FD(a)1516 3748 y Fm(\000)p FB(p)1607 3758 y Fl(j)1643 3781 y FG(.)64 b(One)35 b(can)h(sho)n(w)f (that)h(there)g(is)f(e)o(xactly)i(one)f(num-)448 3907 y(ber)d FD(x)41 b(<)g(p)32 b FG(such)h(that)g FD(x)1297 3874 y FB(d)1333 3884 y Fl(j)1411 3907 y FC(\021)41 b FD(a)1571 3874 y Fm(\000)p FB(p)1662 3884 y Fl(j)1789 3907 y Fq(\(mo)s(d)30 b FD(p)p Fq(\))p FG(,)k(and)e(that)h (furthermore,)k(this)32 b FD(x)g FG(is)g(the)448 4020 y(v)n(alue)39 b FD(a)728 4034 y FB(j)802 4020 y FG(that)f(we)f(seek.)72 b(Since)38 b FD(d)1659 4034 y FB(j)1733 4020 y FG(is)g(quite)h(small,)i (once)e(again)f(we)f(can)i(\002nd)e(the)h FD(x)448 4133 y FG(such)f(that)g FD(x)874 4100 y FB(d)910 4110 y Fl(j)995 4133 y FC(\021)48 b FD(a)1162 4100 y Fm(\000)p FB(p)1253 4110 y Fl(j)1380 4133 y Fq(\(mo)s(d)29 b FD(p)p Fq(\))36 b FG(using)j(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)k FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)g(O)t(N)3065 4148 y FB(k)19 b Fs(log)13 b FB(n)3306 4133 y FG(and)450 4246 y(D)t Fo(I)t(V)t(I)t(S)t(I)t(O)t(N)817 4273 y FB(k)k Fs(log)962 4247 y Fr(2)1008 4273 y FB(n)1055 4246 y FG(.)589 4359 y(Let)38 b FD(s)52 b Fq(=)g FC(b)p FD(iD)s(=)p Fq(\()p FD(p)32 b FC(\000)f Fq(1\))p FC(c)p FG(.)73 b(\(W)-7 b(e)38 b(can)g(think)h(of)g FD(s)e FG(as)h(being)h(a)f(gross)h (approxima-)448 4472 y(tion)c(to)e FD(i)h FG(\226)f(b)n(ut)i(one)f(ha)n (ving)h(some)f(nice)h(properties.\))62 b(Since)34 b FD(s)44 b(<)g(D)s FG(,)35 b FD(s)e FG(has)h(a)f(repre-)448 4585 y(sentation)j Fq(\()p FD(s)887 4599 y Fs(1)926 4585 y FD(;)15 b(:)g(:)g(:)i(;)e(s)1171 4600 y FB(k)1214 4585 y Fq(\))32 b FG(in)h(CRR)1567 4599 y FB(D)1630 4585 y FG(.)57 b(Since)33 b FD(i;)15 b(D)s(;)g(p)28 b FC(\000)f Fq(1)32 b FG(and)i FD(s)e FG(are)h(all)g(short)h(numbers,)448 4698 y FD(s)j FG(and)i(the)g(CRR)1029 4712 y FB(D)1129 4698 y FG(of)f FD(s)g FG(can)g(be)h(computed)h(in)e(FO)o(.)72 b(If)38 b(we)g(de\002ne)g FD(D)2901 4712 y FB(j)2976 4698 y FG(to)g(be)g FD(D)s(=d)3377 4712 y FB(j)3414 4698 y FG(,)448 4811 y(and)33 b FD(u)663 4825 y FB(j)731 4811 y FG(to)f(be)g FD(s)993 4825 y FB(j)1029 4811 y FD(D)1107 4772 y Fm(\000)p Fs(1)1104 4838 y FB(j)1226 4811 y Fq(mo)s(d)25 b FD(d)1473 4825 y FB(j)1509 4811 y FG(,)34 b(then)e(by)g(the)h (Chinese)g(Remainder)g(Theorem)f(we)g(ha)n(v)o(e)448 4924 y FD(s)25 b FC(\021)612 4855 y Fn(P)708 4951 y FB(j)760 4924 y FD(u)812 4938 y FB(j)848 4924 y FD(D)923 4938 y FB(j)985 4924 y Fq(mo)s(d)g FD(D)s FG(.)p eop %%Page: 12 12 12 11 bop 589 573 a FG(Using)30 b(I)t Fo(T)t(E)t(R)t(A)l(T)t(E)t(D)k FG(M)t Fo(U)t(L)m(T)t(I)t(P)t(L)t(I)t(C)t(A)l(T)5 b(I)g(O)t(N)1921 588 y FB(k)19 b Fs(log)12 b FB(n)2152 573 y FG(and)30 b(D)t Fo(I)t(V)t(I)t(S)t(I)t(O)t(N)2679 599 y FB(k)16 b Fs(log)2823 574 y Fr(2)2870 599 y FB(n)2917 573 y FG(,)26 b(we)g(can)h(com-)448 708 y(pute)i(the)e(v)n(alue)i FD(A)k Fq(=)1195 640 y Fn(Q)1281 667 y FB(k)1281 735 y(j)t Fs(=1)1423 708 y FD(a)1471 657 y FB(u)1512 667 y Fl(j)1471 736 y FB(j)1574 708 y Fq(mo)s(d)24 b FD(p)p FG(.)40 b(An)27 b(important)i(insight)h(of)d(Hesse)h(is)f(that)h FD(A)f FG(in)448 834 y(some)22 b(sense)g(is)f(\223close\224)h(to)f FD(a)1385 801 y FB(i)1414 834 y FG(.)27 b(More)21 b(precisely)-6 b(,)24 b(observ)o(e)e(that)g(we)e(can)i(compute)g(the)f(v)n(alue)448 947 y FD(u)41 b Fq(=)g FD(i)27 b FC(\000)808 878 y Fn(P)904 905 y FB(k)904 974 y(j)t Fs(=1)1046 947 y FD(u)1098 961 y FB(j)1134 947 y FC(b)p Fq(\()p FD(p)g FC(\000)f Fq(1\))p FD(=d)1551 961 y FB(j)1589 947 y FC(c)g Fq(mo)s(d)e FD(p)j FC(\000)f Fq(1)31 b FG(in)h(FO)o(.)54 b(Then)32 b FD(a)2661 914 y FB(i)2730 947 y FC(\021)40 b FD(a)2889 914 y FB(u)2934 947 y FD(A)91 b Fq(\(mo)s(d)30 b FD(p)p Fq(\))p FG(.)448 1074 y(Hesse)22 b(furthermore)h(is)f(able)f(to)h(sho)n(w)f(that)g FD(u)26 b(<)f Fq(log)2142 1038 y Fs(2)2197 1074 y FD(n)p FG(.)h(Thus)c(\(by)f(\002rst)g(computing)i FD(a)3264 1041 y Fs(log)13 b FB(n)3414 1074 y FG(,)448 1187 y(if)23 b(need)i(be\))e(we)g(can)h(compute)g FD(a)1520 1154 y FB(u)1565 1187 y FG(.)k(Since)c(we)e(already)j(ha)n(v)o(e)f FD(A)p FG(,)f(and)h(since)g FD(a)2975 1154 y FB(i)3029 1187 y Fq(=)h FD(a)3173 1154 y FB(u)3218 1187 y FD(A)p FG(,)d(we)448 1300 y(ha)n(v)o(e)j(succeeded)h(in)d(computing)j FD(a)1589 1267 y FB(i)1617 1300 y FG(,)d(as)g(desired.)p 3390 1300 48 48 v 448 1593 a FH(6)120 b(A)m(pplications)448 1800 y FG(The)36 b(ne)n(w)f(di)n(vision)i(algorithms)h(ha)n(v)o(e)f (already)g(found)g(application)i(in)d(a)f(rather)i(di)n(v)o(erse)448 1913 y(collection)27 b(of)c(settings.)31 b(Here)23 b(is)g(a)h(small)f (sample.)448 2162 y Fh(6.1)99 b(Graph)26 b(Isomor)o(phism)448 2336 y FG(Although)35 b(there)e(is)g(a)f(long)i(history)g(of)f (research)i(on)d(the)h(graph)h(isomorphism)h(problem)448 2449 y(\()p FD(GI)7 b FG(\),)28 b(there)g(has)g(been)g(v)o(ery)f (little)i(progress)g(on)f(the)f(problem)i(of)e(pro)o(ving)i Fx(lower)e(bounds)448 2562 y FG(on)d(the)g(comple)o(xity)h(of)f(graph)g (isomorphism)i(\226)d(until)i(recently)-6 b(.)589 2675 y(In)30 b([32)q(],)h(T)-7 b(or)5 b(\264)-35 b(an)29 b(sho)n(ws)h(that)h FD(GI)k FG(is)30 b(hard)g(for)g(NL)e(and)i(for)g(Mod)2735 2689 y FB(p)2776 2675 y FG(L)e(under)j FC(\024)3167 2642 y Fs(A)n(C)3269 2618 y Fr(0)3167 2697 y FB(m)3336 2675 y FG(re-)448 2788 y(ductions.)53 b(Using)32 b(the)f(L-uniform)h(TC)1743 2752 y Fs(0)1812 2788 y FG(circuits)h(of)e([13)q(])g(for)g(con)l(v)o (erting)j(from)c(CRR)f(to)448 2901 y(binary)-6 b(,)26 b(T)-7 b(or)5 b(\264)-35 b(an)23 b(w)o(as)h(able)g(to)g(b)n(uild)h(on)f (those)h(hardness)h(results)g(and)e(sho)n(w)g(that)g FD(GI)30 b FG(is)24 b(hard)448 3014 y(for)19 b(GapL)e(\(and)i(for)g(NC) 1226 2981 y Fs(1)1265 3014 y FG(\(GapL\)\))f(under)h(logspace)i(man)o (y-one)f(reductions.)30 b(Using)18 b(the)h(im-)448 3127 y(pro)o(v)o(ed)k(uniformity)h(pro)o(vided)f(by)f([18)q(],)g(it)f(no)n (w)g(follo)n(ws)h(that)h FD(GI)k FG(is)22 b(hard)g(for)g(NC)3131 3094 y Fs(1)3170 3127 y FG(\(GapL\))448 3239 y(under)j FC(\024)749 3206 y Fs(NC)853 3183 y Fr(1)749 3262 y FB(m)914 3239 y FG(reductions)h(\(a)e(v)o(ery)g(slight)h(impro)o(v)o(ement\).) 589 3352 y(T)-7 b(o)35 b(the)g(best)h(of)f(my)g(kno)n(wledge,)40 b(it)35 b(is)g(not)g(kno)n(wn)h(if)f(there)h(is)f(a)g FC(\024)2919 3319 y Fs(A)n(C)3021 3296 y Fr(0)2919 3375 y FB(m)3094 3352 y FG(reduction)448 3465 y(from)24 b(the)g(singularity) j(problem)d(\(gi)n(v)o(en)h(an)e(inte)o(ger)i(matrix,)f(is)g(the)g (determinant)i(zero?\))k(to)448 3578 y FD(GI)7 b FG(.)35 b(This)26 b(presents)i(one)f(of)f(the)g(v)o(ery)h(fe)n(w)e(cases)i (where)g(a)e(hardness)k(result)e(is)f(kno)n(wn)g(for)448 3691 y(logspace)g(man)o(y-one)f(reductions,)h(b)n(ut)e(is)g(not)g(kno)n (wn)f(for)h FC(\024)2425 3658 y Fs(A)n(C)2527 3635 y Fr(0)2425 3714 y FB(m)2588 3691 y FG(reductions.)448 3940 y Fh(6.2)99 b(T)n(ime-Space)27 b(T)-7 b(radeoffs)448 4115 y FG(In)39 b(a)f(recent)i(edition)g(of)f(the)g(Computational)i (Comple)o(xity)f(Column)e([25)r(],)j(Dieter)e(v)n(an)448 4227 y(Melk)o(ebeek)e(pro)o(vided)f(a)e(surv)o(e)o(y)h(of)g(recent)g (progress)i(on)e(time-space)h(tradeof)n(fs.)63 b(Most)448 4340 y(of)34 b(the)g(results)i(surv)o(e)o(yed)f(there)g(are)f(for)g(SA) -10 b(T)31 b(and)k(related)g(problems)g(on)f(deterministic)448 4453 y(and)c(nondeterministic)k(machines)e(using)e(sublinear)j(space.) 48 b(In)29 b(yet)h(another)i(e)o(xample)e(of)448 4566 y(the)k(observ)n(ation)i(that)e(\223upper)h(bounds)g(yield)f(lo)n(wer)f (bounds\224,)38 b(the)33 b(ne)n(w)g(di)n(vision)i(algo-)448 4679 y(rithm)29 b(of)g([13)q(])g(enabled)i(the)e(authors)i(of)d([7)q(]) h(to)f(transfer)j(these)f(lo)n(wer)f(bound)h(techniques)448 4792 y(from)22 b(the)g(domain)h(of)f(nondeterministic)k(computation)f (to)d(the)g(realm)g(of)g(unbounded-error)448 4905 y(probabilistic)28 b(computation.)p eop %%Page: 13 13 13 12 bop 448 573 a Fh(6.3)99 b(Eulerian)26 b(P)o(aths)448 747 y FG(T)-7 b(oda)24 b(w)o(as)f(one)h(of)f(the)h(\002rst)f(authors)i (to)f(sho)n(w)f(that)h(some)g(natural)h(problems)g(are)f(complete)448 860 y(for)g(GapL)f([31)q(].)29 b(Most)24 b(of)g(the)g(reductions)j (presented)f(in)e([31)q(])f(are)h(v)o(ery)h(restricti)n(v)o(e,)g(sho)n (w-)448 973 y(ing)e(that)g(problems)h(are)f(hard)g(for)g(#L)e(or)i (GapL)e(under)j FC(\024)2296 940 y Fs(A)n(C)2398 917 y Fr(0)2296 995 y FB(m)2458 973 y FG(reductions,)h(or)d(e)n(v)o(en)h (under)h(a)448 1086 y(more)h(restricti)n(v)o(e)i(notion)f(kno)n(wn)f (as)f(projections.)35 b(Ho)n(we)n(v)o(er)l(,)24 b(there)i(is)e(a)g (glaring)i(e)o(xample)448 1199 y(where)e(he)g(w)o(as)f(forced)i(to)e (consider)j(a)d(v)o(ery)h(po)n(werful)h(notion)g(of)e(reducibility)-6 b(.)589 1312 y(An)24 b Fx(Euler)g(tour)h FG(is)e(a)h(closed)h(path)g (in)f(a)f(graph)i(that)g(tra)n(v)o(erses)h(each)f(edge.)30 b(T)-7 b(oda)24 b(sho)n(ws)448 1425 y(in)32 b([31)q(])f(that)h (counting)i(the)e(number)g(of)g(Eulerian)g(tours)h(in)e(a)g(graph)i(is) e FC(\024)2928 1392 y Fs(A)n(C)3030 1368 y Fr(0)2928 1452 y FB(T)3069 1425 y FG(-reducible)448 1537 y(to)d(the)g(problem)h (of)f(computing)i(the)e(determinant)i(of)e(an)g(inte)o(ger)h(matrix.)42 b(Thus)28 b(it)f(lies)h(in)448 1650 y FD(AC)588 1617 y Fs(0)627 1650 y FG(\(GapL\).)k(He)f(w)o(as)g(unable)i(to)f(sho)n(w)f (that)i(counting)h(Euler)d(tours)i(is)f(hard)g(for)g(GapL)448 1763 y(under)h FC(\024)757 1730 y Fs(A)n(C)859 1707 y Fr(0)757 1790 y FB(T)928 1763 y FG(reductions,)j(b)n(ut)c(he)g(could)g (sho)n(w)g(that)g(GapL)f(reduces)i(to)e(counting)j(Euler)448 1876 y(tours)c(under)f(P-uniform)g(TC)1409 1841 y Fs(0)1476 1876 y FG(reductions,)j(via)d(a)e(reduction)k(that)e(in)l(v)n(olv)o(es) h(di)n(vision.)45 b(By)448 1989 y(making)23 b(use)g(of)f(the)g (construction)k(in)c([18)q(],)g(we)f(no)n(w)g(see)i(that)f(the)h (P-uniformity)h(condition)448 2102 y(can)g(be)g(replaced)h(by)f (DLOGTIME)n(-uniformity)-6 b(.)448 2351 y Fh(6.4)99 b(Arithmetic)26 b(Cir)n(cuits)448 2526 y FG(The)h(comple)o(xity)j(classes)f(#A)l(C)1498 2493 y Fs(0)1565 2526 y FG(and)f(GapA)l(C)1997 2493 y Fs(0)2063 2526 y FG(were)f(introduced)k(in)c([4)q(])g(and)h(ha)n(v)o(e) g(been)448 2638 y(studied)j(in)f([6])f(and)h([5].)46 b(\(See)29 b(also)h(the)f(surv)o(e)o(y)h(article)h(on)e(arithmetic)i (circuits)g([3)q(],)f(and)448 2751 y(the)h(material)g(on)f(arithmetic)i (circuits)f(in)f([33)r(].\))47 b(The)30 b(main)g(moti)n(v)n(ation)i (for)e(introducing)448 2864 y(and)e(studying)h(these)f(classes)g(comes) f(from)g(the)g(f)o(act)h(that)f(the)o(y)g(gi)n(v)o(e)g(rise)h(to)e(se)n (v)o(eral)i(char)n(-)448 2977 y(acterizations)f(of)d(TC)1145 2941 y Fs(0)1185 2977 y FG(.)589 3090 y(Ho)n(we)n(v)o(er)l(,)38 b(there)d(w)o(as)g(a)f(problem)i(with)f(these)g(characterizations)40 b(\226)35 b(some)g(of)f(them)448 3203 y(were)19 b(not)g(kno)n(wn)g(to)g (hold)g(in)g(the)g(uniform)h(setting.)29 b(F)o(or)17 b(instance,)22 b(four)d(dif)n(ferent)i(language)448 3316 y(classes)31 b(arising)f(from)f(arithmetic)h(A)l(C)1728 3283 y Fs(0)1795 3316 y FG(circuits)h(were)e(sho)n(wn)g(to)f(coincide)j (with)e(TC)3300 3283 y Fs(0)3366 3316 y FG(in)448 3429 y(the)35 b(non-uniform)h(and)f(P-uniform)f(settings,)39 b(b)n(ut)34 b(were)g(not)g(kno)n(wn)g(to)g(coincide)i(in)e(the)448 3542 y(DLOGTIME-uniform)22 b(setting.)30 b(Some)22 b(more)h(of)g(these) h(classes)g(were)f(sho)n(wn)g(to)g(coincide)448 3655 y(in)30 b([6)q(],)g(b)n(ut)h(there)g(still)f(remained)h(a)f(question)i (as)e(to)f(whether)i(these)g(classes)g(were)f(really)448 3768 y(the)24 b(same)g(as)f(DLOGTIME)n(-uniform)i FD(T)13 b(C)1849 3735 y Fs(0)1887 3768 y FG(.)589 3880 y(It)25 b(is)g(an)g(immediate)h(consequence)i(of)d([18)r(])f(that)h(all)h(of)e (the)i(classes)g(introduced)i(in)d([4)q(])448 3993 y(coincide)h(with)d (TC)1080 3958 y Fs(0)1142 3993 y FG(e)n(v)o(en)g(in)h(the)g(uniform)g (setting.)589 4106 y(Another)i(important)g(class)f(of)f(arithmetic)i (circuits)g(arises)g(by)e(arithmetizing)k(NC)3250 4071 y Fs(1)3313 4106 y FG(cir)n(-)448 4219 y(cuits.)53 b(This)31 b(yields)h(the)g(classes)h(#NC)1730 4186 y Fs(1)1799 4219 y FG(and)f(GapNC)2239 4186 y Fs(1)2278 4219 y FG(,)g(which)f(ha)n (v)o(e)h(recei)n(v)o(ed)h(attention)448 4332 y(in)f([11)q(,)e(3,)h(33)q (].)51 b(I)31 b(conjecture)j(in)d([3)q(])g(that)h(the)f(functions)j(in) d(#NC)2676 4299 y Fs(1)2746 4332 y FG(and)h(GapNC)3186 4299 y Fs(1)3255 4332 y FG(actu-)448 4445 y(ally)27 b Fx(coincide)i FG(with)d(the)g(functions)j(in)d(\(Boolean\))i(NC)2243 4412 y Fs(1)2282 4445 y FG(.)36 b(\(This)26 b(conjecture)j(is)d(based)h (on)g(a)448 4558 y(v)o(ery)h(ef)n(\002cient)g(simulation)h(of)e (arithmetic)h(circuits)h(by)e(Boolean)i(circuits,)g(\002rst)e (presented)448 4671 y(by)33 b(Jung)h([22)q(].\))57 b(Ho)n(we)n(v)o(er)l (,)35 b(until)e(the)h(w)o(ork)f(of)f(Chiu,)j(Da)n(vida,)h(and)e(Lito)n (w)-6 b(,)34 b(it)e(w)o(as)h(not)448 4784 y(e)n(v)o(en)d(kno)n(wn)f (whether)i(the)e(functions)j(in)d(these)h(classes)h(can)f(be)f (computed)i(in)e(logspace.)448 4897 y(No)n(w)-6 b(,)27 b(we)f(kno)n(w)h(that)g(the)o(y)g(can)h(be;)h(that)e(is,)g(e)n(v)o(ery) h(function)h(in)e(GapNC)2861 4864 y Fs(1)2926 4897 y FG(is)g(computable)p eop %%Page: 14 14 14 13 bop 448 573 a FG(in)24 b(logspace.)448 863 y FH(7)120 b(Small)30 b(Space)h(Bounds)448 1070 y FG(It)22 b(is)g(observ)o(ed)i (in)f([6])f(that)h(the)f(di)n(vision)i(algorithm)g(of)e([13)r(])f(pro)o (vides)j(a)e(ne)n(w)g(translational)448 1183 y(lemma)h(for)h(small)g (space)h(bounds.)589 1296 y(Usually)20 b(a)d(lo)n(wer)h(bound)i(on)e (the)h(comple)o(xity)h(of)e(the)g(binary)i(encoding)h(of)d(a)f(set)i (follo)n(ws)448 1409 y(from)30 b(a)g(bound)h(on)f(the)g(comple)o(xity)i (of)e(the)g(unary)i(encoding.)50 b(\(The)30 b(unary)h(encoding)h(of)448 1522 y FD(A;)15 b FG(un)r Fq(\()p FD(A)p Fq(\))p FG(,)23 b(is)f(de\002ned)i(to)e(be)h FC(f)p Fq(0)1494 1489 y FB(x)1564 1522 y Fq(:)j FD(x)f FC(2)g FD(A)p FC(g)p FG(.\))j(This)23 b(follo)n(ws)g(from)g(a)f(standard)j Fx(tr)o(anslation)448 1635 y(lemma)p FG(,)e(such)h(as:)448 1834 y Ft(Lemma)f(7.1)46 b(\(T)-7 b(raditional)20 b(T)-7 b(ranslation)20 b(Lemma\))f Fx(If)g FD(s)p Fq(\(log)d FD(n)p Fq(\))25 b(=)g(\012\(log)17 b(log)f FD(n)p Fq(\))j Fx(is)f(fully)448 1947 y(space-constructib)q(le) o(,)29 b(then)24 b(the)g(\002r)o(st)g(statement)h(below)f(implies)h (the)e(second:)585 2123 y FC(\017)46 b FD(A)25 b FC(2)g FG(dspace)r Fq(\()p FD(s)p Fq(\()p FD(n)p Fq(\)\))p Fx(.)585 2306 y FC(\017)46 b FG(un)q Fq(\()p FD(A)p Fq(\))26 b FC(2)f FG(dspace)r Fq(\(log)17 b FD(n)j Fq(+)f FD(s)p Fq(\(log)e FD(n)p Fq(\)\))p Fx(.)448 2483 y(The)23 b(con)l(ver)o(se)k (also)d(holds,)g(if)g FD(s)p Fq(\(log)16 b FD(n)p Fq(\))25 b(=)g(\012\(log)17 b FD(n)p Fq(\))p Fx(.)589 2682 y FG(Note)25 b(in)g(particular)j(that)e(this)f(translation)j(lemma)d(does)h(not)f (allo)n(w)g(one)g(to)g(deri)n(v)o(e)h(an)o(y)448 2794 y(lo)n(wer)35 b(bound)h(on)f(the)g(space)h(comple)o(xity)g(of)f FD(A)p FG(,)i(assuming)f(only)f(a)g(logarithmic)h(lo)n(wer)448 2907 y(bound)25 b(on)f(the)g(space)g(comple)o(xity)i(of)d(un)q Fq(\()p FD(A)p Fq(\))p FG(.)589 3020 y(There)h(is)f(another)i (reasonable)h(w)o(ay)d(to)g(de\002ne)h(small)f(space)h(comple)o(xity)i (classes.)k(De-)448 3133 y(\002ne)22 b(DSP)-8 b(A)l(CE)n Fq(\()p FD(s)p Fq(\()p FD(n)p Fq(\)\))22 b FG(to)h(be)g(the)f(class)i (of)f(languages)i(accepted)g(by)d(T)l(uring)i(machines)g(that)448 3246 y(be)o(gin)37 b(their)f(computation)j(with)c(a)h(w)o(orktape)h (consisting)i(of)c FD(s)p Fq(\()p FD(n)p Fq(\))g FG(cells)i (\(delimited)g(by)448 3359 y(endmark)o(ers\),)i(as)34 b(opposed)i(to)e(the)g(more)g(common)h(comple)o(xity)h(classes)f (dspace)s Fq(\()p FD(s)p Fq(\()p FD(n)p Fq(\)\))448 3472 y FG(where)26 b(the)f(w)o(orktape)i(is)e(initially)j(blank,)e(and)g (the)f(machine)i(must)e(use)h(its)f(o)n(wn)g(computa-)448 3585 y(tional)f(po)n(wer)e(to)g(mak)o(e)g(sure)h(that)g(it)f(respects)i (the)e(space)h(bound)h(of)e FD(s)p Fq(\()p FD(n)p Fq(\))p FG(.)27 b(V)-5 b(ie)n(wed)21 b(another)448 3698 y(w)o(ay)-6 b(,)21 b(DSP)-8 b(A)l(CE)n Fq(\()p FD(s)p Fq(\()p FD(n)p Fq(\)\))20 b FG(is)h(simply)g(dspace)s Fq(\()p FD(s)p Fq(\()p FD(n)p Fq(\)\))f FG(augmented)j(by)e(a)f(small)h(amount)h(of)f (\223ad-)448 3811 y(vice\224,)j(allo)n(wing)f(the)g(machine)g(to)g (compute)g(the)g(space)g(bound.)30 b(\(This)23 b(model)f(w)o(as)g (de\002ned)448 3924 y(under)i(the)f(name)g(\223DEMONSP)-8 b(A)l(CE\224)19 b(by)j(Hartmanis)i(and)f(Ranjan)g([17)r(].)k(See)c (also)g(Szepi-)448 4036 y(eto)n(wski')-5 b(s)25 b(book)g([30)q(])e(on)h (sublogarithmic)i(space.\))589 4149 y(DSP)-8 b(A)l(CE)n Fq(\()p FD(s)p Fq(\()p FD(n)p Fq(\)\))23 b FG(seems)g(at)g(\002rst)g (to)g(share)h(man)o(y)f(of)g(the)h(properties)h(of)e(dspace)s Fq(\()p FD(s)p Fq(\()p FD(n)p Fq(\)\))p FG(.)448 4262 y(In)e(particular)l(,)j(it)c(is)h(still)g(relati)n(v)o(ely)i (straightforw)o(ard)i(to)20 b(sho)n(w)h(that)g(there)h(are)f(natural)h (prob-)448 4375 y(lems,)h(such)i(as)e(the)h(set)g(of)f(palindromes,)j (that)e(are)g(not)g(in)f(DSP)-8 b(A)l(CE)n Fq(\()p FD(o)p Fq(\(log)17 b FD(n)p Fq(\)\))p FG(.)589 4488 y(The)24 b(ef)n(\002cient)g(di)n(vision)h(algorithm)h(of)d([13)q(])g(pro)o (vides)j(a)d(ne)n(w)g(translation)j(lemma.)448 4687 y Ft(Lemma)d(7.2)46 b(New)33 b(translation)j(lemma)e Fx(Let)g FD(s)p Fq(\()p FD(n)p Fq(\))45 b(=)h(\012\(log)16 b FD(n)p Fq(\))34 b Fx(be)g(fully)h(space-con-)448 4800 y(structible)o(.)c(Then) 24 b(the)g(following)h(ar)m(e)e(equivalent:)585 4976 y FC(\017)46 b FD(A)25 b FC(2)g FG(dspace)r Fq(\()p FD(s)p Fq(\()p FD(n)p Fq(\)\))p eop %%Page: 15 15 15 14 bop 585 573 a FC(\017)46 b FG(un)q Fq(\()p FD(A)p Fq(\))26 b FC(2)f FG(DSP)-8 b(A)l(CE)m Fq(\(log)17 b(log)g FD(n)i Fq(+)h FD(s)p Fq(\(log)d FD(n)p Fq(\)\))p Fx(.)448 785 y Ft(Cor)n(ollary)26 b(7.3)46 b Fx(In)29 b(or)m(der)i(to)e(show)g (NP)f(is)h(not)h(contained)i(in)d FG(L)o Fx(,)h(it)f(suf)n(\002ces)j (to)d(pr)m(esent)i(a)448 897 y(set)24 b FD(A)h FC(2)g FD(N)10 b(P)36 b Fx(suc)o(h)24 b(that)g FG(un)q Fq(\()p FD(A)p Fq(\))i FC(62)f FG(DSP)-8 b(A)l(CE)n Fq(\(log)17 b(log)f FD(n)p Fq(\))p Fx(.)589 1109 y FG(At)28 b(\002rst)g(glance,)j (this)e(corollary)i(may)e(seem)f(surprising,)33 b(since)c(there)h(are)e (sets)h(in)g(NP)448 1222 y(\(such)j(as)f(the)g(set)g(of)g(prime)g (numbers\))i(whose)e(unary)h(encoding)h(is)e(kno)n(wn)g Fx(not)h FG(to)e(be)h(in)448 1335 y(dspace)s Fq(\(log)17 b(log)f FD(n)p Fq(\))24 b FG([16)q(].)32 b(It)25 b(might)g(seem)g(as)f (if)h(the)g(computational)j(po)n(wer)d(of)g(the)g(classes)448 1448 y(dspace)s Fq(\(log)17 b(log)f FD(n)p Fq(\))36 b FG(and)h(DSP)-8 b(A)l(CE)m Fq(\(log)17 b(log)g FD(n)p Fq(\))35 b FG(might)i(not)g(be)g(so)f(v)o(ery)h(dif)n(ferent.)70 b(One)448 1561 y(consequence)23 b(of)c(our)h(ne)n(w)e(insight)j(into)f (di)n(vision)h(is)e(that)h(it)f(is)g(no)n(w)f(clear)i(that)g(the)g(DSP) -8 b(A)l(CE)448 1674 y(classes)25 b(can)f(carry)h(out)f(simulations)i (that)e(seem)f(impossible)j(in)e(the)f(dspace)i(model.)448 1954 y FH(Refer)n(ences)490 2139 y Fg([1])44 b(E.)20 b(Allender)-5 b(.)27 b(The)19 b(permanent)e(requires)i(lar)o(ge)f (uniform)g(threshold)g(circuits.)27 b Ff(Chica)o(go)19 b(J)n(our)n(-)632 2239 y(nal)h(of)g(Theor)m(etical)g(Computer)g (Science)p Fg(,)f(article)h(7,)g(1999.)490 2388 y([2])44 b(E.)29 b(Allender)-5 b(.)57 b(Ne)n(ws)30 b(from)e(the)h(Isomorphism)e (Front.)57 b(The)29 b(Computational)e(Comple)o(xity)632 2488 y(Column,)19 b(EA)-9 b(TCS)21 b(Bulletin)f(66,)g(October)m(,)e (1998)h(pp.)g(73\22682.)490 2637 y([3])44 b(E.)26 b(Allender)-5 b(.)48 b(Making)25 b(computation)e(count:)36 b(Arithmetic)26 b(circuits)g(in)g(the)g(nineties.)g(In)g(the)632 2737 y(Comple)o(xity)c(Theory)g(Column,)h(edited)g(by)g(Lane)g (Hemaspaandra,)f(SIGA)m(CT)i(NEWS)g(28,)g(4)632 2836 y(\(December)m(,)18 b(1997\))h(pp.)g(2-15.)490 2985 y([4])44 b(M.)19 b(Agra)o(w)o(al,)g(E.)g(Allender)m(,)f(and)g(S.)i(Datta.)27 b(On)20 b(TC)2172 2949 y Fe(0)2209 2985 y Fd(;)14 b Fg(A)m(C)2358 2949 y Fe(0)2395 2985 y Fd(;)20 b Fg(and)e(Arithmetic)h(Circuits.)27 b(Jour)n(-)632 3085 y(nal)20 b(of)g(Computer)f(and)h(System)g(Sciences) g Fc(60)p Fg(:395\226421,)c(2000.)490 3234 y([5])44 b(E.)27 b(Allender)m(,)g(Andris)g(Ambainis,)h(Da)n(vid)f(A.)g(Mix)g (Barrington,)g(Samir)g(Datta,)i(and)d(Huong)632 3334 y(L)5 b(\210)-33 b(eThanh.)29 b(Bounded)19 b(Depth)h(Arithmetic)g (Circuits:)27 b(Counting)19 b(and)h(Closure.)31 b(In)20 b(Proc.)g(26th)632 3433 y(International)14 b(Colloquium)g(on)h (Automata,)h(Languages,)f(and)g(Programming,)e(1999,)j(Lecture)632 3533 y(Notes)21 b(in)f(Computer)f(Science)h(1644,)e(pp.)i(149\226158.) 490 3682 y([6])44 b(E.)24 b(Allender)m(,)e(D.)i(Mix)f(Barrington,)g (and)f(W)-8 b(.)25 b(Hesse.)40 b(Uniform)22 b(circuits)i(for)e(di)n (vision:)31 b(Con-)632 3782 y(sequences)e(and)f(problems.)57 b(T)-7 b(o)30 b(appear)e(in)h Ff(Pr)l(oc.)h(IEEE)e(Confer)m(ence)h(on)g (Computational)632 3882 y(Comple)n(xity)p Fg(,)20 b(2001.)490 4031 y([7])44 b(E.)30 b(Allender)m(,)h(Michal)f(K)m(ouck)o(y)-5 b(,)30 b(Detlef)g(Ronneb)n(ur)o(ger)m(,)e(Samb)n(uddha)g(Ro)o(y)-5 b(,)32 b(and)d(V)-11 b(.)31 b(V)-5 b(inay)g(.)632 4130 y(T)m(ime-Space)26 b(T)m(radeof)n(fs)g(in)h(the)g(Counting)f(Hierarchy) -5 b(.)50 b(T)-7 b(o)27 b(appear)f(in)i(Proc.)e(16th)h(Annual)632 4230 y(IEEE)20 b(Conference)e(on)i(Computational)e(Comple)o(xity)-5 b(,)18 b(2001.)490 4379 y([8])44 b(D.)25 b(A.)f(M.)g(Barrington,)f(N.)i (Immerman,)e(and)g(H.)i(Straubing.)40 b(On)24 b(uniformity)e(within)i (NC)3379 4343 y Fe(1)3416 4379 y Fg(.)632 4479 y Ff(J)n(ournal)19 b(of)h(Computer)g(and)g(System)g(Sciences)p Fg(,)f Fc(41)p Fg(:274\226306,)d(1990.)490 4628 y([9])44 b(P)-9 b(.)24 b(Beame,)h(S.)g(Cook)e(and)h(J.)g(Hoo)o(v)o(er)-5 b(.)40 b(Log)24 b(depth)f(circuits)h(for)f(di)n(vision)g(and)h(related)f (prob-)632 4728 y(lems.)30 b Ff(SIAM)19 b(J)n(.)i(Comput.)p Fg(,)e Fc(15)p Fg(:994\2261003,)d(1986.)448 4877 y([10])44 b(S.)23 b(Buss,)g(The)f(Boolean)f(formula)g(v)n(alue)g(problem)g(is)i (in)f(ALOGTIME,)f(in)h Ff(Pr)l(oc.)g(19th)f(A)n(CM)632 4976 y(Symposium)e(on)h(Theory)g(of)g(Computing)f(\(ST)o(OC\))p Fg(,)g(pp.)h(123\226131)d(\(1987\).)p eop %%Page: 16 16 16 15 bop 448 573 a Fg([11])44 b(H.)33 b(Caussinus,)i(P)-9 b(.)33 b(McK)n(enzie,)h(D.)e(Th)5 b(\264)-33 b(erien,)34 b(and)e(H.)g(V)-11 b(ollmer)-5 b(.)68 b(Nondeterministic)31 b(NC)3400 543 y Fe(1)632 672 y Fg(computation.)c Ff(J)n(ournal)19 b(of)h(Computer)g(and)f(System)i(Sciences)p Fg(,)e(57\(2\):200\226212,) c(1998.)448 820 y([12])44 b(A.)20 b(Chiu.)29 b(Comple)o(xity)18 b(of)i(parallel)g(arithmetic)f(using)g(the)h(Chinese)g(Remainder)f (representa-)632 920 y(tion.)29 b(Master')-5 b(s)21 b(thesis,)f(U.)h(W) m(isconsin-Mil)o(w)o(auk)o(ee,)d(1995.)h(G.)h(Da)n(vida,)g(supervisor) -5 b(.)448 1067 y([13])44 b(A.)20 b(Chiu,)g(G.)h(Da)n(vida,)e(and)h(B.) g(Lito)n(w)-5 b(.)28 b Fd(N)9 b(C)1936 1037 y Fe(1)1994 1067 y Fg(Di)n(vision.)20 b(Preliminary)e(v)o(ersion,)h(2000.)27 b(A)-6 b(v)n(ail-)632 1167 y(able)20 b(from)f(the)i(website)f Fb(http://www.cs.jcu.edu.au/)p Fa(\030)p Fb(bruce)15 b Fg(as)632 1267 y Fb(/papers/crr00)p 1287 1267 25 4 v 28 w(3.ps.gz)p Fg(.)448 1414 y([14])44 b(G.)19 b(I.)g(Da)n(vida)g (and)f(B.)i(Lito)n(w)-5 b(.)25 b(F)o(ast)20 b(parallel)f(arithmetic)f (via)h(modular)e(representation.)24 b Ff(SIAM)632 1514 y(J)n(.)c(Comput.)p Fg(,)g Fc(20)p Fg(:756\226765,)c(1991.)448 1662 y([15])44 b(P)o(aul)31 b(F)-7 b(.)32 b(Dietz,)i(Ioan)d(I.)g (Macarie,)i(and)d(Joel)i(I.)f(Seiferas.)64 b(Bits)33 b(and)d(relati)n(v)o(e)h(order)f(from)632 1761 y(residues,)20 b(space)g(ef)n(\002ciently)-5 b(.)28 b Ff(Information)18 b(Pr)l(ocessing)i(Letter)o(s)p Fg(,)h Fc(50)p Fg(:123\226127,)c(1994.) 448 1909 y([16])44 b(J.)31 b(Hartmanis)f(and)g(L.)h(Berman.)61 b(On)31 b(tape)f(bounds)f(for)h(single)g(letter)h(alphabet)e(language) 632 2009 y(processing.)f Ff(Theor)m(etical)19 b(Computer)h(Science)f Fc(3)p Fg(:213\226224,)e(1976.)448 2156 y([17])44 b(J.)18 b(Hartmanis)f(and)h(D.)f(Ranjan.)24 b(Space)17 b(bounded)e (computations:)22 b(Re)n(vie)n(w)c(and)f(ne)n(w)g(specula-)632 2256 y(tion.)31 b(In)20 b Ff(MFCS)i('89:)j(Mathematical)19 b(F)-9 b(oundations)19 b(of)i(Computer)f(Science)p Fg(,)31 b(Lecture)19 b(Notes)632 2356 y(in)h(Computer)f(Science)h(379,)f (Springer)n(-V)-9 b(erlag,)17 b(1989,)i(pp.)g(49\22666.)448 2503 y([18])44 b(W)-8 b(.)19 b(Hesse.)26 b(Di)n(vision)18 b(is)h(in)f(Uniform)f(TC)1858 2467 y Fe(0)1895 2503 y Fg(.)26 b(In)18 b Ff(ICALP)g(2001:)k(T)-6 b(wenty-Eighth)17 b(International)632 2603 y(Colloquium)i(on)h(A)n(utomata,)e(Langua)o(g) o(es)h(and)g(Pr)l(o)o(gr)o(amming)g Fg(\(July)h(2001\),)e(to)i(appear) -5 b(.)448 2751 y([19])44 b(N.)24 b(Immerman.)38 b(Progress)23 b(in)h(descripti)n(v)o(e)e(comple)o(xity)-5 b(.)37 b(The)24 b(Computational)d(Comple)o(xity)632 2850 y(Column,)e(EA)-9 b(TCS)21 b(Bulletin)f(67,)g(February)-5 b(,)17 b(1999.)448 2998 y([20])44 b(N.)21 b(Immerman.)26 b Ff(Descriptive)21 b(Comple)n(xity)p Fg(.)29 b(Springer)n(-V)-9 b(erlag,)17 b(1999.)448 3146 y([21])44 b(Neil)24 b(Immerman)e(and)h(Susan)g (Landau.)39 b(The)23 b(Comple)o(xity)f(of)h(Iterated)g(Multiplication.) 38 b(In-)632 3245 y(formation)18 b(and)i(Computation)e Fc(116)i Fg(\(1995\),)d(103-116.)448 3393 y([22])44 b(H.)19 b(Jung.)26 b(Depth)18 b(ef)n(\002cient)g(transformations)f(of)h (arithmetic)g(into)h(Boolean)f(circuits.)26 b(In)19 b Ff(Pr)l(oc.)632 3492 y(FCT)i('85,)e(Lectur)m(e)i(Notes)f(in)h(Computer) f(Science)f Fg(199,)g(pp.)h(167-173.)448 3640 y([23])44 b(I.)20 b(Macarie.)29 b(Space-ef)n(\002cient)19 b(deterministic)g (simulation)h(of)g(probabilistic)f(automata.)28 b Ff(SIAM)632 3740 y(J)n(.)20 b(Comp.)g Fc(27)p Fg(:448-465,)d(1998.)448 3887 y([24])44 b(Ste)n(v)o(en)23 b(Lindell.)38 b(A)24 b(purely)d(logical)i(characterization)e(of)i(circuit)g(uniformity)-5 b(.)36 b(In)23 b(Proc.)g(7th)632 3987 y(Structure)c(in)i(Comple)o(xity) d(Theory)h(Conference)f(\(1992\))g(pp.)i(185\226192.)448 4135 y([25])44 b(D.)25 b(v)n(an)f(Melk)o(ebeek.)42 b(T)m(ime-space)24 b(lo)n(wer)g(bounds)f(for)h(satis\002ability)-5 b(.)44 b(The)25 b(Computational)632 4234 y(Comple)o(xity)19 b(Column,)g(EA)-9 b(TCS)20 b(Bulletin)h(73,)e(February)-5 b(,)18 b(2001,)h(pp.)g(57-77.)448 4382 y([26])44 b(I.)20 b(P)o(arberry)f(and)g(G.)i(Schnitger)-5 b(.)29 b(P)o(arallel)20 b(computation)e(with)i(threshold)f(functions.)28 b Ff(J)n(ournal)632 4482 y(of)20 b(Computer)g(and)g(System)g(Sciences)p Fg(,)f (36:278\226302,)d(1988.)448 4629 y([27])44 b(J.)19 b(Reif,)25 b(On)18 b(threshold)f(circuits)h(and)f(polynomial)f(computation.)22 b(Proc.)17 b(2nd)g(IEEE)h(Structure)632 4729 y(in)i(Comple)o(xity)f (Theory)g(Conference,)f(1987,)g(pp.)i(118\226123.)448 4877 y([28])44 b(J.)31 b(Reif)f(and)f(S.)i(T)-7 b(ate.)61 b(On)30 b(threshold)e(circuits)i(and)f(polynomial)f(computation.)58 b Ff(SIAM)30 b(J)n(.)632 4976 y(Comput.)p Fg(,)19 b Fc(21)p Fg(:896\226908,)d(1992.)p eop %%Page: 17 17 17 16 bop 448 573 a Fg([29])44 b(W)-8 b(.)33 b(L.)g(Ruzzo.)67 b(On)32 b(uniform)f(circuit)h(comple)o(xity)-5 b(.)65 b Ff(J)n(ournal)31 b(of)h(Computer)g(and)g(System)632 672 y(Sciences)p Fg(,)19 b(21:365\226383,)e(1981.)448 822 y([30])44 b(A.)30 b(Szepieto)n(wski.)60 b Ff(T)-5 b(uring)29 b(Mac)o(hines)g(with)i(Sublo)o(garithmic)d(Space)p Fg(.)58 b(Lecture)29 b(Notes)i(in)632 922 y(Computer)19 b(Science)h(843,)f(Springer)n(-V)-9 b(erlag,)17 b(1994.)448 1071 y([31])44 b(S.)26 b(T)-7 b(oda.)44 b(Counting)24 b(problems)g(computationally)e(equi)n(v)n(alent)h(to)j(computing)d(the) i(determi-)632 1171 y(nant.)45 b(T)-6 b(echnical)25 b(Report)g(CSIM)h (91-07,)f(Department)e(of)j(Computer)e(Science,)i(Uni)n(v)o(ersity)632 1270 y(of)20 b(Electro-Communications,)c(T)-7 b(ok)o(yo,)19 b(Japan,)g(1991.)448 1420 y([32])44 b(J.)25 b(T)-7 b(or)5 b(\264)-33 b(an.)40 b(On)24 b(the)g(hardness)f(of)h(graph)e (isomorphism.)40 b(In)24 b Ff(Pr)l(oc.)g(41st)g(Annual)e(Symposium)632 1519 y(on)e(F)-9 b(oundations)18 b(of)i(Computer)g(Science)f(\(FOCS\))p Fg(,)h(pp.)f(180\226186)e(\(2000\).)448 1669 y([33])44 b(H.)21 b(V)-11 b(ollmer)-5 b(.)29 b Ff(Intr)l(oduction)18 b(to)i(Cir)m(cuit)h(Comple)n(xity)p Fg(.)29 b(Springer)n(-V)-9 b(erlag,)17 b(1999.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF