Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-095 | 12th May 2012 01:42

The lower reaches of circuit uniformity

Revision #1
Authors: Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie
Accepted on: 12th May 2012 01:42
Keywords:

Abstract:

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.

Changes to previous version:

Results are stated in more clear way, and overall readability was improved.

Paper:

TR11-095 | 22nd June 2011 22:55

Low uniform versions of NC1

TR11-095
Authors: Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie
Publication: 23rd June 2011 06:21
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint