Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T12:46:00.006Z Has data issue: false hasContentIssue false

Division in logspace-uniform NC 1

Published online by Cambridge University Press:  15 April 2002

Andrew Chiu
Affiliation:
EECS Department, University of Wisconsin-Milwaukee, Milwaukee, WI, U.S.A.
George Davida
Affiliation:
EECS Department, University of Wisconsin-Milwaukee, Milwaukee, WI, U.S.A.; e-mail: davida@cs.uwm.edu
Bruce Litow
Affiliation:
School of Information Technology, James Cook University, Townsville, Qld. 4811, Australia; e-mail: bruce@cs.jcu.edu.au
Get access

Abstract

Beame, Cook and Hoover were the first to exhibita log-depth, polynomial size circuit family for integerdivision. However, the family was not logspace-uniform.In this paper we describe log-depth, polynomialsize, logspace-uniform, i.e., NC 1 circuit family forinteger division. In particular, by a well-known result this showsthat division is in logspace. We also refine the methodof the paper to show that division is in dlogtime-uniformNC 1.

Information

Type
Research Article
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable