An algebra and a logic for NC1

Abstract

Presented here are an algebra and a logic characterizing the complexity class NC1, which consists of functions computed by uniform families of polynomial size, log depth circuits. In both characterizations, NC1 functions are regarded as functions from one class of finite relational structures to another. In the algebraic characterization a recursion scheme called upward tree recursion is applied to a class of simple functions. In the logical characterization, first-order logic is augmented by an operator for defining relations by primitive recursion where it is assumed that every structure has an underlying relation BIT giving the binary representations of integers.