On uniformity within \(NC^ 1\) (Q2640342)

The class \(NC^ 1\) of languages recognized by log-depth polynomial-size circuits is considered. The main goal is to study circuit complexity classes within \(NC^ 1\) in a uniform setting. It is shown that families of circuits defined by first-order formulas and a uniformity corresponding to deterministic log-time reductions are equivalent. This leads to a natural notion of uniformity for low-level circuit complexity classes. In this connection the expressive power of the first-order logic with and without the BIT pedicate is explored. New quantifiers (modular, counting, majority and group quantifiers) are also introduced to express languages in larger complexity classes. Recent results on the characterization of \(NC^ 1\) in terms of constant-width branching programs are shown to still hold true in uniform setting.