A characterization of NC by tree recurrence
Daniel M. Leivant · 2002
We show that a boolean valued function is in NC if it is defined by ramified schematic recurrence over trees. This machine-independent characterization uses no initial functions other than basic tree operations, and no bounding conditions on the recurrence. Aside from its technical interest, our result evidences the foundational nature of NC, thereby illustrating the merits of implicit (i.e. machine independent) computational complexity theory.