TR01-033 Authors: Eric Allender, David Mix Barrington, William Hesse

Publication: 30th April 2001 16:21

Downloads: 3277

Keywords:

Integer division has been known to lie in P-uniform TC^0 since

the mid-1980's, and recently this was improved to DLOG-uniform

TC^0. At the time that the results in this paper were proved and

submitted for conference presentation, it was unknown whether division

lay in DLOGTIME-uniform TC^0 (also known as FOM).

We obtain tight bounds on the

uniformity required for division, by showing that division is complete

for the complexity class FOM+POW obtained by augmenting FOM with

a predicate for powering modulo small primes. We also show that, under

a well-known number-theoretic conjecture (that there are many ``smooth''

primes), POW (and hence division) lies in FOM. Building on this work,

Hesse has shown recently that division is in FOM.

The essential idea in the fast parallel computation of division and

related problems is that of Chinese remainder representation (CRR) --

storing a number in the form of its residues modulo many small primes.

The fact that CRR operations can be carried out in log space has

interesting implications for small space classes. We define two

versions of s(n) space for s(n)=o(log n): dspace(s(n)) as the

traditional version where the worktape begins blank, and DSPACE(s(n))

where the space bound is established by endmarkers before the

computation starts. We present a new translational lemma, and derive

as a consequence that (for example), if one can improve the result of

Hartmanis & Berman that {0^n : n is prime} is not in dspace(loglog n)

to show that {0^n : n is prime} is not in DSPACE(loglog n), it would

follow that L is not equal to NP.