Paper Info
Title
On Adaptive Dlogtime and Polylogtime Reductions (Extended Abstract)
Abstract
We investigate properties of the relativized NC and AC hierarchies in their DLOGTIME-, respectively, ALOGTIME-uniform setting and show that these hierarchies can be characterized in terms of adaptive reducibility in deterministic (poly)logarithmic time, i.e. in time O(log n)i for i0. Using this characterization, we substantially generalize various previous results concerning the structure of the NC and AC hierarchies.
Year
DOI
Venue
1994
10.1007/3-540-57785-8_150
STACS
Keywords
Field
DocType
extended abstract,polylogtime reductions,adaptive dlogtime
Discrete mathematics,Computer science,DLOGTIME
Conference
ISBN
Citations 
PageRank 
3-540-57785-8
1
0.47
References 
Authors
1
2
Name
Order
Citations
PageRank
Carme Àlvarez131628.75
Birgit Jenner224714.47