Details
| Original language | English |
|---|---|
| Article number | 7 |
| Pages (from-to) | 3186-3206 |
| Number of pages | 21 |
| Journal | SIAM J. Comput. |
| Volume | 39 |
| Issue number | 7 |
| Publication status | Published - 2010 |
Abstract
Keywords
- cs.LO, cs.CC
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: SIAM J. Comput., Vol. 39, No. 7, 7, 2010, p. 3186-3206.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Extensional Uniformity for Boolean Circuits
AU - McKenzie, Pierre
AU - Thomas, Michael
AU - Vollmer, Heribert
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2010
Y1 - 2010
N2 - Imposing an extensional uniformity condition on a non-uniform circuit complexity class C means simply intersecting C with a uniform class L. By contrast, the usual intensional uniformity conditions require that a resource-bounded machine be able to exhibit the circuits in the circuit family defining C. We say that (C,L) has the "Uniformity Duality Property" if the extensionally uniform class C \cap L can be captured intensionally by means of adding so-called "L-numerical predicates" to the first-order descriptive complexity apparatus describing the connection language of the circuit family defining C. This paper exhibits positive instances and negative instances of the Uniformity Duality Property.
AB - Imposing an extensional uniformity condition on a non-uniform circuit complexity class C means simply intersecting C with a uniform class L. By contrast, the usual intensional uniformity conditions require that a resource-bounded machine be able to exhibit the circuits in the circuit family defining C. We say that (C,L) has the "Uniformity Duality Property" if the extensionally uniform class C \cap L can be captured intensionally by means of adding so-called "L-numerical predicates" to the first-order descriptive complexity apparatus describing the connection language of the circuit family defining C. This paper exhibits positive instances and negative instances of the Uniformity Duality Property.
KW - cs.LO
KW - cs.CC
U2 - 10.48550/arXiv.0805.4072
DO - 10.48550/arXiv.0805.4072
M3 - Article
VL - 39
SP - 3186
EP - 3206
JO - SIAM J. Comput.
JF - SIAM J. Comput.
SN - 1095-7111
IS - 7
M1 - 7
ER -