| |
Table des matières de ce fascicule | Article précédent | Article suivant
Chiu, Andrew; Davida, George; Litow, Bruce
Division in logspace-uniform $\mbox {NC}^1$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 35 no. 3 (2001), p. 259-275
Texte intégral djvu | pdf | Analyses MR 1869217 | Zbl 1014.68062 | 1 citation dans Numdam
Class. Math.: 68Q05, 68Q10, 68Q15, 68Q17
Mots clés: parallel complexity, NC, integer division, uniformity
URL stable: http://www.numdam.org/item?id=ITA_2001__35_3_259_0
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., $\mbox {NC}^1$ 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 $\mbox {NC}^1$.
[1] E. Allender, M. Agrawal and S. Datta, On $\mbox {TC}^0$, $\mbox {AC}^0$, and arithmetic circuits. J. Comput. System Sci. 60 (2000) 395-421. MR 1784585 | Zbl 0956.68060
[2] E. Allender and D.A. Mix Barrington, Uniform circuits for division: Consequences and problems (2000) allender@cs.rutgers.edu, barring@cs.umass.edu
[3] D. Mix Barrington, N. Immerman and H. Straubing, On uniformity within $\mbox {NC}^1$. J. Comput. System Sci. 41 (1990) 274-306. MR 1079468 | Zbl 0719.68023
[4] P. Beame, S. Cook and H. Hoover, Log depth circuits for division and related problems. SIAM J. Comput. 15 (1986) 994-1003. MR 861365 | Zbl 0619.68047
[5] A. Bertoni, M. Goldwurm and P. Massazza, Counting problems and algebraic formal power series in noncommuting variables. Inform. Process. Lett. 34 (1990) 117-121. MR 1059975 | Zbl 0695.68053
[6] A. Borodin, On relating time and space to size and depth. SIAM J. Comput. 6 (1977) 733-744. MR 461984 | Zbl 0366.68039
[7] S. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control 64 (1985) 2-22. MR 837088 | Zbl 0575.68045
[8] G. Davida and B. Litow, Fast parallel arithmetic via modular representation. SIAM J. Comput. 20 (1991) 756-765. MR 1105936 | Zbl 0736.68040
[9] W. Hesse, Division is in uniform $\mbox {TC}^0$. Comp. Sci., U. Mass. Amherst (2000). MR 2065855
[10] M.A. Hitz and E. Kaltofen, Integer division in residue number systems. IEEE Trans. Comput. 44 (1995) 983-989. MR 1349940 | Zbl 1053.68501
[11] N. Immerman, Descriptive Complexity. Springer-Verlag (1999). MR 1732784 | Zbl 0918.68031
[12] D. Knuth, The Art of Computer Programming, Vol. 2. Addison-Wesley (1969). MR 633878 | Zbl 0191.18001
[13] C. Kruskal, L. Rudolph and M. Snir, A complexity theory of efficient parallel algorithms. Theoret. Comput. Sci. 71 (1990) 95-132. MR 1050080 | Zbl 0699.68069
[14] B. Litow, Computing context-free grammar generating series. Inform. and Comput. (in press). Zbl 1007.68085
[15] I. Macarie, Space-efficient deterministic simulation of probabilistic automata. SIAM J. Comput. 27 (1998) 448-465. MR 1616560 | Zbl 0907.68081
[16] J. Reif, Logarithmic depth circuits for algebraic functions. SIAM J. Comput. 15 (1986) 231-242. MR 822202 | Zbl 0611.68014
[17] W. Ruzzo, On uniform circuit complexity. J. Comput. System Sci. 22 (1981) 365-383. MR 633540 | Zbl 0462.68013
[18] R. Tanaka and N. Szabo, Residue Arithmetic and its Application to Computer Technology. McGraw-Hill (1968). Zbl 0168.15303
[19] H. Vollmer, Introduction to Circuit Complexity. Springer-Verlag (1999). MR 1704235 | Zbl 0931.68055
[20] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). MR 905473 | Zbl 0623.94018
|
|
Copyright Cellule MathDoc 2013 | Crédit | Plan du site
|
