Uniform constant-depth threshold circuits for division and iterated multiplication
✍ Scribed by William Hesse; Eric Allender; David A. Mix Barrington
- Book ID
- 104147640
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 258 KB
- Volume
- 65
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
known since the mid-1980s (SIAM J. Comput. 15 (1986) 994; SIAM J. Comput. 21 (1992) 896) that integer division can be performed by poly-time uniform constantdepth circuits of Majority gates; equivalently, the division problem lies in P-uniform TC 0 : Recently, this was improved to L-uniform TC 0 (RAIRO Theoret. Inform. Appl. 35 (2001) 259), but it remained unknown whether division can be performed by DLOGTIMEuniform TC 0 circuits. The DLOGTIME uniformity condition is regarded by many as being the most natural notion of uniformity to apply to small circuit complexity classes such as TC 0 ; DLOGTIME-uniform TC 0 is also known as FOM, because it corresponds to first-order logic with Majority quantifiers, in the setting of finite model theory. Integer division has been the outstanding example of a natural problem known to be in a P-uniform circuit complexity class, but not known to be in its DLOGTIMEuniform version.
We show that indeed division is in DLOGTIME-uniform TC 0 : First we show that division lies in the complexity class FOM þ POW obtained by augmenting FOM with a predicate for powering modulo small primes. Then we show that the predicate POW itself lies in FOM. (In fact, it lies in FO, or DLOGTIME-uniform AC 0 :)
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 characterizing the unary languages in the DSPACE classes. It is known (Theoret. Comput. Sci. 3 (1976) 213) that f0 n : n is primeg edspaceðlog log nÞ: We show that if this can be improved to f0 n : n is primege DSPACEðlog log nÞ; it follows that LaNP: