Extensional Uniformity for Boolean Circuits
- verfasst von
- Pierre McKenzie, Michael Thomas, Heribert Vollmer
- Abstract
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.
- Organisationseinheit(en)
-
Institut für Mikrobiologie
Institut für Theoretische Informatik
- Typ
- Artikel
- Journal
- SIAM J. Comput.
- Band
- 39
- Seiten
- 3186-3206
- Anzahl der Seiten
- 21
- Publikationsdatum
- 2010
- Publikationsstatus
- Veröffentlicht
- Peer-reviewed
- Ja
- Elektronische Version(en)
-
https://doi.org/10.48550/arXiv.0805.4072 (Zugang:
Offen)
https://doi.org/10.1137/080741811 (Zugang: Unbekannt)