Name
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 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. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0304-3975(95)00033-S | Theor. Comput. Sci. |
Keywords | DocType | Volume |
adaptive dlogtime,polylogtime reduction | Journal | 148 |
Issue | ISSN | Citations |
2 | Theoretical Computer Science | 1 |
PageRank | References | Authors |
0.40 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carme Àlvarez | 1 | 316 | 28.75 |
| Birgit Jenner | 2 | 247 | 14.47 |