ECCC-Report TR11-095https://eccc.weizmann.ac.il/report/2011/095Comments and Revisions published for TR11-095en-usSat, 12 May 2012 01:42:52 +0300
Revision 1
| The lower reaches of circuit uniformity |
Christoph Behle,
Andreas Krebs,
Klaus-Joern Lange,
Pierre McKenzie
https://eccc.weizmann.ac.il/report/2011/095#revision1The 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. Sat, 12 May 2012 01:42:52 +0300https://eccc.weizmann.ac.il/report/2011/095#revision1
Paper TR11-095
| Low uniform versions of NC1 |
Christoph Behle,
Andreas Krebs,
Klaus-Joern Lange,
Pierre McKenzie
https://eccc.weizmann.ac.il/report/2011/095In 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.
Thu, 23 Jun 2011 06:21:13 +0300https://eccc.weizmann.ac.il/report/2011/095