We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as ...
详细信息
We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U-E*-uniform variant of NC1 Ruzzo, J. Comput. System Sci. 22 (1981) 365-383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论