Division in logspace-uniform NC1
Andrew Chiu1, George Davida2 and Bruce Litow3
EECS Department, University of Wisconsin-Milwaukee,
Milwaukee, WI, U.S.A.
2 EECS Department, University of Wisconsin-Milwaukee, Milwaukee, WI, U.S.A.; e-mail: firstname.lastname@example.org
3 School of Information Technology, James Cook University, Townsville, Qld. 4811, Australia; e-mail: email@example.com
Accepted: 3 August 2001
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., NC1 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 NC1.
Mathematics Subject Classification: 68Q05 / 68Q10 / 68Q15 / 68Q17
Key words: Parallel complexity / NC / integer division / uniformity.
© EDP Sciences, 2001