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)