The effect of severely tightening the uniformity of Boolean circuit families is investigated. The impact on NC1 and its subclasses is shown to depend on the characterization chosen for the class, while classes such as P appear to be more robust. Tightly uniform subclasses of NC1 whose separation may be within reach of current techniques emerge.
Results are stated in more clear way, and overall readability was improved.
In the setting known as DLOGTIME-uniformity,
the fundamental complexity classes
AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1 have several
robust characterizations.
In this paper we refine uniformity further and examine the impact
of these refinements on NC^1 and its subclasses.
When applied to the logarithmic circuit depth characterization of NC^1,
some refinements leave NC^1 unchanged
while others collapse NC^1 to NC^0.
Thus we study refinements of other circuit characterizations of NC^1.
In the case of the AC0(A_5) characterization of NC^1,
where A_5 is the NC^1-complete word problem of the group A_5,
our refinements collapse NC^1 to a subset of the regular languages.
For the AC^0(D^+) characterizations of NC^1,
where D^+ is the NC^1-complete language capturing the formula
value problem, interestingly, these
refinements scale down to circuits with linear fan-in.
In particular, the latter refinements bring to the fore two classes, denoted
FO[<]-uniform AC^0(D^+)_{LIN} and
FO[<]-uniform TC^0_{LIN}, whose separation may be within the
reach of current lower bound techniques, and whose separation would amount
to distinguishing the power of a MAJ gate from that of a D^+ gate.