Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform .
Mots clés : parallel complexity, NC, integer division, uniformity
@article{ITA_2001__35_3_259_0, author = {Chiu, Andrew and Davida, George and Litow, Bruce}, title = {Division in logspace-uniform $\mbox{NC}^1$}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {259--275}, publisher = {EDP-Sciences}, volume = {35}, number = {3}, year = {2001}, mrnumber = {1869217}, zbl = {1014.68062}, language = {en}, url = {http://www.numdam.org/item/ITA_2001__35_3_259_0/} }
TY - JOUR AU - Chiu, Andrew AU - Davida, George AU - Litow, Bruce TI - Division in logspace-uniform $\mbox{NC}^1$ JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2001 SP - 259 EP - 275 VL - 35 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_2001__35_3_259_0/ LA - en ID - ITA_2001__35_3_259_0 ER -
%0 Journal Article %A Chiu, Andrew %A Davida, George %A Litow, Bruce %T Division in logspace-uniform $\mbox{NC}^1$ %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2001 %P 259-275 %V 35 %N 3 %I EDP-Sciences %U http://www.numdam.org/item/ITA_2001__35_3_259_0/ %G en %F ITA_2001__35_3_259_0
Chiu, Andrew; Davida, George; Litow, Bruce. Division in logspace-uniform $\mbox{NC}^1$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 3, pp. 259-275. http://www.numdam.org/item/ITA_2001__35_3_259_0/
[1] On , , and arithmetic circuits. J. Comput. System Sci. 60 (2000) 395-421. | MR | Zbl
, and ,[2] Uniform circuits for division: Consequences and problems (2000) allender@cs.rutgers.edu, barring@cs.umass.edu
and ,[3] On uniformity within . J. Comput. System Sci. 41 (1990) 274-306. | MR | Zbl
, and ,[4] Log depth circuits for division and related problems. SIAM J. Comput. 15 (1986) 994-1003. | MR | Zbl
, and ,[5] Counting problems and algebraic formal power series in noncommuting variables. Inform. Process. Lett. 34 (1990) 117-121. | MR | Zbl
, and ,[6] On relating time and space to size and depth. SIAM J. Comput. 6 (1977) 733-744. | MR | Zbl
,[7] A taxonomy of problems with fast parallel algorithms. Inform. and Control 64 (1985) 2-22. | MR | Zbl
,[8] Fast parallel arithmetic via modular representation. SIAM J. Comput. 20 (1991) 756-765. | MR | Zbl
and ,[9] Division is in uniform . Comp. Sci., U. Mass. Amherst (2000). | MR
,[10] Integer division in residue number systems. IEEE Trans. Comput. 44 (1995) 983-989. | MR | Zbl
and ,[11] Descriptive Complexity. Springer-Verlag (1999). | MR | Zbl
,[12] The Art of Computer Programming, Vol. 2. Addison-Wesley (1969). | MR | Zbl
,[13] A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci. 71 (1990) 95-132. | MR | Zbl
, and ,[14] Computing context-free grammar generating series. Inform. and Comput. (in press). | Zbl
,[15] Space-efficient deterministic simulation of probabilistic automata. SIAM J. Comput. 27 (1998) 448-465. | MR | Zbl
,[16] Logarithmic depth circuits for algebraic functions. SIAM J. Comput. 15 (1986) 231-242. | MR | Zbl
,[17] On uniform circuit complexity. J. Comput. System Sci. 22 (1981) 365-383. | MR | Zbl
,[18] Residue Arithmetic and its Application to Computer Technology. McGraw-Hill (1968). | Zbl
and ,[19] Introduction to Circuit Complexity. Springer-Verlag (1999). | MR | Zbl
,[20] The Complexity of Boolean Functions. Wiley-Teubner (1987). | MR | Zbl
,