Voir la notice de l'article provenant de la source Numdam
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., 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 .
@article{ITA_2001__35_3_259_0,
author = {Chiu, Andrew and Davida, George and Litow, Bruce},
title = {Division in logspace-uniform $\mbox{NC}^1$},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {259--275},
publisher = {EDP-Sciences},
volume = {35},
number = {3},
year = {2001},
mrnumber = {1869217},
zbl = {1014.68062},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ITA_2001__35_3_259_0/}
}
TY - JOUR
AU - Chiu, Andrew
AU - Davida, George
AU - Litow, Bruce
TI - Division in logspace-uniform $\mbox{NC}^1$
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2001
SP - 259
EP - 275
VL - 35
IS - 3
PB - EDP-Sciences
UR - http://geodesic.mathdoc.fr/item/ITA_2001__35_3_259_0/
LA - en
ID - ITA_2001__35_3_259_0
ER -
%0 Journal Article
%A Chiu, Andrew
%A Davida, George
%A Litow, Bruce
%T Division in logspace-uniform $\mbox{NC}^1$
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 259-275
%V 35
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_2001__35_3_259_0/
%G en
%F ITA_2001__35_3_259_0
Chiu, Andrew; Davida, George; Litow, Bruce. Division in logspace-uniform $\mbox{NC}^1$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 3, pp. 259-275. http://geodesic.mathdoc.fr/item/ITA_2001__35_3_259_0/