On adaptive DLOGTIME and POLYLOGTIME reductions

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 reducibility in deterministic (poly)logarithmic time, i. e. in time O(log n) i for i ⩾ 0. Using this characterization, we substantially generalize various previous results concerning the structure of the two hierarchies.

Authors

• Carme Àlvarez
• Birgit Jenner

Keywords

No keywords are indexed for this paper.