TR00-065 Authors: Eric Allender, David Mix Barrington

Publication: 8th September 2000 08:31

Downloads: 1310

Keywords:

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. Integer division provides one of the few natural

examples of problems for which all currently-known constructions of

efficient circuits rely on some sort of extra information or

non-uniformity; the major stumbling block has seemed to be the

difficulty of converting from CRR to binary. We give new bounds on

the nonuniformity required for division; it is necessary and

sufficient to be able to compute discrete logarithms modulo an

O(log n) bit number. In particular, we show that the necessary

uniformity predicates lie in a class that (provably) does not

contain L.

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.

Comment #1 Authors: Eric Allender, David Mix Barrington

Accepted on: 11th May 2001 12:27

Downloads: 923

Keywords:

The MS thesis of Andrew Chiu:

("Complexity of Parallel Arithmetic Using the

Chinese Remainder Representation"

University of Wisconsin-Milwaukee, August, 1995)

contains an algorithm for integer division, that

can be implemented in Atime(log n) (i.e., in the

most uniform version of NC^1). Our ECCC Submission

will be revised soon, to reflect this.

This paper became obsolete shortly after it appeared in ECCC.

A new paper (with William Hesse as co-author) is now available

as ECCC report TR01-033.