ON ADAPTIVE DLOGTIME AND POLYLOGTIME REDUCTIONS

Authors
ALVAREZ C JENNER B
Citation
C. Alvarez et B. Jenner, ON ADAPTIVE DLOGTIME AND POLYLOGTIME REDUCTIONS, Theoretical computer science, 148(2), 1995, pp. 183-205
Citations number
26
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
148
Issue
2
Year of publication
1995
Pages
183 - 205
Database
ISI
SICI code
0304-3975(1995)148:2<183:OADAPR>2.0.ZU;2-6
Abstract
We investigate properties of the relativized AC and NC hierarchies in their DLOGTIME-, respectively, ALOGTIME-uniform setting and show that these hierarchies can be characterized in terms of adaptive reducibili ty in deterministic (poly)logarithmic time, i.e. in time O(log n)(i) f or i greater than or equal to 0. Using this characterization, we subst antially generalize various previous results concerning the structure of the two hierarchies.