×

Division in logspace-uniform NC. (English) Zbl 1014.68062

Summary: 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. We describe log-depth, polynomial size, logspace-uniform, i.e., \(\text{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 \(\text{NC}^1\).

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[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 · Zbl 0956.68060 · doi:10.1006/jcss.1999.1675
[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 · Zbl 0719.68023 · doi:10.1016/0022-0000(90)90022-D
[3] 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 · Zbl 0619.68047 · doi:10.1137/0215070
[4] 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 · Zbl 0695.68053 · doi:10.1016/0020-0190(90)90089-G
[5] A. Borodin , On relating time and space to size and depth . SIAM J. Comput. 6 ( 1977 ) 733 - 744 . MR 461984 | Zbl 0366.68039 · Zbl 0366.68039 · doi:10.1137/0206054
[6] S. Cook , A taxonomy of problems with fast parallel algorithms . Inform. and Control 64 ( 1985 ) 2 - 22 . MR 837088 | Zbl 0575.68045 · Zbl 0575.68045 · doi:10.1016/S0019-9958(85)80041-3
[7] G. Davida and B. Litow , Fast parallel arithmetic via modular representation . SIAM J. Comput. 20 ( 1991 ) 756 - 765 . MR 1105936 | Zbl 0736.68040 · Zbl 0736.68040 · doi:10.1137/0220048
[8] W. Hesse , Division is in uniform \(\mbox {TC}^0\) . Comp. Sci., U. Mass. Amherst ( 2000 ). MR 2065855
[9] M.A. Hitz and E. Kaltofen , Integer division in residue number systems . IEEE Trans. Comput. 44 ( 1995 ) 983 - 989 . MR 1349940 | Zbl 1053.68501 · Zbl 1053.68501 · doi:10.1109/12.403714
[10] N. Immerman , Descriptive Complexity . Springer-Verlag ( 1999 ). MR 1732784 | Zbl 0918.68031 · Zbl 0918.68031
[11] D. Knuth , The Art of Computer Programming , Vol. 2. Addison-Wesley ( 1969 ). MR 633878 | Zbl 0191.18001 · Zbl 0191.18001
[12] 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 · Zbl 0699.68069 · doi:10.1016/0304-3975(90)90192-K
[13] B. Litow , Computing context-free grammar generating series . Inform. and Comput. (in press). Zbl 1007.68085 · Zbl 1007.68085 · doi:10.1006/inco.2000.3023
[14] I. Macarie , Space-efficient deterministic simulation of probabilistic automata . SIAM J. Comput. 27 ( 1998 ) 448 - 465 . MR 1616560 | Zbl 0907.68081 · Zbl 0907.68081 · doi:10.1137/S0097539793253851
[15] J. Reif , Logarithmic depth circuits for algebraic functions . SIAM J. Comput. 15 ( 1986 ) 231 - 242 . MR 822202 | Zbl 0611.68014 · Zbl 0611.68014 · doi:10.1137/0215017
[16] W. Ruzzo , On uniform circuit complexity . J. Comput. System Sci. 22 ( 1981 ) 365 - 383 . MR 633540 | Zbl 0462.68013 · Zbl 0462.68013 · doi:10.1016/0022-0000(81)90038-6
[17] R. Tanaka and N. Szabo , Residue Arithmetic and its Application to Computer Technology . McGraw-Hill ( 1968 ). Zbl 0168.15303 · Zbl 0168.15303
[18] H. Vollmer , Introduction to Circuit Complexity . Springer-Verlag ( 1999 ). MR 1704235 | Zbl 0931.68055 · Zbl 0931.68055
[19] I. Wegener , The Complexity of Boolean Functions . Wiley-Teubner ( 1987 ). MR 905473 | Zbl 0623.94018 · Zbl 0623.94018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.