Division in logspace-uniform NC¹
Chiu, Andrew, Davida, George, and Litow, Bruce (2001) Division in logspace-uniform NC¹. RAIRO - Theoretical Informatics and Applications, 35 (3). pp. 259-275.
PDF (Published Version)
- Published Version
Restricted to Repository staff only
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¹.
|Item Type:||Article (Refereed Research - C1)|
|Keywords:||parallel complexity, NC, integer division, uniformity|
Copyright EDP Sciences 2001 Reproduced with permission from EDP Sciences. RAIRO - Theoretical Informatics and Applications: http://www.rairo-ita.org
|Date Deposited:||03 Nov 2006|
|FoR Codes:||08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080201 Analysis of Algorithms and Complexity @ 0%|