Issue Theoret. Informatics Appl. Volume 35, Number 3, May-June 2001 Page(s) 259 - 275 DOI 10.1051/ita:2001119

DOI: 10.1051/ita:2001119


Theoret. Informatics Appl. 35, 259-275 (2001)

Division in logspace-uniform NC¹

Andrew Chiu¹, George Davida¹ and Bruce Litow<sup>2

1</sup>  EECS Department, University of Wisconsin-Milwaukee, Milwaukee, WI, U.S.A.; (davida@cs.uwm.edu)
²  School of Information Technology, James Cook University, Townsville, Qld. 4811, Australia; (bruce@cs.jcu.edu.au)

(Received June 25, 2000. Accepted August 3, 2001.)

Abstract
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., NC¹ 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 NC¹.

AMS Subject: 68Q05, 68Q10, 68Q15, 68Q17.

Key words: Parallel complexity -- NC -- integer division -- uniformity.


© EDP Sciences 2001

What is OpenURL?